huffman

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 哈夫曼树
/*
比如有a,b,c,d,e五个字符，它们出现的频率(即权值)分别为(5,4,3,2,1)
那么先取权值最小的两个来构造一个子树，左孩子是1，右孩子是2，父节点是这两个孩子的权值之和3
那么现在集合中的数为(5,4,3,3)
再取两个最小的来构造另一个子树，左孩子是3，右孩子也是3，父节点是6
那么现在集合中的数为(5,4,6)
再取两个最小的来构造另一个子树，左孩子是4，右孩子是5，父节点是9
那么现在集合中的数为(9,6)
再取两个最小的来构造另一个子树，左孩子是6，右孩子是9，父节点是15
ok，建树完毕
各个字符对应的编码为a:11,b:10,c:00,d:011,e:010
*/
#define MAXBIT 100
#define MAXWEIGHT 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 - 1
// 上面MAXLEAF是叶子节点的数量，如果有MAXLEAF个叶子节点，则整棵树的节点数为MAXLEAF*2 - 1。比如上面a,b,c,d,e那个例子最终会创建一个有九个节点的哈夫曼树
// 编码结构体
typedef struct
{
int bit[MAXBIT];
int start;
}HCodeType;
// 节点结构体
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char value;
}HNodeType;
// 构造一颗哈夫曼树
void HuffmanTree(HNodeType HuffNode[MAXNODE],int n){
// i,j循环变量
// m1,m2,构造哈夫曼树不同过程中两个最小权值节点的权值
// x1,x2,构造哈夫曼树不同过程中两个最小权值节点在数组中的序号
int i,j,m1,m2,x1,x2;
// 初始化存放哈夫曼树的数组HuffNode中的节点
// n是叶子节点的数量
for(i = 0;i < 2 * n - 1;i++){
HuffNode[i].weight = 0;// 权值
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
HuffNode[i].value = 'x';// 实际值，本例中节点中存放的是字符,初始为'x'
}
// 输入n个叶子节点的权值
for(i = 0;i < n;i++){
printf("please input weight of leaf node %d:\n",i);// 输入叶子节点的权值
scanf("%d",&HuffNode[i].weight);
}
for(i = 0;i < n;i++){
printf("please input value of leaf node %d:\n",i);
getchar();// 用于清除输入区缓存，否则上面的回车'\n'由于存放在缓冲区中，将被默认输入到value中,造成正确的输入值被scanf忽略
scanf("%c",&HuffNode[i].value);
}
// 上面说了，有n个叶子节点的哈夫曼树共有2*n-1个节点，所以非叶子节点的个数为n-1。上面已经初始化了n个叶子节点的权值，下面开始初始化n-1个非叶子节点的权值
// 循环构造huffman树的n-1个非叶子节点
for(i = 0;i < n - 1;i++){
m1 = m2 = MAXWEIGHT;// m1,m2存放两个无父节点且权值最小的两个节点的权值
x1 = x2 = 0;
for(j = 0;j < n + i;j++){// n + i是本次循环时树中存在的节点数量
// 下面寻找两个最小值的方式挺好
if(HuffNode[j].weight < m1 && HuffNode[j].parent == -1){
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}else if(HuffNode[j].weight < m2 && HuffNode[j].parent == -1){
m2 = HuffNode[j].weight;
x2 = j;
}
}
HuffNode[x1].parent = n + i;
HuffNode[x2].parent = n + i;
HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n + i].lchild = x1;
HuffNode[n + i].rchild = x2;
}
}




//解码 
void myDecoding(char string[],HNodeType Buf[],int Num){
  int i,tmp = 0;
  int m = 2 * Num - 1;// 树中节点的总数量
  int *nump;
  int num[1024];
  // 将用户输入的字符串型的哈夫曼编码变为int型，存在num数组中
for(i = 0;i < strlen(string);i++){
if(string[i] == '0'){
num[i] = 0;
}else{
num[i] = 1;
}              
} 
i = 0;
nump = &num[0];// nump指向数组的开端
// 依此取出数组中的位，然后根据值去找路径
while(nump <= (&num[strlen(string) - 1])){
tmp = m - 1;// 哈夫曼树树根的index
while( (Buf[tmp].lchild != -1) && (Buf[tmp].rchild != -1) ){
if(*nump == 0){
tmp = Buf[tmp].lchild;          
}else{
tmp=Buf[tmp].rchild;
}
nump++;
}
// 最终找到的tmp是输入的哈夫曼编码string对应的叶子节点在树中的index 
  printf("the value is %c\n",Buf[tmp].value);// 输出叶子节点处的值。哈夫曼树的weight是其在树中出现的频率，value是这个节点处存的值                              
  }
}


int main(){
HNodeType HuffNode[MAXNODE];// 定义一个节点结构体数组
HCodeType HuffCode[MAXLEAF],code;// 定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息
int i,j,childIndex,parentIndex,n;
char pp[100];
printf("please input n:\n");// 输入叶子节点的个数
scanf("%d",&n);
// 构造一个haffman树
HuffmanTree(HuffNode,n);
for(i = 0;i < n;i++){
code.start = n - 1;// n个数的哈夫曼编码最多用n位表示，所以start作为bit数组的下标，取值范围为[0,n - 1]。当然有的数的编码不一定能填满这n位
childIndex = i;
parentIndex = HuffNode[childIndex].parent;
while(parentIndex != -1){// 父节点存在
if(HuffNode[parentIndex].lchild == childIndex){
code.bit[code.start] = 0;
}else{
code.bit[code.start] = 1;
}
code.start--;// 求编码的低一位
childIndex = parentIndex;
parentIndex = HuffNode[childIndex].parent;
}
// 保存求出的每个叶节点的哈夫曼编码和编码的起始位
for(j = code.start + 1;j < n;j++){// 因为上面code.start最终无效时多减了一次
HuffCode[i].bit[j] = code.bit[j];
}
HuffCode[i].start = code.start;// 记录一下下标是从哪开始的
}
// 输出已保存好的所有存在编码的哈夫曼编码
for(i = 0;i < n;i++){
printf("%d 's huffman code is:",i);
for(j = HuffCode[i].start + 1;j < n;j++){// 从start + 1才有数据
printf("%d",HuffCode[i].bit[j]);
}
printf("\n");
}
// 解码
printf("decoding?please enter code:\n");
scanf("%s",pp);
myDecoding(pp,HuffNode,n);
return 0;
}