数据结构课程设计(哈夫曼编码)

1、目 录错误!未定义书签。 1课程设计的目的和意义错误!未定义书签。 2需求分析错误!未定义书签。 3系统设计错误!未定义书签。 (1) 设计思路及方案错误!未定义书签。 (2) 模块的设计及介绍错误!未定义书签。 (3) 主要模块程序流程图错误!未定义书签。 4系统实现错误!未定义书签。 (1) 主调函数错误!未定义书签。 (2) 建立HuffmanTree错误!未定义书签。 (3) 生成Huffman编码并写入文件错误!未定义书签。 (4) 电文译码错误!未定义书签。 5系统调试错误!未定义书签。 小结错误!未定义书签。 参考文献错误!未定义书签。 附录源程序错误!未定义书签。 1课程设计的

2、目的和意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间 和计算机网络的传送时问已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且 非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫 曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的 分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1的 序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递 文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最

3、短，即采用 最短码。 作为软件工程专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过 学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这 个问题提供了一个平台。 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授內容， 借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强 我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累 调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我 们完成系统。更为重要的是，我们同学之间

4、加强了交流，在对问题的认识方面可以交 换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老 师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程 设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略 实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须 严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论 文的能力。只有这样，我们的综合素质才会有好的提高。 2需求分析 题 目：哈夫曼编码/译码器 问题描述： 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短

5、信息传输时 间，降低传输成本。但是这要求在发送端通过一个编码系统对待传数据预 先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可 以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样 的信息收发站写一个哈夫曼码的编译码系统。 具体要求： 1）初始化：键盘输入字符集大小n及n个字符和ni个权值，建立哈夫 曼树，并将它存于文件hfmtree中。 2）编码：利用建好的哈夫曼树，对文件tobetrans中的正文进行编码, 然后将结果存入文件codefile中。 3）解码：利用建好的哈夫曼树将文件codefile中的代码进行译码，结 果存入文件textfile中。 4）打印代

6、码文件：将文件codefile以紧凑格式显示在终端上，每行 50个代码。同时将此字符形式的编码文件写入文件codeprint中。 5） 6）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式（树或凹入 表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 treeprint 中。 7）设字符集及频度如下表: 字符 空 格 A B C D E G H I J K I. M 频度 186 64 23 22 32 103 21 15 47 57 1 5 32 20 字符 N 0 P Q R S T V W X Y Z 频度 20 . 56 19 2 50 51 55 30 $ 10 11 2 21

7、 2 3系统设计 (1) 设计思路及方案 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字 符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符，则电文编码总长 度为(Wl*Ll) + (W2*L2)+-+(Wi*Li) 0若将此对应到二叉树上，Wi为叶结点，Li为根 结点到叶结点的路径长度。那么，(Wl*Ll) + (W2*L2)+-+(Wi*Li)恰好为二叉树上带权 路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权， 构造一棵哈夫曼树，此构造过程称为哈夫曼编码。 该系统将实现以下几大功能：从硬盘读取字符串，建立哈夫曼树，输出哈夫

8、曼树 的存储结构的初态和终态，输出各种字符出现的次数以及哈夫曼编码的译码等。 (2) 模块的设计及介绍 从硬盘读取字符串 fileopen (参数) 实现命令； 打印输出； 建立 HuffmanTree 通过三个函数来实现： void select (参数) 初始化； for 接受命令； 处理命令； 说明：在htl. k中选择parent为0且权值最小的两个根结点的算法 int jsq(参数) 初始化； for 接受命令； 处理命令； 说明：统计字符串中各种字母的个数以及字符的种类 void ChuffmanTreeO 初始化； for 接受命令； 处理命令； 输出字符统计情况； 说明：构造哈

