《数据结构课程设计哈夫曼编码器》由会员分享，可在线阅读，更多相关《数据结构课程设计哈夫曼编码器（17页珍藏版）》请在金锄头文库上搜索。
1、3数据结构课程设计：哈夫曼编码器 摘 要哈夫曼（huffman）树是一种带权路径长度最小的二叉树，也称最优二叉树，它有着极为广泛的应用。而我今天做的课程设计就是其中的一个应用-哈夫曼编码器。其实它的思想很简单，显示根据输入的权值建立一棵哈夫曼树，然后根据哈夫曼数求出各个叶结点的编码。这样就构成了一个最简单的哈夫曼编码器。关键词：哈夫曼树 编码器 最优二叉树 带权路径长度目 录1 课题分析11.1 设计目的11.2 设计要求11.3设计内容12 总体设计与分析321功能函数设计32.1.1建立哈夫曼树32.2.2求哈夫曼编码函数32.2.3打印编码函数33 程序说明43.1 结构图44 程序调试
2、54.1 菜单54.2 输入叶结点和权值64.3 输出哈夫曼编码75 设计问题85.1存入文件85.1.1问题185.1.2问题286 小结9参考文献10源代码111 课题分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字
3、符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。1.1 设计目的（1）复习并灵活掌握二叉树的各种储存结构和遍历方法。（2）了解静态链表，并掌握其构造方法。（3）掌握哈夫曼树的构造过程和哈夫曼编码的求解方法。（4）复习掌握文件读写的基本方法。1.2
4、设计要求（1）求得的哈夫曼编码及WPL必须写入编码文件。（2）哈夫曼树的存储可以采用静态链表或二叉链表。1.3设计内容我在实验中采用的是静态链表作为存储结构，其数据类型可以定义为：#define m 2*n-1 /*m为哈夫曼树的结点*/ /*具有n个叶结点的哈夫曼树共有2n-1个结点*/typedef structint wi; /*定义权值*/char data; /*定义叶结点*/int Parent,Lchild,Rchild; /*定义父结点、左孩子、右孩子*/huffm;huffm HTm+1; /*静态链表HTm+1*/(1)从文件中读取所有结点的权值，将读取的权值放到静态链表中
5、，并初始化静态链表。（2）依据给定的权值，不断生成各分支结点，直到生成树根结点为止，得到生成哈夫曼树后的静态链表。（3）规定所有的左分支为0，右分支为1，从树根到叶子所经过的分支构成的01编码，即是对应叶子的哈夫曼编码。（4）求出所有叶子的哈夫曼编码，并将编码写入文件。2 总体设计与分析通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。21功能函数设计2.1.1建立哈夫曼树void HuffmTree(huf
6、fm HTm+1);我用的是手动输入，首先提醒用户输入8个叶结点，即8个字母，输入完毕后提醒用户输入8个权值。以上的两个输入的输入格式都用空格隔开，以回车结束。哈夫蛮树建立成功。其基本算法是：由给定的8个权值，构造由空二叉树扩充得到的扩充二叉树，每个数只有一个外部结点。在已经构造的扩充二叉树中，选取根结点权值最小和次小的两个。将它们作为左子树、右子树，构造成一颗新的扩充二叉树，它的根结点的权值为两子树的权值之和。重复执行步骤，每次都使扩充的二叉树的个数减一，当只剩下一棵扩充二叉树时，它便是所要构造的哈夫曼树。2.2.2求哈夫曼编码函数void Huffmcode(ctype coden+1);
7、从根结点开始，寻找每一个叶结点，在寻找过程中，经过左子树时，编码增加“0”，经过右子树时，编码增加“1”，当每一个叶结点都访问过时，便得到相应的编码。2.2.3打印编码函数void Output (ctype coden+1);打印编码函数即输出编码函数。当用户输好叶结点和权值后，通过哈夫曼编码函数进行编码，然后通过打印编码函数将哈夫曼编码显示在屏幕上。3 程序说明3.1 结构图哈夫曼编码器建立哈夫曼树哈夫曼编码输出哈夫曼编码这就是整个程序的基本流程，总共分为三大块：建立哈夫曼树、哈夫曼编码、输出哈夫曼编码。其实思想很简单，按照这个步骤来就行了。首先，用户手动输入8个字母和权，建立好哈夫曼树后
8、，左子树为0，右子树为1，根据这个可以写出每个叶结点的编码。最后输出即可。这整个程序过程都是通过C语言实现的，所以都是一些很简单的语句，通俗易懂，这样我修改起来也比较方便。4 程序调试4.1 菜单这只是一个很简单的菜单，在这次的实验中，我没有在菜单上花很多功夫，所以这只是一个再简单不过的开始界面，就是询问用户是否要继续玩下去。4.2 输入叶结点和权值用户手动输入输入8个字母：a s d f g h j k输入8个权值：12 22 33 45 6 9 8 244.3 输出哈夫曼编码在这个环节中，先输出编译好的哈夫曼编码，接下来还要求最短路径WPL。然后下面的那个菜单一开始的那个菜单是相同的意思，
9、就是询问用户是否要继续玩下去，如果选择1，则用户再次手动输入叶结点和权值，再进行编译。5 设计问题5.1存入文件这次课程设计输入的叶结点和权值，还有最后的哈夫曼编码都是要存入文件。刚开始以为加进去个文件会很简单，因为我们上学期也做过课程设计，是C语言的，最主要的就是弄文件，所以这个本来没有多大问题。但是这次加了文件后出现了比较麻烦的问题。5.1.1问题1为什么记事本会出现空白？在我加入文件后显示出现了许多小问题,具体是什么问题我已经记得不清，只知道最后总算是把错误全找出来了，调通了，本来以为没错了，后来运行的一切都很正常。等到最后都执行完了，打开文件发现文件是空白的，什么都没有，就这个问题我尝
10、试过很多遍，可记事本始终是空白的，后来我发现记事本的大小为1KB，就说明里面是肯定有东西，在研究了多遍后，发现记事本里都是空格，所以我们是看不见的，但用鼠标全选一下就会发现有东西。5.1.2问题2为什么记事本中会全都是空格键？上面那个问题算是解决了，但接下来有个更头疼的问题-为什么记事本中会都是空格键呢？怎么样才能让记事本中出现我输入的哪些字符和数字呢？本来我是把保存文件单独弄一个函数的-void save();但是由于文件出了问题，所以我就把文件的那个函数删掉了，把它加入到程序中。然后我发现把文件加入主函数中后、文件夹中就会出现东西。但是至于为什么将文件单独作为一个函数时，文件夹中出现的都是
11、空格还没有弄清楚。6 小结在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码的应用范围，程序结构算法等一系
12、列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。而且我还学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。一个成功的项目必须在写代码前，先要对课题有充分的思考和规
13、划，否则即使完成了项目也会浪费很多的时间和精力，我认为科学合理的编程方法是我这次课程设计的最大收获。参考文献1. 谭浩强著C语言设计（第四版）北京：清华大学大学出版社，20102 陈元春 王中华 张亮 王勇等著实用数据结构基础（第三版）.北京，中国铁道出版社，2011 3 秦锋 袁志祥著.数据结构（C语言版）例题详解与课程设计指导. 安徽:中国科学技术大学出版社,2007源代码#include #include #include #define n 8 /*n为定的8个数*/#define m 2*n-1 /*m为哈夫曼树的结点*/ /*具有n个叶结点的哈夫曼树共有2n-1个结点*/#defi
14、ne max 2000 /*最大值*/typedef struct int wi; /*权值*/ char data; int Parent,Lchild,Rchild;/*定义父结点、左孩子、右孩子*/huffm;huffm HTm+1;typedef struct char bitsn+1; int start; char ch;ctype;ctype coden+1;void HuffmTree(huffm HTm+1);void Huffmcode(ctype coden+1);void Output (ctype coden+1);/* 构造HuffmTree的函数*/void HuffmTree(huffm *HT) int i,j,p1,p2; int s1,s2; for(i=n+1;i=m;i+) p1=p2=0; s1=s2=max; for(j=1;j=i-1;j+) if(HTj.Parent=0) if(HTj.wi s1) s2=s1; s1=HTj.wi;
