1、课 程 设 计 说 明 书课程名称： 数据结构与算法 设计题目： 哈夫曼编译码器 院 系： 计算机科学与信息工程学院 学生姓名： 刘文杰 学 号： 16031210229 专业班级： 软件工程 16-2 指导教师： 孙高飞 2017 年 12 月 11 日设计题目 哈夫曼编译码器 限定人数 3问题描述采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于 5000 字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。设字符集及频度如下表：字符 空格 A B C D
2、E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度 57 63 15 1 48 51 80 23 8 18 1 16 1基本要求与说明1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码2、读取文本文件，并对文件内容编码，生成编码文件3、对编码文件进行译码，获得恢复文件4、比较恢复文件和原文件是否相同。课 程 设 计 任 务 书设计题目 哈夫曼编译码器学生姓名 刘文杰 所在院系 计算机科学与信息工程学院 专业、年级、 班 软件工程 16-2设计要求：1.根据
3、哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码。2.读取文本文件，并对文件内容编码，生成编码文件。3.对编码文件进行译码，获得恢复文件。4.比较恢复文件和原文件是否相同。学生应完成的工作：1. 学生应认真学习参考程序，理解每个文件、每个函数以及各个变量的作用和意义。在此基础上进一步改进程序，最后正确地运行程序。2. 对程序进行测试，设计详细的测试计划，然后根据测试计划设计测试用例，对程序进行测试。测试时应注意对各种边缘情况进行测试。3. 完成课程设计报告。参考文献阅读：1. 严蔚敏数据结构（C 语言版） 清华大学出版社，20112. 谭浩强C 程序设计（第四版） 清华大学出版，20103.
4、蒋立翔C+程序设计技能百练 M中国铁道出版社，2004工作计划：1. 小组审题，查阅资料，进行设计前的必要资料准备（3 天） 。2. 把程序完整运行出来（4 天） 。3. 增加改进程序（3 天） 。4. 写课程设计报告（3 天） 。5. 提交课程设计报告及答辩（1 天）任务下达日期：2017 年 12 月 01 日 任务完成日期：2017 年 12 月 19 日指导教师（签名）： 学生（签名）： 哈夫曼编译码器摘 要：采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于 5000 字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本
5、文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。关键词：构建哈夫曼树 哈弗曼编码 哈夫曼译码 字符串编码 打印编码函数目 录1.设计背景 .11.1 哈夫曼树的介绍 .11.2 设计的作用、目的 .11.3 设计任务及要求 .22.设计方案 .22.1 实验内容 .22.2 操作思路 .22.3 基本操作 .33. 方案实施 .43.1 C 语言编程 .43.2 程序介绍 .123.3 程序流程图以及说明 .13图 3 主程序流程图 .134. 结果与结论 .144.1 程序运行结果 .144.2 总结 .165. 收获与致谢 .176. 参考文献 .1711.设计背景1
6、.1 哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树或者赫夫曼树，它是最优二叉树。定义：给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。 (01) 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1。 (02) 结点的权及带权路径长度定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
7、 (03) 树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。1.2 设计的作用、目的通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过课程设计各环节的实践，应达到如下要求：1理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2根
8、据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树；3掌握哈夫曼编码的优缺点；24通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.3 设计任务及要求1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；2.
9、设计方案2.1 实验内容假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、wn，哈夫曼树的构造规则为：1.将 w1、w2、，wn 看成是有 n 棵树的森林(每棵树仅有一个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林； 4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。2.2 操作思路以5,6,7,8,15为例，来构造一棵哈夫曼树。第 1 步：创建森林，森林包括 5 棵树，这 5
10、棵树的权值分别是 5,6,7,8,15。 3第 2 步：在森林中，选择根节点权值最小的两棵树(5 和 6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是 11。 然后，将“树 5“和“树 6“从森林中删除，并将新的树(树 11)添加到森林中。 第 3 步：在森林中，选择根节点权值最小的两棵树(7 和 8)来进行合并。得到的新树的权值是 15。 然后，将“树 7“和“树 8“从森林中删除，并将新的树(树 15)添加到森林中。第 4 步：在森林中，选择根节点权值最小的两棵树(11 和 15)来进行合
11、并。得到的新树的权值是 26。 然后，将“树 11“和“树 15“从森林中删除，并将新的树(树 26)添加到森林中。 第 5 步：在森林中，选择根节点权值最小的两棵树(15 和 26)来进行合并。得到的新树的权值是 41。 然后，将“树 15“和“树 26“从森林中删除，并将新的树(树 41)添加到森林中。 此时，森林中只有一棵树(树 41)。这棵树就是我们需要的哈夫曼树！3. 方案实施3.1 C 语言编程 #include #include #include #define MAX 99999#define N 27 /定义最多节点个数#define M 2*N - 1 /中间节点个数typ
12、edef struct int weight;int parent;int LChild;int RChild;HTNode,HuffmanTreeM+1;/因为零号单元不使用typedef char * HuffmanCodeN+1;4HuffmanCode co;/创建全局变量用于储存HuffmanCodechar CHN;int weightN = 64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;HuffmanTree ht;char word30;/全局变量用于储存键入的内容void In
13、it_CH()int i;CH26 = ;CH0 = A;for(i=1;i26;i+)CHi = A+i;for(i=0;i27;i+)printf(“%c “,CHi);void select(int *sr,int *sl,int n)int i,point;point = MAX;for(i=0;in;i+)if(hti+1.weightpoint /*sr是最小的point = ht*sr.weight;ht*sr.parent = 1;point = MAX;for(i=0;in;i+)if(hti+1.weightpoint /*sl是第二小point = ht*sl.weigh
14、t;ht*sl.parent = 1;void InitHuffmanCode()int i,sr,sl;for(i=1;i=N;i+)5hti.weight = weighti-1;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;for(i=N+1;i=M;i+)hti.weight = 0;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;printf(“-初始化完成-n“);for(i=N+1;i=M;i+)select(hti.weight = htsr.weight + htsl.weight;htsr.parent = i;htsl.parent = i;hti.LChild = sr;hti.RChild = sl;for(i=1;i=M;i+)printf(“%d %dn“,hti.parent,i);void CreateHuffmanCode()FILE * trans;int i,start,p,c;char *cd;cd = (char *)malloc(N*sizeof(char);cdN-1 = 0;for(i=1;i=N;i+)start = N-1;c = i;p = hti.parent;while(p)-start;if(htp.LChild = c)
