c语言静态三叉链表构造一棵Huffman树并求其编码

1、课程设计题目： 采用静态三叉链表构造一棵Huffman树并求其编码一 课程设计应达到的目的：数据结构课程设计的目的是，为了让学生在学习 数据结构 课程的基础上深入理解数据结构的基本理论，掌握对数据结构的各种操作的算法设计方法，增强对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力，进一步深入巩固所学理论知识、使理论与实际相结合的重要实践环节。本课程设计通过完成一些具有一定难度的程序的编写、调试、运行工作，掌握面向过程程序设计的基本方法，从而提高学生分析问题解决问题的能力。 课程设计是教学中很重要的一项实践环节，它可以帮助学

2、生充分理解课堂教学中的内容，对提高学生的实践认识和实际动手能力都有很重要的实际意义。学生应在规定的时间内，按照课程设计的要求，结合所学的理论知识，查找相关资料，完成好本次课程设计，提高程序编写的能力，为将来的实际工作取得一定的经验。二 课程设计题目及要求采用静态三叉链表构造一棵Huffman树并求其编码 增加了权值的计算和Huffman树的输出 并写入code文件三 主函数及分析it学习网收集 主程序代码Main.cpp#include#include#includereadFile.h#includeHuffmanTree.hint main()c

3、har str1000;cinstr;HuffmanTree htree(str);htree.print();htree.writetoFile(); readFile(htree.getstr1(),htree.gethufcodes(),htree.getleafNum();return 0;HuffmanTree.h#include#include#includetemplatestruct TriNodeT data;int parent,left,right; class HuffmanTreeprivate:char str1000; /输入的字符串char str11000;

4、/哈弗曼叶子值int leafNum; /子叶结点个数TriNode *huftree; / 哈弗曼的结点数组char *hufcodes; /哈弗曼编码数组void createHuffmanTree(int weight,int n); /创建指定权值集合的哈弗曼树void getHuffmanCode(); /获得哈弗曼编码public:HuffmanTree(char str5); HuffmanTree();void writetoFile(); /写入文件char* gethufcodes();char* getstr1();int getleafNum();void print(

5、);void print(int u);int getheight(int r);/得出r节点的深度;const Max_Weight=9999; / 默认最大权值/*/HuffmanTree:HuffmanTree(char str5) strcpy(str,str5);int count=0,i,j,k=0;for(i=0;istrlen(str);i+)/循环做出str1，将每个str里面的字符在str1里面扫描一遍，str中在str1没出现的字符放到str1中for(j=0;jcount+1;j+)if(stri!=str1j) k+;/如果str中的字符在str1中扫描不等k+，k初

6、值为0if(k=count+1)/如果k等于字符串str1的长度的话 说明stri在str1中没出现，加到str1中str1count+=stri; k=0;str1count=0;/将哈弗曼叶子字符数组最后一位置字符串结束符/*/int weight100;for(i=0;icount;i+)/初始化权值为0weighti=0;for(i=0;istrlen(str);i+)/从第一个开始扫描str 让str的每一个字符和str1比较 在str1中相等的地方让weight的值+for(j=0;jcount;j+)if(stri=str1j)weightj+;/weight中的每一位对应着st

7、r1中的每一位break;for(i=0;icount;i+)coutstr1i ;coutendl;for(i=0;icount;i+)coutweighti ;coutendl;/*/createHuffmanTree(weight,count);getHuffmanCode();/*/void HuffmanTree:createHuffmanTree(int weight,int n) /创建指定权值集合的哈弗曼树leafNum=n;huftree=new TriNode2*n-1; int i;for(i=0;in;i+)huftreei.data=weighti;huftreei.

8、parent=huftreei.left=huftreei.right=-1;for(i=0;in-1;i+)int min1,min2,x1,x2;min1=min2=Max_Weight;x1=x2=-1;for(int j=0;jn+i;j+)if(huftreej.datamin1&huftreej.parent=-1)min2=min1;x2=x1;min1=huftreej.data;x1=j;else if(huftreej.datamin2&huftreej.parent=-1)min2=huftreej.data;x2=j;huftreex1.parent=n+i;huftr

9、eex2.parent=n+i;huftreen+i.data=huftreex1.data+huftreex2.data;huftreen+i.parent=-1;huftreen+i.left=x1;huftreen+i.right=x2;void HuffmanTree:getHuffmanCode()int n=leafNum;hufcodes=new char*n;for(int i=0;in;i+)char *code=new charn;coden-1=0;int start=n-1;int child=i;int parent=huftreechild.parent;while

10、(parent!=-1)start-;if(huftreeparent.left=child)codestart=0;elsecodestart=1;child=parent;parent=huftreechild.parent;hufcodesi=code+start;/*/int HuffmanTree:getheight(int r)int t=0;while(r!=-1)r=huftreer.parent;t+;return t;/*/void HuffmanTree:print()cout哈夫曼树节点数组: n;print(2*leafNum-2);/*HuffmanTree*/vo

11、id HuffmanTree:print(int u)/递归打印哈弗曼tree，采用先序遍历if(u!=-1)/判断是否有孩子for(int e=1;egetheight(u);e+)/循环小于高度，目的是为了确定该节点前有多少个空格if(e=getheight(u)-1)/在循环的最后一位输出下面字符 cout|_;else cout ;/循环输出空格couthuftreeu.data;/输出节点权值coutendl; print(huftreeu.left);/找它左子 print(huftreeu.right);/找他右孩子 /*/HuffmanTree:HuffmanTree()del

12、ete huftree;delete hufcodes;/*/void HuffmanTree:writetoFile()FILE *fp;int i,j;fp=fopen(code.txt,w);/以读的方式创建文件for(i=0;istrlen(str);i+)/扫描字符串str每一位与str1中的每一为比较若相等写入该位置的哈弗曼的编码for(j=0;jleafNum;j+)if(stri=str1j) /主要目的是得出j值 str1和weight和hafcodes的每一位都一一对应fputs(hufcodesj,fp);/写入文件couthufcodesj;/输出到屏幕coutendl

13、;fclose(fp);cout写入成功endl;/*/char* HuffmanTree:getstr1()/str1访问器return str1;char* HuffmanTree:gethufcodes()/hufcodes访问器return hufcodes;int HuffmanTree:getleafNum()/leafNum访问器return leafNum;ReadFile.h#include#include#includevoid readFile(char *str1,char *hufcodes,int leafNum)/带入参数 哈弗曼节点字符串 哈弗曼编码字符串数组，

14、哈弗曼节点数char str21000,str3100;/这个方法的思想是，从文件读入哈弗曼编码过的文档读入到str2中int k=0,i=0,j,l,o=0,p=0;/然后从第一个字符开始取字符str2中的hufcodesi的长度和hufcodesi比较 是否相等FILE *fp;/ 若相等i=i+hufcodesi的长度 继续读下面的 知道str2读完fp=fopen(code.txt,r);while(!feof(fp)str2k+=fgetc(fp);fclose(fp);while(ik-1)for(j=0;jleafNum;j+)o=0;p=0;for(l=i;li+strlen(

15、hufcodesj);l+)/复制str2中哈弗曼编码str3p+=str2l;for(l=0;lstrlen(hufcodesj);l+)if(str3l!=hufcodesjl) o+;if(o=0) coutstr1j;i=i+strlen(hufcodesj);break;coutendl;程序执行结果： Huffman树写入到文件里的huffman编码5231456111000四 主要参考文献数据结构（C+版） 叶核亚 编著 电子工业出版社五 程序中出现的问题及解决方案 程序原本采用三叉链表储存结构，但是由于实现方面有问题，所以现在采用静态三叉链表，静态三叉链表采用一个结构数组存储二

16、叉树的所有结点，一个数组元素储存一个结点，每个结点存储其父母，孩子结点的下标，通过下标表示结点间的关系。六 程序改进措施下面的代码为采用顺寻查找方式计算字符的权值 在数据量比较小，单纯为数字且字符个数较小的情况下可以采用，但是如果数据量较大，则此方法效率很低，此种情况下可以采用基于索引顺序表的分块查找，建立一个索引表index，每个索引项储存一块索引信息，由首字母和块起始序号两部分组成，分别对应关键字的首字母和该块在主表中的起始下标。const Max_Weight=9999; / 默认最大权值/*/HuffmanTree:HuffmanTree(char str5) strcpy(str,s

17、tr5);int count=0,i,j,k=0;for(i=0;istrlen(str);i+)/循环做出str1，将每个str里面的字符在str1里面扫描一遍，str中在str1没出现的字符放到str1中for(j=0;jcount+1;j+)if(stri!=str1j) k+;/如果str中的字符在str1中扫描不等k+，k初值为0if(k=count+1)/如果k等于字符串str1的长度的话 说明stri在str1中没出现，加到str1中str1count+=stri; k=0;str1count=0;/将哈弗曼叶子字符数组最后一位置字符串结束符/*/int weight100;fo

18、r(i=0;icount;i+)/初始化权值为0weighti=0;for(i=0;istrlen(str);i+)/从第一个开始扫描str 让str的每一个字符和str1比较 在str1中相等的地方让weight的值+for(j=0;jcount;j+)if(stri=str1j)weightj+;/weight中的每一位对应着str1中的每一位break;for(i=0;icount;i+)coutstr1i ;coutendl;for(i=0;icount;i+)coutweighti ;coutendl; 在数据量极其大，比如是某个文档，其中有各种形态的文字，中文或者字母等等，此时顺序

19、查找和采用索引表的分块查找也会产生效率底下的问题，这时的解决方法使采用散列表。散列是一种按照关键字编址的存储和检索的方法。散列函数实质上市关键字集合到地址集合的映射，如果这种映射是一一对应的，则查找的效率就是O（1）。在实际应用中，因为散列表的存储容量是有限的，散列函数是一个压缩映射，从关键字集合到地址集合是多对一的映射，所以不可避免会产生冲突。因此使用散列表无可避免的就是会产生冲突，虽然好的散列表函数能使散列地址分布均匀，但是只能减少冲突，而不能从根本上避免冲突。因此需要有效地处理冲突。方法有开放定址法，链地址法等等。本程序有计算权值，输出树状图，计算huffman编码并且写入到文件，最后还

20、添加了读取文件 主程序为ReadFile.h #include#include#includevoid readFile(char *str1,char *hufcodes,int leafNum)/带入参数 哈弗曼节点字符串 哈弗曼编码字符串数组，哈弗曼节点数char str21000,str3100;/这个方法的思想是，从文件读入哈弗曼编码过的文档读入到str2中int k=0,i=0,j,l,o=0,p=0;/然后从第一个字符开始取字符str2中的hufcodesi的长度和hufcodesi比较 是否相等FILE *fp;/ 若相等i=i+hufcodesi的长度 继续读下面的 知道st

21、r2读完fp=fopen(code.txt,r);while(!feof(fp)str2k+=fgetc(fp);fclose(fp);while(ik-1)for(j=0;jleafNum;j+)o=0;p=0;for(l=i;li+strlen(hufcodesj);l+)/复制str2中哈弗曼编码str3p+=str2l;for(l=0;lstrlen(hufcodesj);l+)if(str3l!=hufcodesjl) o+;if(o=0) coutstr1j;i=i+strlen(hufcodesj);break;coutendl;这个方法的思想是，从文件读入哈弗曼编码过的文档读入到str2中 这样此程序又能实现一个功能，增加了程序的实用性。七 课程设计总结、通过此次课程设计，我更加扎实的掌握了有关数据结构方面的知识，在课设过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在