C语言:数据结构、哈夫曼编码、Huffman-源代码
程序员文章站
2022-07-04 11:54:20
1. 目标
读取一段字符,生成哈夫曼编码,并输出。如下所示:
2. 代码结构
2.1 统计各个字符出现的次数,并排序;
2.2 根据生成的哈夫曼树,生成哈夫曼编码;
3. 源代码
#in...
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->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 file\n"); 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 %d\n",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]='\0'; //添加字符串结束标记 tablenode *tnode=(tablenode*)malloc(sizeof(tablenode)); //创建一个节点,并将其添加到table链表中 tnode->code=(char*)malloc(sizeof(char)*256+1); strcpy(tnode->code,code); tnode->symbol=tree->symbol; tnode->next=null; if((*table)->first==null) //如果是第一个节点,直接添加即可, 否则添加到尾部即可 { (*table)->first=tnode; (*table)->last=tnode; } else { (*table)->last->next=tnode; (*table)->last=tnode; } } if(tree->left!=null) //向左边递归,并记录编码为0 { code[k]='0'; traversetree(table,tree->left, code, k+1); } if(tree->right!=null) //向右边递归,并记录编码为1 { code[k]='1'; traversetree(table, tree->right, code, k+1); } } hdtablenode* crttable(hhfmtreenode* hfmtree) { hdtablenode* hdtable=(hdtablenode*)malloc(sizeof(hdtablenode)); hdtable->first=null; hdtable->last=null; char code[code_max]; int k=0; //记录树的层级 traversetree(&hdtable, hfmtree->rootnode, code, k); return hdtable; } int main(void) { hhfmtreenode* tree; hdtablenode* table; printf("%s\n\n\n",title); tree=creattree(); table=crttable(tree); int i=0, j=0; tablenode* t=table->first; char* s=t->code; printf("\n\n*************************************************************************************\n"); printf("the huffman code is:\n"); while(t!=null) { for(i=0;i<257;i++) { if((*s)!='\0') { printf("%c",*s); s++; } } printf("%8c\n",t->symbol); t=t->next; if(t) s=t->code; } }