要求:
对于给定的字符串构建哈夫曼树,生成 huffman 编码,并进行编码 / 译码。
思路:
1. 生成 huffman 树
1> 对样本中各个字符出现次数进行统计
2> 按统计结果以 队列 形式排列
3> 从队列中拿出前两个生成子树,父节点大小为两节点之和
4> 将子树再次按顺序插入队列
5> 重复 3 4 操作,至最后只有一个根节点
2. 生成 huffman 编码
1> 以结构体存放字符(变量)及其 huffman 编码(数组)
2> 向左为 0 ,向右为 1 ,到指针指向 NULL
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include "huffman.h" 4 5 int main() 6 { 7 htTree *codeTree = buildTree("I am yan guo dong!"); // 创建huffman树 通过对字符出现的次数进行统计 8 9 hlTable *codeTable = buildTable(codeTree); // huffman树 -> huffman编码 按次数进行 huffman 编码 10 11 encode(codeTable, "I am yan guo dong!"); // 对字符进行编码 12 13 decode(codeTree, "0011111000111"); // 对编码进行解码 14 15 return 0; 16 } 17 18 19 /* 20 1. 生成 huffman 树 21 1> 对样本中各个字符出现次数进行统计 22 2> 按统计结果以 队列 形式排列 23 3> 从队列中拿出前两个生成子树,父节点大小为两节点之和 24 4> 将子树再次按顺序插入队列 25 5> 重复 3 4 操作,至最后只有一个根节点 26 2. 生成 huffman 编码 27 1> 以结构体存放字符(变量)及其 huffman 编码(数组) 28 2> 向左为 0 ,向右为 1 ,到指针指向 NULL 29 */
1 #pragma once 2 #ifndef _PQUEUE_H 3 #define _PQUEUE_H 4 5 #include "huffman.h" 6 7 #define TYPE htNode * 8 9 #define MAX_SZ 256 10 11 typedef struct _pQueueNode // 队列的节点 12 { 13 TYPE val; // 指向一个树的指针 14 unsigned int priority; // 优先级(非负) 即该字符出现的次数 15 struct _pQueueNode *next; // 指向下一个节点 16 } pQueueNode; 17 18 typedef struct _pQueue // 指向队列的头指针类型 19 { 20 unsigned int size; // 队列的长度 21 pQueueNode *first; // 队列的头指针 22 } pQueue; 23 24 // 队列初始化 传入队列头结点的地址 25 void initPQueue(pQueue **queue); 26 // 将节点插入队列 传入(指针头结点的地址 ,待插入树的节点的指针 ,优先级即字符出现的次数 ) 27 void addPQueue(pQueue **queue, TYPE val, unsigned int priority); 28 // TYPE是树节点的类型 从队列中获取树节点 29 TYPE getPQueue(pQueue **queue); 30 31 #endif
1 #pragma once // 防止被重复定义 2 #ifndef _HUFFMAN_H // 如果没有定义 ,已经定义则跳过 3 #define _HUFFMAN_H // 定义 4 5 typedef struct _htNode // 树的节点 6 { 7 char symbol; // 存放的是字符 8 struct _htNode *left, *right; 9 } htNode; 10 11 typedef struct _htTree 12 { 13 htNode *root; // 树的根节点 14 } htTree; 15 16 typedef struct _hlNode // 链表节点 17 { 18 char symbol; // 存放需编码的字符 19 char *code; // 字符指针,即字符串,存放huffman编码 20 struct _hlNode *next; // 指向下一个节点 21 }hlNode; 22 23 typedef struct _hlTable 24 { 25 hlNode *first; 26 hlNode *last; 27 }hlTable; 28 29 htTree *buildTree(char *inputString); 30 hlTable *buildTable(htTree *huffmanTree); 31 void encode(hlTable *table, char *stringToEncode); 32 void decode(htTree *tree, char *stringToDecode); 33 34 #endif
1 #include "queue.h" 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 void initPQueue(pQueue **queue) // 队列初始化 传入队列头结点的地址 6 { 7 (*queue) = (pQueue *) malloc(sizeof(pQueue)); 8 (*queue)->first = NULL; 9 (*queue)->size = 0; 10 } 11 12 // 将节点插入队列 13 // 传入(指针头结点的地址 ,待插入树的节点的指针 ,优先级即字符出现的次数 ) 14 void addPQueue(pQueue **queue, TYPE val, unsigned int priority) 15 { 16 if((*queue)->size == MAX_SZ) // MAX_SZ = 256 判断队列是否已满 17 { 18 printf(" Queue is full. "); 19 return; 20 } 21 22 pQueueNode *aux = (pQueueNode *) malloc(sizeof(pQueueNode)); // 新建节点内存 23 aux->priority = priority; 24 aux->val = val; 25 26 if((*queue)->size == 0 || (*queue)->first == NULL) // 插入的为第一个节点 27 { 28 aux->next = NULL; 29 (*queue)->first = aux; 30 (*queue)->size = 1; 31 } 32 else 33 { 34 if(priority <= (*queue)->first->priority) // 整个队列按字符出现的次数进行前后排序 35 { // 对将插入的队列节点优先级进行判断,排序 36 aux->next = (*queue)->first; 37 (*queue)->first = aux; 38 (*queue)->size++; 39 return; 40 } 41 else 42 { 43 pQueueNode *iterator = (*queue)->first; // 临时变量 ,等于第一个节点 44 while(iterator->next!=NULL) // 遍历整个队列,进行判断排序 45 { 46 if(priority <= iterator->next->priority) 47 { 48 aux->next = iterator->next; 49 iterator->next = aux; 50 (*queue)->size++; 51 return ; 52 } 53 iterator = iterator->next; 54 } 55 56 if(iterator->next == NULL) // 当待插入节点为队列中最大的一个,即该节点位于队列最后 57 { 58 aux->next = NULL; 59 iterator->next = aux; 60 (*queue)->size++; 61 return; 62 } 63 } 64 } 65 } 66 67 // TYPE是树节点的类型 68 TYPE getPQueue(pQueue **queue) // 从队列中获取数据 69 { 70 TYPE returnValue; // 返回的节点数据 (指针类型) 71 72 if((*queue)->size > 0) // 将传入队列节点的下一个队列节点中指向的树节点返回 73 { 74 returnValue = (*queue)->first->val; 75 // 执行删除队列节点操作 76 (*queue)->first = (*queue)->first->next; // 队列指针指向下一个队列节点 77 (*queue)->size--; // 队列长度减一 78 } 79 else 80 { 81 printf(" Queue is empty. "); 82 } 83 return returnValue; // 将指向树节点的指针返回 84 }
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #include "huffman.h" 6 #include "queue.h" 7 8 // 从 huffman树 根节点开始进行 huffman编码 9 // 10 void traverseTree(htNode *treeNode, hlTable **table, int k, char code[256]) 11 { 12 if(treeNode->left == NULL && treeNode->right == NULL) // 没有左右孩子 为叶子节点 13 { 14 15 code[k] = '