《哈夫曼树上机实验报告》由会员分享，可在线阅读，更多相关《哈夫曼树上机实验报告（9页珍藏版）》请在金锄头文库上搜索。
1、霍夫曼树实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。基本要求：熟练掌握树的操作。程序实现：程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。要点分析:题目中涉及的主要知识点： 1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）： （1）由给定的n个权值w0, w1, w2, , wn-1，构造具有n棵二叉树的集合F =T0, T1, T2, , Tn-1，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、
2、右子树均为空。 （2）重复以下步骤, 直到F中仅剩下一棵树为止: 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删去这两棵二叉树。 把新的二叉树加入F。 2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2, dn 作为叶子结点，把w1,w2,wn作为叶子结点 的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右 分支赋1，从根结点到叶子结点的路径上的数字拼接起来就 是这个叶子结点字符的编码。 3、译码的过程是分解电文中的字符串，从根出发，按字符0或1确定找左孩子或右孩子，直至叶子节点，便求得该子串
3、相应的字符。心得体会：通过本次实验，我熟练掌握了结构体、指针及二叉树的生成、遍历等操作，掌握了霍夫曼编码和译码的原理，熟练掌握树的操作，尤其是对霍夫曼树有了更深刻的理解。同时，在编写代码的过程中方，对字符串的相关知识进行了回顾。代码#include#include#includetypedef structint weight;int parent,lchild,rchild;int sign;HTNode,*HuffmanTree;typedef char * *HuffmanCode;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,in
4、t *w,int n,char *s);void select(HuffmanTree &HT,int i,int &s1,int &s2);void creatHuffmanTree(int *w,char *s,char *r);void pr(HuffmanCode &HC,char r,char s,char a);void HuffmanYM(HuffmanCode &HC,char r,char a,int n,HuffmanTree &HT);void HuffmanPass(HuffmanCode &HC,char r,int n,HuffmanTree &HT);int ma
5、in()char s100;char r100;char a100=a;int w100;int n,p;HuffmanTree HT;HuffmanCode HC;printf(请输入进行编码的字符串n);scanf(%s,s);p=strlen(s);if(p!=1)creatHuffmanTree(w,s,r);printf(进行编码.n); if(p!=1) HuffmanCoding(HT,HC,w,strlen(r)-1,r);else printf(%c的霍夫曼编码是: %cn,s0,0);printf(霍夫曼码序列为：n);if(p!=1) for(int i=0;istrle
6、n(s);i+) pr(HC,r,si,a);printf(n);n=strlen(r)-1;if(p=1)printf(0n);printf(霍夫曼编码进行译码:n);if(p=1)printf(%c,s0);else HuffmanYM(HC,r,a,n,HT);printf(n); printf(先序遍历输出叶子节点n);if(p=1)printf(%cn,s0);else HuffmanPass(HC,r,n,HT);return 0;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w,int n,char s)int s1
7、,s2,f,c;int m,i,l;int start;char cd101;if(n1)return;l=strlen(s);m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HT0.weight=10000; for (i=1;i=n;+i) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign=0; for(;i=m+1;+i) HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign
8、=0; for(i=n+1;i=m;i+) select(HT,i-1,s1,s2);/选择最小的两个结点 HTs1.parent=i;HTs2.parent=i;/将它们的父节点赋值 HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cdn-1=0; for(i=1;i=n;i+) start=n; c=i; for(f=HTi.parent;f!=0;f=HTf.parent) if(HTf.lchild=c) start-
9、; cdstart=0; else start-; cdstart=1; c=f; HCi=(char *)malloc(n-start)*sizeof(char); for(int a=0;an-start;a+) HCia=cdstart+a; HCia=0; printf(%c的霍夫曼编码是: %sn,si,HCi);void select(HuffmanTree &HT,int i,int &s1,int &s2)s1=0;s2=0;for(int j=1;j=i;j+)if(HTj.parent=0)if(HTj.weight=HTs1.weight)s1=j;else contin
10、ue;else continue;for(j=1;j=i;j+)if(j=s1)continue;else if(HTj.parent=0) if(HTj.weight=HTs2.weight) s2=j; else continue; else continue;void creatHuffmanTree(int w,char s,char r)int g=1;int q=0;r0=0;r1=s0;w0=1;for(int e=1;estrlen(s);e+)for(int k=1;k=g;k+)if(rk=se)wk-1+;q=1;else continue;if(q=0)r+g=se;w
11、g-1=1;q=0;r+g=0;void pr(HuffmanCode &HC,char r,char s,char a)for(int i=1;istrlen(r);i+)if(ri=s)printf(%s,HCi);strcat(a,HCi);else continue;void HuffmanYM(HuffmanCode &HC,char r,char a,int n,HuffmanTree &HT)int e=strlen(a);int k=0;int f=2*n-1;char b10=1;for(int j=1;j=e;j+)if(HTf.lchild!=0|HTf.rchild!=0)bk=aj;k+; if(aj=1) f=HTf.rchild;else if(aj=0)f=HTf.lchild;else for(int s=1;s=n;s+)if(strcmp(HCs,b)=0)printf(%c,rs);break;else continue;for(int u=0;u10;u+)bu=0;k=0;f=2*n-1;j=j-1;void HuffmanPass(HuffmanCode &HC,char r,int n,Hu
