分享程序员开发的那些事...
更新时间：2022-09-16 17:28:29
|
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，如需转载请自行联系原作者