哈夫曼编码与译码的实现 .pdf

《哈夫曼编码与译码的实现 .pdf》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码的实现 .pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课程设计评阅书题目哈夫曼编码与译码的实现学生姓名万永馨学号1021024016 指导教师评语及成绩指导教师签名：年月日答辩评语及成绩答辩教师签名：年月日教研室意见总成绩：室主任签名：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 28 页 - - - - - - - - - 20112012 学年第一学期专业：信息管理与信息系统学号： 1021024016 姓名：万永馨课程设计名称：数据结构课程设计设计题目：哈夫曼编码与译码的实现完成期限：自 2012 年

2、2 月 20 日至 2012 年 3 月 2 日共 2 周设计依据、要求及主要内容（可另加附页）：该设计题目将按以下要求完成：哈夫曼编码与译码是信息传输中应用的经典算法，运用 C或 VC+ 结合数据结构等基础知识，按以下要求编程实现各种进制的转换。任务要求： 1）阐述设计思想,画出流程图 ;2 ）需要对哈夫曼编码/ 译码的相关原理有所了解，设计数据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能；3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要求完成课程设计说明书。设计要求 : 1）问题分析和任务定义：根据设计题目的

3、要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结

4、构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入后续阶段的工作。设计工作结束，经指导老师验收合

5、格后将设计说明书装订，并答辩。指导教师（签字）：教研室主任（签字）：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 28 页 - - - - - - - - - 批准日期：年月日摘 要在当今信息爆炸时代，如何采取有效的数据压缩技术来节省数据文件的储存空间越来越引起人们的重视。本次课程设计的实验题目为哈夫曼编码与译码的实现。利用哈夫曼树求得的用于通讯的二进制编码称为哈弗曼编码。通常我们将文字转化为二进制称为编码，而将二进制转化为文字称为译码。此次程序就是将一个简单的文件进行

6、编码转化为二进制数存入文件并进行译码进而输出。而将文件转化为二进制编码运用哈夫曼树的相关知识可以有效的节省存储空间与时间。关键词 ：哈夫曼树 ; 哈夫曼树的编码; 哈夫曼树的译码; 哈夫曼树初始化; 哈夫曼树的建立开发工具： visual C+ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 28 页 - - - - - - - - - 4 目录1. 引 言. . 52. 课题描述 . . 63. 程序设计 . . 73.1 实验目的与基本要求 . 73.2 部分函数介绍

7、 . 73.3 主要模块程序流程图 . 84 系统实现 . . 124.1 主函数（菜单函数）. 124.2 建立 HuffmanTree . 124.3生成 Huffman 编码并写入文件. . 144.4对文件哈夫曼译码 .txt 进行译码译码. . 155 系统调试 . . 16附录源程序 . . 22名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 28 页 - - - - - - - - - 5 1.引 言在课程设计过程中，我们四个人一组选择一个课题，认真研究，根

8、据课堂讲授内容，借助书本， 自己动手实践。 这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是， 我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能

9、够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样， 我们的综合素质才会有好的提高。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 28 页 - - - - - - - - - 6 2.课题描述课题：哈夫曼编码与译码的实现问题描述：对文件哈夫曼.txt中的字符串进行编译，统计其中的字符种类、个数作为权值。1. 从 D盘的数据结构课

10、程设计文件夹中建立哈夫曼.txt文件里读出文章（必须大写）；2. 运用 jsp 函数统计这篇文章中的每个字符出现的次数；3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入程序，然后对另一文件中的编码编码进行破译。具体介绍： 在本课题中， 我们在硬盘D盘中预先建立一个哈夫曼 .txt 文档， 在里面编辑一篇文章 ( 大写 ) 。 然后运行程序， 调用 fileopen()函数读出该文章， 显示在界面； 再调用 jsq()函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次

11、数作为权值，调用ChuffmanTree()函数构建哈夫曼树；并调用print1()和 print2()函数将哈夫曼的存储结构的初态和终态进行输出。然后哈夫曼树进行编码， 再对另一文件哈夫曼译码 .txt 编码进行译码，再输出至界面。至此，整个工作就完成了。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 28 页 - - - - - - - - - 7 3.程序设计3.1 实验目的与基本要求利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间， 降低传输成本。这

