C语言实现哈夫曼编码分享！

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

代码来自于《小甲鱼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!");//对输入的字符串进行编码   decode(codeTree,"0011111000111");//解码   system("pause");   return 0;  }

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

  #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：定义了有序队列的结构，将字符按优先级排列，即频率从小到大排列，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] != ''; 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] = '';   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......nnInput string:n%snnEncoded string :n",stringToEncode);   for (int i = 0; stringToEncode[i] != ''; 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("nnDecoding......nnInput string: n%snnDecoded string: n",stringToDecode);   for (int i = 0; stringToDecode[i] != ''; 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("nn");   return;  }

• 1
• 2
• 下一页