赫夫曼树课程设计

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

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

3、1）流程图： 开始 输入叶子结点个数 输入结点权值，m=2n-1 给结点1n和n+1m分别赋初值 构建赫夫曼树结束遍历赫夫曼树，求赫夫曼编码输出赫夫曼树（2）下面的代码是用来生成赫夫曼树的，其中这个过程汇总了select方法来不断寻找当前所有结点中权值最小的结点，然后生成新的结点，再生成相应的树。for(p=*HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; /给每个结点权值赋值(*p).lchild=0; (*p).rchild=0; /双亲，左右孩子赋初值 for(;i=m;+i,+p) (*p).parent=0; for(i=n

4、+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; 3、所有实现功能的函（1）int main() ：接收原始数据：从终端读入整数集大小n，n个整数和n个权值，调用函数HuffmanCoding(&HT,&HC,w,n); ，以及输出编码。（

5、2）void select(HuffmanTree t,int i,int *s1,int *s2)：在所有的树中，找到权值最小的两个赋值给s1和s2,供HuffmanCoding使用。（3）int min1(HuffmanTree t,int i）：找最小权值。（4）void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)：构建赫夫曼树输出赫夫曼树，以及遍历赫夫曼树求编码。四、详细方案设计开始创建赫夫曼树：是结束(*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchi

6、ld=0; i=i+1否否是i=i+1i=m(*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight;i=ni=1初始化赫夫曼表且有m=2n-1结点开始赫夫曼编码：遍历赫夫曼树求每个赫夫曼树的编码，i=1i=n(*HT)i.weight=0，结点状态标志是是否是否结束此时编码为1(*p).lchild=0; (*p).rchild=0; 右子是否空此时编码为0左子是否空P权值是否为1p是否为空5、 代码详细设计1、 源代码#in

7、clude #include / 赫夫曼树和赫夫曼编码的存储表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode, *HuffmanTree; / 动态分配数组存储赫夫曼树typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表/ 函数void select()调用int min1(HuffmanTree t,int i) int j,flag; unsigned int k=UINT_MAX; / 取k为不小于可能的值 for(j=1;j=i;j+) if(

8、tj.weight*s2) j=*s1;*s1=*s2; *s2=j; / 算法6.13 P148 / w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) int m,i,s1,s2; unsigned c,cdlen; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用for(p=*

9、HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; /赋权值(*p).parent=0; /给双亲，左右孩子赋初值(*p).lchild=0; (*p).rchild=0; for(;i=m;+i,+p) (*p).parent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别 为s1和s2 select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (

10、*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; printf(赫夫曼树为：n); printf(元素权值父结点 左孩子 右孩子n); for(i=1;i=2*n-1;i+) printf(%5d %5d %5d %5dn,(*HT)i.weight,(*HT)i.parent,(*HT)i.lchild,(*HT)i.rchild); / 以下为算法6.13，无栈非递归遍历赫夫曼树,求赫夫曼编码，以上同算法6.12 *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(

11、char*)malloc(n*sizeof(char); / 分配求编码的工作空间 c=m; cdlen=0; for(i=1;i1)：); scanf(%d,&n); w=(int *)malloc(n*sizeof(int); printf(请依次输入%d个权值(整型)：n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(&HT,&HC,w,n); printf(赫夫曼编码： n);for(i=1;i=n;i+) puts(HCi); system(pause); return 0; 6、 测试与调试结果7、 分析与改进此算法的时间复杂度为O(n2)。由实验结果知道，建立赫夫曼树，