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 noden"); } return getnode; } hhfmtreenode* crthfmtree(hqueuenode** hqueue) { int count=0; hfmtreenode *left, *right; while((*hqueue)->size>1) { count=(*hqueue)->first->count+(*hqueue)->first->next->count; left=gethfmtreenode(*hqueue); right=gethfmtreenode(*hqueue); hfmtreenode *newnode=(hfmtreenode*)malloc(sizeof(hfmtreenode)); newnode->left=left; newnode->right=right; addqueuenode(hqueue,newnode,count); } hhfmtreenode* tree=(hhfmtreenode*)malloc(sizeof(hhfmtreenode)); tree->rootnode=gethfmtreenode(*hqueue); return tree; } hhfmtreenode* creattree(void) { file *ifile; int *countarray; char c; int i; countarray=(int*)malloc(sizeof(int)*256);//分配空间用于存储各字符出现的次数,并初始化为零 for(i=0;i<256;i++) { countarray[i]=0; } ifile=fopen("d://1.txt","r"); if(!ifile) //检查文件是否打开成功 printf("can't open the filen"); else { while((c=getc(ifile))!=eof) { countarray[(unsigned int)c]++; printf("%c", c); } fclose(ifile); } hqueuenode *hqueue; initqueue(&hqueue); for(i=0;i<256;i++) { if(countarray[i]) { //printf("%c %dn",i, countarray[i] ); hfmtreenode *hnode=(hfmtreenode*)malloc(sizeof(hfmtreenode));//创建一个树节点,并初始化(用来对应队列queuenode中的ptr) hnode->symbol=(char)i; hnode->left=null; hnode->right=null; addqueuenode(&hqueue,hnode,countarray[i]);//将该节点插入队列中的适当位置(按统计的结果,从小到大排列) } } free(countarray);//释放不用的内存 queuenode* q=hqueue->first; printf("n"); do { printf("n%c %d",q->ptr->symbol, q->count); q=q->next; } while(q!=null); //printf("%d",hqueue->size); hhfmtreenode *tree=crthfmtree(&hqueue); return tree; } void traversetree( hdtablenode** table, hfmtreenode* tree, char* code, int k) { if(tree->left==null && tree->right==null) //递归结束检查,即找到叶子节点 { code[k]='