哈夫曼树数据结构课程设计

1、 数据结构 课程设计赫夫曼编码/译码器设计指导教师：孙树森、周维达班级：09数媒（2）班学号：e09700203姓名：林真超数据结构课程设计实验报告一、题目：赫夫曼编码/译码器设计二、目的：1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法的设计。三、要求3.1总体要求 1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。尤其是对编程软件的使用有基本的认识。2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他

2、人内容，否则成绩以不及格计。4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。3.2实施要求1、理解赫夫曼编码/译码的确切意义。2、独立进行方案的制定，系统结构设计要合理。3、在程序开发时，则必须清楚主要实现函数的目的和作用，需要在程序书写时说明做适当的注释。在写课设报告时，必须要将主要函数的功能和参数做详细的说明。4、通过多组数据来检测该系统的稳定性和正确性。3.3 课程设计报告的内容及要求 在完成课题验收后，学生应在规定的时间内完成课程设计报告一份（不少于2000字）。1一、实验目的1 进一步掌握最优二叉树的含义。2 掌握最优二叉树的结构特

3、征，以及各种存储结构的特点及使用范围。3 熟练掌握哈夫曼树的建立和哈夫曼编码方法。4 掌握用指针类型描述、访问和处理运算。二、实验原理哈夫曼（huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复第2步，直到形成一个

4、符号为止（树），其概率最后等于1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。 译码的过程是分解电文中字符串，从根出发，按字符“0”或“1”确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。三、实验内容（一）需求分析一个完整的系统应具有以下功能：(1) i：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中。(2) e：编码。利用已建好的哈夫曼树，对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。(3) d：译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码

5、，结果存入文件textfile中。(4) p：印代码文件（print）.将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprin中。(5) t：印哈夫曼树（treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中。（二）实验步骤1.定义结点结构，定义哈夫曼树结构；2.初始化哈夫曼树，存储哈夫曼树信息；3.定义求哈夫曼编码的函数；4.定义译哈夫曼编码的函数；5.写出主函数。6.测试系统。（三）概要设计1 设计思想赫夫曼树用邻接矩阵作为存储结构，借助静态链表

6、来实现遍历。2 函数间的关系函数间的关系如图所示：主函数显示表头初始化树输入字符编码译码打印编码打印赫夫曼树选最小两个权值select()图3.1 函数间的关系3 数据结构与算法设计赫夫曼编译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较

7、短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。其主要流程图如图3.2所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用select函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0i2*n?i+编码为1结束否否否右子是否为空是是否否是是是图3.2 赫夫曼树编译码器流程图4.功能函数模块划分void main()void printhead()void printree(huffmantree ht,int w) /打印赫夫曼树void copr

8、int(huffmantree start,huffmantree ht)/打印代码文件void printcode() /打印代码void decode() /完成译码功能void encode() /完成编码功能void inputcode() void init()void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)void select(huffmantree t,int i,int &s1,int &s2)int min(huffmantree t,int i)/找两个最小的权值（四）详细设计（1）哈夫曼编码

9、：首先定义函数，找出全部权值中最小的两个，然后定义一个变量，使他始终成为最小的那个。再将两个函数最为叶子结点，并得到一个父亲节点，此父亲节点的权值为其叶子节点的权值之和。并将此父亲节点的权值与其余权值进行比较，重新选出两个最小的权值，再进行上述步骤，直到所有权值形成了一颗二叉树，而此二叉树就是我们所说的最优二叉树，即哈夫曼树。以上为哈夫曼树的建立过程，下面为哈夫曼编码的过程，从叶子节点出发，若此叶子节点为其父亲节点的左孩子，则将其编码为0，若为右孩子，则将其编码为1，然后为其父亲节点编码，若为祖先的左孩子，则变为0，为右孩子则为1，依次向上一层进行遍历，直到遍历到根节点，停止编码。（2）译码：

10、对于已经建好的哈夫曼树，要对其进行译码，首先从根出发如果编码为0，则往左孩子遍历，如果编码为1，则往右孩子遍历，直到遍历到叶子节点，便求得该子串相应的字符。（3）初始化哈夫曼链表:首先输入结点个数，再将字符及权值输入，调用编码函数，得到每个字符编码并将其输出。最后将哈夫曼编码写入文件。（4）完成编码功能：打开目录下文件tobetran.txt，读取里面的字符，对其进行编码后，将编码写入目录下的codefile.txt中。（5）完成译码功能：打开根目录下codefile.txt文件，读取里面的编码，对其中的编码进行译码，并将得到的内容写入根目录下的文件txtfile.txt中。（6）打印编码（7

