课程设计（论文）-哈夫曼编码及其应用.doc

图论论文图论论文 论文题目论文题目 学生姓名学生姓名 专业班级专业班级 学学 号号 邮邮 箱箱 20152015 年年 1212 月月 2020 日日 目 录 摘要摘要 .1 第一章第一章 哈夫曼树哈夫曼树 .2 1.1 哈夫曼树的基本概念.2 第二章第二章 哈夫曼算法构造哈夫曼算法构造 .3 2.1 哈夫曼树的构造算法.3 2.2 举例说明其构造过程.3 第三章第三章 哈夫曼树的应用哈夫曼树的应用 .5 3.1 用于通信编码.5 第四章第四章 运行结果运行结果 .6 第五章第五章 总结总结 .7 参考文献参考文献:7 附录附录 .8 哈夫曼编码及其应用哈夫曼编码及其应用 摘要摘要 在现代社会，通信的发展，使得现代社会更加丰富多彩，我们可以随时随 地在任何 地方了解到世界各地的信息，而这又必须依赖信息的传递。在信息化 高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息 在传递的过程中，能够保持节省性和保密性和无损性，而著名的霍夫曼编码就 能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压就时相当有必 要的，我们用 c+对霍夫曼编码给出简单的算法以实现对文件的压缩和解压。 哈夫曼树是由哈夫曼于 1951 年所创立并改进的,他本人也根据哈夫曼树提出了 相应的编码.由于哈夫曼树是具有最小加权路径长度的二叉树,故哈夫曼编码能 产生较短的码文.基于这个优势,在信息化高度发达的当今社会,对信息的传递也 有着较高要求的我们,希望信息在传递过程中,能够保持节省性和保密性,哈夫曼 编码则很好的满足了这方面的要求,因而对其的研究是相当有必要的. 关键字：哈夫曼树，二叉树，信息压缩编码关键字：哈夫曼树，二叉树，信息压缩编码 2 第一章第一章 哈夫曼树哈夫曼树 1.1 哈夫曼树的基本概念哈夫曼树的基本概念 首先要了解关于树的一些概念。 定义定义 1.1 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路, 称为路径. 定义定义 1.2 若将树中结点都赋给一个具有某种含义的数值,则这个数值称为该结 点的权. 定义定义 1.3 由根结点到所有叶结点的路径长度之和称为二叉树的路径长度. 定义定义 1.4 从根结点到叶结点的路径长度与相应结点权值之积的和叫做二叉树的 带权路径长度. 定义定义 1.5 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构 造的具有最小带权路径长度的二叉树. 如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树 有个带权值的叶结点,那么,二叉树的带权路径长度应记为:n , n k kk lwwpl 1 其中为第个叶结点的权值;为第个叶结点的路径长度.如下图： k wk k lk 图1 . 1 . 1 在图中,即为根结点,而则为叶结点,若的权值分别为则1 . 1 . 1acb,cb,4 , 3 二叉树路径长度为 2,二叉树的带权路径长度为 7,即.71413wpl 例例 下面我们结合实例来说明哈夫曼树.如图 1.2.2 )(a)(b)(c 2 . 2 . 1图 3 ;4922351638 3 ;4132352618 2 ;4222252628 1 wpl wpl wpl 按照的计算方法,经过计算比较后,我们发现,图的值最wpl2 . 2 . 1)(bwpl 小,它即为哈夫曼树. 由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同 的带权路径长度.那么如何找到带权路径长度最小的二叉树呢？根据哈夫曼树的 定义,一棵二叉树要使其值最小,必须使权值越大的叶结点越靠近根结点,wpl 而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具 有最小的带权路径长度,这是生成算法的一种基本思想. 第二章第二章 哈夫曼算法构造哈夫曼算法构造 哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径 长度的二叉树.尽管哈夫曼树可以通过比较后得出,可是在运算过程中往往wpl 会出现一些问题,使其实现起来并不容易,因而我们可以应用编程来有效地解决 这个问题. 2.1 哈夫曼树的构造算法哈夫曼树的构造算法 为了构造权值为的哈夫曼树,哈夫曼提出了一种构造算法,现 n wwww, 321 将其陈述如下: 步骤步骤 1 根据题目给定的个权值构造有下列棵二叉树的集合 n n wwww, 321 n ,其中每棵二叉树中只有一个带权为的根结点,其 n ttttf, 321 i t i w 左右树均为空; 步骤步骤 2 在中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二 f 叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之 和; 步骤步骤 3 在中删除这两棵树,同时将新得到的二叉树加入中;ff 步骤步骤 4 重复步骤 2 和步骤 3,直到只含有一棵树为止,这棵树便是哈夫曼树.f 2.2 举例说明其构造过程举例说明其构造过程 假设叶结点权值集合为的哈夫曼树的构造4 , 3 , 2 , 1w 第一步 我们根据给定的 4 个权值来构造 4 棵二叉树的集合.f 4 第二步 在找出权值中最小的两个作为新二叉树的左右子树,且置新的二f 叉树根结点权值是其左右结点权值之和. 第三步 将次小的树与新生成的树再作为左右子树生成权值为 6 的新树; 第四步 再次将权值为 4 的树在同上一个权值为 6 的树再次生成新树即可. 从以上过程可以计算出这棵二叉树的带权路径长度为 19. 5 第三章第三章 哈夫曼树的应用哈夫曼树的应用 3.1 用于通信编码用于通信编码 在电报通讯中,电文是以二进制的序列传送的.在发送端需要将电文中的1 , 0 字符序列转换成二进制的序列,而在接收端又需要把接收的序列转换成对1 , 01 , 0 应的字符序列. 例如给出一段电文: tasaaatsatcastcast 电文中只使用了这四种字符,各字符出现的频度分别是,若进行tsac,5 , 4 , 7 , 2 等长编码,需要两位二进制位,可依次编码为 11: ,10: ,01: ,00:tsac 则所发电文是: 11011001 01 0111 100111 00011011 00011011 采用不等长编码要避免译码的二义性.例如,字符,10:,001:,010:,01:dcba 的编码是字符的编码的前缀部分.这样对于代码串,既是a01b0100101001 的代码,也是和的代码,因此,这样的编码不能保证译码的唯一性.aacabdbda 所以,若对某一字符集进行不等长编码,可用该字符集中的每个字符作为叶 子结点生成一棵编码二叉树,且约定左子树表示字符,右子树表示字符,则可 0 1 以用从根结点到叶结点路径上的分支字符组成的字符串作为该叶子结点字符的 编码.为了获得传送电文的最短长度,可将每个字符出现的频率作为字符结点的 权值赋给该结点,从而求出此树的最小带权路径长度就等于求出了传送电文的最 短长度. 因此,求传送电文的最短长度问题就转化为求由字符集中所有字符作为叶子 结点和由字符的出现频度作为其权值所产生的哈夫曼树的问题. 例如,各字符出现的概率为,对各概率tsacd,185,184,187,181 取整,得到各字符的权值,利用它们构造哈夫曼树,如图所示,5472， i w3 . 1 . 3 则各字符的编码为:.10:111:0:110:tsac， 6 1 . 2 . 3图 在构造了哈夫曼树之后,为求编码需从叶子结点出发走一条从叶子到根的路径, 而为求译码需从根出发走一条根到叶子的路径.故哈夫曼编码成功地应用于离散 数学与数据结构中的最优二叉树寻找. 第四章第四章 运行结果运行结果 图 4.1 编码界面 7 图 4.2 解码界面 第五章第五章 总结总结 程序经运行得到很好的实现,但程序中仍存在一些不足之处,需要再加以改 进.通过此次论文设计很好的增强了我对编程及二叉树理论的认识和对 c+软件 的应用能力,也是将理论知识运用于解决实际问题的一次新尝试.并且对图论这 门学科有更深刻的认识，感觉应用范围非常广泛。通过本课程的学习，我也认识了 自己还有很多不足，需要进一步学习的地方，在接下来的学习中我会花更多时间，来认真 加深知识理解与运用。 参考文献参考文献: 1 张清华.图论及其应用.m.北京:清华大学出版社,2013:134-231. 2 严蔚敏.数据结构 m .北京:清华大学出版社,1995:145-147. 3 谭浩强.c+面向对象程序设计 m.北京:清华大学出版社,2007:134-231. 8 附录附录 #include #include #include #define maxlen 100 typedef struct huffmantree char ch; /*键值*/ int weight,mark; /*weight 为权值,mark 为标志域*/ struct huffmantree *parent,*lchild,*rchild,*next; hftree,*linktree; /*整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数 */ linktree tidycharacter(char character) int i=0; linktree tree,ptr,beforeptr,node; /*链式 ,tree 为头结点,beforeptr 为 ptr 的前一结点,node 为 新申请的结点*/ tree=(linktree)malloc(sizeof(hftree);/*创建单链表的头结点*/ if(!tree)return null; tree-next=null; /* 头结点为空,且后续结点为空*/ for(i=0;characteri!=0i+) /*遍历直到字符串结束为止*/ ptr=tree; beforeptr=tree; node=(linktree)malloc(sizeof(hftree); /*新申请结点 node*/ if(!node)return null; node-next=null; node-parent=null; node-lchild=null; node-rchild=null; /*置空*/ node-mark=0; node-ch=characteri; node-weight=1; if(tree-next=null) tree-next=node; /*头结点的下一结点为空,连接 node*/ else ptr=tree-next; while(ptr beforeptr=beforeptr-next; /*后移*/ 9 if(ptr free(node); /*释放 node 结点的存储空间*/ else /*新结点与表中结点不相同,将新结点插入链表后*/ node-next=beforeptr-next; beforeptr-next=node; /*node 连接在 beforeptr 之后*/ return tree; /*将整理完的字符串按出现次数从小到大的顺序排列 */ linktree taxisnode(linktree tree) linktree head,ph,pt,beforeph; /*head 为新链表的表头结点*/ head=(linktree)malloc(sizeof(hftree);/*创建新链表的头结点*/ if(!head)return null; head-next=null; /*新结点的头结点为空,后续结点也为空*/ ph=head; beforeph=head; while(tree-next) pt=tree-next;/*取被操作链表的首元结点*/ tree-next=pt-next; pt-next=null; /*取出 pt 所指向的结点*/ ph=head-next; beforeph=head; if(head-next=null) head-next=pt;/*创建当前操作链表首元结点*/ else while(ph beforeph=beforeph-next; pt-next=beforeph-next; beforeph-next=pt; 10 free(tree); return head; /*用排完序的字符串建立霍夫曼树 */ linktree createhftree(linktree tree) linktree p,q,newnode,beforep; for(p=tree-next,q=p-next;p!=nullp=tree-next,q=p-next) tree-next=q-next; q-next=null; p-next=null; newnode=(linktree)malloc(sizeof(hftree);/*申请新结点作为霍夫曼树的中间结*/ if(!newnode)return null; newnode-next=null; newnode-mark=0; newnode-lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/ newnode-rchild=q; p-parent=newnode; q-parent=newnode; newnode-weight=p-weight+q-weight; p=tree-next; beforep=tree; if(p!=null beforep-next=newnode; else while(p!=null beforep=beforep-next; newnode-next=beforep-next; beforep-next=newnode; return (tree-next); /*对霍夫曼树进行编码 */ void huffmancoding(linktree tree) 11 int index=0; char *code; linktree ptr=tree; code=(char *)malloc(10*sizeof(char);/*此数组用于统计霍夫曼编码*/ printf(“字符以及它的相应权数-霍夫曼编码nn“); if(ptr=null) printf(“霍夫曼树是空的!n“); exit(0); else while(ptr-lchild ptr=ptr-lchild; if(!ptr-lchild codeindex=0; printf(“tw%c=%dttt“,ptr-ch,ptr-weight); for(index=0;codeindex!=0;index+) printf(“%c“,codeindex); printf(“n“); ptr=tree; index=0; if(ptr-rchild codeindex+=1; if(!ptr-lchild codeindex+=0; printf(“tw%c=%dttt“,ptr-ch,ptr-weight); for(index=0;codeindex!=0;index+) printf(“%c“,codeindex); printf(“n“); 12 ptr=tree; index=0; if(ptr-lchild-mark=1 ptr=tree; index=0; printf(“n“); free(code); /*解码 */ void decode(linktree tree,char code) int i=0,j=0; char *char0_1; linktree ptr=tree; char0_1=(char *)malloc(10*sizeof(char);/*此数组用于统计输入的 0、1 序列*/ printf(“霍夫曼编码-相应字符nn“); for(j=0,ptr=tree;codei!=0j=0,ptr=tree) for(j=0;codei!=0j+,i+) if(codei=0) ptr=ptr-lchild; char0_1j=0; if(codei=1) ptr=ptr-rchild; char0_1j=1; if(!ptr-lchild for(j=0;char0_1j!=0;j+) printf(“%c“,char0_1j); printf(“tt%cn“,ptr-ch); 13 if(codei=0 printf(“没有与最后的几个 0、1 序列：%s 相匹配的字符!n“,cha