本文实例为大家分享了C语言实现哈夫曼编码的具体代码，供大家参考，具体内容如下

代码来自于《小甲鱼C++快速入门》

主程序main.cpp

#include "stdafx.h"#include <stdlib.h>#include "huffman.h"int main(){ htTree *codeTree = buildTree("I love !");//对输入的字符串进行编码 decode(codeTree,"0011111000111");//解码 system("pause"); return 0;}

两个头文件:
huffman.h:定义了哈夫曼树和编码表的结构

#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是树节点，直接由队列建立起哈夫曼树

#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

两个cpp文件实现两个头文件声明的函数：
huffman.cpp

#include "stdafx.h"#include "queue.h"#include "huffman.h"#include <stdio.h>#include <stdlib.h>#include <string.h>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：

#include "stdafx.h"#include <stdio.h>#include <stdlib.h>#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;}

运行结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。