nyoj801 Haffman编码(优先队列实现)

nyoj801 Haffman编码(优先队列实现)

题目801​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

Haffman编码

1000 ms  |  内存限制： 65535

3

哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：

1.规定哈弗曼树的左子树编码为0，右子树编码为1；

2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；

3.创建的新节点所代表的字符与它的左孩子的字符相同；

4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。

输入包含多组数据（不超过100组）

每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。

输入数据保证每组测试数据的字符不会重复。

输出 对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。 样例输入

3 a 10 b 5 c 8 4 a 1 b 1 c 1 d 1

样例输出

a:0 b:10 c:11 a:00 b:01 c:10 d:11

我真是日了狗了。。。

一直想着出题人不会出n=0的情况把。一直也就没判断，wa了一夜。今天检查错误

一直没发现。就加上n=0 结果ac了。坑坑坑啊、、、

/*8a 5b 29c 7d 8e 14f 23g 3h 11*/#include #include #include #include using namespace std;struct node{ char ch,code[100]; int val,left,right,fa,num; //结构体优先队列。对每个字符的权值排序 //先出权值比较小的，如果权值相等，出字符较小的 friend bool operator<(node a, node b) { if(a.val>b.val) return true; // if(a.val==b.val&&a.num>b.num) return true; if(a.val==b.val&&a.ch>b.ch) return true; return false; }}tree[200];int N;//str字符串为存贮huffman编码 char str[100];//对所有的huffman书按照序号排列 bool cmp(node a,node b){ return a.nums; int n; while(scanf("%d",&n)!=EOF) { if(n==0) continue; //初始str字符串和huffman树 memset(str,0,sizeof(str)); memset(tree,0,sizeof(tree)); //输入n个字符和权值，将其放入优先队列 for(int i=0;i1) { node temp1,temp2,temp3; temp1=s-();s.pop(); temp2=s-();s.pop(); temp3.val=temp1.val+temp2.val; temp3.ch=temp1.ch; temp3.left=temp1.num; temp3.right=temp2.num; temp3.fa=0; temp1.fa=temp2.fa=temp3.num=n++; tree[t++]=temp1; tree[t++]=temp2; s.push(temp3); } //优先队列里面剩下一个元素，它就是根节点，直接加到树中 tree[t++]=s-(); s.pop(); //按照num序号排序 sort(tree,tree+t,cmp); //取消下面的注释，可以看到每个节点的序号，父节点，左子树，右子树，权值。 // for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。