本文实例为大家分享了C语言实现哈夫曼编码的具体代码，供大家参考，具体内容如下
代码来自于《小甲鱼C++快速入门》
主程序main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#include "stdafx.h"#include <stdlib.h>#include "huffman.h"int main(){ htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hlTable *codeTable = buildTable(codeTree);//建立编码表 encode(codeTable,"I love FishC.com!");//对输入的字符串进行编码 decode(codeTree,"0011111000111");//解码 system("pause"); return 0;} |
两个头文件:
huffman.h:定义了哈夫曼树和编码表的结构
|
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
|
#pragma once#ifndef _HUFFMAN_H#define _HUFFMAN_Htypedef struct _htNode{ char symbol; struct _htNode *left,*right;}htNode; typedef struct _htTree{ htNode *root;}htTree; typedef struct _hlNode{ char symbol; char *code; struct _hlNode *next;}hlNode; typedef struct _hlTable{ hlNode *first; hlNode *last;}hlTable; htTree *buildTree(char *str);hlTable *buildTable(htTree *huffmanTree);void encode(hlTable *table, char *stringToEncode);void decode(htTree *tree, char *stringToDecode);#endif |
queue.h：定义了有序队列的结构，将字符按优先级排列，即频率从小到大排列，val是树节点，直接由队列建立起哈夫曼树
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#pragma once#ifndef _PQUEUE_H#define _PQUEUE_H#include "huffman.h"#define MAX_SZ 256#define TYPE htNode * typedef struct _pQueueNode{ TYPE val; unsigned int priority; struct _pQueueNode *next;}pQueueNode; typedef struct _pQueue{ unsigned int size; pQueueNode *first;}pQueue; void initPQueue(pQueue **queue);void addPQueue(pQueue **queue, TYPE val, unsigned int priority);TYPE getQueue(pQueue **queue);#endif |
两个cpp文件实现两个头文件声明的函数：
huffman.cpp
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#include "stdafx.h"#include "queue.h"#include "huffman.h"#include <stdio.h>#include <stdlib.h>#include <string.h>htTree *buildTree(char *str){ int *probability = (int *)malloc(sizeof(int) * 256); //初始化 for (int i = 0; i < 256; i++) { probability[i] = 0; } //统计待编码的字符串各个字符出现的次数 for (int j = 0; str[j] != '\0'; j++) { probability[str[j]]++; } //定义队列的头指针 pQueue *huffmanQueue; initPQueue(&huffmanQueue); //填充队列 for (int k = 0; k < 256; k++) { if (probability[k] != 0) { htNode *aux = (htNode *)malloc(sizeof(htNode)); aux->left = NULL; aux->right = NULL; aux->symbol = (char)k; addPQueue(&huffmanQueue, aux, probability[k]); } } free(probability); //生成哈夫曼树 while (huffmanQueue->size != 1) { unsigned int newPriority = huffmanQueue->first->priority + huffmanQueue->first->next->priority; htNode *aux = (htNode *)malloc(sizeof(htNode)); aux->left = getQueue(&huffmanQueue); aux->right = getQueue(&huffmanQueue); addPQueue(&huffmanQueue, aux, newPriority); } htTree *tree = (htTree *)malloc(sizeof(htTree)); tree->root = getQueue(&huffmanQueue); return tree;} void traverseTree(htNode *treeNode,hlTable **table,int k,char code[256]){ if (treeNode->left == NULL&&treeNode->right == NULL) { code[k] = '\0'; hlNode *aux = (hlNode *)malloc(sizeof(hlNode)); aux->code = (char *)malloc(sizeof(char)*(strlen(code) + 1)); strcpy(aux->code,code); aux->symbol = treeNode->symbol; aux->next = NULL; if ((*table)->first == NULL) { (*table)->first = aux; (*table)->last = aux; } else { (*table)->last->next = aux; (*table)->last = aux; } } if (treeNode->left != NULL) { code[k] = '0'; traverseTree(treeNode->left,table,k+1,code); } if (treeNode->right != NULL) { code[k] = '1'; traverseTree(treeNode->right, table, k + 1, code); }} hlTable *buildTable(htTree *huffmanTree){ hlTable *table = (hlTable *)malloc(sizeof(hlTable)); table->first = NULL; table->last = NULL; char code[256]; int k = 0; traverseTree(huffmanTree->root,&table,k,code); return table;}void encode(hlTable *table, char *stringToEncode){ hlNode *traversal; printf("Encoding......\n\nInput string:\n%s\n\nEncoded string :\n",stringToEncode); for (int i = 0; stringToEncode[i] != '\0'; i++) { traversal = table->first; while (traversal->symbol != stringToEncode[i]) traversal = traversal->next; printf("%s", traversal->code); } printf("\n");}void decode(htTree *tree,char *stringToDecode){ htNode *traversal = tree->root; printf("\n\nDecoding......\n\nInput string: \n%s\n\nDecoded string: \n",stringToDecode); for (int i = 0; stringToDecode[i] != '\0'; i++) { if (traversal->left == NULL&&traversal->right == NULL) { printf("%c", traversal->symbol); traversal = tree->root; } if (stringToDecode[i] == '0') traversal = traversal->left; else if (stringToDecode[i] == '1') traversal = traversal->right; else { printf("The input string is not coded correctly!\n"); return; } } printf("\n\n"); return;} |
queue.cpp：
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include "stdafx.h"#include <stdio.h>#include <stdlib.h>#include "queue.h"void initPQueue(pQueue **queue){ *queue = (pQueue *)malloc(sizeof(pQueue)); (*queue)->first = NULL; (*queue)->size = 0; return;}void addPQueue(pQueue **queue, TYPE val, unsigned int priority){ if ((*queue)->size == MAX_SZ) { printf("\n Queue is full. \n"); return; } pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode)); aux->priority = priority; aux->val = val; if ((*queue)->size == 0||(*queue)->first==NULL) { aux->next = NULL; (*queue)->first = aux; (*queue)->size = 1; return; } else { if (priority <= (*queue)->first->priority) { aux->next = (*queue)->first; (*queue)->first = aux; (*queue)->size++; return; } else { pQueueNode *iterator = (*queue)->first; while (iterator->next!=NULL) { if (priority <= iterator->next->priority) { aux->next = iterator->next; iterator->next = aux; (*queue)->size++; return; } iterator = iterator->next; } if (iterator->next == NULL) { aux->next = NULL; iterator->next = aux; (*queue)->size++; return; } } }}TYPE getQueue(pQueue **queue){ TYPE returnValue; if ((*queue)->size > 0) { returnValue = (*queue)->first->val; (*queue)->first = (*queue)->first->next; (*queue)->size--; } else { returnValue = NULL; printf("\n Queue is empty \n"); } return returnValue;} |
运行结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/u011643312/article/details/53983278
