弄个好名
本文实例为大家分享了c语言实现哈夫曼编码的具体代码，供大家参考，具体内容如下
代码来自于《小甲鱼c 快速入门》
主程序main.cpp
1 2 3 4 5 6 7 8 9 10 11 12 | #include "stdafx.h"#include #include "huffman.h"int main(){ httree *codetree = buildtree("i love wwwwwwwwwfishc.com!");//建立哈夫曼树 hltable *codetable = buildtable(codetree);//建立编码表 encode(codetable,"i love fishc.com!");//对输入的字符串进行编码 decode(codetree,"0011111000111");//解码 system("pause"); return 0;} |
两个头文件:
huffman.h:定义了哈夫曼树和编码表的结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #pragma once#ifndef _huffman_h#define _huffman_htypedef 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; httree *buildtree(char *str);hltable *buildtable(httree *huffmantree);void encode(hltable *table, char *stringtoencode);void decode(httree *tree, char *stringtodecode);#endif |
queue.h：定义了有序队列的结构，将字符按优先级排列，即频率从小到大排列，val是树节点，直接由队列建立起哈夫曼树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #pragma once#ifndef _pqueue_h#define _pqueue_h#include "huffman.h"#define max_sz 256#define type htnode * typedef struct _pqueuenode{ type val; unsigned int priority; struct _pqueuenode *next;}pqueuenode; typedef struct _pqueue{ unsigned int size; pqueuenode *first;}pqueue; void initpqueue(pqueue **queue);void addpqueue(pqueue **queue, type val, unsigned int priority);type getqueue(pqueue **queue);#endif |
huffman.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | #include "stdafx.h"#include "queue.h"#include "huffman.h"#include #include #include httree *buildtree(char *str){ int *probability = (int *)malloc(sizeof(int) * 256); //初始化 for (int i = 0; i < 256; i ) { probability[i] = 0; } //统计待编码的字符串各个字符出现的次数 for (int j = 0; str[j] != '\0'; j ) { probability[str[j]] ; } //定义队列的头指针 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) { unsigned int newpriority = huffmanqueue->first->priority huffmanqueue->first->next->priority; htnode *aux = (htnode *)malloc(sizeof(htnode)); aux->left = getqueue(&huffmanqueue); aux->right = getqueue(&huffmanqueue); addpqueue(&huffmanqueue, aux, newpriority); } httree *tree = (httree *)malloc(sizeof(httree)); tree->root = getqueue(&huffmanqueue); return tree;} void traversetree(htnode *treenode,hltable **table,int k,char code[256]){ if (treenode->left == null&&treenode->right == null) { code[k] = '\0'; 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; } } if (treenode->left != null) { code[k] = '0'; traversetree(treenode->left,table,k 1,code); } if (treenode->right != null) { code[k] = '1'; traversetree(treenode->right, table, k 1, code); }} hltable *buildtable(httree *huffmantree){ hltable *table = (hltable *)malloc(sizeof(hltable)); table->first = null; table->last = null; char code[256]; int k = 0; traversetree(huffmantree->root,&table,k,code); return table;}void encode(hltable *table, char *stringtoencode){ hlnode *traversal; printf("encoding......\n\ninput string:\n%s\n\nencoded string :\n",stringtoencode); for (int i = 0; stringtoencode[i] != '\0'; i ) { traversal = table->first; while (traversal->symbol != stringtoencode[i]) traversal = traversal->next; printf("%s", traversal->code); } printf("\n");}void decode(httree *tree,char *stringtodecode){ htnode *traversal = tree->root; printf("\n\ndecoding......\n\ninput string: \n%s\n\ndecoded string: \n",stringtodecode); for (int i = 0; stringtodecode[i] != '\0'; i ) { if (traversal->left == null&&traversal->right == null) { printf("%c", traversal->symbol); traversal = tree->root; } if (stringtodecode[i] == '0') traversal = traversal->left; else if (stringtodecode[i] == '1') traversal = traversal->right; else { printf("the input string is not coded correctly!\n"); return; } } printf("\n\n"); return;} |
queue.cpp：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #include "stdafx.h"#include #include #include "queue.h"void initpqueue(pqueue **queue){ *queue = (pqueue *)malloc(sizeof(pqueue)); (*queue)->first = null; (*queue)->size = 0; return;}void addpqueue(pqueue **queue, type val, unsigned int priority){ if ((*queue)->size == max_sz) { printf("\n 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 getqueue(pqueue **queue){ type returnvalue; if ((*queue)->size > 0) { returnvalue = (*queue)->first->val; (*queue)->first = (*queue)->first->next; (*queue)->size--; } else { returnvalue = null; printf("\n queue is empty \n"); } return returnvalue;} |
运行结果：
