赫夫曼树课程设计

《赫夫曼树课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计名称：赫夫曼树的建立专业班级：信息与计算科学2013级一班姓名：课题分工（概要设计，详细方案与代码设计，调试与结果）（需求分析，调试与结果，改进方案）课题组成人员：指导教师：完成日期：2015年6月25日一、摘要运用C语言编写程序（工具VC++6.0）,建立函数输入二叉树，并输出赫夫曼树，完成编码。建立赫夫曼树的过程，给定权值Wi（i=l,2,3,……）构成左右子树为空二叉树集合，从集合中选取权值最小的树构成新的二叉树，新二叉树根结点的权值为其左右了树权值之和，将新的二叉树加入到集合中，如此重复，直到只有一棵树（赫夫曼树）。构造好赫夫曼树之后，从根到叶子

2、结点的路径及为编码。二、系统需求分析在信息传递时，希望总长度可能的短，及釆用最短码赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。建立最优二叉树函数，要求可以建立函数输入二叉树，并输出其赫夫曼树以及赫夫曼编码。三、系统概要设计1、存储结构：采用了数组和结构体结合的存储方式。以下是树中结点的存储结构形式，其中包括了权值，左typedefstruet{unsignedintweight;//权值unsignedintparent,lchild,rchild;iHTNodc；//动态分配数组存储赫夫曼树2、基本算法：(1)流程

3、图：(1)下面的代码是用来生成赫夫曼树的，其中这个过程汇总了select方法来不断寻找当前所有结点中权值最小的结点，然后生成新的结点，再生成相应的树。for(p=*HT+l,i=l;i〈二n;++i,++p,++w){(*p)・weight二*w;(*p).parent二0;//给每个结点权值赋值(*p)・lchild二0;(*p).rchild二0;//双亲，左右孩了赋初值}for(;i〈二m;++i,++p)(*p)・parcnt=0;for(i=n+l;i<=m;++i)//建赫夫曼树{//在HT[l~i-l]中选择parent为0且weight最小的两个结点,其

4、序号分别为si和s2select(*HT,i~l,&sl,&s2);(*HT)[si].parent二(*HT)[s2].parent二i;(*IIT)[i]・lchild二si;(*HT)[i].rch订d二s2;(*HT)[i]・weight=(*HT)[si]・weight+(*HT)[s2].weight;!3、所有实现功能的函(1)intmain():接收原始数据：从终端读入整数集大小n,n个整数和n个权值，调用函数HuffmanCoding(&HT,&HC,w,n);,以及输出编码。(2)voidselect(HuffmsnTreet,inti,int*sl

5、,int*s2)：在所有的树中，找到权值最小的两个赋值给si和s2,供HuffmanCoding使用。(3)intmini(HuffmanTrcct,inti):找最小权值。(4)voidIluffmanCodingdluffmanTree*IIT,IluffmanCode*IIC,int*w,intn)：构建赫夫曼树输出赫夫曼树，以及遍历赫夫曼树求编码。四、详细方案设计创建赫夫曼树：赫夫曼编码:五、代码详细设计1、源代码#include#include〈limits.h>//赫夫曼树和赫夫曼编码的存储表示typedefstruct{unsignedi

6、ntweight;unsignedintparent,lchild,rchild;}HTNodc,*HuffmanTrcc;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表//函数voidselect()调用intmini(HuffmanTreet,inti){intj,flag;unsignedintk=UINT_MAX;//取k为不小于可能的值for(j=l;j<=i;j++)if(t[j]・weight

7、l;returnflag;//S1为最小的两个值中序号小的那个voidselect(Huffma.nTreet,inti,int*sl,int*s2)intj:*si二mini(t,i);*s2二mini(t,i);if(*sl>*s2){j=*sl;*sl=*s2;*s2二j;}}//算法6.13P148//w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCvoidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn){intm,i,si,s2;uns