12、要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/ 译码系统。试为这样的信息收发站编写一个赫夫曼码的编/ 译码系统。一个完整的系统应具有以下功能：(1) 初始化（ Initialization ） 。从文件哈夫曼 .txt 读入字符集 ,，统计字母个数作为权值，建立赫夫曼树。(2) 编码（ Encoding） 。利用已建好的赫夫曼树（如不在内存，则从文件中读入），对哈夫曼树进行编码，然后将结果存入文件哈夫曼译码 .txt 中。(3) 译码（ Decoding） 。利用已建好的赫夫曼树将文件哈

13、夫曼译码 .txt 中的代码进行译码3.2 部分函数介绍从硬盘读取字符串fileopen(参数 ) 建立 HuffmanTree 通过三个函数来实现：void select(参数 ) 说明：在ht1.k中选择 parent为 0 且权值最小的两个根结点的算法int jsq(参数 ) 说明：统计字符串中各种字母的个数以及字符的种类void ChuffmanTree() 说明：构造哈夫曼树输出哈夫曼树的存储结构的初态和终态分别调用print1()和 print2()来实现void print1(参数 ) 说明：输出哈夫曼树的初态void print2(参数 ) 说明：输出哈夫曼树的终态哈夫曼编码和

14、译码void HuffmanEncoding(参数 ) 说明：哈夫曼编码char*decode( 参数 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 28 页 - - - - - - - - - 8 说明：哈夫曼译码3.3 主要模块程序流程图主函数流程图：图 3.1 流程图注释：图 3.1 比较简单， 由该图可知主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基开始打开文件统计字符个

15、数哈夫曼树的初始化哈夫曼树的建立哈夫曼树的编码哈夫曼树的译码结束NY名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 28 页 - - - - - - - - - 9 础上对其进行编码，编码之后才是译码。最后输出结束。构造哈夫曼树：图 3.2 开始i=1,s1,s2HTi.weight=cntii+i=numi=num+1调用 select 函数HTi.weight=HTs1.weight+HTs2.weighti0Tp.lchild=ccd-start=0 cd-star

16、t=1 c=pHi.bits=cdstarti+inumHi.bits结束YNNYNY图 3.3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 28 页 - - - - - - - - - 11 流程图解释：流程图 3.3 表示哈夫曼编码情况。首先初始化，Cd-start=0,start=num。然后从首地址开始进行比较，找节点的父母地址然后看节点为父母地址的左孩子是的话为0, 反之为1 . 依次开始上溯。将编码存入Hi.bits。哈夫曼译码：开始打开文件？cdi=f

17、getc(fp)strk=HCj.chstrcmp(HCj.bits,cd)=0p=stri=0,cjs=0j+,k+,cjs=1return(p)结束inum & cjs=0 & !feof(fp)i+j=numj=1!feof(fp)=1NYYNYNYYYN图 3.4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 28 页 - - - - - - - - - 12 流程图解释：流程图 3.4 表示哈夫曼译码情况。首先讲哈夫曼编码存入的文件打开，将哈夫曼编码导出。然

18、后将文件中读出的字符与哈夫曼编码cd 进行比较strcmp(HCj.bits,cd=0，相等的话开始译出strk=HCj.ch。4 系统实现各模块关键代码及算法的解释：4.1 主函数（菜单函数）主函数相对简单，只需了解顺序，依次调用即可。这里不做解释4.2 建立 HuffmanTree 代码解释： 该函数为在ht1.k中选择 parent为 0 且权值最小的两个根结点的算法，其序号为s1 和 s2。void select(HuffmanTree T,int k,int &s1,int &s2) int i,j; int min1=32767; for(i=1;i=k;i+) if(Ti.wei

19、ghtmin1 &Ti.parent=0) j=i;min1=Ti.weight; s1=j;min1=32767; for (i=1;i=k;i+) if(Ti.weightmin1 & Ti.parent=0 & i!=s1) j=i;min1=Ti.weight; s2=j; 代码解释：下面函数用来统计字符串中各种字母的个数以及字符的种类。当字符在A 和 z之间时即被计数，并用strj保存字母到数组中，用cntj统计每种字符个数。j 返回总名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

20、 - 第 12 页，共 28 页 - - - - - - - - - 13 共读取的字符数目。int jsq(char *s,int cnt,char str) int i,j,k; char *p; int temp53; for(i=1;i=A&*p=z) k=*p-64; tempk+; /统计各种字符的个数for(i=1,j=0;i=52;+i) if(tempi!=0 ) j+; strj=i+64; /送对应的字母到数组中cntj=tempi; /存入对应字母的权值 return j; /j是输入字母总数 代码解释：下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树，然后输入前面统计

21、的各结点的权值，用for 循环来构造哈夫曼树。void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) int i,s1,s2; for(i=1;i=2*num-1;i+)/初始化 HT ， 2*num-1 是指哈夫曼/ 所有的结点数目 HTi.lchild=0;HTi.rchild=0; HTi.parent=0;HTi.weight=0; for(i=1;i=num;i+) /输入 num个叶结点的权值HTi.weight=cnti; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

22、- - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 28 页 - - - - - - - - - 14 for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / 在 ht1.k中选择 parent为 0 且权值最小/ 的两个根结点, 其序号为s1 和 s2,i为双亲for(i=0;i=num;i+) /输入字符集的中字符HCi

23、.ch=stri; /字符的种类i=1;while(i=num) printf(字符 %c次数 :%dn,HCi.ch,cnti+); /输出统计的情况4.3 生成 Huffman 编码并写入文件代码解释：根据哈夫曼树T 求哈夫曼编码H。 void HuffmanEncoding(HuffmanTree T,HuffmanCode H) int c,p,i; /c和 p 分别指示 t 中孩子和双亲char cdn; /临时存放编码串int start; /指示码在cd 中的起始位置cdnum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至上溯到tc是树根为止 cd-s

24、tart=(Tp.lchild=c) ? 0 : 1; c=p; /若 tc是 tp的左孩子/ 则生成 0; 否则生成底码strcpy(Hi.bits,&cdstart); Hi.len=num-start; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 28 页 - - - - - - - - - 15 void coding(HuffmanCode HC ,char *str) /对 str所代表的字符串进行编码并写入文件int i,j; FILE *fp; 数据

25、结构课程设计哈夫曼译码 .txt,w); while(*str) for(i=1;i=num;i+) for(j=0;jHCi.len;j+) if(HCi.ch=*str) fputc(HCi.bitsj,fp);/将编码写入文件 str+; fclose(fp); 4.4 对文件哈夫曼译码 .txt 进行译码译码代码解释：代码文件哈夫曼译码.txt的译码，将翻译的二进制码译成原来的字符。char*decode(HuffmanCode HC) FILE *fp; char str254; /假设远文本文件不超过254 个字符char *p; static char cdn+1; int i,

