《良心出品构造哈夫曼树及哈夫曼编码.doc》由会员分享，可在线阅读，更多相关《良心出品构造哈夫曼树及哈夫曼编码.doc（5页珍藏版）》请在三一文库上搜索。
1、数据结构实验报告实验名称：构造哈夫曼树及哈夫曼编码计算机科学与技术专业专 业：级:计算机科学与技术班姓名：.学号：2012/11/22完成日期：年 2012 22 11月曰一、问题描述构造一个哈夫曼树，并根据所构造的哈夫曼树求其哈夫曼树的编码；二、需求分析哈夫曼树有叫做最优二义树，它是指对于一组带有确定的权值的叶节点，构造具 有最小的带权路径程度的二义树。在数据通信中，经常需要将传送的文字转换成山二进制字符0,1组成的二进制串， 称之为编码。如果在所有的编码中每个字符的编码都一样的长短则有的字符在应 用中出现的次数多有的字符在应用中出现的次数少，这样的话有的电文的编码会 很长，所以就想用不同长
2、度的编码区代表字符，及在电文中出现的概率大的用短 的字符表示，而出现的概率小的用长的字符表示，则得到的电文可能就比较短。 基于以上的需求与要求，就出现了哈夫曼编码。三. 概要设计1、先建立哈夫曼树的结构，即哈夫曼树的构造算法；再建立哈夫曼树编码的结构，即哈夫曼树编码的算法八2、3再带入数据进行验证。四、详细设计1.、哈夫曼树构造算法的编码：#include<iostream>using namespace std;define MAXX ALUE 100define MAXLEAF 30MAXLEAF*2-1 #define MAXNODEdefine MAXBIT 10 type
3、def stmctiiit weiflit; 权值iiit parent; 双亲节点 iiit lchild;/左孩子iiit rchild;/ 右孩子JHNodeTxpe;typedef stmctiiitbitMAXBIT;iiit start;HCodeType;void HuffinanTree(HNodeTq)e HuffNodefJjnt n) iiit ij,ml,m2,xl,x2;for(i = 0;i < 2*irl;i+)对数组进行初始化HuffNodei.weiflit = 0; HufiNodefi .parent = -1;HuffNodefi .lchild
4、= -1;HufiENodefi .rchild = -1;输入各个节点的权值for(i = 0;i < n;i+) /vvendl; ?柿?瀾璜？输入笫 个叶节点的权值：cin»HufiENodei.weiflit; for(i = 0;i < n-l;i+) 构造哈夫曼树ml = MAXVALUE;m2=MAXV ALUE;xl = x2 = 0;for(j = 0;j <11 + i;j+)找出两棵权值最小的树if(HuffNodej.weiflit < ml&&HuffNodefj.parent = -1)ni2 = ml;x2 = x
5、l;ml = HufiENodej.weifht;xl=j；else if(Huf£Nodej.weiflit < m2&&HuffNodej.parent = -1)ni2 = HufiENode j . weifht;x2=j;合并两个子树 HufiENodex 1 .parent = n + i; /HuffNodex2 .parent = n + i;HufiENode n+i .weiflit = HufiNodefx 1 .weifht + HuffNodex2 .weiflit;HufiENode n+i .lcliild = xl;HufiNod
6、en+i .rchild = x2;void HaffinanCodeO哈夫曼编码HNodeType HufiNodeMAXNODE;HCodeType HuffCodeMAXLEAF,cd;int i jcpn;澗璜?输入节点的个数：«endl; 输入节点的个数 cin»n;HufiinaiiTree(HuffNode4i);fbr(i = 0;i < n;i+)cd. start = n - 1;c = i;p = HufiNodec .parent;while(p != -1)if(HuffNodep .lchild = c)cd.bitcd.stait = 0
7、;elsecd.bitcd.start = 1;cd. start;c = p；p = HuffNodefc .parent;for(j = cd.start+l;j < n;j+)HuffCodei.bitj = cd.bitj;HuffC ode i. start = cd. start;«endl;哈夫曼编码为：澗璜?for(i = 0;i v n；i卄)for(j = HuffCodei.start + l;j v n;j+)cout«HuffCodei.bitj;cout«endl;iiit main(void)HaffhianCode();retimi 0;五、测试分析结果：输入节点的个数：5输入笫0个叶节点的权值：1输入第1个叶节点的权值：2输入笫2个叶节点的权值：3输入笫3个叶节点的权值：4输入第4个叶节点的权值：5哈夫曼编码为：010011001011Press any key to continue六、总结在本次编写程序的时候开始把哈夫曼树的判断的时候叶节点将(p! =-1)写成 了 (p!=l)结果导致不能读出哈夫曼树的编码。