用python语言编写,给定随机n个权重值,按照哈夫曼编码规则,输出该n个随机值对应的哈夫曼编码
时间: 2024-02-12 08:08:35 浏览: 67
好的,我来回答你的问题。以下是用 Python 编写的代码:
```python
import heapq
from collections import defaultdict
# 定义节点类
class Node:
def __init__(self, freq, value=None, left=None, right=None):
self.freq = freq
self.value = value
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
# 哈夫曼树构建函数
def build_huffman_tree(freq_dict):
heap = [Node(freq, value) for value, freq in freq_dict.items()]
heapq.heapify(heap)
while len(heap) > 1:
node1 = heapq.heappop(heap)
node2 = heapq.heappop(heap)
parent_node = Node(node1.freq + node2.freq, left=node1, right=node2)
heapq.heappush(heap, parent_node)
return heap[0]
# 哈夫曼编码生成函数
def generate_huffman_code(root_node, code_dict, current_code=""):
if root_node is None:
return
if root_node.value is not None:
code_dict[root_node.value] = current_code
return
generate_huffman_code(root_node.left, code_dict, current_code + "0")
generate_huffman_code(root_node.right, code_dict, current_code + "1")
# 主函数
def main():
weights = [5, 9, 12, 13, 16, 45]
freq_dict = defaultdict(int)
for weight in weights:
freq_dict[weight] += 1
root_node = build_huffman_tree(freq_dict)
code_dict = {}
generate_huffman_code(root_node, code_dict)
for weight in weights:
print(f"Weight: {weight}, Code: {code_dict[weight]}")
if __name__ == "__main__":
main()
```
以上代码实现了给定随机 n 个权重值,按照哈夫曼编码规则,输出该 n 个随机值对应的哈夫曼编码的功能。
阅读全文