26、j,k=0,cjs; 数据结构课程设计哈夫曼译码 .txt,r);/打开文本文档txt while(!feof(fp) /feof(fp)判断文件是否真正结束， /feof(fp)=1时文件结束 cjs=0; for(i=0;inum & cjs=0 & !feof(fp);i+) cdi= ; cdi+1=0; cdi=fgetc(fp); /数组接受从fp 指针所指向文件中读 /入的一个字符 for(j=1;j=num;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15

27、 页，共 28 页 - - - - - - - - - 16 if(strcmp(HCj.bits,cd)=0) strk=HCj.ch; k+; cjs=1;break; /haffman编码和密码译码相比较 strk=0; p=str; return p; 5 系统调试本次测试是在我的电脑的D 盘中建立一个名为哈夫曼.txt的文本文档，其中有大写字母KONGYONGKAISB 运行程序后，我们可以见到一下的运行界面。首先选择 1 打开文件哈夫曼 .txt 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

28、- - - - - 第 16 页，共 28 页 - - - - - - - - - 17 然后选择 2 初始化并建立哈夫曼树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 28 页 - - - - - - - - - 18 接下来选择3 开始对已经建立的哈夫曼树进行编码并写入文件哈夫曼译码 .txt 最后对文件哈夫曼译码 .txt进行编译选择 4 开始进行译码的运算名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

29、- - 名师精心整理 - - - - - - - 第 18 页，共 28 页 - - - - - - - - - 19 由此可见此次程序圆满成功。本程序能够有效的多文件进行编码，并且在译码文件中至于要输入你想要的子母编码，在最后即可输出。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 28 页 - - - - - - - - - 20 总结通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈

30、谈我在设计期间我遇到的难点。开始的时候， 代码中有许多的错误，其中之一便是部分信息无法有效的传递，不过在后面的改正中我发现的我的错误。还有很多很多，例如，在树的初始化输出中，没有权值的节点却出现乱码，这个问题我最终是换了一种方法输出才成功余兴了， 还有就是循环中出现的错误。比如将哈夫曼编码写入文件，就因为多了一个等号以至于哈夫曼译码总是不能成功译出。许多的错误让我明白了一个道理- 细心是非常重要的。 同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。 而且，某些错误对于我们来说有时候想

31、半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，明白了做事情只有认真，才能真正做得更好！名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 28 页 - - - - - - - - - 21 参考文献1 严蔚敏 . 吴伟民 . 数据结构 (C 语言版 ). 清华大学出版社2 施伯乐 . 数据结构 . 复旦大学出版社3 谭浩强 .C 语言程序设计教程. 高等教育出版社4 金远平 . 数据

32、结构 . 清华大学出版社5 王燕 . 面向对象的理论与 C+ 实践 . 清华大学出版社6 李春葆 .C+ 语言习题与解析. 清华大学出版社7 殷人昆，陶永雷，谢若阳等. 数据结构 . 清华大学出版社8 朱战立，张选平 . 数据结构学习指导与典型题解. 西安：西安交通大学出版社，9 罗文劼，王苗，石强 . 数据结构习题解答与实验指 . 中国铁道出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 28 页 - - - - - - - - - 22 附录 源程序#inclu

33、de #include #include #include #define n 100 /叶子结点数#define m 2*n-1 int g; /哈夫曼树中的结点树typedef struct char ch; char bits9; /存放编码位串int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct int weight; /权值int lchild,rchild,parent; /左右孩子几双亲指针HTNode; typedef HTNode HuffmanTreem+1; /0号单元不用int num; /

34、*建立 HuffmanTree* void select(HuffmanTree T,int k,int &s1,int &s2) /选择 parent为 0 且权值最小的两个根结点的算法/ 其为 s1 和 s2 int i,j;int min1=32767; for(i=1;i=k;i+) if(Ti.weightmin1 &Ti.parent=0) j=i;min1=Ti.weight; s1=j;min1=32767; for (i=1;i=k;i+) if(Ti.weightmin1 & Ti.parent=0 & i!=s1) j=i;min1=Ti.weight; 名师资料总结 -

35、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 28 页 - - - - - - - - - 23 s2=j; int jsq(char *s,int cnt,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int temp53; for(i=1;i=A&*p=z) k=*p-64; tempk+; for(i=1,j=0;i=52;+i) if(tempi!=0 ) j+; strj=i+64; cntj=tempi; retur

36、n j; /j是输入字母总数 void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt) /构造哈夫曼树HT int i,s1,s2; for(i=1;i=2*num-1;i+) HTi.lchild=0;HTi.rchild=0; HTi.parent=0;HTi.weight=0; for(i=1;i=num;i+) /输入 num个叶结点的权值HTi.weight=cnti; for(i=num+1;i=2*num-1;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

37、 - 名师精心整理 - - - - - - - 第 23 页，共 28 页 - - - - - - - - - 24 select(HT,i-1,s1,s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; void HuffmanEncoding(HuffmanTree T,HuffmanCode H) /生成哈夫曼编码 int c,p,i; /c和 p 分别指示 t 中孩子和双亲char cdn; int start; cdnum=0; for(i

38、=1;i0) cd-start=(Tp.lchild=c) ? 0 : 1; c=p; strcpy(Hi.bits,&cdstart); Hi.len=num-start; for(i=1;i=num;i+) printf(输出编码： %sn,Hi.bits); char*decode(HuffmanCode HC) /代码文件哈夫曼译码.txt的译码FILE *fp; char str254; /假设文本文件不超过254 个字符char *p; static char cdn+1; int i,j,k=0,cjs; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

39、- - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 28 页 - - - - - - - - - 25 数据结构课程设计哈夫曼译码 .txt,r);/打开文本文档txt while(!feof(fp)/feof(fp)判断文件是否真正结束，feof(fp)=1时文件结束 cjs=0; for(i=0;inum & cjs=0 & !feof(fp);i+) cdi= ;cdi+1=0; cdi=fgetc(fp);/数组接受从fp 指针所指向文件中读入的一个字符 for(j=1;j=num;j+) if(strcmp(HCj.bits,cd)=0

40、)/haffman编码和密码译码相比较 strk=HCj.ch; k+; cjs=1;break; strk=0; p=str; return p; /*输出 HuffmanTree 存储结构 * void print1(HuffmanTree HT)/初建哈夫曼 int x; for(x=1;xnum) printf(t t%dt %dt %dn,HTx.parent,HTx.lchild,HTx.rchild); else printf(t%-6d %dt %dt %dn,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild); printf(-n); 名

41、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 28 页 - - - - - - - - - 26 void print2(HuffmanTree HT) int k; for(k=1;k=2*num-1;k+) printf( t%dt %dt %dt %dn,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild); printf(-n); void DhuffmanTree(HuffmanTree HT,int cnt) /初始化哈夫

42、曼树int i; for(i=1;i=num;i+) /输入 num个叶结点的权值HTi.weight=cnti; /*打开文本 * int open(char string) FILE *fp; 数据结构课程设计哈夫曼 .txt,r)=NULL) printf(不能打开文件 !n); exit(1); while(fgets(string,100,fp)!=NULL) printf(%sn,string); fclose(fp); return 0; void main() char string100; char *s,str53; int cnt53; 名师资料总结 - - -精品资料欢

43、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 28 页 - - - - - - - - - 27 int choice; int i; HuffmanTree HT; HuffmanCode HC; while(choice) printf(nnnt * 哈夫曼编码与译码的实现*nnn); printf(ttt1.打开 D盘的的数据结构.txt文件 nn); printf(ttt2.初始化并建立哈夫曼树nn); printf(ttt3.进行哈夫曼编码nn); printf(ttt4.进行哈夫曼译码nn

44、); printf(ttt0.退出编码译码器nn); printf(nn请输入 0-4, 选择要执行的操作:); scanf(%d,&choice); system(CLS); switch(choice) case 1: printf(读出文本为： n); open(string); num=jsq(string,cnt,str); for(i=0;i=num;i+) /输入字符集的中字符HCi.ch=stri; /字符的种类i=1;while(i=num) printf(字符 %c次数 :%dn,HCi.ch,cnti+); / 统 计 字 符的种类及各类字符出现的频率 system(pa

45、use); break; case 2: printf(-n); if(num=0) printf(未建立哈夫曼树。);exit(0); else DhuffmanTree(HT,cnt); /初始化printf(HuffmanTree的初始化 :n); print1(HT); ChuffmanTree(HT,HC,cnt); /建立哈夫曼树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 28 页 - - - - - - - - - 28 printf(-n); sys

46、tem(pause); printf(HuffmanTree的建立 :n); print2(HT); printf(-n); system(pause); break; case 3: printf(-n); if(num=0) printf(未建立哈夫曼树。);exit(0); else HuffmanEncoding(HT,HC); /生成哈夫曼编码printf(-n); system(pause); break; case 4: printf(-n); if(num=0) printf(未建立哈夫曼树。);exit(0); else s=decode(HC); /读编码文件译码 printf(译码后的字符串:n); printf(%sn,s); printf(-n); system(pause); break; case 0: break; system(CLS); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 28 页 - - - - - - - - -