依权建立哈夫曼树

哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1L1+W2L2+W3L3+…+WnLn),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明霍夫曼树的WPL是最小的。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct HTNode{
int weight;
HTNode *parent,*lchild,*rchild;
}HTNode;
//typedef char **HuffmanCode; //动态存储哈夫曼编码表
int n=0;

int empty(int weights[]){
for(int i=0;i<n;i++){
if(weights[i]!=0)return 0;
}return 1;
}
int popsmall(int weights[]){
if(empty(weights))return 101;
int k=0,small=101;
for(int i=0;i<n;i++){
if(weights[i]!=0){
small=small<weights[i]?small:weights[i];
if(small==weights[i])k=i;
}
}
weights[k]=0;return small;
}
int getsmall(int weights[]){
if(empty(weights))return 101;
int small=101;
for(int i=0;i<n;i++)if(weights[i]!=0)small=small<weights[i]?small:weights[i];
return small;
}
int emptyroots(HTNode *roots[]){
for(int i=0;i<n;i++)if(roots[i]!=NULL)return 0;
return 1;
}
int getsmallroots(HTNode *roots[]){
HTNode *p=NULL;
int small=101;
for(int i=0;i<n;i++){
p=roots[i];
if(p!=NULL)small=small<p->weight?small:p->weight;
}
return small;
}
HTNode *popsmallroots(HTNode *roots[]){
if(emptyroots(roots))return NULL;
HTNode *p=NULL,*root=NULL;
p=(HTNode*)malloc(sizeof(HTNode));p->weight=101;
int k=0;
for(int i=0;i<n;i++){
if(roots[i]){
p=p->weight<roots[i]->weight?p:roots[i];
if(p=roots[i])k=i;
}
}
roots[k]=NULL;return p;
}
void pushroot(HTNode *roots[],HTNode *root){
for(int i=0;i<n;i++){
if(roots[i]==NULL){roots[i]=root;return;}
}
}
int oneroot(HTNode *roots[]){
int nn=0;
for(int i=0;i<n;i++){
if(roots[i]!=NULL)nn++;
}
if(nn==1)return nn;
else return 0;
}
void visit(HTNode *root){
if(root->lchild)visit(root->lchild);
cout<<root->weight<<"\t";
if(root->rchild)visit(root->rchild);
}

int main(){
cout<<"输入权值的数目:";
cin>>n;
int weights[n+1];
cout<<"输入权值(1-100):"<<endl;
for(int i=0;i<n;i++){
while(1){
cin>>weights[i];
if(weights[i]>0&&weights[i]<101)break;
else cout<<"重新输入"<<endl;
}
}
// for(int i=0;i<n;i++)cout<<weights[i]<<"\t";
HTNode *pn=NULL,*l=NULL,*r=NULL,*root=NULL,*roots[n];
for(int i=0;i<n;i++)roots[i]=NULL;
int a=popsmall(weights),b=popsmall(weights);
root=(HTNode*)malloc(sizeof(HTNode));root->parent=NULL;root->weight=(a+b);
root->lchild=(HTNode*)malloc(sizeof(HTNode));root->rchild=(HTNode*)malloc(sizeof(HTNode));
root->lchild->lchild=root->lchild->rchild=root->rchild->lchild=root->rchild->rchild=NULL;
root->lchild->parent=root->rchild->parent=root;
root->lchild->weight=a;root->rchild->weight=b;
roots[0]=root;
while(!empty(weights)||!emptyroots(roots)){
// cout<<popsmall(weights)<<"\t";
if(getsmall(weights)<getsmallroots(roots)){
l=(HTNode*)malloc(sizeof(HTNode));
l->weight=popsmall(weights);l->lchild=l->rchild=l->parent=NULL;
if(getsmall(weights)<getsmallroots(roots)){
r=(HTNode*)malloc(sizeof(HTNode));
r->weight=popsmall(weights);r->lchild=r->rchild=r->parent=NULL;
}else{
r=popsmallroots(roots);
}
}else if(getsmall(weights)>getsmallroots(roots)){
l=popsmallroots(roots);
if(getsmall(weights)<getsmallroots(roots)){
r=(HTNode*)malloc(sizeof(HTNode));
r->weight=popsmall(weights);r->lchild=r->rchild=r->parent=NULL;
}else{
r=popsmallroots(roots);
}
}
root=(HTNode*)malloc(sizeof(HTNode));root->parent=NULL;root->weight=(l->weight+r->weight);
root->lchild=l;root->rchild=r;
root->lchild->parent=root->rchild->parent=root;
pushroot(roots,root);
if(empty(weights)&&oneroot(roots))break;
}
cout<<"创建成功"<<endl;
cout<<"中序遍历:"<<endl;
visit(root);
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录