《数据结构哈夫曼树》由会员分享，可在线阅读，更多相关《数据结构哈夫曼树（4页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告1问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码2问题分析求哈夫曼编码，首先要根据字符出现的频率，即权值，构建哈夫曼树，然后 根据哈夫曼树求出哈夫曼编码。3.算法设计创建哈夫曼树：对n个权值，创建2n-1个节点，pare nt都默认为0,然后进 行循环查找，每次循环都从所有节点中找出pare nt为0且weight最小的两个节点，序号分别为si和s2,将si节点和s2节点作为本节点的Ichild和 rchild，构建出一颗哈夫曼树，循环 2n-1次，最后只剩下一颗哈夫曼树，即 所要求的哈夫曼树。哈夫曼编码：从叶子节点出发，寻找双亲节点，若没有则说明已经到根节 点；若
2、有双亲节点，如果本节点是双亲节点的左孩子，则编码为0,右孩子编码为1,依次寻找直到走到根节点。最后将所求编码倒序输出即为哈夫曼 编码。4.测试数据测试数据为8个字符，权值分别为：5,29,7,8,14,23,3,11测试结果：请蓊入套编码阳字将，页空格开 a b c d e f 1请输入要编码字符的权值，以空格輛开5 29 7 a 14 23 3 11 赫夫曼编码为：b：18c:0Q01d:0603fi：01f9：0U1h：lll5总结建立哈夫曼树的时候，是逆向构建，即先创建叶节点，再创建根节点，从下往上 仓U建。求哈夫曼编码的时候也是一样，从叶子节点不断找该节点的根节点，直到找到 该哈夫曼树
3、的根节点。6附录#in elude #i nclude #in elude #define ERROR 0#define OK 1/赫夫曼树和赫夫曼编码的存储表示 typedef structun sig ned int weight;un sig ned int pare nt,lchild,rchild;HTNode,* Huffma nTree;typedef char * Huffma nCode;/赫夫曼算法void Select(HuffmanTree HT, int n, int &min 1, int &min2)un sig ned int m1,m2;m1=m2=-1;/随
4、意确定两个权值为最小for(i nt i=1;i=n ;i+) if(m2!=-1)break;if(HTi.pare nt=O) if(m 1=-1)m仁 HTi.weight;min 1=i; elsem2=HTi.weight;mi n2=i;II找最小权值for(i nt k=1;k=n; k+)if(HTk.pare nt=O)int w=HTk.weight; if(k=mini | k=min2)con ti nue;if(wm2)m2=w;min 2=k;else if(w0)，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCif(n =1)return;int m = 2*
5、n-1;HT = (Huffma nTree)malloc(m+1)*sizeof(HTNode);/0号单元未用int i;Huffma nTree p=HT;for(p+,i=1;iweight = *w;p-pare nt = 0;p-lchild = 0;p-rchild = 0;for(;iweight = 0;p-pare nt = 0;p-lchild = 0;p-rchild = 0;int s1,s2;for(i=n+1;i=m;i+)建赫夫曼树/在HT1.i-1选择pare nt为0且weight最小的两个节点，其序号分别为si和s2Select(HT,i-1,s1,s2)
6、;HTs1.pare nt = i;HTs2.pare nt = i;HTi.lchild = si;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;/-从叶子到根逆向求每个字符的赫夫曼编码-HC = (Huffma nCode)malloc( n+1)*sizeof(char*);char* cd = (char*)malloc( n*sizeof(char);cdn-1=0;int start;for(i=1;i=n; i+)start = n-1;for(unsigned int c=i,f=HTi.parent;f!=O;c
7、=f,f=HTf.parent)if(HTf.l child = c)cd-start = 0;elsecd-start = 1;HCi = (char*)malloc(n-start)*sizeof(char); 为第 i 个字符编码分配空间 strcpy(HCi,&cdstart);free(cd);void mai n()int num;cout请输入要编码字符的数量：；cinnum;char* zifu = new char nu m;cout请输入要编码的字符，以空格隔开endl;for(i nt i=0;i zifui;int* qua n=new intnu m;cout请输入要编码字符的权值，以空格隔开endl;for(int i2=0;i2 qua ni2;Huffma nTree ht;Huffma nCode hc;Huffma nCod in g(ht,hc,qua n,nu m);cout赫夫曼编码为:endl;for(int i3=1;i3=num;i3+)coutzifui3-1:hci3e ndl;delete zifu;delete qua n;
