基于贪心法求解哈夫曼编码问题；要求使用java

实现

哈夫曼编码是一种可变长度编码，用于压缩数据。它的基本思想是将出现频率较高的字符用短编码表示，出现频率较低的字符用长编码表示，以此来实现压缩。

在哈夫曼编码中，每个字符对应一个编码，这个编码是由0和1组成的序列，称为编码串。编码串的长度是不固定的，根据字符出现的频率和位置不同而有所变化。

贪心法求解哈夫曼编码问题的基本思路是：首先根据字符出现的频率来构造一棵哈夫曼树，然后根据哈夫曼树来生成每个字符的编码。

以下是Java实现：

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

class HuffmanNode implements Comparable<HuffmanNode> {
    int frequency;
    char data;
    HuffmanNode left;
    HuffmanNode right;

    // 构造函数
    public HuffmanNode(int frequency, char data, HuffmanNode left, HuffmanNode right) {
        this.frequency = frequency;
        this.data = data;
        this.left = left;
        this.right = right;
    }

    // 比较函数，用于优先队列中的排序
    @Override
    public int compareTo(HuffmanNode o) {
        return this.frequency - o.frequency;
    }
}

public class HuffmanEncoding {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter input string: ");
        String input = scanner.nextLine();

        int[] freq = new int[128]; // 记录每个字符出现的频率
        for (int i = 0; i < input.length(); i++) {
            freq[input.charAt(i)]++;
        }

        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
        // 将输入字符串中出现的字符构造为一个个哈夫曼节点，并加入优先队列中
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                priorityQueue.offer(new HuffmanNode(freq[i], (char) i, null, null));
            }
        }

        // 构造哈夫曼树
        while (priorityQueue.size() > 1) {
            HuffmanNode node1 = priorityQueue.poll();
            HuffmanNode node2 = priorityQueue.poll();
            priorityQueue.offer(new HuffmanNode(node1.frequency + node2.frequency, '\0', node1, node2));
        }

        // 生成每个字符的哈夫曼编码
        generateCodes(priorityQueue.peek(), "");

        // 输出每个字符的哈夫曼编码
        System.out.println("Character\tFrequency\tCode");
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                System.out.println((char) i + "\t\t" + freq[i] + "\t\t" + codes[i]);
            }
        }
    }

    private static String[] codes = new String[128];

    // 递归生成哈夫曼编码
    private static void generateCodes(HuffmanNode node, String code) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            codes[node.data] = code;
            return;
        }
        generateCodes(node.left, code + "0");
        generateCodes(node.right, code + "1");
    }
}

在这个实现中，我们首先使用一个整型数组freq来记录输入字符串中每个字符出现的频率。然后，我们将每个出现过的字符构造为一个个哈夫曼节点，加入优先队列中。

在构造哈夫曼树时，我们每次从优先队列中取出两个频率最小的节点，构造为一个新的节点，然后将这个新节点加入优先队列中。这样，当优先队列中只剩下一个节点时，这个节点就是整棵哈夫曼树的根节点。

在生成每个字符的哈夫曼编码时，我们使用递归算法来实现。对于每个节点，如果它是一个叶子节点，我们就将它对应的字符的编码设置为当前的编码串。如果它不是叶子节点，我们就依次递归地处理它的左子树和右子树。在处理左子树时，我们将当前的编码串加上一个0；在处理右子树时，我们将当前的编码串加上一个1。这样，递归结束后，我们就可以得到每个字符的哈夫曼编码了。

最后，我们输出每个字符的哈夫曼编码，以及它出现的频率和字符本身。