|
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
|
typedef
struct
{
unsigned
int
weight;
unsigned
int
parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef
char
** HuffmanCode;
void
HuffmanCoding(HuffmanTree& HT,HuffmanCode & HC,
int
*w,
int
n) {
if
(n < 1)
return
;\
int
m = 2* n + 1;
HT = (HuffmanTree)
malloc
(m+1)*
sizeof
(HTNode);
//0 号单元未用
for
( HuffmanTree p = HT; i=1; i<=n; ++i; ++p; ++w)
*p = {*w,0,0,0,0};
for
(; i<=m; ++i; ++p)
*p = {0,0,0,0};
for
(i = n+1; i<=m; i++) {
//建立HuffmanTree
Select(HT,i-1,s1,s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)
malloc
((n+1)*
sizeof
(
char
*));
cd = (
char
*)
malloc
(n*
sizeof
(
char
));
cd [n-1] =
"\0"
;
for
( i=1; i<=n; i++) {
int
start = n-1;
for
( c=i, f = HT[i].parent; f!=0; c=f; f = HT[f].parent )
if
( HT[f].lchild == c ) cd [--start] =
"0"
;
else
cd [--start] =
"1"
;
HC[i] = (
char
*)
malloc
( (n-start)*
sizeof
(
char
));
strcyp(HC[i],&cd[start]);
}
free
(cd);
}
|
------ 无栈非递归遍历赫夫曼树，求赫夫曼编码------
HC = (HuffmanCode) malloc ( (n+1) * sizeof(char*)); int p = m, cdlen = 0; for ( int i=1; i<=m; ++i) HT[i].weight = 0; while(p) { if ( HT[p].weight == 0 ) { HT[p].weight = 1; if ( HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] = "0"; }else if ( HT[p].lchild == 0) { HC[p] = (char*) malloc ((cdlen+1) * sizeof(char)); cd[cdlen] = "\0"; strcpy(HC[p],cd); } }else if ( HP[p].weight == 1) { HT[p].weight = 2; if ( HT[p].rchild != 0) { p = HT[p].rchild; cd [cdlen++] = "1"; }else { HT[p].weight = 0; p = HT[p].parent; --cdlen; } } }
本文转自莫水千流博客园博客，原文链接：http://www.cnblogs.com/zhoug2020/archive/2012/11/30/2795617.html，如需转载请自行联系原作者
