求助!有关赫夫曼树的
有人帮忙把这个改成C语言的么,我不会C++,只会C,代码是求赫夫曼树求带权路径长度的程序代码:
#include<cstdio> #include<cstdlib> typedef struct{ int weight; int flag; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 void Select(HuffmanTree HT, int num, int &s1, int &s2){ //s1是最小值,s2是次小值 int minx = 1<<30; int mminx = 1<<30; for(int i = 1; i <= num; ++i){ if(HT[i].weight < minx && !HT[i].flag){ mminx = minx; s2 = s1; minx = HT[i].weight; s1 = i; } else if(HT[i].weight < mminx && !HT[i].flag){ mminx = HT[i].weight; s2 = i; } } HT[s1].flag = HT[s2].flag = -1; } int L,length; void AllLength(HuffmanTree HT, int m){ length++; if (!HT[m].lchild && !HT[m].rchild) { L += HT[m].weight * (length-1); } else{ int m1 = HT[m].lchild; AllLength(HT,m1); length--; int m2 = HT[m].rchild; AllLength(HT,m2); length--; } } void HuffmanCoding(HuffmanTree &HT,int *w, int n,int m){ //w存放n个字符的权值(均>0),构造赫夫曼树HT HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用 HuffmanTree p = HT + 1; for(int i = 1; i <= n; ++i,++p){ p->weight = w[i]; p->parent = p->lchild = p->rchild = p->flag = 0; } for(int i = n+1; i <= m; ++i,++p){ p->weight = p->parent = p->lchild = p->rchild = p->flag = 0; } int s1,s2; for(int i = n + 1; 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; } } int main(){ int n; int w[1010]; while(scanf("%d",&n)!=EOF){ int m = 2 * n - 1; HuffmanTree T; for(int i = 1; i <= n; ++i){ scanf("%d",&w[i]); } HuffmanCoding(T,w,n,m); length = L = 0; AllLength(T,m); free(T); printf("%d\n",L); } return 0; }