从键盘输入一个数据文件(字符串),储存并统计各字符以及各字符出现的次数,设计并输出每个字符对应的哈夫曼编码。的代码
时间: 2024-03-10 14:46:50 浏览: 47
统计字符串中每个字符出现次数并排序工具
好的,这里是一个Python实现的代码示例:
```python
import heapq
from collections import defaultdict
# 定义节点类
class Node:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char # 节点对应的字符
self.freq = freq # 节点对应的出现次数
self.left = left # 左子节点
self.right = right # 右子节点
# 定义 __lt__ 方法,用于堆排序
def __lt__(self, other):
return self.freq < other.freq
# 统计各字符出现次数
def count_chars(s):
freq = defaultdict(int)
for c in s:
freq[c] += 1
return freq
# 构建哈夫曼树
def build_huffman_tree(freq):
heap = []
for c, f in freq.items():
node = Node(char=c, freq=f)
heapq.heappush(heap, node)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
parent = Node(freq=left.freq + right.freq, left=left, right=right)
heapq.heappush(heap, parent)
root = heapq.heappop(heap)
return root
# 生成哈夫曼编码
def generate_huffman_codes(root):
codes = {}
def dfs(node, code):
if node is None:
return
if node.char is not None:
codes[node.char] = code
return
dfs(node.left, code + '0')
dfs(node.right, code + '1')
dfs(root, '')
return codes
# 读取数据文件
filename = input("请输入数据文件名:")
with open(filename, 'r') as f:
s = f.read()
# 统计各字符出现次数
freq = count_chars(s)
# 构建哈夫曼树
root = build_huffman_tree(freq)
# 生成哈夫曼编码
codes = generate_huffman_codes(root)
# 输出每个字符对应的哈夫曼编码
print("字符\t出现次数\t哈夫曼编码")
for c, f in freq.items():
code = codes[c]
print(f"{c}\t{f}\t\t{code}")
```
这段代码首先读取一个数据文件,并使用 `count_chars` 函数统计各字符出现次数。然后,使用 `build_huffman_tree` 函数构建哈夫曼树,并使用 `generate_huffman_codes` 函数生成哈夫曼编码。最后,输出每个字符对应的哈夫曼编码。
阅读全文