(数据结构课程设计之赫夫曼编码的应用.docVIP

学生课程设计 题 目： 赫夫曼编码的应用 学生姓名： 赵旺 学 号：124090102042 所在院(系)： 计算机与信息科学学院 专 业： 2012级计算机科学与技术 班 级： (二） 指导教师： 冯韵 2014年9月24日 目 录 一、概述 1 二、系统分析 1 三、概要设计 2 四、详细设计 4 4.1 赫夫曼树的建立 4 4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 5 4.1.2 统计字符串中字符的种类以及各类字符的个数 7 4.1.3构造赫夫曼树 8 4.2赫夫曼编码 10 4.2.1赫夫曼编码算法 10 4.2.2建立正文的编码文件 11 4.3代码文件的译码 12 五、运行与测试 14 六、总结与心得 14 参考文献 15 附录 15 一、概述 本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出 电文字符串。 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 二、系统分析 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。 假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。那么，∑W i L i 恰好为二叉 树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。 根据设计要求和分析，要实现设计，必须实现以下方面的功能： 赫夫曼树的建立； 赫夫曼编码的生成； 编码文件的译码； 三、概要设计 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。 void main() void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)//编码部分 char *decode(HuffmanCode Hc)//译码 void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]) //生成Huffman树 void select(HufmanTree HT,int k,int s1,int s2) //找寻parent为0,权最小的两个节点 其流程图如下： 四、详细设计 4.1 赫夫曼树的建立 由赫夫曼算法的定义可知，初始森林中共有 n 棵只含根节点的二叉树。算法的第二步是：将当前森林 中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新 节点。显然要进行 n-1 次合并，所以共产生 n-1 个新节点，它们都是具有两个孩子分支结点。由此可 知，必威体育精装版求得的赫夫曼树中一共有2n-1 个结点，其中n 个结点是初始森林的n 个孤立结点。并且赫夫 曼树中没有度数为1 的分支结点。我们可用一个大小为2n-1 的一维数组来存储赫夫曼树中的结点。因 此，赫夫曼树的存储结构描述为： #define n 100 #define m 2*n-1 typedef struct{ int weight; int lchild,rchild,parent; }HTNode; T typedef HTNode HuffmanTree[m+1]; 4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 void select(HuffmanTree T,int k,int