数据结构课件精要（最终版）rar

typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; //建哈夫曼树 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) {if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用 for(p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0}; for(;i<=m;++i,++p) *p={0,0,0,0}; for(i=n+1;i<=m;++i) {Select(HT,i-1,s1,s2);//在Ht[1..i-1]选择parent为0且weight最小的两个结点 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=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]="\0"; for(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"; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd) }