赫夫曼编码注释的讲解
大家知道电报吧，就是这种编码。是一种前缀编码。大家可以去数据结构的书中看详细的内容，已经很清楚了饿
因为涉及到结构体和数据结构，所以比较难读懂，我就不细讲了。
#include <stdio.h>
#include <string.h> #include <stdlib.h> #include <windows.h> #define N 100 typedef struct hufmantnode{ int weight; int left,right,parent; }HUFNODE,*HUFTREE; int select_two_min(HUFTREE HT,int n,int *min,int *min_second){ //从树的节点中选出两个最小的。并且partent是零 int _min,_min_second; int i; int count=0; if(n<2) return -1; for(i = 1;i<=2*n-1;i++){ if(count == 2)break; else if(count == 0){ if(HT[i].parent == 0){_min = HT[i].weight;*min = i;count++;} else continue; } else if(count == 1){ if(HT[i].parent == 0){ if(HT[i].weight < _min){_min_second = _min;*min_second = *min;*min = i;_min = HT[i].weight;} else{_min_second = HT[i].weight;*min_second = i;count++;} } else continue; } } while(i<=2*n-1){ if(HT[i].parent) {i++;continue;} else if(HT[i].weight <= _min&&HT[i].weight!='0'){ _min_second = _min;*min_second = *min; _min = HT[i].weight;*min = i; } else if(HT[i].weight <= _min_second&&HT[i].weight!='0'){ _min_second = HT[i].weight;*min_second = i; } i++; } return 1; } int hufman(int *weight,int n,char ***HC,HUFTREE *tree)//这里用到了三级指针，因为想改变一个二级指针的地址，这里大家好好理解。有点绕，呵呵 { int i = 1; char **code; char* temp; HUFTREE HT = *tree; HT = (HUFTREE)malloc((2*n)*sizeof(HUFNODE));//对于赫夫曼树若有n个权重则会有2n-1个节点，这样我分配2n个节点，就把下标为0的节点舍去不用了。下面也有同样的例子。 if(!HT){ printf("no free mem\n");exit (-1); } while(i <=n )//对权重节点的初始化 {/*HT[i] = {weight[i-1],0,0,0};i++;*/ HT[i].weight=weight[i-1]; HT[i].parent=0; HT[i].left=0; HT[i].right=0; i++; } while(i<=2*n-1)//对要生成的节点的初始化 {/*HT[i] = {'0',0,0,0};i++;*/ //我原本这样赋值，但会有语法错，这样估计在c中是不允许的吧！ HT[i].weight='0'; HT[i].parent=0; HT[i].left=0; HT[i].right=0; i++; } for(i=n+1;i<=2*n-1;i++){ //第一个for实现树的建立 int min,min_second; select_two_min(HT,n,&min,&min_second); HT[min].parent = i; HT[min_second].parent = i; HT[i].weight = HT[min].weight+HT[min_second].weight; HT[i].left = min;HT[i].right = min_second; } *HC= (char **)malloc(sizeof(char *)*(n+1)); code = *HC; temp= (char*)malloc(sizeof(char)*(N+1));//临时存放编码结果 if(!temp) {printf("no free mem \n");exit (-1);} for(i=1;i<=n;i++){ int k=N; int p;int z; code[i] = (char *)malloc(N*sizeof(char)); temp[k] = '\0'; for(z=i,p = HT[z].parent;p != 0;z = p,p = HT[p].parent){ if(HT[p].left == z) temp[--k] = '0'; else temp[--k] = '1'; } strcpy(code[i],temp+k);//将编码存放到hunmancode【i】中。 } return 1; } int main(void) { int weight[26]; //定义一个权重数组，存放26个英文字母 int n = 26; char **hufmancode;//存放转换后的编码。是一个二级指针，每一个指针放一个字符串。 HUFTREE HT; //定义赫夫曼树 int i; char temp = 'a'; for(i=0;i<n;i++) weight[i] = (int)(temp++); //初始化权重数组，赋值为26个字母 putchar('\n'); hufman(weight,n,&hufmancode,&HT); for (i = 1;i<=n;i++)//打印结果 printf("%c\t\t%s\n",weight[i-1],hufmancode[i]); system("pause"); } //select_two_min 这个函数希望大家好好看看，如果你会从一堆数中找到两个最小数，那么会很容易读懂，原理是一样的，不过我个人认为自己的算法（先找两个数做基准，再循环比较，进行更新）不是很高效，谁有好方法可以给我留言。呵呵