资源描述：
《哈夫曼树编码以及译码——实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、华北水利水电大学数据结构实验报告2013～2014学年第一学期级计算机科学与技术专业班级：学号：姓名：实验三：哈夫曼编/译码器一．实验目的掌握哈夫曼树编码原理二．实验内容根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。基本要求：（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈
2、夫曼编码（写入文件）。（3）计算压缩比（选作）（4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={？},出现频率为w={？}三．程序源代码#include#include#include///.............数据结构的构造..........typedefstructHTNode{intweight;intparent;intlchild;intrchil
3、d;HTNode(intw,intp,intl,intr){weight=w;parent=p;lchild=l;rchild=r;}}HTNode,*HuffmanTree;typedefchar**HuffmanCode;typedefstruct///译码参照表{charword;char*code;}LNode,*List;///.......选取最小和次小的......voidSelect(HuffmanTree&HT,intnum,int*s1,int*s2){inti;for(i=1;i<=num;i++){if(HT[i].parent==0)
4、{*s1=i;break;}}for(i=1;i<=num;i++){if(HT[i].parent==0){if(HT[*s1].weight>HT[i].weight)*s1=i;}}for(i=1;i<=num;i++){if(i==*s1)continue;if(HT[i].parent==0){*s2=i;break;}}for(i=1;i<=num;i++){if(HT[i].parent==0){if(i==*s1)continue;if(HT[*s2].weight>=HT[i].weight)*s2=i;}}}///..........哈夫曼
5、树构造函数..........voidHuffmanTreeCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){inti,c,m,start;intf,s1,s2;char*cd;HuffmanTreep;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++w)*p=HTNode(*w,0,0,0);for(;i<=m;++i,++p)*p=HTNode(0,0,0,0);
6、for(i=n+1;i<=m;++i){Select(HT,i-1,&s1,&s2);////调用选取最小和次小的函数HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}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;
7、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)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}///.............译码函数................intTranslate(ListArrayList,char*s1,char*s2){inti,j,k=0;intnum=0
8、;intlen;for(i=1;i<=