11、）打印哈夫曼树四、实验结果1程序运行环境为dos，执行文件为：huffman2.exe2 . 初始化哈夫曼链表(实验一)在这里，有一个要注意的问题，在程序刚开始运行的时候，需要先用“i”命令对哈夫曼树进行初始化。若不进行初始化，则表明哈夫曼树并未建立，这样就无法进行后续的调试。3.编码字符4.编码5.译码6.打印编码7.打印哈夫曼树（实验二）1.初始化的内容如表所示：字符abcdefghijklm频度1886413223210321154757153220字符nopqrstuvwxyz频度57631514851802381811612.初始化3.输入的字符以及其对应的编码4、译码5. 文件te

12、xtfile.txt中内容： this1program1is1my1favorit（这里的空格字符定义为1，故出现此译码）6.打印编码7.打印哈夫曼树五、实验结果分析此算法的时间复杂度为：o（n），n为哈夫曼树的结点个数。在对哈夫曼编码/译码器算法设计过程中，主要参考了教材中对哈夫曼编码/译码的算法。在实现的过程中遇到了一些问题，后来参考网上的一些代码，进行与自己带吗的整合，将编码/译码算法完成。而在对编码以及字符进行文件保存、打开时，也遇到了不小的问题，很大一部分来源于对于以前c语言对文件操作的不熟练，所以在解决过程中，参考了一些类似的成功算法实例。六、实验心得对于本次课程设计，主要是需要掌

13、握哈夫曼树建立、哈夫曼编码以及哈夫曼译码的算法。并能将其熟练应用于编译码器的完成。经过这次的课程设计，使我们更加了解了数据结构，也更深入地了解了哈夫曼编码与译码算法，课程设计的题目比我们平常的实验内容要难，完成它不仅需要有厚实的语言基础，而且还要熟练掌握哈夫曼编码与译码的算法，另外对于文件的基本操作也需要熟悉。由于本次课程设计时间安排得比较迟，所以大部分同学都在上课之前就把实验做好了，由于在课外做，碰到许多问题无法请教老师，但是通过上网找寻解决办法，大部分的错误与问题也都能基本解决。七、主要代码#include #include #include #include #include const

14、 int uint_max=1000;typedef struct /哈夫曼树的存储表示 int weight; /权值int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点htnode,* huffmantree; /动态分配数组存储哈夫曼树typedef char *huffmancode;/动态分配数组存储哈夫曼编码表/-全局变量-huffmantree ht; /代表赫夫曼树huffmancode hc; /代表赫夫曼编码int *w,i,j,n; char *z;int flag=0; int numb=0;/ -求赫夫曼编码-void line()/画

15、分割线的函数coutn-n;int min(huffmantree t,int i)/找两个最小的权值 int j,flag;int k=uint_max; / 取k为不小于可能的值for(j=1;j=i;j+)if(tj.weights2)/ s1为最小的两个值中序号较小的那个j=s1;s1=s2;s2=j;void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)int m,i,s1,s2,start;int c,f;huffmantree p;char *cd;if(n=1)return;m=2*n-1;/申请2n-1

