赫夫曼编码码器.doc

《赫夫曼编码码器.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、赫夫曼编码/译码器一、实验目的1．进一步掌握最优二叉树的含义。2．掌握最优二叉树的结构特征，以及各种存储结构的特点及使用范围。3．熟练掌握哈夫曼树的建立和哈夫曼编码方法。4．掌握用指针类型描述、访问和处理运算。二、实验内容编写一个哈夫曼码的编/译码系统，一个完整的系统应具有以下功能：(1)初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree.txt中。(2)编码。利用已建好的哈夫曼树，对文件ToBeTra.txt中的正文进行编码，然后将结果存入文件CodeFil.txt中。(3)译码。利用已建好的哈夫曼

2、树将文件CodeFile.txt中的代码进行译码，结果存入文件Textfile.txt中。(4)印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint.txt中。三、实验步骤1.定义结点结构，定义哈夫曼树结构；2.初始化哈夫曼树，存储哈夫曼树信息；3.定义求哈夫曼编码的函数；4.定义译哈夫曼编码的函数；1．写出主函数。2．测试系统。一、实现提示typedefstruct{charinfo;unsignedintweight;unsignedintpare

3、nt,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;intn,*w;char*info;HuffmanTreeHT;HuffmanCodeHC;voidSelect(HuffmanTreeHT,intj,int&s1,int&s2){//选择双亲节点为0，并且最小的两个子叶节点………..}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn,char*info){//算法6.12inti,j,m,s1,s2,st

4、art;char*cd;unsignedintc,f;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;i++){HT[i].weight=w[i-1];HT[i].info=info[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;i++){HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild

5、=0;}printf("哈夫曼树的构造过程如下所示：");printf("HT初态:结点weightparentlchildrchild");for(i=1;i<=m;i++)printf("%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("按任意键，继续...");getch();for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i

6、;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;printf("select:s1=%ds2=%d",s1,s2);printf("结点weightparentlchildrchild");for(j=1;j<=i;j++)printf("%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);printf("按任意键，继续...");getch();

7、}//---从叶子到根逆向求每个字符的哈夫曼编码---HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(i=1;i<=n;++i){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*

8、sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}//HuffmanCo