这一题，题目很长，但是大多都是废话。主要的意思就是：给出一个字符串，将各个字符变成Huffman编码，并计算其长度。但是，需要注意的是，这里的字符，只需要统计大写字母和下划线的，其他的不需要统计。也就是其他Huffman编码的长度不用计算进去。
这一题我是先构造Huffman树，再来计算各个Huffman编码的长度的。
需要我们输出的是原来字符串的长度 * 8，编码之后的长度，以及压缩率。
下面是AC的代码：
# include <iostream># include <string>using namespace std;class Treenode//Huffman树的结点{public:char a, t;//a为该字符，t为0或1字符int weight, flag, len;//len为该字符编码长度，flag为是否被用过的标记Treenode *lchild, *rchild; //左右孩子};char table[20], str[10001];int len, length, tag;Treenode *p = new Treenode[70]; //前27个为叶子结点，后面的为备用结点，构造Huffman树需要用到的int main(){Treenode *bulid_Huffman();//构造Huffman树的函数void make_table(Treenode *root, int x); //求解Huffman编码的递归函数while(cin >> str){if(!strcmp(str, "END")) //判断是否结束break;int i, len = 0; tag = 0;for(i = 0; i < 70; i++)//初始化结构体数组{p[i].weight = p[i].flag = p[i].len = 0;p[i].lchild = p[i].rchild = NULL;if(i <= 25)p[i].a = 'A' + i;else if(i == 26)p[i].a = '_';elsep[i].a = ' ';}length = strlen(str);//字符串长度Treenode *root;for(i = 0; i < length; i++)//统计各个字符权值{if(str[i] >= 'A' && str[i] <= 'Z'){p[str[i] – 'A'].weight++;}else if(str[i] == '_'){p[26].weight++;}}root = bulid_Huffman();//构造Huffman树make_table(root, 0);for(i = 0; i < 70; i++)//计算各个编码长度len += p[i].weight * p[i].len;//len为编码之后的长度cout << length * 8 << ' ' << len << ' ';printf("%.1lf\n", (1.0 * length * 8) / len);}return 0;}int is_empty1()//判断结构体数组是否剩下一个结点{int count = 0;for(int i = 0; i < 70; i++){if(p[i].weight > 0 && p[i].flag == 0)count++;}if(count > 1)return 1;elsereturn 0;}int get_min()//返回结构体中没用过的权值最小的结点{int i = 0;while(p[i].weight == 0 || p[i].flag == -1)i++;int min = i;for( ; i < 70; i++){if(p[min].weight > p[i].weight && !p[i].flag && p[i].weight > 0)min = i;}return min;}Treenode *bulid_Huffman()//构造Huffman树{int k = 27, flag = 0;//备用结点的开始的位置为27，flag为一开始只有一个结点的标记while(is_empty1()){flag = 1;int i = get_min();p[i].flag = -1;int j = get_min();//获得两个权值最小的，并标记已用过p[j].flag = -1;p[k].lchild = (p + i); //连接到备用结点的左右孩子p[i].t = '1';p[k].rchild =(p + j);p[j].t = '0';p[k++].weight = p[i].weight + p[j].weight; //权值相加}if(flag == 0)//一开始只有一个结点，，不用构造Huffman树{tag = 1;//tag标记为1int i = get_min();(p + i)->t = '0';return (p + i);}p[k – 1].t = ' ';return (p + k – 1);}void make_table(Treenode *root, int x) //递归求解编码长度{Treenode *p;p = root;table[x] = p->t;if(p->lchild == NULL && p->rchild == NULL){table[++x] = '\0';char *q = table;if(!tag)//tag为0，说明开始结点不止一个，所以根节点的t为空格，需要跳过q++;p->len = strlen(q);}if(p->lchild != NULL)make_table(p->lchild, x + 1);if(p->rchild != NULL)make_table(p->rchild, x + 1);}有什么不懂的，欢迎来询问！~~~
也可以去参考我的另外一篇博客，实现Huffman编码解码的！~~
这是地址：
不必在乎目的地，在乎的是沿途的风景以及看风景的心情，让心灵去旅行！
