範例程式碼 uva240
//uva240
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct symbol{
int l; // alphabet level
int f; // frequency
int fa; // father
int leaf; // -1 = not leaf, 0..1..2....n-1 means from left to right
bool iss; // is symbol?
bool exist; // can be merged?
symbol(int _l = 0, int _f = 0, int _fa = 0, int _leaf = -1, bool _iss = true, bool _exist = true):\
l(_l), f(_f), fa(_fa), leaf(_leaf), iss(_iss), exist(_exist) {}
}v[100];
int R, N, num, vsize, tcnt = 0;
int lans[26];
char pans[26][26];
void huffman() {
int i, j, del = 0;
while(num != 1) {
int pick[10];
for(i = 0; i < R; i++) {
for(j = 0; j < vsize && v[j].exist == false; j++);
int cur = j;
for(j = cur+1; j < vsize; j++) {
if(v[j].exist == false) continue;
if(v[j].f < v[cur].f ||(v[j].f == v[cur].f && v[j].l < v[cur].l)) {
cur = j;
}
}
pick[i] = cur;
v[cur].exist = false;
}
int tmpl = 27, tmpf = 0; // 27 is greater than 26
for(i = 0; i < R; i++) {
tmpf += v[pick[i]].f;
tmpl = min(tmpl, v[pick[i]].l);
v[pick[i]].fa = vsize;
v[pick[i]].leaf = i;
}
v[vsize] = symbol(tmpl, tmpf, -1, -1, false, true);
del += R;
num -=(R - 1);
vsize++;
}
double totlen = 0, totfreq = 0;
memset(lans, 0, sizeof(lans));
for(i = 0; i < vsize; i++) {
if(v[i].iss == true) {
int cur = i;
while(v[cur].fa != -1) {
pans[v[i].l][lans[v[i].l]] = '0' + v[cur].leaf;
lans[v[i].l]++;
cur = v[cur].fa;
}
totfreq += v[i].f;
totlen += lans[v[i].l] * v[i].f;
}
}
totlen /= totfreq;
printf("Set %d; average length %.2lf\n", ++tcnt, totlen);
for(i = 0; i < N; i++) {
printf(" %c: ",'A'+i);
for(j = lans[i]-1; j >= 0; j --) {
printf("%c",pans[i][j]);
}
printf("\n");
}
printf("\n");
}
int main() {
int i, f;
while(scanf("%d",&R) && R) {
scanf("%d", &N);
for(i = 0; i * (R - 1) + R < N; i++);
num = i * (R - 1) + R;
if(num != N) {
num = num - N;
for(i = 0; i < num; i++) {
v[i] = symbol(26, 0, -1, -1, false, true);
}
}
else
num = 0;
for(i = 0; i < N; i++, num++) {
scanf("%d", &f);
v[num] = symbol(i, f, -1, -1, true, true);
}
vsize = num;
huffman();
}
return 0;
}