哈夫曼编码
实验六：哈夫曼编码
已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
综合训练：试编写一个将百分制分数转换为五级分制的程序。要求其时间性能尽可能好（即平均比较次数尽可能少）。假设学生成绩的分布情况如下：
| 分数 |
0-59 |
60-69 |
70-79 |
80-89 |
90-100 |
| 比例 |
0.05 |
0.15 |
0.4 |
0.3 |
0.1 |
源码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0
#define OK 1
typedef int Status;
typedef struct //声明赫夫曼树的结点
{
int weight;
int parent;
int lchild;
int rchild;
} Htnode, *Huffmantree;
typedef char ** Huffmancode;//相当于声明一个二维数组，来记录每个权值对应的编码。
void Select (Huffmantree &HT, int t, int &p, int &q); //选择结点中权值最小的两个结点，用p,q来返回。
void creathuffmantree(Huffmantree &HT, Huffmancode &HC, int *w, int n) //创建赫夫曼树。
{
int m, i, p, q, j, start, s;
if (n <= 1)
return;
m = 2 * n - 1; //当n大于1时，就需要2*n-1个结点
HT = (Huffmantree)malloc(sizeof(Htnode) * (m + 1)); //因为0不存东西，而从1开始存，所以申请m+1个空间。
for (i = 1; i <= n; i++) //对叶子结点进行初始化，除权之外全赋值为0。
{
HT[i].weight = w[i - 1];
HT[i].parent = 0;
HT[i].rchild = 0;
HT[i].lchild = 0;
}
for (i = n + 1; i <= m; i++) //对非叶子结点进行初始化，所有的值全为0
{
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].rchild = 0;
HT[i].lchild = 0;
}
for (i = n + 1; i <= m; i++) //这是创建树的主要步骤，找出权值和最小的两棵树，再把它们合并成一棵树，依次进行，知道走后还剩仅有的一棵树。
{
Select(HT, i - 1, p, q); //这是选择权值最小的两棵树的函数，并用p,q来返回，在上面已经声明过。
HT[i].weight = HT[p].weight + HT[q].weight; //对刚合并的新树的根结点的权值进行赋值。
HT[i].lchild = p; //新树的左孩子赋为p;
HT[i].rchild = q; //新树的右孩子赋为q;
HT[p].parent = i; //把他们的双亲都赋为i;
HT[q].parent = i;
}
HC = (Huffmancode)malloc(sizeof(char*) * (n + 1)); //申请一个大小为n+1的存放指针的数组。
char* cd = (char*)malloc(sizeof(char) * n); //申请一个一维数组，作为一个中转站，最后把他复制到HC中的一个数组中。
for (i = 1; i <= n; i++) //对赫夫曼树的数组从1到n进行依次遍历，这是从叶子结点到根节点。
{
start = n - 1; //对这个一位数组进行倒着存，最后正着读取。
cd[start] = '\0';
s = i;
while (HT[s].parent != 0)
{
j = s;
s = HT[s].parent;
if (HT[s].lchild == j) //如果该结点是双亲结点的左孩子，应该把它赋为0；
cd[--start] = '0';
if (HT[s].rchild == j) //如果该结点是双亲结点的右孩子，应该把它赋为1；
cd[--start] = '1';
}
HC[i] = (char *)malloc(sizeof(char) * (n - start));
strcpy(HC[i], &cd[start]); //把cd数组里的内容复制到HC[i]里，再用cd去盛其他的编码。
}
free(cd);//最后可以把cd数组给释放了。
}
void Select (Huffmantree & HT, int t, int &min1, int &min2) //选择结点中权值最小的两个结点，用p,q来返回。
{
int i = 1, flag = 0;
while (flag < 2) //这个while循环是为了找出前两棵树的根结点，把他们当成最小的两棵树，以后来做比较，求出最小的两个。
{
if (HT[i].parent != 0) //如果不是根结点，继续朝后找，直到找到根结点。
i++;
else//如果是根结点，就把他们分别赋给min1和min2.
{
if (flag == 0)
min1 = i;
else
min2 = i;
flag++;
i++;
}
}
if (HT[min1].weight > HT[min2].weight) //对min1和min2进行比较，把最小的的付给min1,第二小的付给min2.
{
t = min1;
min1 = min2;
min2 = t;
}
while (i <= t) //把以后的各个结点的权值与最小的两个比较，调整下，最后得出的就是最小的两个结点。
{
if (HT[i].parent != 0) //如果不是根结点，继续朝后找，直到找到根结点。
i++;
else
{
if (HT[i].weight <= HT[min1].weight) //如果该结点的权值比最小的结点还小，把最小的两个全重新赋值。
{
min2 = min1;
min1 = i;
}
else if (HT[i].weight >= HT[min1].weight && HT[i].weight <= HT[min2].weight) //如果该结点的权值在最小和第二小之间的话，
//就把第二小的重新赋值。
min2 = i;
i++;
}
}
}
Status exhuffmantree(Huffmantree &HT, int m, char *code, int *ex, int &j) //这是解码的函数，m为那棵树的根结点，code是输入的赫夫曼码，
//解码后最后给他存到ex数组中，j为数组的长度。
{
int i = 0, k = m;
while (code[i] != '\0') //从根结点到叶子节点去匹配，输出最后的那个权值
{
if (code[i] == '0' && HT[k].lchild != 0) //如果code[i]是0,并且左孩子不为0，则继续朝叶子结点找。
{
k = HT[k].lchild;
i++;
}
else if (code[i] == '1' && HT[k].rchild != 0) //如果code[i]是1,并且右孩子不为0，则继续朝叶子结点找。
{
k = HT[k].rchild;
i++;
}
else if (HT[k].rchild == 0 && HT[k].lchild == 0) //如果是叶子结点，则把它的权值赋给ex[j].
{
ex[j] = HT[k].weight;
j++;
k = m;
}
else//其他的则返回ERROR。
return ERROR;
}
if (HT[k].rchild == 0 && HT[k].lchild == 0) //当跳出循环的时候，说明应该到了叶子结点，如果是叶子结点，则把它的权值赋给ex[j].
{
ex[j] = HT[k].weight;
return OK;
}
else//其他的则返回ERROR。
return ERROR;
}
int main()
{
Huffmantree HT;
Huffmancode HC;
char Code[100];
int i, n, a[100], b[100], j = 0, t;
printf("输入叶子结点的个数n为：\n");
scanf("%d", &n);
printf("依次输入n个叶子结点的权值为：\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
creathuffmantree(HT, HC, a, n);
printf("输出该赫夫曼树各个叶子结点的编码为：\n");
for (i = 1; i <= n; i++)
{
t = 0;
while (HC[i][t] != '\0')
{
printf("%c", HC[i][t]);
t++;
}
putchar(' ');
}
putchar('\n');
getchar();
printf("输入该赫夫曼树关联的要译码的code数组：\n");
gets(Code);
exhuffmantree(HT, 2 * n - 1, Code, b, j);
printf("输出解码后的各权值为：\n");
for (i = 0; i <= j; i++)
printf("%d ", b[i]);
putchar('\n');
return 0;
}