哈夫曼编码/译码器（**）
问题描述：设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。基本要求：
（1）将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 。
（2）初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树。
（3）编码：利用建好的哈夫曼树生成哈夫曼编码。
（4）输出编码。
（5）对给定的由“0”和“1”字符串实现译码。
（6）显示哈夫曼树。
（7）界面设计的优化。
数据结构定义如下：
#define n 7 /叶子数目/
#define m 2n /结点总数，下标为0不用/
typedef int datatype;
typedef struct
{ float weight;
int lchild,rchild,parent;
}hufmtree;
hufmantree tree[m];
建立哈夫曼树算法描述如下：
for i=1 to n
{读入tree [i]. weight的值； tree [i].lchild= tree [i].rchild=0;}
for i=1 to m
tree [i].parent=0
for k=n+1 to M
Select ( k-1, i, j ) //从W[K-1]中选出双亲为零的两个权值最小的下标 I，J
tree [k]. weight = tree [I]. weight + tree [J]. weight；
tree [k].lchild = I ; tree [k].rchild = J;
tree [I].parent = k ; tree [J].parent = k ;
}
https://blog.csdn.net/u011710873/article/details/21548523
你给的伪码不是C的吗？还是说用python实现？
#Tree-Node Type
class Node:
def __init__(self,freq):
self.left =None
self.right =None
self.father =None
self.freq = freq
def isLeft(self):
return self.father.left == self
#create nodes创建叶⼦节点
def createNodes(freqs):
return[Node(freq)for freq in freqs]
#create Huffman-Tree创建Huffman树
def createHuffmanTree(nodes):
queue = nodes[:]
while len(queue)>1:
queue.sort(key=lambda item:item.freq)
node_left = queue.pop(0)
node_right = queue.pop(0)
node_father = Node(node_left.freq + node_right.freq)
node_father.left = node_left
node_father.right = node_right
node_left.father = node_father
node_right.father = node_father
queue.append(node_father)
queue[0].father =None
return queue[0]
#Huffman编码
def huffmanEncoding(nodes,root):
codes =['']*len(nodes)
for i in range(len(nodes)):
node_tmp = nodes[i]
while node_tmp != root:
if node_tmp.isLeft():
codes[i]='0'+ codes[i]
else:
codes[i]='1'+ codes[i]
node_tmp = node_tmp.father
return codes
#解压缩huffman文件
def decode_huffman(input_string, char_store, freq_store):
#input_string 哈夫曼编码
#char_store 字符集合
#freq_store 字符转编码01序列
encode =''
decode =''
for index in range(len(input_string)):
encode = encode + input_string[index]
for item in zip(char_store, freq_store):
if encode == item[1]:
decode = decode + item[0]
encode =''
return decode
#获取Huffman编码
def getHuffmanCode(char, freq):
dict1 = dict(zip(char,freq))
#for i in string:
# if i in dict1.keys():
# dict1[i]+=1
# else:
# dict1[i]=1
#将字符根据频次排序
chars_freqs =sorted(dict1.items(), key =lambda kv:(kv[1], kv[0]))
#创建huffman节点树
nodes = createNodes([item[1]for item in chars_freqs])
root = createHuffmanTree(nodes)
#每个字符的Huffman编码
codes = huffmanEncoding(nodes,root)
#print codes
dict2 ={}
for item in zip(chars_freqs,codes):
#print 'Character:%s freq:%-2d encoding: %s' % (item[0][0],item[0][1],item[1])
dict2[item[0][0]]= item[1]
str=''
for v in char:
str+= dict2[v]
return [str,dict2]
n = input("输入字母个数：")
n_c = input("输入字母:").split(" ")
n_w = input("输入字母权重:").split(" ")
print(getHuffmanCode(n_c, n_w))
print(decode_huffman("000000000000010000000010000000100000010000010001001011", n_c, "000000001"))