1974 - Haffman编码
哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：
1.规定哈弗曼树的左子树编码为0，右子树编码为1；
2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；
3.创建的新节点所代表的字符与它的做孩子的字符相同；
4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。
Input
输入包含多组数据（不超过100组）
每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。
Output
对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。
Examples
Input
3 a 10 b 5 c 8 4 a 1 b 1 c 1 d 1
Output
a:0 b:10 c:11 a:00 b:01 c:10 d:11
Solution C
#include <stdio.h> #include <stdlib.h> #include <string.h> #define swap(A,B,C) (C)=(A),(A)=(B),(B)=(C) typedef struct{ char value; int weight; int parent; int lchild; int rchild; }HTNode, *HuffmanTree; typedef struct{ int weight; char value; }pair; void Select(HTNode HT[], int n , int *s1, int *s2){ int min1=10000, min2=10000; for(int i = 1;i <= n; i++){ if(HT[i].weight<min1&&HT[i].parent==0){ min1=HT[i].weight; *s1=i; } } HT[*s1].parent=1; for(int i = 1;i <= n; i++){ if(HT[i].weight<min2&&HT[i].parent==0){ min2=HT[i].weight; *s2=i; } } HT[*s2].parent=1; if(HT[*s1].weight==HT[*s2].weight && HT[*s1].value>HT[*s2].value){ int temp; swap(*s1,*s2,temp); } } void HuffmanCoding(pair *w, int n){ if(n<=1) return; int m=2*n-1; HTNode HT[m+1]; HuffmanTree p; int i; for(i=1,p=&HT[i];i<=n;i++,p++,w++){ p->weight=w->weight; p->value=w->value; p->lchild=0; p->rchild=0; p->parent=0; } for(;i<=m;i++,p++){ p->lchild=0; p->parent=0; p->rchild=0; p->weight=0; } int s1=0, s2=0; for(i=n+1;i<=m;i++){ Select(HT,i-1,&s1,&s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; HT[i].value=HT[s1].value; } char HC[n+1][n]; for(i = 1;i<=n;i++){ char cd[n]; cd[n-1]='\0'; int start=n-1,c,f; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){ if(HT[f].lchild==c){ cd[--start]='0'; } else{ cd[--start]='1'; } } strcpy(HC[i],&cd[start]); } for(int j=1;j<=n;j++){ printf("%c:%s\n",HT[j].value,HC[j]); } } int main() { int n; while(scanf("%d",&n)!=EOF){ getchar(); pair a[n]; for(int i = 0;i < n; i++){ scanf("%c",&a[i].value); getchar(); scanf("%d",&a[i].weight); getchar(); } pair *w=&a[0]; HuffmanCoding(w,n); } return 0; }
Solution C++
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; int N; char str[101]; struct Node { int father, left, right, num; char ch, code[101]; ///结构体优先队列。对每个字符的权值排序 ///先出权值比较小的，如果权值相等，出字符较小的 friend bool operator<(Node a, Node b) { if (a.father>b.father) return true; if (a.father == b.father&&a.ch>b.ch) return true; return false; } } tree[200]; bool cmp(Node a, Node b) { return a.num<b.num; } void dfs(int t, int i) {///t表示huffman树的节点个数 if (t<N)///说明t编号的节点就是叶子节点 { str[i] = '\0';///str[q]='\0'，表示字符的结尾，便于后面的strcpy（）函数 strcpy(tree[t].code, str); return; } else { ///递归访问左孩子 str[i] = '0'; i++; dfs(tree[t].left, i); i--; ///递归访问右孩子 str[i] = '1'; i++; dfs(tree[t].right, i); i--; } } int main() { priority_queue<Node>Q; int n; while (~scanf("%d", &n)) { if (n == 0) continue; memset(str, 0, sizeof(str)); memset(tree, 0, sizeof(tree)); for (int i = 0; i<n; i++) { getchar(); Node node; scanf("%c %d", &node.ch, &node.father); node.num = i;///叶子节点的编号 Q.push(node); } N = n; int t = 0; ///创建huffman树 ///利用优先队列 每次选择权值最小的两个，然后将其结果在加入优先队列 /// 将权值最小的两个 ，添加到树中 while (Q.size()>1) { Node node1, node2, node3; node1 = Q.top(); Q.pop(); node2 = Q.top(); Q.pop(); node3.father = node1.father + node2.father; node3.ch = node1.ch; node3.left = node1.num; node3.right = node2.num; node3.num = n++; tree[t++] = node1; tree[t++] = node2; Q.push(node3); } tree[t++] = Q.top();///优先队列里面剩下一个元素，它就是根节点，直接加到树中 Q.pop(); sort(tree, tree + t, cmp);///按照num序号排序,最后可以按编号输出，排除非叶子节点 dfs(t - 1, 0); for (int i = 0; i<N; i++) printf("%c:%s\n", tree[i].ch, tree[i].code); } }