哈夫曼树编码的问题,求大神赐教
(1)输入一串包含abcdefgh 8种字符的字符串,统计并输出每种字符出现的次数,并据此创建相应的哈夫曼树(2)输出每种字符的哈夫曼编码
(3)输入一个字符串,其可能出现的字符有abcdefgh 8种,输出该字符串的编码结果
#include<stdio.h> #include<stdlib.h> #include <string.h>#define N 6 /* 叶子结点数 */#define MAX_NODE 2*N-1 /* 总结点数=2n-1 */ #define M MAX_NODE+1 /* 数组大小=总结点数+1,下标0废弃 */typedef struct{ int Weight; /* 权值域 */ int Parent , Lchild , Rchild ;} HTNode ;void main(){ int i; char *MyHC[M]; //存放每个叶子结点Huffman编码的指针 HTNode MyHT[M]; void Create_Huffman(int n, HTNode HT[ ], int m); //n叶子结点数,m总结点数(2*n-1) void Huff_coding( int n, HTNode HT[ ], int m,char *HC[]); /* m应为n+1,编码的最大长度n加1 */ Create_Huffman(N, MyHT, M); printf("Huffman树结点数组HT[]:\n"); printf("HT[i]\t权\t父\t左\t右\t\n"); for (i=1; i<M; i++) //输出Huffman结点数组MyHT[] printf("%d\t%d\t%d\t%d\t%d\n",i,MyHT[i].Weight,MyHT[i].Parent,MyHT[i].Lchild,MyHT[i].Rchild); Huff_coding(N, MyHT, M, MyHC); printf("\n Huffman编码如下:\n"); printf("权值:\t"); for (i=1; i<N+1; i++) printf("(%d)%d\t",i,MyHT[i]); printf("\n"); printf("编码:\t"); for (i=1; i<N+1; i++) printf("%s\t",MyHC[i]); printf("\n");} void Create_Huffman(int n, HTNode HT[ ], int m) //n叶子结点数,m总结点数(2*n-1) /* 创建一棵叶子结点数为n的Huffman树 */{ int w , k , j ; for (k=1 ; k<m ; k++) //初始化HT[ ]向量 { if (k<=n) //创建n个叶子结点的权值 { printf("请输入权值W%d即HT[%d]=:",k,k); scanf("%d", &w) ; HT[k].Weight=w ; } /* 输入时,所有叶子结点都有权值 */ else HT[k].Weight=0; /* 非叶子结点没有权值 */ HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ; } /* 初始化向量HT */ for (k=n+1; k<m ; k++) { int w1=32767 , w2=w1 ; /* w1 , w2分别保存权值最小的两个权值 */ int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标*/ for (j=1 ; j<=k-1 ; j++) { if (HT[j].Parent==0) /* 尚未合并 */ { if (HT[j].Weight<w1)/* 找到权值最小的两个值及其下标 */ { w2=w1 ; p2=p1 ; w1=HT[j].Weight ; p1=j ; } else if (HT[j].Weight<w2) { w2=HT[j].Weight ; p2=j ; } } } HT[k].Lchild=p1 ; HT[k].Rchild=p2 ; HT[k].Weight=w1+w2 ; HT[p1].Parent=k ; HT[p2].Parent=k ; }//end for}void Huff_coding(int n , HTNode HT[] , int m,char * HC[]) /* m应为n+1,编码的最大长度n加1 */{ int k , sp ,fp, p ; char *cd;// , *HC[M] ; cd=(char *)malloc(m*sizeof(char)) ; /* 动态分配求编码的工作空间 */ cd[n]='\0'; /* 编码的结束标志 */ for (k=1 ; k<n+1 ; k++) /* 逐个求字符的编码 */ { sp=n ; p=k ; fp=HT[k].Parent ; for ( ; fp!=0 ;p=fp , fp=HT[p].Parent) /* 从叶子结点到根逆向求编码,逐次压站,正向输出即为正向编码 */ if (HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)) ; /* 为第k个字符分配保存编码的空间 */ strcpy(HC[k] , &cd[sp]) ; } free(cd) ;}