赫夫曼树编码.docx

#include stdio.h #include malloc.h #include string.h #include stdlib.h #define n 6//n个叶子结点 #define m 2 * n -1//m个结点 #define size sizeof(HTNode) typedef struct { unsigned int weight; unsigned int parent; unsigned int lchild; unsigned int rchild; }HTNode, * HuffmanTree; typedef char ** HuffmanCode; //赫夫曼树初始化 void inithf(HuffmanTree T) { int i; HuffmanTree p; T = (HuffmanTree)malloc((m + 1) * size);//动态分配数组孀储 for( i = 1; i = m ; p++, i++) { p = T + i; p -weight = 0; p -parent = 0; p -lchild = 0; p -rchild = 0; } } //输入权重 void inputhf(HuffmanTree T) { int i; int w; for(i = 1; i = n; i++) { scanf(%d, w); T[i].weight = w; } } //得到权值最小的两个结点 void selectmin(HuffmanTree T, int k, int *s1, int *s2) { int i = 1; HuffmanTree p = T; int small1, small2; small1 = p[i].weight; small2 = small1; for(; i = k; i++) { if(T[i].parent == 0) if(T[i].weight small1) { small2 = small1; small1 = T[i].weight; *s2 = *s1; *s1 = i; } else if(T[i].weight small2) { small2 = T[i].weight; *s2 = i; } } } //建赫夫曼树 void creathftree(HuffmanTree T) { int i, s1,s2; inithf(T); inputhf(T); for(i = n + 1; i = m; i++) { selectmin(T, i - 1, s1, s2);//得到权值最小的两个结点 T[s1].parent = i; T[s2].parent = T[s1].parent; T[i].lchild = s1; T[i].rchild = s2;//建树 T[i].weight = T[s1].weight + T[s2].weight;//加入新的权值 } } //遍历赫夫曼树 void show(HuffmanTree T) { int i; printf(weight\tparent\tlchild\trchild\n); for(i = 1; i = m; i++) { printf(%d \t%d\t%d\t%d, (T + i) - weight, (T + i) - parent, (T + i) - lchild, (T + i) - rchild); printf(\n); } } //从叶子到根逆向求每个字符的赫夫曼编码 void creathfco