哈夫曼课程设计报告.doc

哈夫曼编码器 16摘 要在数据通信中，经常需要将传送的文字转换成二进制字符0和1组成的二进制代码，而这称之为编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构成一种不等长的编码，则电文的代码就可能更短。哈夫曼是一种用于构造使电文的编码总长最短的编码方案。关键词：哈夫曼编码 数据通信 电文 频率 二进制目 录1 哈夫曼编码器11.1设计目的11.2设计要求12 问题的描述与解决23 哈夫曼编码器的概要设计53.1 结构图53.2概要设计介绍54 结果显示及说明74.1结果显示74.2执行方法说明95 小结10参考文献11附录121 哈夫曼编码器数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。1.1设计目的 （1）复习并灵活掌握二叉树的各种存储结构和遍历方法 （2）了解静态链表，并掌握其构造方法 （3）掌握哈夫曼树的构造过程和哈夫曼编码的求解方法 （4）复习并掌握文件读写的基本方法1.2设计要求（1）结点的权值由人工输入，输入保存至文件中（2）求得的哈夫曼编码及wpl也必须写入编码文件中（3）哈夫曼树的存储可以采用静态链表或二叉链表2 问题的描述与解决 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。程序设计包含的几个方面：哈夫曼树的建立，哈夫曼树的编译，求wpl哈夫曼树的建立由哈夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。举例：abdc77425图(a) abdc7757274767图(b)cbad7727574767117图(c)cdab7757274767117187图(d)求哈夫曼编码的方法：（1）构造哈夫曼树（2）在哈夫曼树上求叶结点的编码。假设哈夫曼树按数据频度的权值从小到大，采用顺序存储结构存储。每次找到的权值最小值作为新生结点的左孩子，权值次小值作为新生结点的右孩子，则左孩子的权值加右孩子的权值之和为根结点的权值。规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便成为该叶子结点对应的编码。wpl:从根结点到各个叶结点的路径长度与相应结点权值的乘积之和。3 哈夫曼编码器的概要设计3.1 结构图哈夫曼编码器初始化哈夫曼树编码输出哈夫曼编码载入文件系统结构图3.2概要设计介绍（a）哈夫曼树结点的类型定义：typedef struct /结点类型定义 int wi; / 权值 char data; int parent,lchild,rchild; /定义父结点、左孩子、右孩子huffm;（b）哈夫曼树的编码类型定义;typedef struct char bitsn+1; /用来存放0和1编码 int start; char ch;ctype;ctype coden+1;这一次的程序中，我们一共用了三个函数：void huffmtree(huffm htm+1); / 构造huffmtree的函数 1.由给定的8个权值，构造8颗由二叉树扩充得到的扩充二叉树，每一个扩充二叉树只有一个外部结点。2.在已经构造的所有扩充二叉树中，选取根结点的权值最小和次小的两个，将它们作为左右子树，构造成一颗新的扩充二叉树，它的根结点的权值为两子树的权值之和。3.重复执行步骤2，每次都使扩充二叉树的个数减一，当只剩下一颗扩充二叉树时，它便是所要构造的哈夫曼树。void huffmcode(ctype coden+1); /求huffmtree编码的函数 从根结点开始，寻找每一个叶子结点，在寻找的过程中，经过左子树时，编码增加0，经过右子树时编码增加1，当每个叶子结点都被访问过时，便得到相应的编码。void output (ctype coden+1); /打印编码函数 只要将已经建立好的哈夫曼编码，一一输出就行了，用程序来实现，再好好排版，就能显示出来了。4 结果显示及说明4.1结果显示图（1）图（2） 图（3） 图（4）4.2执行方法说明图（1）：执行菜单主界面 图（2）：输入“1”，执行哈夫曼编码。根据上面的提示输入8个字符和8个权值，按回车后就会显示出字符，权值，叶结点及哈夫曼编码图（3）：将输入的字符及权值保存至记事本huffman中图（4）：将执行后得到的哈夫曼编码保存至huffmancode中5 小结在这一次的课程设计中，我们编写好源代码后的调试过程中出现了不少的错误，遇到了很多麻烦及困难，经过千辛万苦的纠结最终我们最终还是找出错误，调试成功了。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题，它使我对数据结构改变了看法。在这次设计过程中，体现出自己设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。我们编好后在老师的指导下，努力想使程序更完美，更符合要求，老师让我们在做好的基础上，尝试一下哈夫曼译码的实现。于是我在课后参考了老师给的程序，我花费了很多的时间去把载入文件这块做的更好，功夫不负有心人，我最终胜利的完成了。但译码的实现最终没有成功，但通过对译码的编写过程中，我们也了解了哈夫曼译码的求解思想。通过本次数据结构的课程设计，我学到了很多在上课没来得及消化的知识，并对求哈夫曼树及哈夫曼编码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。参考文献1. 谭浩强c程序设计（第四版）. 清华大学出版社2 陈元春，王中华，张亮，王勇 编著 实用数据结构基础（第三版）.中国铁道出版社.3 何钦铭，冯雁，陈越 著. 数据结构课程设计. 浙江大学出版社4 陈媛，何波，蒋鹏，刘洁 编著. 数据结构 学习指导实验指导课程设计. 机械工业出版社5 秦锋，袁志祥 主编 陈学进，郑啸，程泽凯，王森玉副编. 数据结构（c语言版）例题详解与课程设计. 指导中国科学技术大学出版社附录#include #include #include #define n 8 /n为定的8个数#define m 2*n-1 /具有n个叶结点的哈夫曼树共有2n-1个结点*/#define 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; p2=p1; p1=j; else if(htj.wis2) s2=htj.wi ; p2=j; htp1.parent=htp2.parent=i; hti.lchild=p1; hti.rchild=p2; hti.wi=htp1.wi+htp2.wi; return ;/求huffmtree编码的函数void huffmcode(ctype coden+1) int i,p,s; ctype md; for(i=1;i=n;i+) md.ch=codei.ch; md.start = n+1; s=i; p=hti.parent; while(p!=0) md.start-; if(htp.lchild=s) md.bitsmd.start=0; else md.bitsmd.start =1; s=p; p=htp.parent; codei = md; /打印编码函数void output(ctype coden+1) file *fp; if (fp=fopen(huffmancode.txt,w)=null) printf(不能打开文件n); exit(0); fprintf(fp,n哈夫曼编码); int i,j; int wpl=0,count=0; printf(n); printf(n); puts( tt=); printf(n); printf(ttt叶结点tt哈夫曼编码); for(i=1;i=n;i+) printf(nttt %ctt,codei.ch ); for(j=1;j=n;j+) if(jcodei.start) printf( ); else if(codei.bitsj=0)|(codei.bitsj=1) printf(%c,codei.bitsj); count+; fputc(codei.bitsj,fp); fprintf(fp,n); wpl=wpl+count*hti.wi; count=0; printf(nn);printf(ttttwpl=%dn,wpl);fprintf(fp,n wpl=%d,wpl);puts( tt= );fclose(fp);void main()file *fp;if (fp=fopen(huffman.txt,w)=null) printf(不能打开文件n); exit(0); int i,j; int w; int flag=1; int choice; ctype coden+1; char tempn+1; int temp2n+1; printf(n); ( ntt 哈夫曼编码器 n);printf( ntt printf 主菜单 n);printf( ntt*n); printf( ntt* would you want to play? *n);printf( ntt* 1-yes and start *n);printf( ntt* 0-no and exit *n);printf( ntt*n);printf( ntt请选择菜单号: ); scanf(%d,&choice); printf(n); while(flag&(choice=1) choice = 0; for(i=1;i=m;i+)/初始化 hti.data =null; hti.wi=0; hti.parent = 0; hti.lchild = hti.rchild = 0; for(i=1;i=n;i+) codei.start = 0; codei.ch = null; for(j=1;j=n;j+) codei.bitsj = null; printf( ttplease input %d char(用空格隔开，以回车结束): n,n);/*输入字母*/ printf( tt); getchar(); scanf(%c %c %c %c %c %c %c %c,&temp1,&temp2,&temp3,&temp4,&temp5,&temp6,&temp7,&temp8); fprintf(fp,字符); for(i=1;i=n;i+) codei.ch =tempi; hti.data =tempi; fputc(tempi,fp); printf(nn); printf( ttplease input %d rate(用空格隔开，以回车结束): n,n);/*输入权值*/ fprintf(fp