9、夫曼树 输出哈夫曼树的存储结构的初态和终态 分别调用printl ()和print2()来实现 void printl (参数) 初始化； 输出初态； 说明：输出哈夫曼树的初态 void print2（参数） for 输出终态； ） 说明：输出哈夫曼树的终态 哈夫曼编码和译码 void HuffmanEncoding（参数） 定义变量； 处理命令； ） 说明：哈夫曼编码 char*decode （参数） 定义变量； wh订e 接受命令； 处理命令； 说明：哈夫曼译码 (3)主要模块程序流程图 下面介绍三个主要的程序模块流程图: 主函数流程图: 图 流程图注释： 该图比较简单，主要是调用各个函数

10、模块，首先代开已经存在的文件，然后统计总的 字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基 础上对其进行编码，编码之后才是译码。最后输出结束。 构造哈夫曼树: 流程图注释： 该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2相inn-l是循环结束。最后输出所得到的字符统 计情况。 哈夫曼编码: Cd一一start=O.start=n Cd 一一startCd start 否 流程图解释: 该流程图表四哈夫曼编码情况。首先初始化，Cd-start=O, start=numo然后进行 编码，使用了一个三目

11、运算符。cd-start = (Tp.lchild=c) : i,即当 cd-start=Tp. lchild= =c 时，cd-start=O；当 cd-start=TI p l.lchild ! =c时，cd-start=l这个编码循环一直到i=num时结束。 4系统实现 各模块关键代码及算法的解释： (1)主调函数 代码解释：这是main函数里的各个函数调用情况。 fileopen(string) ；. k中选择parent为0且权值最小的两个根结 点的算法，其序号为si和s2。 void select(HuffmanTree T,int k,int int minl=101: for(

12、i=l；i=k；i+) if (Tl.i. weightminl $ FILE *fp； fp=fopen(”,； while(*str) for(i=l；i=num；i+) if (HCiJ. ch*str) for(j=0；j=HCi. len； j+) fputc(HCi. bitsj,fp)； break； str+； fclose(fp)； (4)电文译码 代码解释：代码文件的译码，将翻译的二进制码译成原来的字符。 char*decode(HuffmanCode HC) FILE *fp； char str254:its,cd)=0) strk=HCj.ch； k+; cjs=l；b

13、reak； |读岀文本为： FAVOKITE ITHIS program IS UY f ”iiFFnianTry 巳的初态二 2 0 21111332134212 s =i=m-M =瓠熱蝕瓶熱蝕熱熱瓠= aefghimoprstuy 宀x-s-i-x-Ti-s-s-i-s-i-x-s-子 17 17 20 20 13 24 16 24 17 27 27 27 mrawsv hHIS PRO GRAM IS MY FAU OR ITE DPress any key to continue： 据结构（C语言版）清华大学岀版社，2007 苏仕华数据结构课程设计机械工业出版社，2007 3谭浩强.

14、C语言程序设计教程髙等教育岀版社，2006 附录源程序 #include include include #include .k中选择parent为0且权值最小的两个根结点的算法 eightminl p=str； return p； arent=0： HTx. lchild=0； HTx.rchild=O； printf(%lld %dt %dt %dn.HTxweightrHTx. parent JITx. lch订d.HTxrc hild)； void prin12(HuffmanTree HT) int k； for(k=l；k=stril) HTi. weight=(char)*; /

15、*r4* int fileopen(char stringE) FILE *fp； if(fp=fopen(wE：数据结构课程设计Mr-)=NULL) printf 不能打开文件! n); exit (1)； while(fgets(string,100,fp)!=NULL) printf(n%sn,string)； fclose(fp)； return 0； /* 调函 l* void main() char string100: char *s,str27: int ent27: UuffmanTree HT： HuffmanCode HC； printf 读出文本为：nn): fileopen(string)； num=jsq (string, ent, str);/统计字符的种类及各类字符出现的频率 DhuffmanTree(HT,ent, str)； -nn)； /建立哈夫曼树 /生成哈夫曼编码 /建立电文哈夫曼编码文件 printf(n printf (