哈夫曼树应用Word下载.docx

1、; Huffi.weight=0; Huffi.parent=-1; Huffi.lchild=-1; Huffi.rchild=-1; printf（输入%d个字符及它的权值: n,n）;/读入数据 getchar（）;n;i+）请输入第%d个字符:,i+1）; scanf（%c,&d）; Huffi.ch=d;请输入第%d个字符的权值:%dw）; Huffi.weight=w;n-1;/构造哈夫曼树并生成该树的n-1个分支结点 m1=m2=32767; x1=x2=0; for（j=0;jn+i;j+） /选取最小和次小两个权值结点并将其序号送x1和x2 if（Huffj.parent=-

2、1&Huffj.weightm1） m2=m1; x2=x1; m1=Huffj.weight; x1=j; elsem2） m2=Huffj.weight; x2=j; /将找出的两棵子树合并为一棵新的子树 Huffx1.parent=n+i; Huffx2.parent=n+i; Huffn+i.weight=Huffx1.weight+Huffx2.weight; Huffn+i.lchild=x1; Huffn+i.rchild=x2;2.对哈夫曼树进行编码void HuffmanCode（HNode Huff,int n） /生成哈夫曼编码 FILE *fw; HCode HuffC

3、odeMAXSIZE/2,cd;/ MAXSIZE/2为叶结点的最大个数 int i,j,c,p;/求每个叶结点的哈夫曼编码 HuffCodei.weight=Huffi.weight; cd.start=MAXBIT-1; c=i; p=Huffc.parent; while（p!=-1） if（Huffp.lchild=c） cd.bitcd.start=0; cd.bitcd.start=1; cd.start-; c=p; for（j=cd.start+1;MAXBIT;/保存该叶结点字符的哈夫曼编码 HuffCodei.bitj=cd.bitj; HuffCodei.start=cd

4、.start; /保存该编码在数组bit中的起始位置3.根据哈夫曼编码进行译码void decode（HNode Huff,int n）/依次读入电文，根据哈夫曼树译码 FILE *fs; int i,j=0; char bMAXSIZE;i=2*n-2;/从根结点开始往下搜索【输入电文，并进行译码】n）;输入发送的编码（以2为结束标志）：n gets（b）;译码后的字符为: while（bj!=） if（bj=0 i=Huffi.lchild; /走向左孩子 i=Huffi.rchild; /走向右孩子 if（Huffi.lchild=-1） /treei是叶结点,Huffi.ch）; i=

5、2*n-2; /回到根结点 j+;if（Huffi.lchild!=-1&bj!） /电文读完，但尚未到叶子结点nERRORn /输入电文4.菜单调用void menu（）菜单如下n1-建立哈夫曼树n ）;2-进行哈夫编码n3-进行哈夫译码n0-程序退出n5.main函数进行调用int main（） HNode HuffMAXSIZE; int n,sel; 哈夫曼编码与译码nprintf（Input numbers of leaf : /n为叶结点个数n）; do menu（）;请输入您的选择:sel）; switch（sel） case 1: HuffTree（Huff,n）;/建立哈夫曼

6、树 break; case 2: HuffmanCode（Huff,n）; /生成哈夫曼编码 case 3: decode（Huff,n）;/译码变代码 while（sel!=0）; return 0;4源代码#includestdlib.h#define MAXSIZE 1000#define MAXBIT 1000 /定义哈夫曼编码的最大长度typedef struct char ch;/增加一个域用于存放该节点的字符 int weight,parent,lchild,rchild;HNode; /哈夫曼树结点类型 int weight; int bitMAXBIT; int start;

7、HCode; /哈夫曼编码类型i+） /对数组Huff初始化哈夫曼树的列表:n_|nzifu | Huff| weight | lchild | rchild| parent | n /输出哈夫曼树即数组Huff的信息_|_|_|_|_|_|n%4c |%4d | %5d | %10d |%10d |%10d |n,Huffi.ch, i, Huffi.weight, Huffi.lchild,Huffi.rchild, Huffi.parent）;_|n if（fp=fopen（d:hfmtree.txt,w）=NULL）/建立hfmtree文件cannot open the file of

8、 hfmtreen fprintf（fp,zifu Huff weight lchild rchild parent n%3c %3d %5d %10d %10d %10d n,Huffi.ch,i, Huffi.weight, fclose（fp）;void HuffmanCode（HNode Huff,int n） /生成哈夫曼编码i+） /求每个叶结点的哈夫曼编码/保存该编码在数组bit中的起始位置字母哈夫曼编码如下:-|-|-|-|nzifu |HuffCode| weight | bit |n /输出数组HuffCode的有关信息i+） /输出各叶结点对应的哈夫曼编码%4c |%5d

9、 |%4d | ,Huffi.ch,i,HuffCodei.weight）; for（j=HuffCodei.start+1;j+）%d |,HuffCodei.bitj）; if（fw=fopen（CodeFile.txt）=NULL）/建立codeFile文件cannot open the file of CodeFilen fprintf（fw,zifu HuffCode weight bit n%4c%5d%8d fclose（fw）; /从根结点开始往下搜索 /输入电文有错 if（fs=fopen（textFile.txt）=NULL）/建立textFile文件cannot open

10、 the textFile.txt of CodeFilen fprintf（fs,译码后的字符为 /n为叶结点个数五测试内容用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”字符A B C D E F G H I J K L M频度64 13 22 32 103 21 15 47 57 1 5 32 20N O P Q R S T U V W X Y Z57 63 15 1 48 51 80 23 8 18 1 16 1补充：在字母后输入了空格 这个字符，及其频度为1，对其进行编码。六运行结果1.输入树结

11、点：2.选择1，输入结点权值，构建哈夫曼树3.选择2，进行哈夫编码4.根据自己要编译的话输入对应的编码，进行翻译七收获及体会经过一个周的课程设计，我发现了我平时学习方面的许多不足。仅仅通过半学期的数据结构学习是不能够轻松完成任务的，我们必须在课外多多学习一些其他的函数来充实自己以及将书本上的一些思想融会贯通成为自己的知识。此外学习是一个不间断的过程，我们应该适时温故而知新，否则学过的东西会很快遗忘。就像这次的课设，编程之前我把数据结构书和C语言又前前后后的翻看了两遍，才回忆起好多原来学习过的知识，但在编程时仍然觉得很吃力。后来我们在网上搜到了一些程序，结果有好多我们没有学过的函数，为此我们又一边编程一边学习一些能够对程序起一些作用的函数，这样我们才勉强把程序编完。同时，让我体会到编程序难，调试程序更难，调试程序需要足够的耐心，在这个过程中需要我们一遍又一遍的修改数据或是结构，直到达到我们的目的。这个过程让我学到了很多知识，也让我觉得好有成就感。一个周的课设已经完了，但是它带给我的冲击还没有散去，在接下来的日子里我会继续深入地学习c语言和数据结构等，仅仅有课本上的知识是远不能达到需求的，我应该多学习，多实践，希望能在学习上更上一层楼。只要相信自己能做到，自己就能做到，再难的程序，只要自己喜欢去做，就一定能取得成功，告诉了自己只有永不言弃，这就是我的原则；八、参考文献