下载文档原格式
数据结构哈夫曼树和哈夫曼编码权值一、引言在计算机领域，数据结构是非常重要的一部分，而哈夫曼树和哈夫曼编码是数据结构中非常经典的部分之一。
本文将对哈夫曼树和哈夫曼编码的权值进行全面评估，并探讨其深度和广度。
通过逐步分析和讨论，以期让读者更深入地理解哈夫曼树和哈夫曼编码的权值。
二、哈夫曼树和哈夫曼编码的基本概念1. 哈夫曼树哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。
它的概念来源于一种数据压缩算法，可以有效地减少数据的存储空间和传输时间。
哈夫曼树的构建过程是基于给定的权值序列，通过反复选择两个最小权值的节点构建出来。
在构建过程中，需要不断地重排权值序列，直到构建出一个满足条件的哈夫曼树。
2. 哈夫曼编码哈夫曼编码是一种变长编码方式，它利用了哈夫曼树的特点，对不同的字符赋予不同长度的编码。
通过构建哈夫曼树，可以得到一套满足最优存储空间的编码规则。
在实际应用中，哈夫曼编码经常用于数据压缩和加密传输，能够有效地提高数据的传输效率和安全性。
三、哈夫曼树和哈夫曼编码的权值评估1. 深度评估哈夫曼树和哈夫曼编码的权值深度值得我们深入探究。
从构建哈夫曼树的角度来看，权值决定了节点在树中的位置和层次。
权值越大的节点往往位于树的底层，而权值较小的节点则位于树的高层。
这种特性使得哈夫曼树在数据搜索和遍历过程中能够更快地找到目标节点，提高了数据的处理效率。
而从哈夫曼编码的角度来看，权值的大小直接决定了编码的长度。
权值越大的字符被赋予的编码越短，可以有效地减少数据传输的长度，提高了数据的压缩率。
2. 广度评估另哈夫曼树和哈夫曼编码的权值也需要进行广度评估。
在构建哈夫曼树的过程中，权值的大小直接影响了树的结构和形状。
当权值序列较为分散时，哈夫曼树的结构会更加平衡，节点的深度差异较小。
然而，当权值序列的差异较大时，哈夫曼树的结构也会更不平衡，而且可能出现退化现象。
这会导致数据的处理效率降低，需要进行额外的平衡调整。
数据结构：哈夫曼树和哈夫曼编码哈夫曼树哈夫曼树是⼀种最优⼆叉树，其定义是：给定n个权值作为n个叶⼦节点，构造⼀棵⼆叉树，若树的带权路径长度达到最⼩，这样的树就达到最优⼆叉树，也就是哈夫曼树，⽰例图如下：基本概念深⼊学习哈夫曼树前，先了解⼀下基本概念，并以上⾯的哈夫曼树图为例路径：树中⼀个结点到另⼀个结点之间的分⽀序列构成两个结点间的路径。
路径长度：路径中分⽀的数⽬，从根结点到第L层结点的路径长度为L-1。
例如100和80的路径长度为1，50和30的路径长度为2。
结点的权：树中结点的数值，例如100，50那些。
结点带权路径长度：根结点到该结点之间的路径长度与该结点的权的乘积。
如结点20的路径长度为3，该结点的带权路径长度为：3*20 = 60。
树的带权路径长度：所有叶⼦结点的带权路径长度之和，记为WPL。
例如上图树的WPL = 1100 + 280 +320 +310 = 350。
带权路径长度⽐较前⾯说到，哈夫曼树是最优⼆叉树，因为符合哈夫曼树特点的树的带权路径长度⼀定是最⼩的，我们将哈夫曼树和普通的⼆叉树做个⽐较，仍以上图为例，上图的哈夫曼树是结点10，20，50，100组成的⼆叉树，WPL是350，⽤这四个结点组成普通的⼆叉树，结果如下：不难计算，该⼆叉树的WPL = 210 + 220 + 250 + 2100 = 360，明显⽐哈夫曼树⼤，当然⼆叉树的组成结果不唯⼀，但WPL⼀定⽐哈夫曼树⼤。
所以说哈夫曼树是最优⼆叉树。
哈夫曼树的构造现在假定有n个权值，设为w1、w2、…、wn，将这n个权值看成是有n棵树的森林，根据最⼩带权路径长度的原则，我们可以按照下⾯步骤来将森林构造成哈夫曼树：1. 在森林中选出根结点的权值最⼩的两棵树进⾏合并，作为⼀棵新树的左、右⼦树，且新树的根结点权值为其左、右⼦树根结点权值之和；2. 从森林中删除选取的两棵树，并将新树加⼊森林；3. 重复1、2步，直到森林中只剩⼀棵树为⽌，该树即为所求得的哈夫曼树。
主题：数据结构——哈夫曼树和哈夫曼编码权值1. 引言在计算机科学中，对于大规模的数据存储和传输，有效地压缩数据是一项重要的任务。
哈夫曼树和哈夫曼编码权值是一种经典的数据结构和算法，用于实现数据的高效压缩和解压缩。
本文将介绍哈夫曼树和哈夫曼编码权值的概念和原理，探讨其在数据压缩中的应用以及个人对该主题的理解。
2. 哈夫曼树2.1 概念哈夫曼树，又称最优二叉树，是一种具有最小带权路径长度的二叉树。
树的带权路径长度定义为树中所有叶子节点的权值乘以其到根节点的距离，即路径长度的总和。
2.2 构造方法哈夫曼树的构造方法是一种贪心算法。
将所有的权值作为叶子节点构建n棵单节点树。
从这些树中选择两棵权值最小的树合并，得到一棵新的树，新树的根节点的权值为这两棵树根节点权值之和。
重复此过程，直到只剩下一棵树，即为哈夫曼树。
2.3 例子以数据集[7, 5, 2, 4]为例，构造哈夫曼树的过程如下： 1. 初始状态下，将每个权值看作一棵树：7、5、2、4。
2. 选择两棵权值最小的树2和4进行合并，得到一棵新树，根节点的权值为2+4=6。
此时，剩下的树为6、5、7。
3. 选择两棵权值最小的树5和6进行合并，得到一棵新树，根节点的权值为5+6=11。
此时，剩下的树为11、7。
4. 选择两棵权值最小的树7和11进行合并，得到一棵新树，根节点的权值为7+11=18。
得到最终的哈夫曼树。
3. 哈夫曼编码权值3.1 概念哈夫曼编码权值是指在哈夫曼树中，从根节点到每个叶子节点的路径上所经过的边的权值。
对于哈夫曼树中的每个字符（叶子节点），都可以通过从根节点到叶子节点的路径上的边的权值，来进行编码。
3.2 编码方法哈夫曼编码方法的基本原则是将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示。
在哈夫曼树中，根节点到左子树的路径上的边标记为0，到右子树的路径上的边标记为1。
通过遍历哈夫曼树，可以分配每个字符的编码。
课程设计（数据结构）哈夫曼树和哈夫曼编码二○○九年六月二十六日课程设计任务书及成绩评定课题名称表达式求值哈夫曼树和哈夫曼编码Ⅰ、题目的目的和要求：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○○九年六月二十六日目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计及实现代码 (8)第五章调试过程中的问题及系统测试情况 (12)第六章结束语 (13)参考文献 (13)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。
课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。
《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。
这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。
哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。
哈夫曼（huffman）树和哈夫曼编码讨论QQ群：待定哈夫曼树哈夫曼树也叫最优二叉树（哈夫曼树）问题：什么是哈夫曼树？例：将学生的百分制成绩转换为五分制成绩：≥90 分: A，80～89分: B，70～79分: C，60～69分: D，＜60分: E。
if (a < 60){b = 'E';}else if (a < 70) {b = ‘D’;}else if (a<80) {b = ‘C’;}else if (a<90){b = ‘B’;}else {b = ‘A’;}判别树：用于描述分类过程的二叉树。
如果每次输入量都很大，那么应该考虑程序运行的时间如果学生的总成绩数据有10000条，则5％的数据需1 次比较，15％的数据需 2 次比较，40％的数据需 3 次比较，40％的数据需 4 次比较，因此 10000 个数据比较的次数为： 10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次此种形状的二叉树，需要的比较次数是：10000 (3×20％＋2×80％)＝22000次，显然：两种判别树的效率是不一样的。
问题：能不能找到一种效率最高的判别树呢?那就是哈夫曼树回忆树的基本概念和术语路径：若树中存在一个结点序列k1,k2,…,kj，使得ki是ki+1的双亲，则称该结点序列是从k1到kj的一条路径。
路径长度：等于路径上的结点数减1。
结点的权：在许多应用中，常常将树中的结点赋予一个有意义的数，称为该结点的权。
结点的带权路径长度：是指该结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：其中，n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和树根结点到叶子结点ki之间的路径长度。
赫夫曼树（哈夫曼树，huffman树）定义：在权为w1,w2,…,wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。
数据结构c+python代码6：哈夫曼树构造及编码⾸先介绍⼀下什么是哈夫曼树？给定N个权值作为N个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。
哈夫曼树⼜称为最优树.1、路径和路径长度在⼀棵树中，从⼀个结点往下可以达到的孩⼦或孙⼦结点之间的通路，称为路径。
通路中分⽀的数⽬称为路径长度。
若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度哈夫曼树哈夫曼树(3张)若将树中结点赋给⼀个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度树的带权路径长度规定为所有叶⼦结点的带权路径长度之和，记为WPL。
哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶⼦结点。
n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有⼀个结点)；(2) 在森林中选出两个根结点的权值最⼩的树合并，作为⼀棵新树的左、右⼦树，且新树的根结点权值为其左、右⼦树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加⼊森林；(4)重复(2)、(3)步，直到森林中只剩⼀棵树为⽌，该树即为所求得的哈夫曼树。
c代码过程分析构造哈夫曼树算法的实现可以分成两⼤部分：1、初始化：⾸先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1⾄2n-1所有单元中的双亲、左孩⼦、右孩⼦的下标都初始化为0；最后再循环n次，输⼊前n个单元中叶⼦节点的权值。
2、创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。
选择是从当前森林中选择双亲为0且权值最⼩的两个树跟节点是s1和s2；删除是指将节点s1和s2的双亲改为⾮0；合并就是将s1和s2的权值和作为⼀个新节点的权值依次存⼊到数组的第n+1之后的单元中，同时记录这个新节点左孩⼦的下标为s1，右孩⼦的下标为s2。
数据结构实验报告题目哈夫曼编码学生姓名王某某专业班级测控120X班学号U2012XXXXX1 问题描述输入一字符串，以字符串中各字符出现的频数为权值构造哈夫曼编码。
然后输入一0—1序列，根据生成的哈夫曼编码解码序列。
2 算法描述（1）哈夫曼树的表示设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。
用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。
迷宫定义如下：typedef struct{int weight;int lchild;int rchild;int parent;char key;}htnode;typedef htnode hfmt[MAXLEN];（2）对原始字符进行编码初始化哈夫曼树（inithfmt）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。
并显示出每个字符的编码。
1.void inithfmt(hfmt t)//对结构体进行初始化2.void inputweight(hfmt t)//输入函数3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数4.void creathfmt(hfmt t)//创建哈夫曼树的函数5.void phfmnode(hfmt t)//对字符进行初始编码（3）对用户输入的字符进行编码void encoding(hfmt t)//对用户输入的电文进行编码{char r[1000];//用来存储输入的字符串int i,j;printf("\n\n请输入需要编码的字符:");gets(r);printf("编码结果为:");for(j=0;r[j]!='\0';j++)for(i=0;i<n;i++)if(r[j]==t[i].key)hfmtpath(t,i,j);printf("\n");}（4）对用户输入的字符进行编码void decoding(hfmt t)//对用户输入的密文进行译码{char r[100];int i,j,len;j=2*n-2;//j初始从树的根节点开始printf("\n\n请输入需要译码的字符串:"); gets(r);len=strlen(r);printf("译码的结果是:");for(i=0;i<len;i++){if(r[i]=='0'){j=t[j].lchild;if(t[j].lchild==-1){printf("%c",t[j].key);j=2*n-2;}}else if(r[i]=='1'){j=t[j].rchild;if(t[j].rchild==-1){printf("%c",t[j].key); j=2*n-2;}}}printf("\n\n");}3 程序设计流程图4 运行测试1.用户输入字符串，以回车键作为结束2.对字符统计打印统计结果、编码表和编码结果3.对一串数据解码4.统计编码前后的数据大小，计算压缩率5 实验收获代码编写完会有很多与预期不同的结果，耐心调试，修改代码，开始写代码的时候就认真的写，在调试时找出逻辑问题比较困难，做到一步到位。
课程设计（数据结构）课程设计任务书及成绩评定课题名称表达式求值哈夫曼树和哈夫曼编码Ⅰ、题目的目的和要求：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计及实现代码 (5)第五章调试过程中的问题及系统测试情况 (9)第六章结束语 (10)参考文献 (11)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。
课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。
《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。
这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。
哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。
功能：表达式求值以栈为存储结构，实现输入的表达式的求值；哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。
利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。
第二章系统分析一、表达式求值根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式所有指数不相同的项，则分别复抄到“和多项式”中去。
在此，安装上述抽象数据类型Polynomial中基本操作的定义，“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。
其运算规则如下：假设指着qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针qa所指结点的指数值<指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去；②指针qa所指结点的指数值>指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；③指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。
二、哈夫曼树和哈夫曼编码建立哈夫曼树的算法思想是：1)根据给定的几个权值{w1，w2，……，w n}构成n颗二叉树的集合F={T1，T2，……，T n}，其中每颗二叉树T i中只有一个带权为w i的根结点，其左右子树均空。
2)在F中选取两棵根结点的权值最小作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3)在F中删除这两棵树，同时将新得到的二叉树加入F中。
4)重复（2）和（3），直到F只含一棵树为止。
这棵树便是哈夫曼树。
第三章概要设计一、表达式求值：ADT Polynomial{数据对象：D={a[i]|a[i]∈Elemset,i=1,2,…,n, n>=0TerSet中的咩歌元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,…,n}基本操作：CreatPolyn（&P，m）操作结果：输入m项的系数和指数，建立一元多项式P。
Destroystack(&s)初始条件：一元多项式P已存在。
操作结果：销毁一元多项式P。
PrintPolyn（P）初始条件：一元多项式P已存在。
操作结果：打印输出一元多项式P。
PolynLength（P）初始条件：一元多项式P已存在。
操作结果：返回一元多项式P中的项数。
AddPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。
SubtrantPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相减运算，即：Pa=Pa-Pb,并销毁一元多项式Pb。
MultiplyPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb。
}ADT Polynomial以下算法描述了这个求值过程。
int cmp(term a, term b);//依a的指数值<(或=)(或>)b的指数值，分别返回-1、0、+1void CreatPolyn(polynomail&p,int m){//输入m项的系数和指数，建立表示一元多项式的有序链表pInitList(p); h =GetHead(p);e.coef =0.0; e.expn = -1; SetCurElem(h,e); //设置头结点的数据元素for (i=1; i<=m ; ++i){ //依次输入m个非零项scanf (e.coef, e.expn);if (!LocateElem(P,e,q(*cmp)())){ //当前链表中不存在该指数项if(MakeNode(s,e)) InsFirst(q,s); //生成结点并插入链表}} } //CreatPolynvoid AddPolyn(polynomai &Pa, polynomai &Pb){//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”。
ha =GetHead(Pa); hb =GetHead(Pb);//ha 和hb分别指向Pa和Pb中当前结点while(qa&&qb){//qa和qb均非空a=GetCurElem(qa); b=GetCurElem(qb);//a和b为两表中当前比较元素switch(*cmp(a,b)) {case -1://多项式PA中当前结点的指数值小ha=qa; qa=NextPos(pa,qa);break;case 0: //两者的指数值相等sum=a.coef+b.coef;if(sum!=0.0){//修改多项式PA中当前结点的系数值SetCurElem(qa,sum);ha=qa;}else{// 删除多项式PA中当前结点DelFirst(ha,qa); FreeNode(qa);}DelFirst(hb,qb); FreeNode(qb); qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;case 1: //多项式PB中当前结点的指数值小DelFirst(hb,qb); InsFirst(ha,qb);qb=Nextpos(Pb,hb); ha=NextPos(Pa,ha);break;}//switch}//whileif(!ListEmpty(Pb)) Append(Pa,qb); //链接pb中剩余结点FreeNode(Pb): //释放Pb的头结点}//AddPolyn二、哈夫曼树及哈夫曼编码求哈夫曼树及编码的算法如下：Void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n){//w存放n个字符的权值（均>0），构造哈夫曼树HT，并求n个字符的哈夫曼编码HC。
if(n<=1) return; m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用。
for(p=HT+1,i=1;i<=n,++i,++p,++w) *p={*w,0,0,0};for(;i<=m,++i,++p,) *p={0,0,0,0};for(i=n+1;i<=m,++i,){//建哈夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。
Select(HT,i-1,s1,s2);HT[s1].parent=I; HT[s2].parent=i;HT[i].lchild=s1; HT[i].rchild=s2;HT[i].weight= HT[s1].weight+ HT[s2].weight; }//从叶子到根逆向求每个字符的哈夫曼编码。
HC=(HaffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量cd=(char *)malloc(n*sizeof(char *));//分配求编码的工作空间cd[n-1]=”\0”; //编码结束符。
for(i=1;i<=n;++i){ //逐个字符求哈夫曼编码start=n-1; //编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c) cd[--start]=”0”;eles cd[--start]=”1”;HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]); //从cd复制编码（串）到HC }}free(cd); //释放工作空间}//HuffmanCoding第四章详细设计及实现代码表达式求值的源代码：#include "stdio.h"#include "stdlib.h"typedef struct polynode{int cofe;int exp;struct polynode *next;}PNode;PNode *Creat_Linkst(int n){PNode *head,*p,*s;int i;head=(PNode*)malloc(sizeof(PNode));head->next=NULL;p=head;printf("enter cofe,exp:\n");for(i=1;i<=n;++i){s=(PNode *)malloc(sizeof(PNode));scanf("%d,%d",&s->cofe,&s->exp);s->next=NULL;p->next=s;p=s;}return(head);}void polyADD(PNode *pa,PNode *pb){PNode *pre,*qa,*qb,*q;int sum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb){if(qa->exp==qb->exp){sum=qa->cofe+qb->cofe;if(sum){qa->cofe=sum;pre=qa;}else{pre->next=qa->next;free(qa);}qa=pre->next;q=qb;qb=qb->next;free(q);}else{if(qa->exp>qb->exp){pre=qa;qa=qa->next;}else{pre->next=qb;pre=qb;qb=qb->next;pre->next=qa;}}}if(qb)pre->next=qb;free(pb);}void print_Linkst(PNode *H){PNode *p;p=H->next;while(p){printf("%dx^%d+",p->cofe,p->exp);p=p->next;} if(p->exp)printf("%dx^%d\n",p->cofe,p->exp);else printf("%d\n",p->cofe);}main(){PNode *HA,*HB;int la,lb;printf("enter la,lb:");scanf("%d,%d",&la,&lb);printf("\ncreat HA\n");HA=Creat_Linkst(la);printf("A(x)=");print_Linkst(HA);printf("\ncreat HB\n");HB=Creat_Linkst(lb);printf("B(x)=");print_Linkst(HB);polyADD(HA,HB);printf("\nA(x)=");}哈夫曼树和哈夫曼编码的程序：#define maxvalue 10000#define maxnodenumber 100#define maxbit 10typedef struct{int weight;int parent,lchild,rchild;}htnode;typedef struct{int bit[maxbit];int start;}hcodetype;typedef htnode *huffmantree;htnode ht[maxnodenumber];hcodetype cd[maxnodenumber];void crthuffmantree(int n){int i,j,m1,m2,k1,k2;for(i=0;i<2*n-1;i++){ht[i].weight=0;ht[i].parent=1;ht[i].lchild=1;ht[i].rchild=1;}printf("shuruyizuweight:\n");for(i=0;i<n;i++)scanf("%d",&ht[i].weight);printf("i weight parent lchild rchild\n");for(i=0;i<n-1;i++){m1=maxvalue;m2=maxvalue;k1=0;k2=0;for(j=0;j<n+i;j++)if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}if(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}ht[k1].parent=n+i;ht[k2].parent=n+i;ht[n+i].weight=ht[k1].weight+ht[k2].weight;ht[n+i].lchild=k1;ht[n+i].rchild=k2;}for(i=0;i<2*n-1;i++){printf("%d %5d %5d %5d %5d\n",i,ht[i].weight,ht[i].parent,ht[i].l child,ht[i].rchild);printf("\n");}}/*crthuffmantree*/void gethuffmancode(htnode ht[],int n){int i,j,c,p;printf("code:%d\n",n);for(i=0;i<n;i++){c=i;j=maxbit;do{j--;p=ht[c].parent;if(ht[p].lchild==c)cd[i].bit[j]=0;elsecd[i].bit[j]=1;c=p;}while(p!=1);cd[i].start=j+1;/*根也置1，所以编码从下一位置始*/ }for(i=0;i<n;i++){printf("%d:",ht[i].weight);{for(j=cd[i].start;j<maxbit;j++)printf("%d",cd[i].bit[j]);printf("------i:%d,start:%d",i,cd[i].start);printf("\n");}}}/*gethuffmancode*/main(){int n;printf("shuru n:\n");scanf("%d",&n);crthuffmantree(n);printf("hufmancode:\n");gethuffmancode(ht,n);}第五章调试过程中的问题及系统测试情况在输入过程中，一定要细心。
