《数据结构实验报告huffman编码和解码算法》由会员分享，可在线阅读，更多相关《数据结构实验报告huffman编码和解码算法（7页珍藏版）》请在金锄头文库上搜索。
1、（规格为A4纸或 A3纸折叠）佛山科学技术学院（用四号宋体）实验报告（用小二号黑体）课程名称数据结构实验 实验项目用 Huffman 树进行编码和解码算法 专业班级姓 名学 号 指导教师成 绩日 期 （用小四号宋体）一、目的和要求 1、通过本实验，熟悉二叉树、Huffman 树的基本概念，掌握二叉树的存储结构及各种 算法。 2、熟悉用 Huffman 树进行电文的加密与解密算法。 二、实验原理 Huffman 树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符 的频度，能够达到编码电文的最小化。 三、实验步骤 1、统计电文中字符的出现频率。 2. 用统计频率建立 Hffman
2、 树。 3生成前缀码； 4建立 huffman 树的解码算法 5用随机输入的电文完成编码与解码过程。 四、源程序 #include #include #include #define MAX 100 struct HTNode char a; int weight; int parent,lchild,rchild; *HT; /动态分配数组存储赫夫曼树 char *HC; int n=0,m=0; char *write()/存储输入的电文 char *p,*q; printf(“请输入电文 ( 结束输入请按 enter ） ：n“); p=(char *)malloc(MAX*sizeof
3、(char);/申请存储输入的电文的空间 if(!p) exit(0); q=p; scanf(“%c“,q); while(*q!=n) /*录入电文，每录入一个字符同时给电文长度计数器n 加一* /*遇到换行符时结束录入 * n=n+1; if(n=MAX)/判断已申请的空间是否足够录入，不足则追加空间 p=(char *)realloc(q,(MAX+10)*sizeof(char); if(!p) exit(0); q+; scanf(“%c“,q); return(p); void weight(char *p)/求电文中各字符的概率，并将该概率当作各字符的权值 char *q,*q
4、1,temp; struct HTNode *q2; int i,j,t; q1=q=(char *)malloc(n*sizeof(char); for(;*p!=n;p+,q1+) *q1=*p;/将电文存放到 q1 指向的空间中 q1=q; for(i=0;i*(q1+j) t=j; temp=*(q1+i); *(q1+i)=*(q1+t); *(q1+t)=temp; temp=*q1;/标记当前为何种字符 m=1; for(i=1;ia=*q1;*q1=q2-a;q1+) t+; i+; q2-weight=(int)(t*100/n); q2-lchild=0; q2-paren
5、t=0; q2-rchild=0; q2+; for(i=m+1;ilchild=0; q2-parent=0; q2-rchild=0; q2-weight=0; free(q); void Select(int t,int *s1,int *s2) /*在 HT1，t 选择 parent 为 0 且 weight 最小的两个结点，其序号分别为s1 和 s2。*/ int temp,j; for(j=1;jHT*s2.weight) temp=*s2; *s2=*s1; *s1=temp; for(;t0;t-) if(t!=*s1 else if(HT*s1.weightHTt.weigh
6、t) *s2=*s1; *s1=t; void Huffmancoding() /*构 造 赫 夫 曼 树HT， 并 求 出m 个 字 符 的 赫 夫 曼 编 码 HC*/ int i,t,s1,s2,start,f,c; char *cd; for(i=m+1;i2*m;i+) /*建立赫夫曼树 * t=i-1; Select(t, HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /*从叶子到根逆向求每个字符的赫夫曼编码* HC=(char *)ma
7、lloc(m+1)*sizeof(char *);/分配 m个字符编码的头指针向量 cd=(char *)malloc(m*sizeof(char);/分配求编码的工作空间 cdm-1=0;/编码结束符 for(i=1;i=m;i+) /*逐个字符求赫夫曼编码 * start=m-1;/编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char *)malloc(m-start)*sizeof(char);/为第 i
8、个字符编码分配空间 strcpy(HCi,/从 cd 复制编码到 HC free(cd);/释放工作空间 void visit(char *p) /*对电文进行编码和解码 * int i,j,k,t=0; char *q,*q1,*q2; q=(char *)malloc(sizeof(char);/申请编码后的电文存储空间 printf(“电文编码加密后为： n“); /*将编码后的电文输出并存储到q 所指向的空间 * for(j=1;j=n;j+,p+) for(i=1;i=m;i+) if(HTi.a=*p) k=t; printf(“%s“,HCi); for(q2=HCi;*q2!=
9、0;q2+) t+;/*用 t 统计 HCi 中前缀码的长度，以便 准确申请空间大小 */ q=(char *)realloc(q,(t+1)*sizeof(char); q1=q+k; strcpy(q1,HCi); printf(“n“); printf(“对编码进行解码后为： n“); /*将编码加密后的电文重新编码出来* for(q1=q;*q1!=0;) for(i=1;i=m;i+) /*从 q 的首地址开始对比所有字符的前缀码，* /*一旦相同则输出该字符并继续往下对比，知道q 指向的空间中字符对比 完结*/ t=0; for(q2=HCi;*q2!=0;q2+) t+; q2=
10、(char *)malloc(t+1)*sizeof(char); for(j=0;jt;j+) q2j=q1j; q2t=0; if(strcmp(q2,HCi)=0) /*比较此段加密码是否跟该字符前缀码一样，是则输出* printf(“%c“,HTi.a); q1=q1+t; break; free(q2); printf(“n“); /*主函数 * void main() int i; char *p; p=write();/输入电文 weight(p);/统计电文各字符的概率并作为权值，初始化赫夫曼树HT Huffmancoding();/建立赫夫曼树并求出每个字符的赫夫曼编码 pr
11、intf(“该电文中所包含字符及各自对应的前缀编码如下：n“); for(i=1;i=m;i+) printf(“字符： %c 前缀码： %sn“,HTi.a,HCi); visit(p);/对电文进行编码和解码 五、实验结果六、讨论分析 同第一个实验一样，本次实验结果也同样完成了实验要求的内容，能成功的解码与编码。 相对于第一个实验来说， 本次的实验不管是在算法本身还是编程运用难度都提升了不少，所 以较第一个算法来说花的时间更多了。 在这次的实验过程中，相对于第一次的生疏，这次能够较好的运用C中的各种语句了， 也没有犯下想第一个实验那样的scanf 忘了加地址符等小问题， 但最终还是因为对算
12、法和C 中某些函数的不懂而导致卡住了的情况。因为对算法的了解不够， 再加上此次的算法要用到 很多次循环， 所以导致了循环经常出错。 另外，由于我自己为了保证不会申请过多空间导致 浪费，所以在几个地方用到了relloc函数，导致了程序出错，后来在进一步了解了relloc 函数后，才知道是追加空间时不够空间追加所导致的。 总的来说这次的实验还是比较顺利的，能够自己独立完成， 对我编程方面的能力又有了 一次很大的锻炼。 七、改进实验建议 我觉得老师的实验要求方面写的不够明了，一开始看到题目时我搞不清楚是要先建立起 一个对所有的字符统计比较全面的赫夫曼树前缀编码，然后不管输入什么样的电文都有此个 编码表编码和解码； 还是每次输入电文都对输入的电文建立赫夫曼树求前缀编码然后解码和 编码。所以觉得此实验的步骤和要求最好能再写详细些。注： 1、实验报告的内容: 一、实验目的；二、实验原理；三、实验步骤；四、实验结果；五、讨论分析（完成指定的思考题和作业题）；六、改进实验建议
