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

软 件 学 院 课程设计报告书 课程名称 数据结构 设计题目 赫夫曼编码系统 专业班级 学 号 姓 名 指导教师 2012 年月 1 设计时间 3 2 设计目的 3 3设计任务 3 4 设计内容 3 4.1需求分析 3 4.2总体设计 4 4.3详细设计 6 4.4测试与分析 10 4.4.1测试 10 4.4.2分析 11 4.5 附录 11 5 总结与展望 16 参考文献 18 1 设计时间 2012年1月2日到2012年1月6日 2 设计目的 巩固赫夫曼树的算法； 实现赫夫曼树的建立； 赫夫曼编码的生成； 赫夫曼文件的译码； 3设计任务 设计时间一周，对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。 4 设计内容 4.1需求分析 哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。称为赫夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树哈弗曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 假设输入字符‘ BCD ’编码成二进制代码应与特殊的编码表上的二进制编码相同输出应0010100000，若出其他情况的结果，错误；假设输入二进制代码0010100000，则编译成字符串正确应为‘ BCD ’， 若出先其他情况的结果，错误。设计#define N 50 #define M 2*N-1 #define MAXSIZE 100 输入输出语句 输入语句 scanf ([格式串]，变量1，变量2，。。。。。变量n); 输出语句 printf([格式串]，变量1，变量2，。。。。。变量n); 赋值语句 变量名=表达式； 循环语句 for(赋初值表达式序列；条件；修改表达式序列) 结束语句 return表达式； 类型定义Typedef int status 赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedef struct { char a[N]; int start; }HCode; 4.3详细设计主函数 void main() { int n=6,i; char str[]={A,B,C,D,E,F}; //初始化 int b[]={3,7,4,5,9,1}; //初始化 HTNode [M]; //建立结构体 HCode hcd[N]; //建立结构体 for (i=0;in;i++) //把初始化的数据存入结构体中 {