求助赫夫曼树编码的问题
程序是模仿严慧敏数据结构算法6.12和算法6.13的思路写的。程序执行后会无响应报错退出,于是调试了几次,只发现了cdlen的值会被减到负数,目前发现会减到-1和-2,请大家帮忙看下哪里出问题了,谢谢。程序代码:
#include <stdio.h> #include <malloc.h> #include <string.h> typedef struct { int weight; int parent,lchild,rchild; }htnode,*huffmantree; void select(huffmantree &HT,int n,int &s1,int &s2) { int i; int min_weight=65536; for(i=0;i<n;i++) { if(HT[i].parent==0) { if(HT[i].weight<min_weight) { min_weight=HT[i].weight; s1=i; } } } HT[s1].parent=1; min_weight=65536; for(i=0;i<n;i++) { if(HT[i].parent==0) { if(HT[i].weight<min_weight) { min_weight=HT[i].weight; s2=i; } } } HT[s2].parent=1; } void huffmancoding(huffmantree &HT,char ** &HC,int *w,int n) { //构造赫夫曼树 int i; int m=2*n-1; int s1,s2; huffmantree t; HT=t=(huffmantree)malloc((m+1)*sizeof(htnode)); if(!HT) return; for(i=1;i<=n;i++,w++,t++) { (*t).weight=*w; (*t).parent=0; (*t).lchild=0; (*t).rchild=0; } for(;i<=m;i++,t++) { t->weight=0; t->parent=0; t->lchild=0; t->rchild=0; } for(i=n;i<m;i++) { 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; } //求赫夫曼编码,从根出发遍历 HC=(char **)malloc((n+1)*sizeof(char *)); char cd[1000]; int p=m-1,cdlen=0,flag=0; for(i=0;i<m;i++) HT[i].weight=0; while(1) { if(HT[p].weight==0) { HT[p].weight=1; if(HT[p].lchild!=0) { p=HT[p].lchild; cd[cdlen++]='0'; } else if(HT[p].rchild==0) { HC[p]=(char *)malloc((cdlen+1)*sizeof(char)); if(!HC[p]) return; cd[cdlen]='\0'; strcpy(HC[p],cd); flag++; if(flag==n) break; } } else if(HT[p].weight==1) { HT[p].weight=2; if(HT[p].rchild!=0) { p=HT[p].rchild; cd[cdlen++]='1'; } } else if(HT[p].weight==2) { HT[p].weight=0; p=HT[p].parent; cdlen--; } } } void main() { int n,i; int *w,*p; huffmantree HT; char ** HC; printf("请输入待编码字符数n<n大于0>:"); scanf("%d",&n); printf("\n"); p=w=(int *)malloc(n*sizeof(char)); if(!w) return; printf("请输入待编码字符:\n"); for(i=1;i<=n;i++) scanf("%d",w++); huffmancoding(HT,HC,p,n); for(i=0;i<n;i++) printf("%s\n",HC[i]); }