快捷導(dǎo)航

C語言實(shí)現(xiàn)哈夫曼編碼

更新時(shí)間：2020年04月28日 10:28:23 作者：_yxy_

這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)哈夫曼編碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了C語言實(shí)現(xiàn)哈夫曼編碼的具體代碼，供大家參考，具體內(nèi)容如下

代碼來自于《小甲魚C++快速入門》

主程序main.cpp

#include "stdafx.h"
#include <stdlib.h>
#include "huffman.h"
int main()
{
 htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼樹
 hlTable *codeTable = buildTable(codeTree);//建立編碼表
 encode(codeTable,"I love FishC.com!");//對輸入的字符串進(jìn)行編碼
 decode(codeTree,"0011111000111");//解碼
 system("pause");
 return 0;
}

兩個(gè)頭文件:
huffman.h:定義了哈夫曼樹和編碼表的結(jié)構(gòu)

#pragma once
#ifndef _HUFFMAN_H
#define _HUFFMAN_H
typedef 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：定義了有序隊(duì)列的結(jié)構(gòu)，將字符按優(yōu)先級排列，即頻率從小到大排列，val是樹節(jié)點(diǎn)，直接由隊(duì)列建立起哈夫曼樹

#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

兩個(gè)cpp文件實(shí)現(xiàn)兩個(gè)頭文件聲明的函數(shù)：
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;
 }
 //統(tǒng)計(jì)待編碼的字符串各個(gè)字符出現(xiàn)的次數(shù)
 for (int j = 0; str[j] != '\0'; j++)
 {
 probability[str[j]]++;
 }
 
 //定義隊(duì)列的頭指針
 pQueue *huffmanQueue;
 initPQueue(&huffmanQueue);
 //填充隊(duì)列
 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;
}

運(yùn)行結(jié)果：