数据结构学到霍夫曼编码了,自己结合课本编了一个,有个错误解决不了,求高手解决!!!
程序代码:
#include<iostream> #include<cstdlib> #include<cstring> using namespace std; typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void Select(HuffmanTree &HT,int s,int& s1,int& s2){ int k; int tag; for(k=1;k<=s;k++){ if(HT[k].parent!=0){ s1=k; tag=k+1; break; } } for(;k<=s;k++){ if(HT[k].parent!=0&&HT[k].weight<=HT[s1].weight) s1=k; } for(k=tag;k<=s;k++){ if(HT[k].parent!=0){ s2=k; break; } } for(;k<=s;k++){ if(HT[k].parent!=0&&HT[k].weight<=HT[s2].weight&&k!=s1) s2=k; } } int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ int m; int i; char* cd; HuffmanTree p; if(n<=1) return 0; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT, i=1;i<=n;++i,++p,++w){ p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p){ p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i){ int 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; } cout<<"huffman tree"<<endl; for(i=1,p=HT;i<=m;++i,++p){ cout<<p->weight<<"----"<<p->parent<<"----"<<p->lchild<<"----"<<p->rchild<<endl; } HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ int start=n-1; int f; int c; 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'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); return 0; } int main(){ HuffmanTree HT; HuffmanCode HC; int* w; int n; int m; HuffmanTree ht; cout<<"please input the value of n="; cin>>n; w=(int *)malloc(n*sizeof(int)); for(m=0;m<n;m++){ cout<<"please input the weight of the "<<m+1<<"value :"; cin>>w[m]; } HuffmanCoding(HT,HC,w,n); system("pause"); return 0; }
上边的代码有一处错误,已经标注出来,求高手解决,先谢过了~~~