数据结构课程设计-赫夫曼编码

《数据结构课程设计-赫夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、软件学院课程设计报告书课程名称数据结构设计题目赫夫曼编码系统专业班级学号姓名指导教师2012年1月27目录1设计时间32设计目的33设计任务34设计内容34.1需求分析34.2总体设计44.3详细设计64.4测试与分析104.4.1测试104.4.2分析114.5附录115总结与展望16参考文献18271设计时间2012年1月2日到2012年1月6日2设计目的1)巩固赫夫曼树的算法；2)实现赫夫曼树的建立；3)赫夫曼编码的生成；4)赫夫曼文件的译码；3设计任务设计时间一周，对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。电报通信是传递文字的二进

2、制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。设计实现的功能：(1)赫夫曼树的建立；(2)赫夫曼编码的生成；(3)编码文件的译码。4设计内容4.1需求分析哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。称为赫夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵

3、赫夫曼树。哈弗曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码

4、，输入二进制代码时可以编译成字符串。假设输入字符‘BCD’编码成二进制代码应与特殊的编码表上的二进制编码相同输出应为270010100000，若出现其他情况的结果，错误；假设输入二进制代码0010100000，则编译成字符串正确应为‘BCD’，若出先其他情况的结果，错误。4.2总体设计（1）、程序中用到的所有抽象数据类型的定义预定义常量#defineN50#defineM2*N-1#defineMAXSIZE100输入输出语句输入语句scanf([格式串]，变量1，变量2，。。。。。变量n);输出语句printf([格式串]，变量1，变量2，。。。。。变量n);赋值语句变量名=表达式

5、；循环语句for(赋初值表达式序列；条件；修改表达式序列)结束语句return表达式；类型定义Typedefintstatus（2）、赫夫曼编码要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：typedefstruct{chara[N];intstart;}HCode;进行赫夫曼编码译码之前建立赫夫曼二叉树，新建立赫夫曼树，建立赫夫曼编码，进行主函数时，输入A到F所有的字符，并输入其权值，将其进行编码；将data的权值赋给ht,判断结点是否大于1，输出根结点及权值。比较i<2*N-1;若是调用调用SELECT函数算出算出父亲结点然后输出两子结点及

6、父亲结点。27开始N>1将data和weigth赋给HT输出根结点和权值调用SELECT函数计算根结点函数双亲为两结点之和输出两子结点和双亲结点是否为根结点？左子树为空此时编码为0I<2*N-1?I++编码为1结束否否否右子树为空是是否否是是是图4.2关系流程图274.3详细设计（1）、主函数voidmain(){intn=6,i;charstr[]={'A','B','C','D','E','F'};//初始化intb[]={3,7,4,5,9,1};//初始化HTNodeHT[M];//建立结构体HCodehcd[N];//建立结构体for(i=0;i

7、数据存入HT结构体中{ht[i].data=str[i];ht[i].weight=b[i];}CreateHffumanTree(HT,n);CreateHffumanCode(HT,hcd,n);DipHffumanCode(HT,hcd,n);printf("请输入要进行编码的字符串(以#结束):");HffumanCode(HT,hcd,n);printf("请输入编码(以#结束):");HffumanCodeTranslate(HT,hc