个人中心
gpt4 book ai didi

C语言实现哈夫曼编码

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言实现哈夫曼编码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

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

主程序main.cpp 。

?
1
2
3
4
5
6
7
8
9
10
11
12
#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:定义了哈夫曼树和编码表的结构 。

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

C语言实现哈夫曼编码

?
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

两个cpp文件实现两个头文件声明的函数： 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 <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:

?
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 <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;
}

运行结果:

C语言实现哈夫曼编码

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

原文链接：https://blog.csdn.net/u011643312/article/details/53983278 。

最后此篇关于C语言实现哈夫曼编码的文章就讲到这里了,如果你想了解更多关于C语言实现哈夫曼编码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 一篇带你创建 Tekton 流水线
文章推荐： C语言实现哈夫曼树
文章推荐： C++控制台循环链表实现贪吃蛇
文章推荐： C++控制台实现贪吃蛇游戏
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com