Catalog
  1. 1. 题目
  2. 2. 项目简介
  3. 3. 功能描述
  4. 4. 代码清单
数据结构课程设计实验四

题目

哈夫曼编/译码器

项目简介

哈夫曼编/译码器问题:利用哈夫曼编码(加密)进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本,保证报文安全。这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(解密)。

功能描述

1.初始化 (Initialization):从终端读入n个字符,建立哈夫曼树;

2.编码 (Coding):利用已建好的哈夫曼树,对字符进行编码,然后将正文编码结果存入文件codefile.txt中;

3.译码 (Decoding):利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码,结果存入文件textfile.txt中。

代码清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
encoder = {}
decoder = {}


class treeNode:
def __init__(self, data):
self.weight = data[0]
self.frequency = data[1]
self.left_child = None
self.right_child = None
self.code = ""


class nodeQueue:
def __init__(self, codes):
self.queue = createNodeQueue(codes)
self.length = len(self.queue)

def addNode(self, node):
self.queue = addNodeQueue(self.queue, node)
self.length += 1

def deleteNode(self):
self.length -= 1
return self.queue.pop(0)


def createNodeQueue(codes):
que = []
for code in codes:
que.append(treeNode(code))
return que


def addNodeQueue(queue, new_node):
if len(queue) == 0:
return [new_node]
for i in range(len(queue)):
if queue[i].frequency >= new_node.frequency:
return queue[:i] + [new_node] + queue[i:]
return queue + [new_node]


def countFreq(input_str):
match = {}
for ch in input_str:
if ch in match:
match[ch] += 1
else:
match[ch] = 1
return sorted(match.items(), key=lambda x: x[1])


def createTree(node_queue):
while node_queue.length != 1:
node_lchild = node_queue.deleteNode()
node_rchild = node_queue.deleteNode()
node_parent = treeNode([None, node_lchild.frequency + node_rchild.frequency])
node_parent.left_child = node_lchild
node_parent.right_child = node_rchild
node_queue.addNode(node_parent)
return node_queue.deleteNode()


def initCoder(node, x):
global coder
if node:
initCoder(node.left_child, x + '0')
node.code += x
if node.weight:
decoder[node.code] = node.weight
encoder[node.weight] = node.code
initCoder(node.right_child, x + '1')


def encode(en_str):
global encoder
encode = ""
print("\nCoding...")
for c in en_str:
encode += encoder[c]
with open('D:\\stu\\大二下\\数据结构课程设计\\实验四\\codefile.txt', 'w') as f:
f.write(encode)
print("Coding succeed!\nIt is saved in: D:\\stu\\大二下\\数据结构课程设计\\实验四\\codefile.txt\n")
return encode


def decode(de_str):
global decoder
decode = ""
tmp = ""
print("Decoding...")
for c in de_str:
tmp += c
if tmp in decoder:
decode += decoder[tmp]
tmp = ""
with open('D:\\stu\\大二下\\数据结构课程设计\\实验四\\textfile.txt', 'w') as f:
f.write(decode)
print("Decoding succeed!\nIt is saved in: D:\\stu\\大二下\\数据结构课程设计\\实验四\\textfile.txt")
return decode


if __name__ == '__main__':
myStr = input("Please enter the character to encode:")
myQueue = nodeQueue(countFreq(myStr))
myTree = createTree(myQueue)
initCoder(myTree, '')
enStr = encode(myStr)
decode(enStr)
Author: Christopher Shen
Link: https://www.pasxsenger.com/2020/03/21/数据结构课程设计实验四/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