#include#include #include using namespace std; typedef struct { int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree;//动态数组,元素为HTNode typedef char** HuffmanCode; //编码表,每一个元素都是一个编码,即char*方式存储的字符串 //初始化权重数组 void Init_Weight(int **w, int n){ while(!(*w=(int*)malloc((n+1)*sizeof(int)))); } //创建权值数组 void Create_Weight(int n, int *w){ int i, data; for(int i = 1;i <= n;i++){ cin>>data; w[i] = data; } } //初始化哈夫曼树 void Init_HuffmanTree(HuffmanTree *HT, int *w, int n){ int i; int m = 2*n-1; HTNode *p; while(!((*Ht)=(HTNode*)malloc(sizeof(HTNode)*(m+1)))); for(p = (*HT)+1, i = 1;i <= n;i++,p++){ p->weight = w[i]; p->parent = 0; p->lchild = 0; p->rchild = 0; } for(;i <= m;i++,p++){ p->lchild = 0; p->rchild = 0; p->parent = 0; p->weight = 0; } } //利用选择排序,循环一次即可得到最小的两个值 //在HT中选择parent为0,且权重最小的两个节点,返回他们的下标s1和s2 void Select(HuffmanTree HT, int i, int *s1, int *s2){ int mi1 = 0. mi2 = 0; int j = 1; for(;j <= i;j++){ if(HT[j].parent == 0){ if(mi1==0){*s1 = j; mi1++; continue;} if(mi2==0){*s2 = j; mi2++; continue;} if(HT[*s1].weight > HT[*s2].weight&&mi1 == 1&&mi2 == 1){ int vim = *s1, *s1 = *s2, *s2 = vim; } if(HT[j].weight < HT[*s1].weight){ *s2 = *s1, *s1 = j; continue; } if(HT[j].weight < HT[*s2].weight){ *s2 = j; } } } if(*s1 > *s2){int vim = *s1;*s1 = *s2;*s2 = vim;} } //创建哈夫曼树 void Create_HuffmanTree(HuffmanTree HT, int n){ int i = n+1; for(;i <= n*2-1;i++){ int s1 = 0, s2 = 0; Select(HT,i-1,&s1,&s2); HT[i].lchild = s1, HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; HT[s1].parent = i, HT[s2].parent = i; } } //初始化哈夫曼编码表 void Init_HuffmenCode(HuffmanTree *HC, int n){ while(!((*HC)=(HuffmanCode)malloc((n+1)*sizeof(char*)))); } void GetHuffmanCode(HuffmanCode HC, HuffmanTree HT, int n){ char ch[n]; ch[n-1] = ''; for(int i = 1;i <= n;i++){ int st = n-2, f = HT[i].parent, c = i; while(f!=0){ --st; if(HT[f].lchild==c)ch[st] = '0'; else ch[st] = '1'; c = f; f = HT[f].parent; } HC[i] = new char[n-st]; strcpy(HC[i], &ch[st]); } } //打印哈夫曼编码 void PrintCode(HuffmanCode HC, int n){ for(int i = 1;i <= n;i++){ cout< >n; //初始化权重数组 Init_Weight(&w, n); //创建权值数组 Create_Weight(n, w); //初始化哈夫曼树 Init_HuffmanTree(&HT, w, n); //创建哈夫曼树 Create_HuffmanTree(HT, n); //初始化哈夫曼编码表 Init_HuffmenCode(&HC, n); //求哈夫曼编码 GetHuffmanCode(HC, HT, n); //打印哈夫曼编码表 PrintCoder(HC,n); //释放空间 Destroy(&HT,&HC); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)