编写一个哈夫曼编码译码程序。

按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。

为确保构建的哈夫曼树唯一，本题做如下限定：

（1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。

（2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。

生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

第一行输入字符个数n；

第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）；

最后一行输入需进行译码的串。

输出格式:

首先按树的先序顺序输出所有字符的编码，每个编码占一行；

最后一行输出需译码的原文，加上original:字样。

输出中均无空格

输入样例:

3
m1
n1
c2
10110

输出样例:

c:0
m:10
n:11
original:mnc

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define MAX_INT 1000
#define MAX_Double (numeric_limits<double>::max)()using namespace std;//Huffman树结点结构体
typedef struct TreeNode{double weight;//因为频率有可能为小数，所以用doublechar Ch;//用于存放该节点字符char *code;//用于存放该字符的 Huffman编码int parent,lchild,rchild;//存放每个结点的 父节点 以及 子结点
}TreeNode;//Huffman树结构体
typedef struct HFTree{TreeNode* data;//用堆实现该Huffman树int length;//该树总结点的个数
}HFTree;//初始化哈夫曼树
HFTree* initTree(double* weight,char* ch,int n){HFTree* T = (HFTree*)malloc(sizeof(HFTree));//根据性质，n个结点生成的Huffman树会有2*n-1个结点T->data = (TreeNode*)malloc(sizeof(TreeNode)*(2*n-1));T->length = n;//初始化每个结点for(int i = 0; i < n; ++i){T->data[i].Ch = ch[i];T->data[i].weight = weight[i];T->data[i].parent = 0;T->data[i].lchild = -1;T->data[i].rchild = -1;//初始化每个结点的code数组T->data[i].code = (char*)malloc(sizeof(char)*MAX_INT);memset(T->data[i].code,'\0',MAX_INT);	}return T;
}//选择两个权值最小的结点
int* selectMin(HFTree* T){//定义两个哨兵变量，他们的值为double所表示的最大值//(numeric_limits<double>::max)();double min = MAX_Double;double secondMin = MAX_Double;//两个最小结点的下标int minIndex;int secondIndex;//先选择第一小的结点for(int i=0;i<T->length;++i){//只要没有父节点就可以选择if(T->data[i].parent == 0){if(T->data[i].weight < min){min = T->data[i].weight;minIndex = i;}}}//其次选择第二小的结点for(int i =0;i<T->length;++i){//没有父节点且不等于第一小的才选择if(T->data[i].parent == 0 && i != minIndex){if(T->data[i].weight < secondMin){secondMin = T->data[i].weight;secondIndex = i;}}}//因为返回两个值，所以可以使用指针int* res = (int*)malloc(sizeof(int)*2);res[0] = minIndex;res[1] = secondIndex;return res;
}//Huffman编码器
void Hfmcode(HFTree* T,int n){//分别给n个字符编码for(int k=0;k<n;k++){//从0号位的叶子节点开始回溯int i = 0,j = 0;int ch = k;//记录单个字符的编码char str[MAX_INT];memset(str,'\0',MAX_INT);int parent = T->data[k].parent;for(i = n-1;parent != 0;i--){//如果该左孩子与 回溯起点index相符if(T->data[parent].lchild == ch){str[j++] = '0';ch = parent;//向上回溯parent = T->data[ch].parent;}else{//同上 右孩子.....str[j++] = '1';ch = parent;parent = T->data[ch].parent;}}int f = 0;//因为是回溯编码，所以需要反转for(int s = j-1;s>=0;s--){T->data[k].code[f] = str[s];f++;}}
}//创建Huffman树
void createHFTree(HFTree* T,int nn){int* res;int min;int secondMin;int n = T->length * 2 - 1;for(int i = T->length; i < n;++i){T->data[i].parent = 0;res = selectMin(T);min = res[0];secondMin = res[1];//给父节点赋值T->data[i].weight = T->data[min].weight + T->data[secondMin].weight;T->data[i].lchild = min;T->data[i].rchild = secondMin;//给儿子们赋值T->data[min].parent = i;T->data[secondMin].parent = i;T->length++;}//为每个字符编码Hfmcode(T,nn);
}//递归遍历Huffman树 T->length-1为根结点
void preOrder(HFTree* T,int index){if(index != -1){if(T->data[index].lchild == -1 || T->data[index].rchild == -1)cout << T->data[index].Ch <<":"<<T->data[index].code<<endl;preOrder(T,T->data[index].lchild);preOrder(T,T->data[index].rchild);}
}//Huffman译码
char* Decode(char* str,int length,HFTree* T){int index = length - 1,ct = 0,j = 0;char ch;ch = str[0];char* res = (char*)malloc(sizeof(char)*MAX_INT);while(true){//当密文字符为0时向左走if(ch == '0'){index = T->data[index].lchild;//为1时向右走}else if(ch == '1'){index = T->data[index].rchild;}//直到遍历到叶子节点if(T->data[index].lchild == -1 || T->data[index].rchild == -1){//此时的字符值即为这一段密文的密码字符res[ct] = T->data[index].Ch;ct++;//回到根结点index = length-1;}//记录当前遍历密文的位置j++;ch = str[j];//当走完时直接及解码完成 退出循环if(j == (int)strlen(str))break;}return res;
}int main(){//输入n个字符int n;scanf("%d",&n);getchar();//初始化n个 char和double类型的数组 用于存放 字符和对应的频率char* chNums = (char*)malloc(sizeof(char)*n);double* nuNums = (double*)malloc(sizeof(double)*n);//输入 字符以及相应的频率for(int i=0;i<n;++i){scanf("%c%lf",&chNums[i],&nuNums[i]);getchar();}//输入 需要译码的字符串char str[MAX_INT];scanf("%s",str);getchar();//创建一棵Huffman树HFTree* T = initTree(nuNums,chNums,n);createHFTree(T,n);//遍历每个字符及其编码preOrder(T,T->length-1);//遍历解码后的密文cout<<"original:"<<Decode(str,T->length,T)<<endl;return 0;
}