数据结构与算法实验报告3霍夫曼树.doc

1、数据结构与程序设计专题实验报告 实验报告 一、实验任务 实验题目：数据结构与程序设计专题实验二、实验内容实验三：树的基本操作及基于霍夫曼树的编码/译码（一）实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。（二）基本要求：熟练掌握树的操作。（三）内容提要：给定一段字符，构建霍夫曼树；根据该树求每个字符的编码，并对该段字符串进行编码；将得到的编码进行译码；基于该霍夫曼树，通过遍历算法来输出该树中的叶子节点。 注：在实现时要求霍夫曼树的左右孩子的大小关系（左孩子节点值小于右孩子节点），在遍历的时候也可以为递归与非递归办法寻找叶子节点。三、要点分析题目中涉及的主要知识点

2、1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）： （1）由给定的n个权值w0, w1, w2, , wn-1，构造具有n棵二叉树的集合F = T0, T1, T2, , Tn-1，其中每一棵二叉树Ti只有一个带有权值wi的根结 点，其左、右子树均为空。 （2）重复以下步骤, 直到F中仅剩下一棵树为止： 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的 权值之和。 在F中删去这两棵二叉树。 把新的二叉树加入F。2、用构造赫夫曼树以完成赫夫曼编码：把d1,d2, dn 作为叶子结点，把w1,w2,wn作为叶子结

3、点的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右分支赋1，从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。3、译码的过程是分解电文中的字符串，从根出发，按字符0或1确定找 左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。四、解题步骤编程平台：Microsoft Visual C+ 6.0编程平台应用：第一步：打开Microsoft Visual C+ 6.0运行软件；第二步：在主菜单中选文件新建。第三步：在出现的如下界面中选取“工程”项，选择“Win32 Console Application”，填写工程名称，选择存储路径，点击“确定”。第四步：勾选“一个简单的

4、程序”复选框。第五步：在出现的编译环境中编写程序。五、程序的算法描述1、所用存储结构： typedef struct HfNode int weight; int parent,lchild,rchild; HfNode,*HuffmanTree; /动态分配数组存储霍夫曼树 typedef char *HuffmanCode; /动态分配数组存储霍夫曼编码表2、 程序中各函数的简要说明： (1)void Select(HuffmanTree &HT,int i,int &a,int &b) 从前i个节点中选择权值最小的两个节点分别存入a,b中。设置a，b两个变量用“打擂台”的方 法求出两个最

5、小值。 (2)void CreatHuffmanTree(HuffmanTree &HT,int n,int Weight) 根据Weight53及Letter52中的信息建立具有2n-1个节点的Huffman树。 首先创建有2*n-1 个节点的存储空间，将前n个节点的权值付为对应的Weighti，双亲结点和左右孩子结点均置 为零。剩余结点的权值、双亲结点和左右孩子结点置为零。之后，i从n+1到2*n-1每次加1， 在HT1.i-1中选取parent为零且weight最小的两个节点，将他们的双亲结点置为HTi。 (3)void HuffmanCoding(HuffmanTree &HT,Huf

6、fmanCode &HC, int n) 获得n个字符的Huffman码。从叶子节点到根逆向求编码。先求叶子结点的双亲结点，如果该结 点为左孩子，则在Huffman码中从后往前字符置为0；若为右孩子则置为1，直至根节点结 束。 (4)char *HuffmanEncoding(HuffmanCode hc, int n,char Text,char Letter) 对输入文本进行Huffman编码。将要编码的字符串传入函数，截取一个字符，与编码表中的字符 比较，找到对应的huffman码，连接到编码串后，直至所有的字符都读入。 (5)void HuffmanDecoding(HuffmanTr

7、ee &HT, char a, int n,char Letter)对输入文本进行Huffman解码。从根结点出发，按字符0，1确定找左孩子或右孩子，直至 叶子结点，便求得该子串相应的字符。将所有子串找遍，得译码结果。 (6)int Statistic(int Weight,char Letter,char Text)对输入文本中的字母出现频数进行统计，存入Text100,Letter53,Weight53中。逐个读入 字符，与Letter中的字符比较，如果该字符已经出现过，则将相应的权值加1；否则，新建一 个字符统计项，相应的权值加1.直至所有的字符都读入。 (7)void main() 在

8、主函数中输出交互信息，提示用户输入要编码的字符串，调用Statistic函数并输出统计结果。 调用CreatHuffmanTree、HuffmanCoding，并输出每一个字符的huffman码。最后调用 HuffmanEncoding、HuffmanDecoding对其编码和解码。3、源代码完整程序及相应说明如下;#include #include #include typedef struct HfNode int weight; int parent,lchild,rchild;HfNode,*HuffmanTree; /动态分配数组存储霍夫曼树typedef char *Huffman

