这里是使用哈夫曼树定义来给一组字符串的元素编码，从而理解哈夫曼树。
定义理解：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
代码定义：就是一颗特别的二叉树：
//哈夫曼节点
typedef struct _htNode {
char symbol;
struct _htNode *left, *right;
}htNode;
//树根
typedef struct _htTree {
htNode *root;
}htTree;
哈夫曼的树实现：
规定：左小，右大
代码及理解：一些定义：
#define TYPE htNode *
将一组字符串，按照出现次数算权重（优先级），按照优先级高的放在距离树根的位置来构建哈夫曼树：
第一步：将字符串中的字符存入树节点，再将节点存入队列。
将一个字符串的每个字符存入一个树节点中，再将树节点存放再队列中，其中队列节点除了存放树节点以外，还要存放该字符的权重（priority）和一个指针（指向下一个栈节点）：
typedef struct _pQueueNode {
TYPE val;
unsigned int priority;
struct _pQueueNode *next;
}pQueueNode;
队列：
typedef struct _pQueue {
unsigned int size;
pQueueNode *first;
}pQueue;
入队列操作，这里的队列和之前的栈不一样，为了使得后面操作方便，这里入栈时要排序，让权重小的树节点放在前面 ：
void addPQueue(pQueue **queue, TYPE val, unsigned int priority) {
if((*queue)->size == 256) {
printf("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 getPQueue(pQueue **queue) {
TYPE returnValue;
if ((*queue)->size > 0) {
returnValue = (*queue)->first->val;
(*queue)->first = (*queue)->first->next;
(*queue)->size--;
} else {
printf("The queue is wmpty!n");
}
return returnValue;
}
第二部：利用创建好的栈来填充哈夫曼树。
代码：
每次选取权重最小的俩个组成一个小二叉树，根为俩个节点权重和。
htTree* buildTree(char *inputString){
int *probability = (int*)malloc(sizeof(int) * 256);
//初始可能出现的字符次数 （256 = 2^8 ASCLL 码就是二进制八位数）
for (int i = 0; i < 256; i++) {
probability[i] = 0;
}
//计数（字符串中单个字符出现次数）
for (int i = 0; inputString[i] != ' '; i++) {
probability[(unsigned char)inputString[i]]++;
}
//队列初始
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) {
int priority = huffmanQueue->first->priority;
priority += huffmanQueue->first->next->priority;//俩最小权值之和
htNode* left = getPQueue(&huffmanQueue);
htNode* right = getPQueue(&huffmanQueue);//获取俩个最小的权值节点
htNode* newNode = (htNode*)malloc(sizeof(htNode));
newNode->left = left;
newNode->right = right;
addPQueue(&huffmanQueue, newNode, priority);//新的节点 入栈
}
htTree *tree = (htTree*)malloc(sizeof(htTree));
tree->root = getPQueue(&huffmanQueue);
return tree;
}
哈夫曼树转哈夫曼编码
规则：左拐为0，右拐为1；
从根开始递归这个树，然后遇到左节点，就在编码中加0，遇到右节点就在编码中加1，直到遇到没有子节点的节点.这里利用递归完成。
hlTable* buildTable(htTree* huffmanTree) {
hlTable *table = (hlTable *)malloc(sizeof(hlTable));
table->first = NULL;
table->last = NULL;
char code[256];
int k = 0;
traverseTable(huffmanTree->root, &table, k, code);
return table;
}
void traverseTable(htNode* treeNode, hlTable **table, int k, char code[256]) {
if (treeNode->left != NULL) {//递归左节点
code[k] = '0';
traverseTable(treeNode->left, table, k+1, code);
}
if (treeNode->right != NULL) {//递归右节点
code[k] = '1';
traverseTable(treeNode->right, table, k+1, code);
}
if (treeNode->left == NULL && treeNode->right == NULL) {
code[k] = ' ';
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;
}
}
}
其他：
字符串转转编码：
void getcode(hlTable *paraCodeTable, char* paraChar) {
char* result;
int cnt = strlen(paraChar);
printf("'%s' => ", paraChar);
for (int i = 0; i < cnt; i++) {
hlNode *temp1 = paraCodeTable->first;
while ( temp1->symbol != paraChar[i] ) {
temp1 = temp1->next;
if (temp1 == NULL) {
printf("no coden");
return;
}
}
printf("%s", temp1->code);
}
printf("n");
}
编码转字符串：
void decode(htTree* paraTree, char *s) {
htNode *temp = paraTree->root;
printf("nn "%s"-> ", s);
for (int i = 0; s[i] != ' '; i++) {
if (s[i] == '0') {
temp = temp->left;
} else if (s[i] == '1') {
temp = temp->right;
} else {
printf("The code is not right.n");
return;
}
if (temp->left == NULL && temp->right == NULL) {
printf("%c", temp->symbol);
temp = paraTree->root;
}
}
printf("n");
}
总代码：
#include#include #include #define TYPE htNode * //哈夫曼节点 typedef 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; //队列节点 typedef struct _pQueueNode { TYPE val; unsigned int priority; struct _pQueueNode *next; }pQueueNode; //队列 typedef struct _pQueue { unsigned int size; pQueueNode *first; }pQueue; //打印编码表 void printTable(const hlTable *codeTable) { hlNode* temp = codeTable->first; while (temp != codeTable->last) { printf("sympol : %c || code: %8s n", temp->symbol, temp->code); temp = temp->next; } printf("sympol : %c || code: %8s n", temp->symbol, temp->code); } //初始化队 void initPQueue(pQueue **queue){ (*queue) = (pQueue*)malloc(sizeof(pQueue)); (*queue)->first = NULL; (*queue)->size = 0; } //入队列，（排序，从小到大） void addPQueue(pQueue **queue, TYPE val, unsigned int priority) { if((*queue)->size == 256) { printf("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 getPQueue(pQueue **queue) { TYPE returnValue; if ((*queue)->size > 0) { returnValue = (*queue)->first->val; (*queue)->first = (*queue)->first->next; (*queue)->size--; } else { printf("The queue is wmpty!n"); } return returnValue; } //字符串转树 htTree* buildTree(char *inputString){ int *probability = (int*)malloc(sizeof(int) * 256); //初始可能出现的字符次数 （256 = 2^8 ASCLL 码就是二进制八位数） for (int i = 0; i < 256; i++) { probability[i] = 0; } //计数（字符串中单个字符出现次数） for (int i = 0; inputString[i] != ' '; i++) { probability[(unsigned char)inputString[i]]++; } //栈初始 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) { int priority = huffmanQueue->first->priority; priority += huffmanQueue->first->next->priority;//俩最小权值之和 htNode* left = getPQueue(&huffmanQueue); htNode* right = getPQueue(&huffmanQueue);//获取俩个最小的权值节点 htNode* newNode = (htNode*)malloc(sizeof(htNode)); newNode->left = left; newNode->right = right; addPQueue(&huffmanQueue, newNode, priority);//新的节点 入栈 } htTree *tree = (htTree*)malloc(sizeof(htTree)); tree->root = getPQueue(&huffmanQueue); return tree; } //遍历， 将每个字符转化为码 （递归） void traverseTable(htNode* treeNode, hlTable **table, int k, char code[256]) { if (treeNode->left != NULL) {//递归左节点 code[k] = '0'; traverseTable(treeNode->left, table, k+1, code); } if (treeNode->right != NULL) {//递归右节点 code[k] = '1'; traverseTable(treeNode->right, table, k+1, code); } if (treeNode->left == NULL && treeNode->right == NULL) { code[k] = ' '; 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; } } } //哈夫曼转编码 hlTable* buildTable(htTree* huffmanTree) { hlTable *table = (hlTable *)malloc(sizeof(hlTable)); table->first = NULL; table->last = NULL; char code[256]; int k = 0; traverseTable(huffmanTree->root, &table, k, code); return table; } void getcode(hlTable *paraCodeTable, char* paraChar) { char* result; int cnt = strlen(paraChar); printf("'%s' => ", paraChar); for (int i = 0; i < cnt; i++) { hlNode *temp1 = paraCodeTable->first; while ( temp1->symbol != paraChar[i] ) { temp1 = temp1->next; if (temp1 == NULL) { printf("no coden"); return; } } printf("%s", temp1->code); } printf("n"); } void decode(htTree* paraTree, char *s) { htNode *temp = paraTree->root; printf("nn "%s"-> ", s); for (int i = 0; s[i] != ' '; i++) { if (s[i] == '0') { temp = temp->left; } else if (s[i] == '1') { temp = temp->right; } else { printf("The code is not right.n"); return; } if (temp->left == NULL && temp->right == NULL) { printf("%c", temp->symbol); temp = paraTree->root; } } printf("n"); } int main(void){ char s1[] = "man hua su test!"; //建立哈夫曼 htTree *codeTree = buildTree(s1); //将哈夫曼转化为编码表 hlTable *codeTable = buildTable(codeTree); //打印哈夫曼 printTable(codeTable); getcode(codeTable, s1); char s3[] = "1001110100000111101011100001110100010111110110101110"; decode(codeTree, s3); return 0; }