16、个内存单元ht=(huffmantree)malloc(m+1)*sizeof(htnode); / 0号单元未用for(p=ht+1,i=1;iweight=*w;/赋权值p-parent=0;p-lchild=0;p-rchild=0;for(;iparent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 select(ht,i-1,s1,s2);/调用建子树的函数hts1.parent=hts2.parent=i;/i是s1和s2的父节点hti.lchild=s1;hti.rchild=s2;/s1和s2是i的儿子节点hti.weight=hts1.weight+hts2.w

17、eight;/i的权值为s1和s2的和hc=(huffmancode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间cdn-1=0; /编码结束符for(i=1;i=n;i+)/逐个字符求哈夫曼编码start=n-1; /编码结束符位置for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) / 从叶子到根逆向求编码if(htf.lchild=c)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-st

18、art)*sizeof(char);/为第i个字符编码分配空间strcpy(hci,&cdstart); /从cd复制编码（串）到hcfree(cd);/释放工作空间/-初始化哈夫曼链表-void init() flag=1;int num;int num2;cout下面初始化赫夫曼链表endlnum;/输入结点个数n=num;w=(int*)malloc(n*sizeof(int);/权值z=(char*)malloc(n*sizeof(char);/字符coutn请依次输入n个字符(字符型)n注意:必须以回车结束：endl;char temp2;for(i=0;in;i+)/输入字符 co

19、ut第i+1个字符:endl; gets(temp); *(z+i)=*temp;line();for(i=0;i=n-1;i+)/输出字符coutsetw(6)*(z+i);line();coutn请依次输入n个权值(n注意:必须以回车结束)：endl;for(i=0;i=n-1;i+)/输入权值coutendl第i+1num2;*(w+i)=num2;huffmancoding(ht,hc,w,n);/调用哈夫曼编码/-打印编码-cout字符对应的编码为:endl;for(i=1;i=n;i+)/输出所有编码puts(hci);/-将赫夫曼编码写入文件-cout下面将赫夫曼编码写入文件en

20、dl;file *htmtree;char r= ,0; if(htmtree=fopen(htmtree.txt,w)=null)cout文件打开失败endl;return;fputs(z,htmtree);for(i=0;in+1;i+)fprintf(htmtree,%6d,*(w+i);fputs(r,htmtree);for(i=1;i=n;i+)fputs(hci,htmtree);fputs(r,htmtree);fclose(htmtree);cout已将字符与对应编码写入根目录下文件htmtree.txt中endlendl;/init/-获取字符并写入文件-void inpu

21、tcode() file *virttran,*tobetran;char str100;if(tobetran=fopen(tobetran.txt,w)=null)cout不能打开文件endl;return;cout请输入你想要编码的字符endl;gets(str);fputs(str,tobetran);cout获取字符成功endl;fclose(tobetran);/-void encode() /完成编码功能cout下面对目录下文件tobetran.txt中的字符进行编码endl;file *tobetran,*codefile;if(tobetran=fopen(tobetran.

22、txt,rb)=null)cout不能打开文件endl;if(codefile=fopen(codefile.txt,wb)=null)cout不能打开文件endl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char); /为tran分配100个字节while(i=99)if(fgets(tran,100,tobetran)=null)cout不能打开文件endl;break;for(i=0;*(tran+i)!=0;i+)for(j=0;jn)cout字符错误，无法编码!endl;break;cout编码工作完成endl编码写入目录下的cod

23、efile.txt中endlendl;fclose(tobetran);fclose(codefile);free(tran);/-void decode() /完成译码功能cout下面对根目录下文件codefile.txt中的字符进行译码endl;file *codef,*txtfile;if(txtfile=fopen(textfile.txt,w)=null)cout不能打开文件endl;if (codef=fopen(codefile.txt,r)=null)cout不能打开文件endl;char *tbdc,*outext,i2;int io=0,i,m;unsigned long

24、length=10000;tbdc=(char*)malloc(length*sizeof(char); /分配空间fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char); /分配空间m=2*n-1;for(i=0;*(tbdc+i)!=0;i+) /进入循环i2=*(tbdc+i);if(htm.lchild=0) *(outext+io)=*(z+m-1);io+;m=2*n-1;i-;else if(i2=0) m=htm.lchild;else if(i2=1) m=htm.rchild;*(outext+io

25、)=0;fputs(outext,txtfile);cout译码完成endl内容写入根目录下的文件txtfile.txt中endlendl;free(tbdc);free(outext);fclose(txtfile);fclose(codef);/-void printcode() /打印代码cout下面打印根目录下文件codeprin.txt中编码字符endl-n;file * codeprin,* codefile;if(codeprin=fopen(codeprin.txt,w)=null)cout不能打开文件endl;return;if(codefile=fopen(codefile

26、.txt,r)=null)cout不能打开文件endl;return;char *work3;work3=(char*)malloc(51*sizeof(char);doif(fgets(work3,51,codefile)=null)cout不能读取文件endl;break;fputs(work3,codeprin);puts(work3);while(strlen(work3)=50);free(work3);cout打印工作结束endlendl;fclose(codeprin); fclose(codefile);void coprint(huffmantree start,huffmantree ht)/打印代码文件char t= ;if(start!=ht)file * treeprint;if(treeprint=fopen(treeprint.txt,a)=null)cout创建文件失败rchi