哈夫曼编码的抽象数据结构

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 }

源代码

  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 }