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

#include<>#include<>#include<>#include<>#defineMaxLength1000//输入文本最大长度#defineN20/*叶子结点数*/typedefintDataType;typedefstruct{charch;DataTypeweight;/*假设叶子权值为整型*/intlchild,rchild,parent;}Htnode;/*哈夫曼树结点类型*/typedefstruct{char*code;charleaf;intlength;/*编码的长度*/}CodeType;/*叶编码类型*/voidselectsort(Htnodehuftree[],intend,int*s1,int*s2){ intmin,min2; inti,j,k; for(i=1;i<=end;i++) { if(huftree[i].parent==-1)//找父节点是-1的点{ min=i; break; } } for(j=2;j<=end;j++) { if(huftree[j].parent==-1&&huftree[j].weight<huftree[min].weight) { min=j; } } *s1=min; for(i=1;i<=end;i++) { if(huftree[i].parent==-1&&i!=min) { min2=i; break; } } for(k=2;k<=end;k++) { if(k==min) continue; if(huftree[k].parent==-1&&huftree[k].weight<huftree[min2].weight) { min2=k; } } *s2=min2;}//voidHufcoding(Htnodehuftree[],CodeTypecd[],intw[],intn)voidHufcoding(Htnodehuftree[],CodeTypecd[],charchs[],intw[],intn){/*哈夫曼树存放在静态链表huftree中,w存放结点权重,n是叶子个数,最后的编码放在cd[]*/inti,j,k,s1,s2,s,m,f,c,sum;chartemp[N];/*暂存叶子编码字符串,最后需要转置*/m=2*n-1;/*计算哈夫曼树的结点总数*/charch;for(i=1;i<=n;i++)/*初始化每个结点自成一棵树*/{huftree[i].weight=w[i-1];huftree[i].lchild=huftree[i].rchild=huftree[i].parent=-1;huftree[i].ch=chs[i-1];} for(i=n+1;i<=m;i++)/*初始化*/ { huftree[i].weight=-1; huftree[i].lchild=huftree[i].rchild=huftree[i].parent=-1; } for(i=1;i<=n-1;i++)/*生成n-1个非叶子结点的循环*/ { selectsort(huftree,n+i-1,&s1,&s2);/*对数组huftree [1..n+i-1]中无双亲的结点权值进行排序,