Huffman编码

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <string>
  7 using namespace std;
  8 
  9 struct Node {
 10     char character;
 11     unsigned int weight;
 12     unsigned int parent;
 13     unsigned int lchild;
 14     unsigned int rchild;
 15 };
 16 
 17 Node *HT = NULL;
 18 char **HC = NULL;
 19 int n = 0;
 20 
 21 void CreatHuffmanTree(void);
 22 void CodeHuffman(void);
 23 void Encode(void);
 24 void Decode(void);
 25 void Free(void);
 26 void Select(const int len, int &a, int &b);
 27 int Search(const char &key);
 28 
 29 int main(void)
 30 {
 31     freopen("cin.txt", "r", stdin);
 32     freopen("cout.txt", "w", stdout);
 33     while (cout << "请输入字符个数：\n", cin >> n) {    //    n>=2
 34         getchar();                //    吸收回车，防止空格字符的输入异常
 35 
 36         CreatHuffmanTree();        //    建哈夫曼树
 37 
 38         CodeHuffman();            //    为每个字符编码
 39 
 40         Encode();                //    为明文编码
 41 
 42         Decode();                //    从密文译码
 43 
 44         Free();                    //    释放动态分配的空间
 45     }
 46     system("pause");// 有用？
 47     return 0;
 48 }
 49 
 50 void CreatHuffmanTree(void)
 51 {
 52     // weight存放n个字符的权值(均>0)，构造哈夫曼树HT，
 53     // 并求出n个字符的哈夫曼编码HC
 54     if (n <= 1)
 55         return;
 56     int m = 2 * n - 1;
 57 
 58     HT = (Node *)malloc((m + 1) * sizeof(Node));    //    0号单元未用
 59     if( HT == NULL) {
 60         cerr << "Allocate failed!" << endl;
 61         exit(OVERFLOW);
 62     }
 63     memset(HT, 0, (m + 1) * sizeof(Node));
 64 
 65     cout << "请输入各字符及其权值：" << endl;
 66     for (int i = 1; i <= n; i++) {
 67         HT[i].character = getchar();
 68         cin >> HT[i].weight;                        //    输入字符及权值的信息
 69         getchar();
 70     }
 71     cout << n << "个字符及其权值：" << endl;
 72     for (int i = 1; i <= n; i++) {
 73         printf("%c(%3d) ", HT[i].character, HT[i].weight);
 74         if (i % 10 == 0)
 75             cout << endl;
 76     }
 77     cout << endl;
 78 
 79     /*    printf("\n哈夫曼树的构造过程如下所示：\n");
 80     printf("HT初态:\n  结点  weight  parent  lchild  rchild");
 81     for (int i = 1; i <= m; i++)
 82     printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 83     printf("    按回车键，继续 ...");
 84     //    getchar();*/
 85 
 86     for (int i = n + 1; i <= m; i++) {
 87         // 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
 88         // 其序号分别为s1和s2。
 89         int s1(0);
 90         int s2(0);
 91         Select(i - 1, s1, s2);
 92         HT[s1].parent = i;
 93         HT[s2].parent = i;
 94         HT[i].lchild = s1;
 95         HT[i].rchild = s2;
 96         HT[i].weight = HT[s1].weight + HT[s2].weight;
 97 
 98         /*        printf("\nselect: s1=%d   s2=%d\n\n", s1, s2);
 99         printf("  结点  weight  parent  lchild  rchild");
100         for (int j = 1; j <= i; j++)
101         printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
102         printf("    按回车键，继续 ...");
103         //        getchar();*/
104     }
105 }
106 
107 void CodeHuffman(void)
108 {
109     //--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
110     HC = (char **)malloc((n + 1) * sizeof(char *));            //    指针数组
111     if (HC == NULL) {
112         cerr << "Allocate failed!" << endl;
113         exit(OVERFLOW);
114     }
115     memset(HC, 0, (n + 1) * sizeof(char *));                //    0号单元未用
116 
117     char *cd = (char *)malloc(n * sizeof(char));            // 分配求编码的工作空间
118     if (cd == NULL) {
119         cerr << "Allocate failed!" << endl;
120         exit(OVERFLOW);
121     }
122     memset(cd, 0, n * sizeof(char));                        // 编码结束符。
123 
124     for (int i = 1; i <= n; ++i) {                            // 逐个字符求哈夫曼编码
125         int start = n - 1;                                    // 编码结束符位置
126         unsigned int c(0);
127         unsigned int f(0);
128         for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {                                                        
129             if (HT[f].lchild == c)                            // 从叶子到根逆向求编码
130                 cd[--start] = ‘0‘;
131             else
132                 cd[--start] = ‘1‘;            
133         }
134 
135         HC[i] = (char *)malloc((n - start) * sizeof(char));    // 为第i个字符编码分配空间
136         if (HC[i] == NULL) {
137             cerr << "Allocate failed!" << endl;
138             exit(OVERFLOW);
139         }
140 
141         strcpy(HC[i], &cd[start]);                            // 从cd复制编码(串)到HC
142     }
143     free(cd);
144     cd = NULL;
145 
146     printf("\n\n各字符的哈夫曼编码如下：\n");
147     for(int i = 1; i <= n; i++) {
148         printf("%c(%3d): %s\n" ,HT[i].character, HT[i].weight, HC[i]);
149     }
150 }
151 
152 void Encode(void)
153 {
154     cout << "请输入报文：" << endl;
155     string str;
156     getline(cin, str);
157     for (unsigned int i = 0; i < str.size(); i++) {
158         int loc = Search(str[i]);
159         cout << HC[loc] << endl;
160     }
161     cout << endl;
162 }
163 
164 void Decode(void)
165 {
166     cout << "请输入密文：" << endl;
167     string str;
168     cin >> str;
169     for (unsigned int i = 0; i < str.size();) {
170         int cursor = 2 * n - 1;
171         while (HT[cursor].lchild != 0 && HT[cursor].rchild != 0) {    //    全非0
172             switch (str[i++]) {
173 
174             case ‘0‘:
175                 cursor = HT[cursor].lchild;
176                 break;
177 
178             case ‘1‘:
179                 cursor = HT[cursor].rchild;
180                 break;
181 
182             default:
183                 cerr << "Input error!" << endl;
184                 exit (1);
185             }
186         }
187         if (!(HT[cursor].lchild == 0 && HT[cursor].rchild == 0)) {    //    此时应是全0
188             cerr << "Input error!" << endl;
189             exit (1);            
190         }
191         cout << HT[cursor].character << endl;
192     }
193 }
194 
195 void Free(void)
196 {
197     free(HT);    //    释放动态分配的空间
198     HT = NULL;
199     for(int i = 1; i <= n; i++) {
200         free(HC[i]);
201         HC[i] = NULL;
202     }
203     free(HC);
204     HC = NULL;
205 }
206 
207 void Select(const int len, int &a, int &b)
208 {
209     // 在HT[1..len]中选择parent为0且weight最小的两个结点，
210     // 其序号分别为a和b。
211     for (int i = 1; i <= len; i++) {
212         if (HT[i].parent == 0) {
213             a = i;
214             break;
215         }
216     }
217     for (int i = a + 1; i <= len; i++) {
218         if (HT[i].parent == 0) {
219             b = i;
220             break;
221         }
222     }
223     if (HT[a].weight > HT[b].weight)    //    保持a的始终小于b的，有序
224         swap(a, b);
225     for (int i = max(a, b) + 1; i <= len; i++) {
226         if (HT[i].parent == 0) {
227             if (HT[i].weight > HT[b].weight)
228                 continue;
229             else if (HT[i].weight < HT[a].weight) {
230                 b = a;
231                 a = i;
232             }
233             else
234                 b = i;
235         }
236     }
237     if ( !(HT[a].parent == 0 && HT[b].parent == 0) ) {
238         cerr << "Error!" << endl;
239         exit(1);
240     }
241 }
242 
243 int Search(const char &key)        //    找到key在HT中的下标，找不到则返回0
244 {
245     HT[0].character = key;        //    哨兵,顺序查找
246     int i;
247     for (i = n; HT[i].character != key; --i);
248     if (i == 0) {
249         cerr << "Inexistence!" << endl;
250         exit(1);
251     }
252     return i;
253 }
254 
255 /*
256 cin.txt:
257 27
258   186
259 a 64
260 b 13
261 c 22
262 d 32
263 e 103
264 f 21
265 g 15
266 h 47
267 i 57
268 j 1
269 k 5
270 l 32
271 m 20
272 n 57
273 o 63
274 p 15
275 q 1
276 r 48
277 s 51
278 t 80
279 u 23
280 v 8
281 w 18
282 x 1
283 y 16
284 z 1
285 this program is my favorite
286 */