2022年数据库作业 2.pdf

《2022年数据库作业 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据库作业 2.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、理学院School of Science 数据结构课程设计报告学生姓名：王玉晓学生学号：201001156 所在班级：数学 101 所在专业：数学与应用数学指导教师：伊海丽实习场所：青岛理工大学实习时间：第五学期成绩评定名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 题目：哈夫曼编码译码一课程设计的目的及意义我们应该很好的哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径

2、，对路径上的各分支约定：指向左子树的分支表示“ 0”码，指向右子树的分支表示“1”码，取每条路径上的“ 0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立

3、思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。二、需求分析问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。问题补充： 1. 从硬盘的一个文件里读出一段英语文章； 2. 统计这篇文章中的每个字符出现的次数； 3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出； 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。具体介绍：在本课题中，我们在硬盘中预先建立一个文档，在里面编辑一篇文

4、章。然后运行程序，调用函数读出该文章，显示在界面；再调用函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 次数作为权值，调用函数构建哈夫曼树；并调用函数将哈夫曼的存储结构的初态和终态进行输出。然后调用函数对哈夫曼树进行编码，调用函数将编码写入文件；再调用对编码进行译码，再输出至界面。至此，整个工作就完三、设计要求用最优二叉树即哈夫曼

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

6、符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。四、程序编码赫夫曼树的存储结构描述为：#define N 50 / 叶子结点数#define M 2*N-1 / 赫夫曼树中结点总数typedef struct int weight; / 叶子结点的权值int lchild, rchild, parent; / 左右孩子及双亲指针HTNode; / 树中结点类型typedef HTNode HuffmanTreeM+1; 哈弗曼树的算法void CreateHT(HTNode ht,in

7、t n) /调用输入的数组 ht,和节点数 n 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值 -1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int 的范围是 -327

8、6832767 lnode=rnode=-1; /lnode和 rnode记录最小权值的两个结点位置for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=h

9、tlnode.weight+htrnode.weight; /父节点权值是两个的和hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - （4）主函数void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,

10、V,W,X,Y,Z;/初始化int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化HTNode htM; /建立结构体HCode hcdN; /建立结构体for (i=0;in;i+) /把初始化的数据存入ht 结构体中 hti.data=stri; hti.weight=fnumi; 五、心得体会课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题 ,锻炼实践能力的重要环节 ,回顾起此次课程设计， 至今我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -