最近在学算法,用python和c++各自写了一遍代码,虽然实现的并不是很好,还是贴出来记录一下吧.
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 = [Node(key, value) for key, value in dict.items()]
# 将字典中的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[0] # 根节点=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[i])
# print(node._name + '编码为：', str_num)
self.d[node._name] = str_num
return
# 在找到字符节点前进行递归
self.b[length] = 0
self.pre(node._left, length+1)
self.b[length] = 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[i] = 1
else:
symbolDict[i] = 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[MAXBIT]; //存储01编码的数组
int start; //编码在数组中开始的位置,从最后往前减小
}HCodeType;
HNodeType HuffNode[MAXNODE]; //定义一个足够大的节点数组
HCodeType HuffCode[MAXLEAF];
void HuffmanTree (HNodeType HuffNode[MAXNODE],int n) //构造霍夫曼树
{
int i,j,x1,x2;
double m1,m2;
for(i=0;i<2*n-1;i++) //初始化节点数据
{
HuffNode[i].weight = 0;
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
}
for(i=0;i<n;i++) //输入节点数据
{
cout<<"please input the value and weight of leaf node "<<i+1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].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[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} //最后m1,m2为最新权重节点的权重,x1,x2为其位置
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=m1+m2;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl;
}
}
void HuffmanCode(HCodeType HuffCode[MAXLEAF],int n) //对生成的树进行编码
{
HCodeType cd; //临时结构体
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent; //p为遍历过程中每个节点的parent值
while(p!=-1) //如果未到根节点
{
if(HuffNode[p].lchild==c) //为parent的左节点则在该处编码为0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--; //编码长度加1,start位置减1
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start+1;j<n;j++)
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].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[i].value<<" :Huffman code is: ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
return 0;
}
然后python写起来简单多了.
发表于 2019-1-15 08:05
|
发表于 2019-4-23 21:54
