哈夫曼编码上机实验报告.doc

《哈夫曼编码上机实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、--第四次上机实验报告姓名：康辉学号：班级：1518021一、题目要求对输入的一串电文字符(ABCDEFGH8个字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11)实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。实现功能如下：•Huffman树的建立•Huffman编码的生成•编码文件的译码二、程序思路设置一个数组v存放待编码元素，一个数组w存放权值，n为元素个数，ht为创建的哈夫曼树，hc为指针数组存储哈夫曼编码，这些作为函数参数传递到函数haffcoding中

2、，创建编码树，然后按权值进行编码，这些都在一个函数中实现。哈夫曼树节点：typedefstruct{chardata;Intweight;Intparent,lchild,rchild;}htnode,huffmantree;三、程序设计中遇到的问题1、选择一个数组来存储来存放编码，但是指针数组运用的不够熟练，造成值传递时出错。最后查看c语言书籍得以解决.--优质---1、在选择所有权值中最小，次小的时候出现错误，造成乱序，编出来的编码不正确，最后通过单步调试找出错误。2、hc=(huffmancode)malloc((n+1)*sizeof(

3、char*));这里第一次分配空间为char型，对指针数组很不熟悉造成的。3、还有其他的很多问题在程序中都有注释加重点。一、程序源码#include#include#include#definelengthsizeof(htnode)typedefstructhtnode{chardata;intweight;intparent,lchild,rchild;}htnode,*huffmantree;//哈夫曼存储结构typedefchar**huffmancode;//存储哈夫曼编码表v

4、oidhuffmancoding(huffmantreeht,huffmancode&hc,int*w,char*v,intn)//v是待编码元素数组，w是每个元素的权值，构造哈夫曼树ht，hc存放哈夫曼编码--优质---{inti,m,s1,s2,min1,min2,j;char*cd;intstart,c,f;if(n<=1)return;m=2*n-1;ht=(huffmantree)malloc((m+1)*length);//有n个叶子节点的hfuumantree需要2n-1个结点存储for(i=1;i<=n;++i,++w,++v)

5、//对n个元素进赋值，权值，父亲左右孩子标记为0{ht[i].data=*v;ht[i].weight=*w;ht[i].lchild=0;ht[i].parent=0;ht[i].rchild=0;}for(;i<=m;++i)//对后m-n个非叶子节点标记{ht[i].data=0;ht[i].weight=0;ht[i].lchild=0;ht[i].parent=0;ht[i].rchild=0;}for(i=n+1;i<=m;++i)//建树{--优质---s1=s2=0;min1=min2=32767;for(j=1;j<=i-1;

6、++j){if(ht[j].parent==0){if(ht[j].weight

7、alloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量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*)mal

8、loc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(hc[i],cd+start);}free(cd);