9、Code; /动态分配数组存储霍夫曼编码表/从前i个节点中选择权值最小的两个节点分别存入a,b中void Select(HuffmanTree &HT,int i,int &a,int &b) int j=1; if(i2)return; while(!(HTj.weight) j+; b=a=j; for(j=1;j(HTj.weight)a=j; if(b!=a) for(j=1;j(HTj.weight)&j!=a) b=j; else j=a+1; while(!(HTj.weight) j+; b=j; for(j=1;j(HTj.weight) b=j; /*根据Weight53及

10、Letter52中的信息建立具有2n-1个节点的Huffman树*/void CreatHuffmanTree(HuffmanTree &HT,int n,int Weight) int i,m;if(n=1)return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HfNode);/*不用0号单元*/ for(i=1;i=n;+i) HTi.weight=Weighti; HTi.parent=HTi.lchild=HTi.rchild=0; for(i=n+1;i=m;+i) HTi.weight=HTi.parent=HTi.lchild=H

11、Ti.rchild=0; for(i=n+1;i=m;+i) /*构造赫夫曼树*/ int s1,s2; Select(HT,i-1,s1,s2); /*在HT1.i-1选择parent为0且weight最小的两个节点，其序号 分别为s1和s2*/ HTs1.parent=i; HTs2.parent=i; HTi.lchild=s2; HTi.rchild=s1; (HTi.weight)=(HTs1.weight)+(HTs2.weight); (HTs1.weight)=(HTs2.weight)=0; /*获得n个字符的Huffman码*/void HuffmanCoding(Huff

12、manTree &HT,HuffmanCode &HC, int n) int i,start,c; int f; char *cd; if(!HT)return; HC=(HuffmanCode)malloc(n + 1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i) /*求每个字符的赫夫曼编括码*/ start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if (HTf.lchild=c)cd-start=0; else cd-start

13、1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi, &cdstart); free(cd);/*对输入文本进行Huffman编码*/char *HuffmanEncoding(HuffmanCode hc, int n,char Text,char Letter) int i,j=0; char a400; for(i=0;i400;i+)ai=0; while(Textj) for(i=1;i=n;i+) if(Textj=Letteri) strcat(a,hci); break; j+; return a;/*对输入文本进行H

14、uffman解码*/void HuffmanDecoding(HuffmanTree &HT, char a, int n,char Letter) int i=0,m,count=0,location; char b100; m=2*n-1; for(i=0;i100;i+)bi=0; i=0; while(acount!=0) location=m; while(1) if(!(HTlocation.lchild)&!(HTlocation.rchild)break; if(acount=0)location=HTlocation.lchild;elselocation=HTlocatio

15、n.rchild;count+; bi+=Letterlocation; printf(nHuffman解码的结果:n%sn,b);/*对输入文本中的字母出现频数进行统计，存入Text100,Letter53,Weight53中*/int Statistic(int Weight,char Letter,char Text) char a; int count=0,i,j=0,flag=0; for(i=1;i=52;i+) /字母及权值置零Letteri=Weighti=0; while(a=getchar()!=n) /逐个读入字符并统计 Textj+=a; for(i=1;i=count

16、i+) if(a=Letteri) Weighti+; flag=1; break; if(flag)flag=0;continue; else Lettercount+1=a; Weightcount+1+; count+; Textj=0; return count;void main()int Weight53;/权值 HuffmanCode hc;/霍夫曼编括码HuffmanTree ht;/霍夫曼树骸char Letter53,Text100;/letter统计每个字母的信息，text存储要编括码的字符串 int i=1,n; char *a; printf(请输入将要进行Huff

17、man编码的字母序列:n); n=Statistic(Weight,Letter,Text); printf(n字母序列统计:n%sn,Text);while(i=n)printf(%3c%3dn,Letteri,Weighti) ;i+; CreatHuffmanTree(ht,n,Weight); HuffmanCoding(ht,hc,n); printf(n每一个字的Huffman编码:n);i=1;while(i=n)printf(%c %sn,Letteri,hci);i+; a=HuffmanEncoding(hc,n,Text,Letter); printf(nHuffman编

18、码的结果:n%sn,a); HuffmanDecoding(ht,a,n,Letter);六、 程序运行结果七、 实验总结 通过本次实验熟练掌握了结构体、指针及二叉树的生成、遍历等操作，掌握了霍夫曼编码/译码的原理，熟练掌握树的操作。尤其是对霍夫曼树有了更深的理解。同时，在编写统计函数时，复习了对字符串的各种操作。八、致谢词 非常感谢刘老师对编写解码函数的指导。九、参考文献1. 陈维兴，林小茶.C+面对对象的程序设计教程（第三版）.北京：清华大学出版社,20092. 谭浩强.C程序设计（第四版）.北京：清华大学出版社，20103. 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，1997.411