数据结构哈夫曼树.doc

数据结构实验报告1. 问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。2. 问题分析求哈夫曼编码，首先要根据字符出现的频率，即权值，构建哈夫曼树，然后根据哈夫曼树求出哈夫曼编码。3. 算法设计创建哈夫曼树：对n个权值，创建2n-1个节点，parent都默认为0，然后进行循环查找，每次循环都从所有节点中找出parent为0且weight最小的两个节点，序号分别为s1和s2，将s1节点和s2节点作为本节点的lchild和rchild，构建出一颗哈夫曼树，循环2n-1次，最后只剩下一颗哈夫曼树，即所要求的哈夫曼树。哈夫曼编码：从叶子节点出发，寻找双亲节点，若没有则说明已经到根节点；若有双亲节点，如果本节点是双亲节点的左孩子，则编码为0，右孩子编码为1，依次寻找直到走到根节点。最后将所求编码倒序输出即为哈夫曼编码。4. 测试数据测试数据为8个字符，权值分别为：5,29,7,8,14,23,3,11。测试结果：5. 总结建立哈夫曼树的时候，是逆向构建，即先创建叶节点，再创建根节点，从下往上创建。求哈夫曼编码的时候也是一样，从叶子节点不断找该节点的根节点，直到找到该哈夫曼树的根节点。6. 附录#include #include #include #define ERROR 0#define OK 1/-赫夫曼树和赫夫曼编码的存储表示-typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,* HuffmanTree;typedef char * HuffmanCode;/-赫夫曼算法-void Select(HuffmanTree HT, int n, int &min1, int &min2)unsigned int m1,m2;m1=m2=-1;/随意确定两个权值为最小for(int i=1;i=n;i+)if(m2!=-1)break;if(HTi.parent=0)if(m1=-1)m1=HTi.weight;min1=i;elsem2=HTi.weight;min2=i;/找最小权值for(int k=1;k=n;k+)if(HTk.parent=0)int w=HTk.weight;if(k=min1 | k=min2)continue;if(wm2)m2=w;min2=k;else if(w0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCif(n=1)return;int m = 2*n-1;HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用int i;HuffmanTree p=HT;for(p+,i=1;iweight = *w;p-parent = 0;p-lchild = 0;p-rchild = 0;for(;iweight = 0;p-parent = 0;p-lchild = 0;p-rchild = 0;int s1,s2;for(i=n+1;i=m;i+)/建赫夫曼树/在HT1.i-1选择parent为0且weight最小的两个节点，其序号分别为s1和s2Select(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*);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!=0;c=f,f=HTf.parent)if(HTf.lchild = c)cd-start = 0;elsecd-start = 1;HCi = (char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,&cdstart);free(cd);void main()int num;coutnum;char* zifu = new charnum;cout请输入要编码的字符，以空格隔开endl;for(int i=0;izifui;int* quan=new intnum;cout请输入要编码字符的权值，以空格隔开endl;for(int i2=0;i2quani2;HuffmanTree ht;HuffmanCode hc;HuffmanCoding(