用户登录
用户注册

分享至

哈夫曼编码（包含C语言实现代码）

  • 作者: 弄个好名
  • 来源: 51数据库
  • 2022-10-09

本文实例为大家分享了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是树节点，直接由队列建立起哈夫曼树

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

运行结果：



推荐阅读
热点文章

Copyright 2018 51数据库(www.51sjk.com)

软件
前端设计
程序设计
Java相关