数据结构实验哈夫曼编码

哈夫曼编码是一种用于数据压缩的编码方法，它通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现对数据的压缩。下面是一个演示哈夫曼编码的例子：

假设有一个文本文件SourceFile.txt，其中包含一段文本。首先，需要统计每个字符在文本中出现的频率，并根据频率构建哈夫曼树。然后，根据哈夫曼树生成每个字符的编码表。最后，根据编码表将文本中的字符转换成相应的编码，并将编码结果保存到另一个文件ResultFile.txt中。

以下是一个Python实现的示例代码：

import heapq
import os

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_frequency_table(text):
    frequency_table = {}
    for char in text:
        if char in frequency_table:
            frequency_table[char] += 1
        else:
            frequency_table[char] = 1
    return frequency_table

def build_huffman_tree(frequency_table):
    heap = []
    for char, freq in frequency_table.items():
        node = HuffmanNode(char, freq)
        heapq.heappush(heap, node)

    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged_node = HuffmanNode(None, node1.freq + node2.freq)
        merged_node.left = node1
        merged_node.right = node2
        heapq.heappush(heap, merged_node)

    return heap[0]

def build_encoding_table(huffman_tree):
    encoding_table = {}
    def build_encoding_table_helper(node, code):
        if node is None:
            return
        if node.char is not None:
            encoding_table[node.char] = code
        build_encoding_table_helper(node.left, code + "0")
        build_encoding_table_helper(node.right, code + "1")
    build_encoding_table_helper(huffman_tree, "")
    return encoding_table

def encode_text(text, encoding_table):
    encoded_text = ""
    for char in text:
        encoded_text += encoding_table[char]
    return encoded_text

def decode_text(encoded_text, huffman_tree):
    decoded_text = ""
    current_node = huffman_tree
    for bit in encoded_text:
        if bit == "0":
            current_node = current_node.left
        else:
            current_node = current_node.right
        if current_node.char is not None:
            decoded_text += current_node.char
            current_node = huffman_tree
    return decoded_text

# 读取源文件
with open("SourceFile.txt", "r") as file:
    text = file.read()

# 构建频率表
frequency_table = build_frequency_table(text)

# 构建哈夫曼树
huffman_tree = build_huffman_tree(frequency_table)

# 构建编码表
encoding_table = build_encoding_table(huffman_tree)

# 编码文本
encoded_text = encode_text(text, encoding_table)

# 将编码结果保存到文件
with open("ResultFile.txt", "w") as file:
    file.write(encoded_text)

# 解码文本
decoded_text = decode_text(encoded_text, huffman_tree)

print("Huffman编码完成！")

请注意，上述代码中的SourceFile.txt是输入文件，ResultFile.txt是输出文件。你可以根据实际情况修改这两个文件的路径。