/***********************************************************/
/**************** 第6.7节 哈夫曼树及其应用 （146页——152页）**********
算法6.16【哈夫曼树的构造算法】（148页）
算法6.17【哈夫曼编码算法】（151页）
算法6.18【哈夫曼译码算法】（151页）（书中算法6.18有点问题，
看所列的DeCode函数）
************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 4 //叶结点数，也作为哈夫曼编码位数
#define m 2*n-1 //树的结点总数
#define MAXSIZE 128 //要译码的字符串或哈夫曼编码串长度
/*********哈夫曼树结点的存储结构（147页）********************/
typedef char datatype;
typedef struct { // 结点结构体
datatype data; //结点值
int weight; //权值，不妨设均大于零
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
} hufmtree;
/*********哈夫曼编码的数组结构描述（150页）********************/
typedef struct { //编码结构体
char bits[n]; //存储编码位串，存放哈夫曼编码
int start; //指示位串在bits中的起始位置，从start开始读bits中的哈夫曼编码
datatype data;
} codetype;
/***************算法6.16【哈夫曼树的构造算法】（148页）*************
************************************************/
void CreateHUFMT(hufmtree tree[]) {
int i, j, p1, p2; //p1和p2记录最小权值和次最小权值的结点位置
int small1, small2; //small1和small2分别用于存放最小权值和次最小权值
char ch;
int f;
printf(" 数组下标 lchild data weight rchild parent \n");
for (i = 0; i < m; i++) { //将数组tree初始化
tree[i].parent = tree[i].lchild = tree[i].rchild = 0; //置初值
// tree[i].weight = 0;
// tree[i].data = '0';
}
/* //n个叶子结点的权值和字符也可由main函数里给出
for (i = 0; i < n; i++) { //输入n个叶子结点的权值和字符至tree[0]~tree[n-1]
scanf("%d", &f);
tree[i].weight = f;
scanf("%c", &ch);
tree[i].data = ch;
}
*/
//当n个叶子结点的权值和字符由main函数给出时，tree[n]~tree[m-1]的初始化
for (i = n; i < m; i++) {
tree[i].weight = 0;
tree[i].data = '0';
}
//构造哈夫曼树
for (i = n; i < m; i++) { //进行n-1次合并，将产生的n-1个新结点依次存入 tree[n]~tree[m-1]
p1 = p2 = 0; //p1和p2记录最小权值的两个结点位置
small1 = small2 = 32767; //int型范围是-32768-32767
for (j = 0; j <= i - 1; j++) {
if (tree[j].parent == 0) { //只在尚未构造二叉树的结点中查找
if (tree[j].weight < small1) { //若权值小于最小的左结点的权值
small2 = small1; //改变最小权和次最小权及位置
small1 = tree[j].weight;
p2 = p1;
p1 = j;
} else if (tree[j].weight < small2) {//改变次最小权及位置
small2 = tree[j].weight;
p2 = j;
}
}
}
tree[p1].parent = i; //给合并的两个结点的双亲域赋值
tree[p2].parent = i; //两个最小结点的父结点是i
tree[i].weight = tree[p1].weight + tree[p2].weight; //两个最小结点的父结点权值为两个最小结点权值之和
tree[i].lchild = p1; //最小权的根结点是新结点的左孩子，父结点的左结点
tree[i].rchild = p2; //次最小权的根结点是新结点的右孩子，父结点的右结点
}
for (i = 0; i < m; i++) {
printf("%6d %6d %8c %6d %6d %6d\n", i, tree[i].lchild,
tree[i].data, tree[i].weight, tree[i].rchild, tree[i].parent);
}
}
/**************************************************************
***************算法6.17【哈夫曼编码算法】（151页）*************
**************************************************************/
void HUFMCode(codetype code[], hufmtree tree[]) {
//code: 存放求出的哈夫曼编码的数组。tree:已知的哈夫曼树。
int i, c, p;
codetype cd; //缓冲变量，临时存放编码
for (i = 0; i < n; i++) { //根据哈夫曼树求哈夫曼编码.n为叶子结点数目，循环产生n个字符的哈夫曼编码
cd.start = n; //从叶子结点出发向上回溯，从bits的高位开始存储
c = i; //c指示第i个叶子结点
p = tree[c].parent; //p指示结点c的双亲结点
cd.data = tree[c].data; //对结点数据域赋值
while (p != 0) { //循序直到树根结点结束循环，c指示到根结点时，p为0
cd.start--;
if (tree[p].lchild == c) //若结点c是双亲结点p的左孩子，置0；否则，置1；
cd.bits[cd.start] = '0';
else
cd.bits[cd.start] = '1';
c = p; //双亲结点p作为孩子结点，用c指示
p = tree[c].parent; //p指示结点c的双亲结点
}
code[i] = cd; //一个字符的编码存入code[i]
}
}
/**********************************************
函数功能：输出哈夫曼编码表
函数输入：哈夫曼树、哈夫曼码编码表
函数输出：（哈夫曼数组）
************************************************/
void ShowHUFMCode(codetype code[], hufmtree tree[]) {
int i, k;
printf(" 输出哈夫曼编码:\n");
for (i = 0; i < n; i++) { //输出data中的所有数据
printf(" %c:\t", tree[i].data);
for (k = code[i].start; k < n; k++) { //输出所有data中数据的编码
printf("%c", code[i].bits[k]);
}
printf("\n");
}
}
/**************************************************************
***************算法6.18【哈夫曼译码算法】（151页）*************
此为书中算法，该算法有问题，看后面的DeCode函数
**************************************************************/
void HUFMDecode(codetype code[], hufmtree tree[]) {
int i, c, p, b;
int endflag = -1; //电文结束标志取-1
i = m - 1; //从根结点开始向下搜索
scanf("%d", &b); //读入一个二进制代码
while (b != endflag) {
if (b == 0)
i = tree[i].lchild; //走向左孩子
else
i = tree[i].rchild; //走向右孩子
if (tree[i].lchild == 0) { //tree[i]是叶子结点
putchar(code[i].data);
i = m - 1; //回到根结点
}
scanf("%d", &b); //读入下一个二进制代码
}
if ((tree[i].lchild != 0) && (i != m - 1)) //电文读完尚未到叶子结点
printf("\n ERROR \n"); //输入电文有错
}
//哈夫曼树译码
void DeCode(hufmtree tree[], char codestr[]) { //codestr为电文序列
int i = m - 1; //当前节点下标，从根结点开始向下搜索
int j;
for (j = 0; codestr[j] != '\0'; j++) { //遍历电文序列中的每个字符
if (codestr[j] == '0') { //走向左孩子
i = tree[i].lchild;
} else if (codestr[j] == '1') { //走向右孩子
i = tree[i].rchild;
} else { //非法字符
printf("\n Invalid Code Error！\n");
exit(1);
}
if (tree[i].lchild == 0 && tree[i].rchild == 0) { // 到达叶子节点
printf("%c", tree[i].data); // 输出对应字符
i = m - 1; // 返回根节点继续遍历
}
}
printf("\n");
}
int main() {
int i;
char str[] = {'a', 'b', 'c', 'd'};
int fnum[] = {7, 5, 2, 4};
hufmtree tree[m]; //建立哈夫曼树结构体
for (i = 0; i < n; i++) { //把初始化的数据存入hufmtree结构体中
tree[i].data = str[i];
tree[i].weight = fnum[i];
}
CreateHUFMT(tree);
codetype code[n]; //建立编码表结构体
HUFMCode(code, tree); //建立哈夫曼编码表
ShowHUFMCode(code, tree); //输出哈夫曼编码表
//HUFMDecode(code, tree);
char c[] = "0110010101110";
printf("\n 电文 %s \n译码后为：", c);
DeCode(tree, c);
return 0;
}