数据结构 C++ 建立哈夫曼树

#include<stdio.h> #include<malloc.h> #include<string.h> #include <cstdlib> #include <iostream> int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char *HuffmanCode; //动态分配数组存储赫夫曼编码表 void Select(HuffmanTree HT,int n) { int i,j,temp; for(i = 1;i <= n;i++) if(!HT[i].parent){s1 = i;break;} for(j = i+1;j <= n;j++) if(!HT[j].parent){s2 = j;break;} for(i = 1;i <= n;i++) if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j <= n;j++) if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; if(s1>s2) { temp=s1; s1=s2; s2=temp; } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) { // w存放n个字符的权值(均>0)，构造赫夫曼树HT， int i, j; // 并求出n个字符的赫夫曼编码HC char *cd; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i<=n; i++)//初始化 { HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i<=m; i++) //初始化 { HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } puts("\n赫夫曼树的构造过程如下所示："); printf("HT初态:\n 结点\tweight\tparent\tlchild\trchild"); for (i=1; i<=m; i++) printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild); for (i=n+1; i<=m; i++) // 建赫夫曼树 { // 在HT[1..i-1]中选择parent为0且weight最小的两个结点， 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; printf("\nselect: s1=%d s2=%d\n", s1, s2); printf(" 结点\tweight\tparent\tlchild\trchild"); for (j=1; j<=i; j++) printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild); } //-----------从叶子到根逆向求每个字符的赫夫曼编码 ------ cd = (char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;i++) { int start=n-1; for(unsigned int 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)); for(int j=start;j<=n;j++) HC[i][j-start]=cd[j]; } free(cd); } // HuffmanCoding int main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i; printf("--------------------------\n",n); printf(" 哈夫曼树的建立 \n",n); printf("--------------------------\n",n); puts("请输入结点数:"); scanf("%d",&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf("请输入%d个结点的权值\n",n); for(i = 0;i < n;i++) scanf("%d",&w[i]); HuffmanCoding(HT,HC,w,n); puts("\n各结点的赫夫曼编码为:"); for(i = 1;i <= n;i++) printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); system("PAUSE"); return EXIT_SUCCESS; }