1. 目标
读取一段字符，生成哈夫曼编码，并输出。如下所示：
2. 代码结构
2.1 统计各个字符出现的次数，并排序；
2.2 根据生成的哈夫曼树，生成哈夫曼编码；
3. 源代码
#include
#include
#include
#define title #define queueSize_Max 256 //队列的最大长度 #define code_Max 256 //编码的最大长度 /**************************************/ /*定义Huffman Tree节点 */ /*其中symbol记录节点存储的字符 */ /*left, right指向左右子节点 */ /**************************************/ typedef struct hfmTreeNode{ int symbol; struct hfmTreeNode *left; struct hfmTreeNode *right; } hfmTreeNode, *phTreeNode; /**************************************/ /*定义一个指向Huffman Tree的根节点 */ /**************************************/ typedef struct hHfmTreeNode{ hfmTreeNode* rootNode; } hHfmTreeNode; /**************************************/ /*定义队列的节点 */ /*ptr是一个指向phTreeNode的指针， */ /*主要是方便后续建立Huffman Treee */ /*Count记录字符出现的频次， */ /*next指向下一个节点 */ /**************************************/ typedef struct queueNode{ phTreeNode ptr; int count; struct queueNode *next; } queueNode, *ptrQueue; /**************************************/ /*定义指向queueNode的头节点 */ /*其中size记录节点的数量 */ /*first指向queueNode的第一个节点 */ /**************************************/ typedef struct hQueueNode{ int size; ptrQueue first; } hQueueNode; /**************************************/ /*定义指向记录编码的table节点 */ /*symble为字符，code指向对应的编码 */ /*next用来指向下一个节点 */ /**************************************/ typedef struct tableNode{ char symbol; char* code; struct tableNode *next; } tableNode; /**************************************/ /*定义指向tableNode的头节点 */ /*first标记第一个节点 */ /*last指向最后一个节点 */ /**************************************/ typedef struct hdTableNode{ tableNode *first; tableNode *last; } hdTableNode; /**************************************/ /*对队列进行初始，添加一个头节点 */ /*其中size记录节点的数量 */ /*first指向queue节点 */ /**************************************/ void initQueue(hQueueNode** hQueue) { *hQueue=(hQueueNode*)malloc(sizeof(hQueueNode)); (*hQueue)->size=0; (*hQueue)->first=NULL; } void addQueueNode(hQueueNode **hQueue,hfmTreeNode *hNode,int count)//新建一个队列节点并按统计的结果从小到大的顺序加入队列 { queueNode *qNode=NULL; if((*hQueue)->size==queueSize_Max)//队列规模检查，正常情况下不会出现 { printf("\nERR: The queue is full!!!"); } else //如果正常，则按照从小到大的顺序，寻找正确的位置插入节点 { if(0==(*hQueue)->size)//如果是添加的第一个节点，直接添加即可 { qNode=(queueNode*)malloc(sizeof(queueNode)); (*hQueue)->first=qNode; qNode->count=count; qNode->ptr=hNode; qNode->next=NULL; (*hQueue)->size++; } else if(count<(*hQueue)->first->count)//如果要添加的字符的统计数量小于现有最小的，则直接放在第一个节点处 { qNode=(queueNode*)malloc(sizeof(queueNode)); qNode->next=(*hQueue)->first; (*hQueue)->first=qNode; qNode->count=count; qNode->ptr=hNode; (*hQueue)->size++; } else //对于第三类情况，则需要遍历队列，直到寻找到合适的位置 { queueNode* p=(*hQueue)->first; qNode=(queueNode*)malloc(sizeof(queueNode)); qNode->count=count; qNode->ptr=hNode; (*hQueue)->size++; while(p->next!=NULL && count>=p->next->count) p=p->next; qNode->next=p->next; p->next=qNode; } } } hfmTreeNode* getHfmTreeNode(hQueueNode* hQueue) { hfmTreeNode* getNode; if(hQueue->size>0) { getNode=hQueue->first->ptr; hQueue->first=hQueue->first->next; hQueue->size--; } else { printf("\nERR: Can't get a node\n"); } return getNode; } hHfmTreeNode* crtHfmTree(hQueueNode** hQueue) { int count=0; hfmTreeNode *left, *right; while((*hQueue)->size>1) { count=(*hQueue)->first->count+(*hQueue)->first->nex