数据结构_哈弗曼树编码.doc

#include#include#include#include#define MaxLength 1000 /输入文本最大长度 #define N 20 /* 叶子结点数 */typedef int DataType ;typedef struct char ch; DataType weight; /*假设叶子权值为整型*/ int lchild,rchild,parent;Htnode; /* 哈夫曼树结点类型 */typedef struct char *code; char leaf ; int length; /*编码的长度*/CodeType ; /* 叶编码类型 */ void selectsort(Htnode huftree,int end,int *s1,int* s2)int min,min2;int i,j,k;for(i=1;i=end;i+)if(huftreei.parent=-1)/找父节点是-1的点 min=i;break;for(j =2;j=end;j+)if(huftreej.parent=-1 & huftreej.weighthuftreemin.weight)min=j;*s1=min;for(i=1;i=end;i+)if(huftreei.parent=-1& i!=min)min2=i;break;for(k=2;k=end;k+)if(k=min)continue;if(huftreek.parent=-1 & huftreek.weighthuftreemin2.weight)min2=k;*s2=min2; /void Hufcoding(Htnode huftree , CodeType cd , int w ,int n)void Hufcoding(Htnode huftree, CodeType cd ,char chs,int w ,int n) /*哈夫曼树存放在静态链表huftree中,w存放结点权重,n是叶子个数,最后的编码放在cd*/ int i,j,k,s1,s2,s,m,f,c,sum; char tempN; /*暂存叶子编码字符串，最后需要转置 */ m=2*n-1; /*计算哈夫曼树的结点总数 */ char ch; for(i=1;i=n;i+) /* 初始化每个结点自成一棵树 */ huftreei.weight=wi-1; huftreei.lchild=huftreei.rchild=huftreei.parent=-1; huftreei.ch=chsi-1; for(i=n+1;i=m;i+) /*初始化*/ huftreei.weight=-1;huftreei.lchild=huftreei.rchild=huftreei.parent=-1;for(i=1;i=n-1;i+) /* 生成n-1个非叶子结点的循环 */ selectsort(huftree,n+i-1,&s1,&s2); /* 对数组 huftree 1.n+i-1中无双亲的结点权值进行排序，s1,s2将是 无双亲且权重最小的两个结点下标 */ sum=huftrees1.weight+huftrees2.weight;/计算它的权重 huftreen+i.weight=sum;/ huftrees1.parent=huftrees2.parent=n+i; huftreen+i.lchild=s1; /左孩子节点指向S1 huftreen+i.rchild=s2;/右孩子节点指向S1 for(i=1;i=0) cdi.codek+=tempc-;/*将temp转置到cd中 */ cdi.leaf=huftreei.ch; cdi.length=k; /*end for */void encode(char text,CodeType cd,char bits)/把输入的字符按所编的哈夫曼树的规则译成二进制码 int i,j,k,index=0;int len=strlen(text);memset(bits,0,sizeof(bits);/把一片连续的内存填充第二个参数的值 char ch;for(i=0;ilen;i+)ch=texti;j=1;while(ch!=cdj.leaf)j+;for(k=0;kcdj.length;k+)bitsindex+=cdj.codek;bitsindex=0;void decode(char bits,Htnode* huftree,char forText)/解码过程 /找根节点 int root=1,cur=1;while(cur!=-1) root=cur;cur=huftreecur.parent;int index=0;int len=strlen(bits);int j=0;char c;Htnode cNode=huftreeroot;for(j=0;jlen;j+)c=bitsj;if(c=0)cNode=huftreecNode.lchild;/左孩子节点当叶节点 elsecNode=huftreecNode.rchild;/右孩子节点当叶节点 if(cNode.lchild=-1&cNode.rchild=-1)forTextindex+=cNode.ch;cNode=huftreeroot;forTextindex=0;int main()char textMaxLength; /输入文本printf(请输入测试文本:); scanf(%s,text);printf(测试文本如下:%snn,text); int length=strlen(text);/计算输入字符串长度 int wtemplength; /权重统计 int i;for(i=0;ilength;i+)wtempi=0;char ctemplength; /存放字符int n=0; /字符个数（叶子节点个数）char ch;int j;for(i=0;ilength;i+)ch=texti;j=0;while(ch!=ctempj&jn)j+;if(j=n) /从未出现的字符 ，权重值都一样为1 ctempj=ch;wtempj=1;n+;else /已经出现的字符，权重值就加1 wtempj+;char cn;int wn;for(i=0;in;i+)ci=ctempi;wi=wtempi;CodeType cdn+1;/叶子结点 Htnode huftree2*n;/哈夫曼数 Htnode* node=huftree;Hufcoding(huftree,cd,c,w,n);/创建哈夫曼树/打印字符不等长编码信息 printf(测试文本中各字符的编码如下:n); for(int i=1;i=n;i+)printf(%c:,cdi.leaf);printf(%s ,cdi.code);int bitmaxLength=1+n*(int)floor(log(n)/log(2);char bi