快捷導(dǎo)航

C語言實(shí)現(xiàn)BMP圖像處理(哈夫曼編碼)

更新時(shí)間：2021年10月25日 17:08:56 作者：傻不拉幾的程序員

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

哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是 Huffman 于 1952 年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。這些代碼都是二進(jìn)制碼，且碼的長(zhǎng)度是可變的。

下面給出具體的 Huffman 編碼算法：

(1) 首先統(tǒng)計(jì)出每個(gè)符號(hào)出現(xiàn)的頻率，上例 S0 到 S7 的出現(xiàn)頻率分別為 4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。
(2) 從左到右把上述頻率按從小到大的順序排列。
(3) 每一次選出最小的兩個(gè)值，作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。
(4) 重復(fù)(3)，直到最后得到和為 1 的根節(jié)點(diǎn)。
(5) 將形成的二叉樹的左節(jié)點(diǎn)標(biāo) 0，右節(jié)點(diǎn)標(biāo) 1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的 0,1 序列串起來，就得到了各個(gè)符號(hào)的編碼。

產(chǎn)生 Huffman 編碼需要對(duì)原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中，每個(gè)值出現(xiàn)的頻率，第二遍是建立 Huffman 樹并進(jìn)行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡(jiǎn)單有效，因而得到廣泛的應(yīng)用。

第一步：實(shí)現(xiàn)哈夫曼編碼與解碼

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
 
// 結(jié)構(gòu)體
typedef struct Tree
{
 int weight; // 權(quán)值
 int id;     // 后面解碼用到
 struct Tree * lchild; // 左孩子
 struct Tree * rchild; // 右孩子
}TreeNode;
 
// 創(chuàng)建哈夫曼樹
TreeNode* createTree(int *arr, int n)
{
 int i, j;
 TreeNode **temp, *hufmTree;
 temp = (TreeNode**)malloc(sizeof(TreeNode*)*n); // 創(chuàng)建結(jié)構(gòu)體指針數(shù)組
 for (i = 0; i < n; ++i)
 {
  temp[i] = (TreeNode*)malloc(sizeof(TreeNode));
  temp[i]->weight = arr[i];
  temp[i]->lchild = temp[i]->rchild = NULL;
  temp[i]->id = i;
 }
 
 for (i = 0; i < n - 1; ++i)
 {
  int small1 = -1, small2; // 存儲(chǔ)最小權(quán)值的兩個(gè)節(jié)點(diǎn)
  for (j = 0; j < n; ++j)  // 第一步：找到最開始兩個(gè)非空節(jié)點(diǎn)
  {
   if (temp[j] != NULL && small1 == -1)
   {
    small1 = j;
    continue;
   }
   if (temp[j] != NULL)
   {
    small2 = j;
    break;
   }
  }
  for (j = small2; j < n; ++j) // 找到權(quán)值最小的兩個(gè)節(jié)點(diǎn)，并將最小的序號(hào)賦給small1，次小的賦給small2
  {
   if (temp[j] != NULL)
   {
    if (temp[j]->weight < temp[small1]->weight)
    {
     small2 = small1;
     small1 = j;
    }
    else if (temp[j]->weight < temp[small2]->weight)
    {
     small2 = j;
    }
   }
  }
  hufmTree = (TreeNode*)malloc(sizeof(TreeNode));
  hufmTree->lchild = temp[small1];
  hufmTree->rchild = temp[small2];
  hufmTree->weight = temp[small1]->weight + temp[small2]->weight;
 
  temp[small1] = hufmTree;
  temp[small2] = NULL;
 }
 free(temp);
 return hufmTree;
}
 
// 前序遍歷
void PreOrderTraversal(TreeNode* hufmTree)
{
 if (hufmTree)
 {
  printf("%d", hufmTree->weight);
  PreOrderTraversal(hufmTree->lchild);
  PreOrderTraversal(hufmTree->rchild);
 }
}
 
// 哈夫曼編碼
void hufmTreeCode(TreeNode* hufmTree,int depth)
{
 static int code[10],i;
 
 if (hufmTree)
 {
  if (hufmTree->lchild == NULL && hufmTree->rchild == NULL)
  {
   int i=0;
   printf("權(quán)值為%d的節(jié)點(diǎn)，哈夫曼編碼為：", hufmTree->weight);
   for (i = 0; i < depth; ++i)
   {
    printf("%d", code[i]);
   }
   printf("\n");
  }
  else
  {
   code[depth] = 0;
   hufmTreeCode(hufmTree->lchild, depth + 1);
   code[depth] = 1;
   hufmTreeCode(hufmTree->rchild, depth + 1);
  }
 }
}
 
// 哈夫曼解碼
// 思想：通過定位ID，找到源碼中的位置
void hufmTreeDecode(TreeNode* hufmTree, char a[],char st[])
{
 int i,arr[100];
 TreeNode* temp;
 for (i = 0; i < strlen(a); ++i) // 轉(zhuǎn)化字符串編碼為數(shù)組編碼
 {
  if (a[i] == '0')
   arr[i] = 0;
  else
   arr[i] = 1;
 }
 i = 0;
 while (i < strlen(a))
 {
  temp = hufmTree;
  while (temp->lchild != NULL && temp->rchild != NULL)
  {
   if (arr[i] == 0)
    temp = temp->lchild;
   else
    temp = temp->rchild;
   i++;
  }
  printf("%c", st[temp->id]);
 }
 printf("\n");
 free(temp);
}
 
int main()
{
 int i, n, arr[100];
 printf("輸入需要?jiǎng)?chuàng)建的節(jié)點(diǎn)個(gè)數(shù)：\n");
 scanf("%d", &n);
 printf("輸入權(quán)值：\n");
 for (i = 0; i < n; ++i)
  scanf("%d", &arr[i]);
 
 printf("\n請(qǐng)輸入每個(gè)權(quán)值對(duì)應(yīng)的字符:\n");
 char st[100];
 scanf("%s",st);
 
 // 創(chuàng)建哈夫曼樹
 TreeNode* hufmTree;
 hufmTree = createTree(arr, n);
 
 // 哈夫曼編碼
 printf("\n哈夫曼編碼為：\n");
 hufmTreeCode(hufmTree, 0);
 
 // 遍歷
 printf("\n前序遍歷：\n");
 PreOrderTraversal(hufmTree);
 
 // 解碼
 printf("\n請(qǐng)輸入需要解碼的碼字:\n");
 char codeSt[100]; 
 scanf("%s",codeSt);
 printf("\n解碼的碼字為:\n");
 hufmTreeDecode(hufmTree, codeSt, st);
 
 free(hufmTree);
 system("pause");
 return 0;
}