哈夫曼编码的抽象数据结构
1 typedef struct
2 {
3 int weigth;
4 int parent;
5 int lchild;
6 int rchild;
7 }HTNode, * HuffmanTree;/*动态分配数组存储哈夫曼树*/
求哈夫曼编码的算法
1 void HuffmanCoding(HuffmanTree* HT, char*** HC, int* W, int n)
2 {/* 指针W指向的数组中存放 n 个字符的权值(均>0),构造哈夫曼树HT ，并求出 n 个字符的哈夫曼编码HC*/
3 int s1 = 0;
4 int s2 = 0;
5 int i = 0;
6 int m = 2 * n - 1;
7 int child = 0;
8 int parent = 0;
9 int start = 0;
10 char* cd = NULL;
11 HuffmanTree P = NULL;
12 if (n <= 1)
13 {
14 return;
15 }
16
17 (*HT) = (HuffmanTree)calloc(m + 1, sizeof(HTNode));/*0号单元未使用*/
18 for (P = (*HT) + 1, i = 1; i <= n; ++i, ++P, ++W)
19 {
20 P->weigth = *W;
21 }
22 for (i = n + 1; i <= m; ++i)/*建霍夫曼树*/
23 {/*在 HT[1... i - 1]选择 parent 为 0 且 weigth 值最小的两个结点，其序号分别为 s1 和 s2*/
24 Select((*HT), i - 1, &s1, &s2);
25
26 (*HT)[s1].parent = i;
27 (*HT)[s2].parent = i;
28 (*HT)[i].lchild = s1;
29 (*HT)[i].rchild = s2;
30 (*HT)[i].weigth = (*HT)[s1].weigth + (*HT)[s2].weigth;
31 }
32
33 /*下面从叶子到根逆向求每个字符的哈夫曼编码*/
34 (*HC) = (char**)calloc(n + 1, sizeof(char*));
35 cd = (char*)calloc(n, sizeof(char));/*临时编码数组*/
36 cd[n - 1] = '\0';/*从后向前逐位求编码，首先放编码结束符*/
37 for (i = 1; i <= n; ++i)
38 {
39 start = n - 1;
40 for (child = i, parent = (*HT)[i].parent; parent != 0; child = parent, parent = (*HT)[parent].parent)
41 {
42 if ((*HT)[parent].lchild == child)
43 {
44 cd[--start] = '0';
45 }
46 else
47 {
48 cd[--start] = '1';
49 }
50 (*HC)[i] = (char*)calloc(n - start, sizeof(char));
51 strcpy((*HC)[i], &cd[start]);
52 }
53 /*printf("哈夫曼码为：%s\n", HC[i]);*/
54 }
55 }
在权值数组中寻找权值最小的两个结点
1 void Select(HuffmanTree HT, int N, int* s1, int* s2)
2 {/*在 HT[1... N]选择 parent 为 0 且 weigth 值最小的两个结点，其序号分别为 s1 和 s2*/
3 int i = 1;
4 int t1 = 0;
5 int t2 = 0;
6 for (i = 1; i <= N; ++i)
7 {
8 if (HT[i].parent == 0)
9 {
10 t1 = i;
11 break;
12 }
13 }
14 if (t1 == 0)
15 {
16 printf("\n最小结点t1异常\n");
17 }
18 for (i = 1; i <= N; ++i)
19 {/*找t1*/
20 if (HT[i].parent == 0 && HT[i].weigth < HT[t1].weigth)
21 {
22 t1 = i;
23 }
24 }
25
26 for (i = 1; i <= N; ++i)
27 {
28 if (HT[i].parent == 0 && i != t1)
29 {
30 t2 = i;
31 break;
32 }
33 }
34 if (t2 == 0)
35 {
36 printf("\n最小结点t2异常\n");
37 }
38 for (i = 1; i <= N; ++i)
39 {/*找t2*/
40 if (HT[i].parent == 0 && HT[i].weigth < HT[t2].weigth && i != t1)
41 {
42 t2 = i;
43 }
44 }
45 *s1 = t1;
46 *s2 = t2;
47 }
View Code
源代码
1 /*-------------------------------------------------------------------------
2 * Name: 哈夫曼编码源代码
3 * Date: 2022.01.15
4 * Author: 吕辉
5 * 在 Visual Studio Community 2022 下测试通过
6 *------------------------------------------------------------------------*/
7 #define _CRT_SECURE_NO_WARNINGS
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11
12 typedef struct
13 {
14 int weigth;
15 int parent;
16 int lchild;
17 int rchild;
18 }HTNode, * HuffmanTree;/*动态分配数组存储哈夫曼树*/
19
20 void HuffmanCoding(HuffmanTree* HT, char*** HC, int* W, int n);
21 void Select(HuffmanTree HT, int N, int* s1, int* s2);
22
23 int main(void)
24 {
25 HuffmanTree HT = NULL;
26 char** HC = NULL;
27 int weight[8] = { 5, 29, 7, 8, 14, 23, 3, 11 };
28 int* W = weight;
29 int n = 8;
30 int i = 0;
31
32 HuffmanCoding(&HT, &HC, W, n);
33
34 for (i = 1; i <= n; i++)
35 {
36 printf("权值为%2d的哈夫曼码为：%s\n", HT[i].weigth, HC[i]);
37 }
38
39 system("pause");
40 return 0;
41 }
42 void HuffmanCoding(HuffmanTree* HT, char*** HC, int* W, int n)
43 {/* 指针W指向的数组中存放 n 个字符的权值(均>0),构造哈夫曼树HT ，并求出 n 个字符的哈夫曼编码HC*/
44 int s1 = 0;
45 int s2 = 0;
46 int i = 0;
47 int m = 2 * n - 1;
48 int child = 0;
49 int parent = 0;
50 int start = 0;
51 char* cd = NULL;
52 HuffmanTree P = NULL;
53 if (n <= 1)
54 {
55 return;
56 }
57
58 (*HT) = (HuffmanTree)calloc(m + 1, sizeof(HTNode));/*0号单元未使用*/
59 for (P = (*HT) + 1, i = 1; i <= n; ++i, ++P, ++W)
60 {
61 P->weigth = *W;
62 }
63 for (i = n + 1; i <= m; ++i)/*建霍夫曼树*/
64 {/*在 HT[1... i - 1]选择 parent 为 0 且 weigth 值最小的两个结点，其序号分别为 s1 和 s2*/
65 Select((*HT), i - 1, &s1, &s2);
66
67 (*HT)[s1].parent = i;
68 (*HT)[s2].parent = i;
69 (*HT)[i].lchild = s1;
70 (*HT)[i].rchild = s2;
71 (*HT)[i].weigth = (*HT)[s1].weigth + (*HT)[s2].weigth;
72 }
73
74 /*下面从叶子到根逆向求每个字符的哈夫曼编码*/
75 (*HC) = (char**)calloc(n + 1, sizeof(char*));
76 cd = (char*)calloc(n, sizeof(char));/*临时编码数组*/
77 cd[n - 1] = '\0';/*从后向前逐位求编码，首先放编码结束符*/
78 for (i = 1; i <= n; ++i)
79 {
80 start = n - 1;
81 for (child = i, parent = (*HT)[i].parent; parent != 0; child = parent, parent = (*HT)[parent].parent)
82 {
83 if ((*HT)[parent].lchild == child)
84 {
85 cd[--start] = '0';
86 }
87 else
88 {
89 cd[--start] = '1';
90 }
91 (*HC)[i] = (char*)calloc(n - start, sizeof(char));
92 strcpy((*HC)[i], &cd[start]);
93 }
94 /*printf("哈夫曼码为：%s\n", HC[i]);*/
95 }
96 }
97
98 void Select(HuffmanTree HT, int N, int* s1, int* s2)
99 {/*在 HT[1... N]选择 parent 为 0 且 weigth 值最小的两个结点，其序号分别为 s1 和 s2*/
100 int i = 1;
101 int t1 = 0;
102 int t2 = 0;
103 for (i = 1; i <= N; ++i)
104 {
105 if (HT[i].parent == 0)
106 {
107 t1 = i;
108 break;
109 }
110 }
111 if (t1 == 0)
112 {
113 printf("\n最小结点t1异常\n");
114 }
115 for (i = 1; i <= N; ++i)
116 {/*找t1*/
117 if (HT[i].parent == 0 && HT[i].weigth < HT[t1].weigth)
118 {
119 t1 = i;
120 }
121 }
122
123 for (i = 1; i <= N; ++i)
124 {
125 if (HT[i].parent == 0 && i != t1)
126 {
127 t2 = i;
128 break;
129 }
130 }
131 if (t2 == 0)
132 {
133 printf("\n最小结点t2异常\n");
134 }
135 for (i = 1; i <= N; ++i)
136 {/*找t2*/
137 if (HT[i].parent == 0 && HT[i].weigth < HT[t2].weigth && i != t1)
138 {
139 t2 = i;
140 }
141 }
142 *s1 = t1;
143 *s2 = t2;
144 }
View Code