霍夫曼编码的python和c++实现
本帖最后由 笙若 于 2019-1-15 08:17 编辑最近在学算法,用python和c++各自写了一遍代码,虽然实现的并不是很好,还是贴出来记录一下吧.
```python
class Node:
def __init__(self, name=None, value=None):
self._name = name
self._value = value
self._left = None
self._right = None
class HuffmanTree:
# 根据Huffman树的思想：以叶子节点为基础，根据value排序，反向创建Huffman树
def __init__(self, char_weights):
self.a =
# 将字典中的key和值逐个添加到节点列表a中
while len(self.a) != 1:
self.a.sort(key=lambda node: node._value, reverse=True)# 按叶子的值排序
c = Node(value=(self.a[-1]._value + self.a[-2]._value))
# 将最小的两个节点的值相加赋给新节点c
c._left = self.a.pop(-1)
c._right = self.a.pop(-1)# 删掉最小的两个节点
self.a.append(c)# 将新节点添加到列表中
self.root = self.a# 根节点=a中第一个节点
self.b = list(range(20))# b用来存储字符的二进制序列
self.d = {}
# 递归的思想生成编码
def pre(self, tree, length):
node = tree
if (not node):
return# 树为空则直接返回
elif node._name:# 当节点是一个字符时进行编码
str_num = ""
for i in range(length):
str_num += str(self.b)
# print(node._name + '编码为：', str_num)
self.d = str_num
return
# 在找到字符节点前进行递归
self.b = 0
self.pre(node._left, length+1)
self.b = 1
self.pre(node._right, length+1)
# 生成霍夫曼编码
def get_code(self):
self.pre(self.root, 0)
print(self.d)
def fRead(filename):
symbolDict = {}
fl = 0
f = open(filename, 'r')
str = f.read()
f.close()
for i in str:
for j, k in symbolDict.items():
if i == j:
fl = 1
k = k + 1
break
if fl == 0:
symbolDict = 1
else:
symbolDict = k
return symbolDict
if __name__ == '__main__':
dict = fRead('test.py')
tree = HuffmanTree(dict)
tree.get_code()
```
顺便吐槽一下vscode真的很严格,写python时连有几个空行都要管.
~~~c++
```
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 1000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
typedef struct //定义节点
{
double weight;
int parent;
int lchild;
int rchild;
char value;
}HNodeType;
typedef struct //定义编码类型
{
int bit; //存储01编码的数组
int start; //编码在数组中开始的位置,从最后往前减小
}HCodeType;
HNodeType HuffNode; //定义一个足够大的节点数组
HCodeType HuffCode;
void HuffmanTree (HNodeType HuffNode,int n) //构造霍夫曼树
{
int i,j,x1,x2;
double m1,m2;
for(i=0;i<2*n-1;i++) //初始化节点数据
{
HuffNode.weight = 0;
HuffNode.parent = -1;
HuffNode.lchild = -1;
HuffNode.rchild = -1;
}
for(i=0;i<n;i++) //输入节点数据
{
cout<<"please input the value and weight of leaf node "<<i+1<<endl;
cin>>HuffNode.value>>HuffNode.weight;
}
for(i=0;i<n-1;i++) //循环合并n-1次
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++) //在已有的节点里找权重最小的且没有parent的节点
{
if(HuffNode.weight<m1&&HuffNode.parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode.weight;
x1=j;
}
else if (HuffNode.weight<m2&&HuffNode.parent==-1)
{
m2=HuffNode.weight;
x2=j;
}
} //最后m1,m2为最新权重节点的权重,x1,x2为其位置
HuffNode.parent=n+i;
HuffNode.parent=n+i;
HuffNode.weight=m1+m2;
HuffNode.lchild=x1;
HuffNode.rchild=x2;
cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode.weight<<"\t"<<HuffNode.weight<<endl;
}
}
void HuffmanCode(HCodeType HuffCode,int n) //对生成的树进行编码
{
HCodeType cd; //临时结构体
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode.parent; //p为遍历过程中每个节点的parent值
while(p!=-1) //如果未到根节点
{
if(HuffNode.lchild==c) //为parent的左节点则在该处编码为0
cd.bit=0;
else
cd.bit=1;
cd.start--; //编码长度加1,start位置减1
c=p;
p=HuffNode.parent;
}
for(j=cd.start+1;j<n;j++)
HuffCode.bit=cd.bit;
HuffCode.start=cd.start; //将临时变量复制到编码结构体
}
}
int main()
{
int i,j,n;
cout<<""<<endl;
cin>>n;
HuffmanTree(HuffNode,n);
HuffmanCode(HuffCode,n);
for(i=0;i<n;i++)
{
cout<<HuffNode.value<<" :Huffman code is: ";
for(j=HuffCode.start+1;j<n;j++)
cout<<HuffCode.bit;
cout<<endl;
}
return 0;
}
```
~~~
然后python写起来简单多了. Fris 发表于 2019-4-23 17:22
第12行应该是：
self.a =
感谢大佬提醒，不过因为并没有超出dict的作用域，所以像我那么写也是可以正确运行的吧 笙若 发表于 2019-4-23 21:54
感谢大佬提醒，不过因为并没有超出dict的作用域，所以像我那么写也是可以正确运行的吧
当前例子可以运行，但作为独立模块被其他模块调用就会出问题 收藏了，顺道坐个沙发 可以，很强 可以，很强 学些学习是必要的！ python写起来简单，但是提高水平的还是c++ 观井映天 发表于 2019-1-15 09:44
python写起来简单，但是提高水平的还是c++
应该说侧重点不同吧,python水平高了也很厉害的 越简单的东西，集成的越多，然后运行效率越低， 学习一哈 厉害，学习下
页:
[1]
2