问题描述

关于哈夫曼编码的程序运行时出错，我分析是由于cd定义出现了问题，导致后边cd[--start]出错

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
//w存放n个字符的权值（均>0），构造赫夫曼树 HT，并求出n个字符的赫夫曼编码 HC
printf("123");
system("pause");
int s1,s2,i,start;
int f=0;
char *cd;
int c;
HuffmanTree p=NULL;
if(n<=1) return;
int m;
m=2*n-1;
if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)))) //0号单元未用
exit(OVERFLOW);
for(p=HT,i=1;i<=n;++i,++p,++w){
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}//for
for(;i<=m;++i){ //建赫夫曼树
//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为是s1和s2
Select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}//for
//---------------从叶子到根逆向求每个字符的赫夫曼编码------------------

if(!(HC=(HuffmanCode)malloc(sizeof(HTNode))))
    exit(OVERFLOW);

if(!(cd=(char *)malloc(n*sizeof(char))))
    exit(OVERFLOW);
cd[n-1]= '';

for(int i=1;i<=n;++i){
    start=n-1;
    for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
        if(HT[f].lchild==c)
            cd[--start]='0';
        else
            cd[--start]='1';
          }
    if(!(HC[i]=(char *)malloc((n-start)*sizeof(char))))
        exit(OVERFLOW);

    strcpy(HC[i],&cd[start]);
}//for

free(cd);  //释放工作空间

}//HuffmanCoding