目录

存储结构赫夫曼树创建赫夫曼编码

存储结构

typedef struct { int weight; int parent, lchild, rchild; }HTNode,*HuffManTree; typedef char* * HuffManCude; Status min(HuffManTree& HT, int k) {//从HT数组中选出最小且parent为0的元素 int min_weight;//用来存放weight最小的值 int min;//用来存放weight值最小的序号 int i = 1; //记录第一个元素，用作后面比较的标准； while (HT[i].parent != 0) i++; min = i; min_weight = HT[i].weight; //寻找最小元素 for (;i < k + 1;i++) { if (HT[i].weight < min_weight && HT[i].parent == 0) { min = i; min_weight = HT[i].weight; } } //选出最小元素后将该元素的parent值赋1，使得下一次比较将其排除在外； HT[min].parent = 1;//刚开始编写的时候这里min直接写成i，一直报错 //仔细分析不难发现，为i时，min=i，但是后面i还会继续循环改变，则min！=i； return min; } Status min_2(HuffManTree& HT, int k,int &min1,int &min2) {//从HT数组的前k个元素中选出最小的两个，并返回相应的序号 min1 = min(HT, k); min2 = min(HT, k); return OK; }

赫夫曼树创建

根据n个权值 {w1, w2, ⋯,wn}，构造成n棵二叉树的集合F={T1, T2, ⋯,Tn}，其中每棵二叉树只有一个权值为wi的根结点，没有左、右子树；在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和；在F中删除这两棵树，同时将新得到的树加入F中；重复2、3，直到F只含一颗树为止。 Status CreatHuffManTree(HuffManTree& HT, int *w,int n) {//构造赫夫曼树 //将a划分为n个子集； int m = 2 * n - 1; HT = (HuffManTree)malloc((m+1) * sizeof(HTNode)); HuffManTree p; int i; for ( i = 1;i < n + 1;++i) { w++; HT[i] = { *w,0,0,0 }; } for (;i < m + 1;++i) { HT[i] = { 0,0,0,0 }; } //构建赫夫曼树 int s1, s2;//用于记录最小两元素的序号 for (int i = n + 1;i < m + 1;i++) { min_2(HT, i - 1, s1, s2); HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1;HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } return OK; }

赫夫曼编码

Status HuffManCoding(HuffManTree HT, HuffManCude& HC,int n) {//从叶子到根逆向求每个字符的赫夫曼编码 HC = (HuffManCude)malloc((n+1) * sizeof(char*)); char* cd = (char*)malloc(n * sizeof(char)); cd[n - 1] = '\0'; int start = 0; //逐个字符求赫夫曼编码 for (int i = 1;i < n + 1;++i) { start = n - 1; for (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)); strcpy(HC[i], &cd[start]); } free(cd); return OK; }

完整代码