一 原题链接

Variable Radix Huffman Encoding - UVA 240 - Virtual Judge

https://vjudge.net/problem/UVA-240

二 输入与输出

1 输入

输入将包含一个或多个数据集，每行一个。每个数据集都包含整数值 R、整数值 N 和整数频率 f1到 fn。整个数据都以 R 为 0 结束，它不被认为是单独的数据集。

2 输出

对每个数据集都单行上显示其编号（编号从1开始顺序排列）和平均目标符号长度。然后显示 N 个源字母和相应的哈夫曼代码，每行都有一个字母和代码。

3 输入样例

2 5 5 10 20 25 40

2 5 4 2 2 1 1

3 7 20 5 8 5 12 6 9

4 6 10 23 18 25 9 12

0

4 输出样例

Set 1; average length 2.10

A: 1100

B: 1101

C: 111

D: 10

E: 0

Set 2; average length 2.20

A: 11

B: 00

C: 01

D: 100

E: 101

Set 3; average length 1.69

A: 1

B: 00

C: 20

D: 01

E: 22

F: 02

G: 21

Set 4; average length 1.32

A: 32

B: 1

C: 0

D: 2

E: 31

F: 33

 三 问题分析

本问题为可变基哈夫曼编码，普通的哈夫曼编码为二叉树，即 R=2。

例如，输入 3 4 5 7 8 15，表示基数 R=3，字符个数 N=4，每个字符的频率为 A:5，B;7，C:8，D:15,构建的哈夫曼树如下。

？：表示虚拟字符

下方数字：表示频率

左上方数字：表示优先级

节点中的值：表示字符

需要补充一些虚拟字符，使总数满足k*（R-1）+R，k 为整数，这样可以保证每个分支节点都有 R 个叉。虚拟字符的频率为 0，其优先值排在所有字母之后、生成一个组合节点时，组合节点的频率为所有子节点频率之和，组合节点的优先值为所有子节点中的最小优先值。

四 算法设计

1 先补充虚拟字符，使 N = k*（R-1）+R，k 为整数，即 （N-R）%（R-1）= 0

2 每个节点都包含 frequency、va、id 这三个域，分别表示频率、优先值、序号。

3 定义优先级。频率越小越优先，如果频率相等，则优先级值越小越优先。

4 将所有节点都加入优先队列。

5 构建可变基哈夫曼树。

6 进行可变哈夫曼编码。

五 代码实现

package tree;

import java.util.PriorityQueue;
import java.util.Scanner;

public class UVA240 {
    public static void main(String[] args) {
        final int maxn = 100;
        int cas = 1;
        while (true) {
            int father[] = new int[maxn];
            int code[] = new int[maxn];
            int R, N; // 基数，字母个数
            int n, c; // 补虚拟字母后的个数，新生成字母编号
            Scanner scanner = new Scanner(System.in);
            R = scanner.nextInt();
            if (R == 0) {
                return;
            }
            N = scanner.nextInt();

            int fre[] = new int[maxn];
            int total = 0;
            for (int i = 0; i < N; i++) {
                fre[i] = scanner.nextInt();
                total += fre[i];
            }
            n = N;
            while ((n - R) % (R - 1) != 0)//补虚拟结点
                n++;
            PriorityQueue<node> Q = new PriorityQueue<>(); //优先队列
            for (int i = 0; i < n; i++) // 所有结点入队
            {
                Q.add(new node(fre[i], i, i));
            }

            c = n; // 新合成结点编号
            int rec = 0;//统计所有频率和值
            while (Q.size() != 1) {//剩余一个结点停止合并
                int sum = 0, minva = n;
                for (int i = 0; i < R; i++) {
                    sum += Q.peek().freq; // 统计频率和
                    minva = Math.min(Q.peek().va, minva); // 求最小优先值
                    father[Q.peek().id] = c; // 记录双亲
                    code[Q.peek().id] = i; // 记录编码
                    Q.poll(); // 出队
                }
                Q.add(new node(sum, minva, c));//新结点入队
                c++;
                rec += sum;
            }
            c--;
            System.out.printf("Set %d; average length %f\n", cas, 1.0 * rec / total);

            for (int i = 0; i < N; i++) {
                int cur = i;
                String s = "";
                while (cur != c) {
                    s += Character.toString((char) ('0' + code[cur]));
                    cur = father[cur];
                }
                s = reverseTestThree(s); // 翻转编码
                System.out.println("    " + (char) ('A' + i) + ": " + s);
            }
            System.out.println();
            cas++;
        }
    }

    public static String reverseTestThree(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

class node implements Comparable<node> {
    int freq = 0; // 频率
    int va = 0; // 优先值
    int id = 0; // 序号

    node(int x, int y, int z) { // 构造函数
        freq = x;
        va = y;
        id = z;
    }

    @Override
    public int compareTo(node b) {
        if (freq == b.freq)
            return va - b.va;
        return freq - b.freq;
    }
}

六 测试

绿色为输入，白色为输出。

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系