《数据结构课程设计-赫夫曼编码的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计-赫夫曼编码的实现（37页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告赫夫曼编码的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目赫夫曼编码的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩
2、指导教师评语： 日期： 年 月 日目 录1课程设计目标与任务11.1课程设计目的11.2 课程设计任务11.3 赫夫曼编码介绍22 分析与设计32.1 题目需求分析32.2 存储结构设计32.3 算法描述32.4 程序结构图73 程序清单84 测试144.1 测试数据144.2 测试结果分析145 总结16参考文献171课程设计目标与任务1.1课程设计目的在当今信息时代，信息技术已成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径、在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为
3、计算机上处理的数据。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高思维能力，促进综合应用能力和专业素质的提高。通过此次课程设计主要达到一下目的：（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发工程的问题分析，系统设计，程序编码，测试等基本方法和技能；（3）提高综合运用所学理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计任务设计赫夫曼编码的相关函数库，以便在程序设计中调用，要求：（1）任意输入
4、100个英文字母，根据每个字母的使用频率，构造赫夫曼树并输出每个字母的赫夫曼编码。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 赫夫曼编码介绍赫夫曼编码是一种编码方式，哈夫曼编码是一种编码方式，以赫夫曼树即最二叉树，带权路径长度最小的二叉树，经常应用于数据压缩，称为赫夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为WiLi。若将此对应到二叉树上，W为叶结点的权，Li为根结点到叶结点的路径长度。那么
5、，WiLi恰好为二叉树上带权路径长度。因此,设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树。赫夫曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛。利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1
6、”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。2 分析与设计2.1 题目需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的的数据压缩技术。本设计要求对任意输入100个英文字母，根据每个字母的使用频率，构造赫夫曼树并输出每个字母的赫夫曼编码。2.2 存储结构设计对输入的100个字符，其中每个字符的信息都用一个结构体存储，包含结点值、权值、双亲结点、左孩子结点、右孩子结点等数据。本次课程利用动态分配数组存储赫夫曼树。赫夫曼编码的存储结构描述为：#include #include #
7、include typedef struct /赫夫曼树的结构体 char ch; int weight; /权值 int parent,lchild,rchild; htnode,*hfmtree; 2.3 算法描述进行赫夫曼编码译码之前建立赫夫曼二叉树，新建立赫夫曼树，建立赫夫曼编码，进行主函数时，输入100个字符，并输入其权值，将其进行编码；将str的权值赋给ht，判断结点是否大于1，输出根结点及权值。比较i2*N-1;若是调用SELECT函数算出父亲结点然后输出字符编码和译码。（1）赫夫曼树结构体（初始化赫夫曼树，处理InputHuffman函数得到的数据，按照赫夫曼规则建立二叉树。）
8、：void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC int i,start,c,f,m,w; int p1,p2; char *cd,z; if(n=1) （2）根据提示输入字符，对输入字符进行初始化，即初始化赫夫曼树：if(choice=I|choice=i) /初始化赫夫曼树 coutn; hfmcoding(HT,HC,n); for(i=1;i=n;+i) for(i=1;i=n;i+) output_file(HTi.chHCi); output_file.close(); cout赫夫曼树
9、已经创建完毕，并且已经放入hfmTree.txt文件中!endl; （3）主函数（利用已建立好的赫夫曼树对文件中的正文进行编码，如不存在则从文件hfmtree中读入，然后将结果存入文件codefile.txt中，如果文件中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的赫夫曼编码存储到CodeFile中。）：int main() char code100,h100,hl100; int n,i,j,k,l; ifstream input_file; /文件输入输出流ofstream output_file; char choice,s
10、tr100; hfmtree HT; hfmcode HC; （4）所实现的功能：a.赫夫曼编码（对所输入字符进行编码，即压缩过程）if(choice=E|choice=e) /进行编码,并将字符放入ToBeTran.txt,码值放入CodeFile.txt中printf(请输入字符：); gets(str); output_file.close(); coutn; coutcode; cout编码码值为：codeendl; input_file.close(); b.赫夫曼译码（读取文件中的编码，并与原先生成的赫夫曼编码表进行比较，遇到相等时，即读取其对应的字符存入一个新串中，即解压过程）i
11、f(choice=D|choice=d) /读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中 input_file.open(CodeFile.txt); if(!input_file) coutcant open file!endl; return 1; input_file.close(); cout译码结束，字符已经存入Textfile.txt文件中！1 否 是输出根结点和权值I2*N-1 是 计算根结点函数i+ 否调用SEELECT函数双亲为两结点之和是否为根结点左子树为空右子树为空 否 是编码为1此时编码为0 否结束 图2-1程序结构图3 程序清单#include #include #include #include #include typedef struct /赫夫曼树的结构体char ch; int weight; /权值int parent,lchild,rchild; htnode,*hfmtree; typedef char *hfmcode; void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数,选出HT树到a为止，权值最小且parent为的2个节点 int i,j,x,y; for(j=
