《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（28页珍藏版）》请在金锄头文库上搜索。
1、目录:目 录1III1课程设计的目的和意义2II2需求分析3III 3系统设计4II1(1)设计思路及方案4III装 (2)模块的设计及介绍 4II1(3)主要模块程序流程图6III14系统实现10II订 (1)主调函数10IIII(2)建立 HuffmanTree 10III(3)生成Huffma n编码并写入文件13线I(4)电文译码14III5系统调试16III丨 小 结18II： 参考文献19III! 附录源程序20I1 课程设计的目的和意义IIIIIIIIIIIi在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间III 和计算机网络的传送时间已越来越引起人们的重视
2、。哈夫曼编码正是一种应用广泛且III 非常有效的数据压缩技术。III哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫III 曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的III 分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的I装 序列作为和各个对应的字符的编码，这就是哈夫曼编码。III通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递III 文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用II 最短码。订I作为软件工程专业的学生，我们应该很好的掌握这门技术。在课堂上，
3、我们能过III 学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这III 个问题提供了一个平台。I线在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，III 借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强III 我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累II 调试 C 程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。II在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我III 们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交III
4、 换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老III 师那学到更多的实用的知识。II数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程 设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略 实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须 严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论 文的能力。只有这样，我们的综合素质才会有好的提高。2 需求分析题目：哈夫曼编码 / 译码器问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是
5、这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样 的信息收发站写一个哈夫曼码的编译码系统。具体要求：1）初始化：键盘输入字符集大小n及n个字符和m个权值，建立哈夫 曼树，并将它存于文件 hfmtree 中。2）编码：利用建好的哈夫曼树，对文件 tobetrans 中的正文进行编码， 然后将结果存入文件 codefile 中。3）解码：利用建好的哈夫曼树将文件 codefile 中的代码进行译码，结 果存入文件 textfile 中。4）打印代码文件：将文件 codefil
6、e 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件 codeprint 中。5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中。6） 设字符集及频度如下表字符空 格ABCDEFGHIJKLM频度1866423223210321154757153220字符NOPQRSTUVWXYZ频度205619250515530101122123 系统设计IIIIIIIII(1)设计思路及方案 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字II 符在电文中出现的次数为
7、Wi，编码长度为Li,电文中有n种字符，则电文编码总长II 度为(Wl*L1) + (W2*L2)+(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根I 结点到叶结点的路径长度。那么，(Wl*L1) + (W2*L2)+(Wi*Li)恰好为二叉树上带权I 路径长度。II 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权， 装-构造一棵哈夫曼树，此构造过程称为哈夫曼编码。I 该系统将实现以下几大功能：从硬盘读取字符串，建立哈夫曼树，输出哈夫曼树II 的存储结构的初态和终态，输出各种字符出现的次数以及哈夫曼编码的译码等。I订(2)模块的设计及介绍 从硬盘读取字符串II
8、I fil eopen(参数)II: II线实现命令；II 打印输出；III II 建立 HuffmanTreeII通过三个函数来实现：III void select(参数)III II初始化；IIIfor接受命令；处理命令；说明：在ht l.k中选择parent为0且权值最小的两个根结点的算法IIiint jsq(参数)III iii 初始化；IIii forIIIii IIi接受命令；ii处理命令；iII iii说明：统计字符串中各种字母的个数以及字符的种类IIIivoid ChuffmanTree()IIi 初始化；iiforii接受命令；ii 处理命令；III iii 输出字符统计情况
9、；iIiIii 说明：构造哈夫曼树ii 输出哈夫曼树的存储结构的初态和终态丨分别调用printl()和print2()来实现void pri ntl(参数)初始化；输出初态；说明：输出哈夫曼树的初态void prin t2（参数）IIIi IIi forII iIii 输出终态；Iii IIiiii说明：输出哈夫曼树的终态装哈夫曼编码和译码I:void HuffmanEncoding（参数）III iIi定义变量；卩IIi 处理命令；II iii说明：哈夫曼编码IIi char *decode（参数）IIII iii 定义变量；iIi whileIIIIiii 接受命令；i处理命令；说明：哈夫
10、曼译码（3）主要模块程序流程图下面介绍三个主要的程序模块流程图： 主函数流程图：图 3.1流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的 字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。 构造哈夫曼树：否i=num?是否i=2 *num-l?是否i=num?是结束开始第i个结点权值/第i个根结点创建哈夫曼树输出字符统计情况图 3.2流程图注释： 该图是表示构造哈夫曼树的过程。首先输入 num 个叶结点的权值，当 i=num 是循环结 束。然后进行哈夫曼树的构建，当 i=2*num
11、-l 是循环结束。最后输出所得到的字符统 计情况。 哈夫曼编码：图 3.3流程图解释：该流程图表四哈夫曼编码情况。首先初始化，Cd-start=O,start=num。然后进行编 码 ， 使 用 了 一 个 三 目 运 算 符 。 cd-start=(Tp.lchild=c) ? 0 : 1， 即 当cd-start=Tp.lchild= =c 时，cd-start=O ；当 cd-start=Tp.lchild ！ = =c 时，cd-start=l。这个编码循环一直到i=num时结束。4 系统实现各模块关键代码及算法的解释：(1) 主调函数代码解释：这是main函数里的各个函数调用情况。f
12、ileopen(string);/从硬盘中读取文件num=jsq(string,cnt,str);/统计字符种类及各类字符出现的频率DhuffmanTree(HT,cnt,str);printf (HuffmanTree 的初态:n);print1(HT);/输出哈夫曼树的初态ChuffmanTree(HT,HC,c nt ,s tr);/建立哈夫曼树 HuffmanEncoding(HT,HC);/生成哈夫曼编码printf (HuffmanTree 的终态:n);print2(HT);/输出哈夫曼树的终态s=decode(HC);/读编码文件译码printf (“译码后的字符串：n);printf(%sn,s);/输出译码后的字符串(2) 建立 HuffmanTree代码解释：该函数为在ht l.k中选择parent为0且权值最小的两个根 结点的算法，其序号为s1和s2。void select(HuffmanTree T,int k,int &s1,int &s2)int i,j;int min1=101;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
