数据结构—赫夫曼编码的应用.docx
一、课题名称：赫夫曼编码的应用二、课题来源：课程组自拟三、课题类型：综合型四、目的意义：1. 学会编写实现树的各种操作的算法；2. 掌握树的定义、存储结构；3. 掌握哈夫曼树的建立和实现哈夫曼编码，解码及译码。五、基本要求：对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行 译码，输出电文字符串。根据输入的一串电文字符，建立赫夫曼树，并输出显示赫夫曼树。对输入的一串电文字符实现赫夫曼编码，为每个字符生成它们的编码。实现赫夫曼编码的解码。六、运行环境使用数据结构（严蔚敏，吴伟民，1997, C语言版）中给出的算法，将 二叉树存放在连续空间里（静态链表），空间的每个结点内仍有左子树、 右子树、双亲等指针。使用VC+6.0软件实现。七、课程设计步骤简介1 I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符 和n个权值，建立哈夫曼树。2 E：编码（Encoding）。利用已建好的哈夫曼树对输入的字符进行编码。3 D：译码（Decoding）。利用已建好的哈夫曼树对输入的字符进行译码。 编码算法：（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化 为权值w1,w2,.，wN构成n棵二叉树的集合F=T1,T2,.，Tn把它们保 存到结构体数组HTn中，其中Ti是按它们的ASCII码值先后排序。其中每 棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的 权值之和。（2）在HT1.i中选取两棵根结点的权值最小且没有被选过的树作为左右子 树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点 的权值之和。（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。.译码算法：译码的过程是分解电文中字符串，从根出发，按字符'0'，或'1'确定找左孩子或右孩 子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。八.流程图1赫夫曼树的初始化:否r结束2输入赫夫曼树的数据:3找出最小的两个数:4建赫夫曼树:5赫夫曼编码表:6编码:7解码:九.源程序#include <string.h>#include <stdio.h>#include <stdlib.h>#define n 6/定义字符数n为6#define m 2*n-1typedef structfloat weight;int lchild,rchild,parent;codenode;typedef codenode huffmantreem; /赫夫曼树结构typedef structchar ch;char bitsn+1;code;/编码结点 typedef code huffmancoden;/编码结构void inithf(huffmantree T) 一哈夫曼树的初始化 int i;for(i=0;i<m;i+)Ti.weight=0; /定义权值为零Ti.parent=-1;/ 定义父母为-1Ti.lchild=-1;/定 义左孩子为-1Ti.rchild=-1;/定 义右孩子为-1void inputhf(huffmantree T)/ 一输入哈夫曼树的树据int i;/输入 ifloat k;/定义单精度浮点数kprintf("请输入%d个结点的权值:",n);for(i=0;i<n;i+)scanf("%f",&k);/输入 kTi.weight=k;/权值为 kvoid selectmin(huffmantree T,int k,int *p1,int *p2) /找出最小的两个数，用 p1,p2返回int i;float small1=10000,small2=10000;for(i=0;i<=k;i+)if(Ti.parent=-1)/如果 Ti.parent=-1 if(Ti.weight<small1)/ 如果权值 <small1 small2=small1;/将 small2的值赋给 small1 small1=Ti.weight;/权值=small1 *p2=*p1;/*p2=*p1 *p1=i;/*p1=ielse if(Ti.weight<small2)/如 果权值 <small2small2=Ti.weight;/权值=small2 *p2=i;/*p2=iif(*p1>*p2)/如 果*?1>*?2int t=*p1;/将 t的值赋给*p 1并且输入*p1=*p2;/*p1=*p2*p2=t;/*p2=tvoid creathftree(huffmantree &T) 一建哈夫曼树int i,p1,p2;inithf(T); /初始化哈夫曼树inputhf(T); /输入数据for(i=n;i<m;i+)selectmin(T,i-1,&p1,&p2)/在所有权值中选择两个最小的数分别为p1,p2Tp1.parent=Tp2.parent=i;/p1 父母的值=p 2 父母的值=1Ti.lchild=p1;/将左孩子的值赋给p1Ti.rchild=p2;/将右孩子的值赋给p2Ti.weight=Tp1.weight+Tp2.weight;/i 的权值=p1 的权值权值+p2的权 值void creathfcode(huffmantree &T, huffmancode &H) / 一哈夫曼编码表int i,c,p,start;char cdn+1;/分配求编码的工作空间(每个字符编码结果最长n再加上'0') cdn='0'/编码结束符printf("请输入%d个字符作为电文内容:",n);for(i=0;i<n;i+)/逐个字符求哈弗曼编码Hi.ch=getchar();/getchar()在这里它只返回你输入字符串的第一个字符， 并把返回值赋值给Hi.chstart=n;c=i;while(p=Tc.parent)>=0)/如 果(p=Tc.parent)>=0cd-start=(Tp.lchild=c)?'0':T;/从根开始根据 0 1 选择找 lchild还是rchild,直至叶子点，解码出一个数据单位。再从根开始c=p;/将 c的值赋给pstrcpy(Hi.bits,&cdstart);/字符串复制函数(将cdstart的内容复制给Hi.bits)0printf("电文的哈夫曼编码如下：，for(i=0;i<n;i+)/逐个字符求哈弗曼编码printf("n%c %s",Hi.ch,Hi.bits);void zip(huffmancode &H,char *ch,char *s)/ 一编码int j=0;unsigned int i;/位域 bitfor(i=0;i<strlen(ch);i+)/判 断循环次数while(chi!=Hj.ch&&chj) j+;/如果 chi!=Hj strcat(&s0,Hj.bits);/连接j=0;printf("%s 的编码：",ch);puts(s);void uzip(huffmancode H,char *s,huffmantree T) /一解码int j=0,p;unsigned int i=0;/位域 bit i=0char chn+1;/分配求解码的工作空间 while(i<strlen(s)/判 断 i 是否<sp=m-1;while(Tp.lchild!二定1义/Tp.lchiJP 等于-1(if(si='(如果si=0 P=Tp.lchild;i+;指向左孩子else(p=Tp.rchild;i+否!/p 指向右孩子chj+=Hp.ch循环结束后 Hp.chK字符赋给 chj+chj='0'printf (魅解码为：，s)输出赋值后的字符puts(ch);/*/void main()(char ch=abcdef”, s36="0"huffmantree T;huffmancode H;赫夫曼编码表printf("ln 哈夫曼树n");creathftree(T);getchar();printf(编码表n");creathfcode(T,H);printf(编码n");zip(H,ch,s);printf(解码n");char ss="11101111110000110"uzip(H,ss,T);十.运行结果e: Documents and Se11 ingsAdministrator®.6晶码表feiiAG个字符作为电文内容:
