哈夫曼编码实现字符串的压缩与解压（C语言）（数据结构大作业）

前言

本文章为作者数据结构大作业的总结，附有源码和思路，附实验报告，各位学数据结构的本科生可以直接拿走食用，大一新生可以先收藏备用，记得点赞关注---会说话的锅

一. 实现步骤

输入字符串

--->统计字符串中各个字符出现的频率

--->将字符串出现的频率视为哈夫曼树节点的权重来构建哈夫曼树

--->根据生成的哈夫曼树得到每个字符所对应的哈夫曼编码

--->将输入的字符串根据对应的哈夫曼编码转换为二进制位(压缩)

--->计算压缩前后所占字节大小

--->将压缩后的二进制码还原为字符串(解压)

二. 实现原理

原本字符串的储存一个字符需要占据一个字节也就是八个二进制位的内存，字符串的字符出现频率越高，它的哈夫曼编码就越短，将字符串中的字符储存的二进制位替换为它所对应的哈夫曼编码，就能减少储存需要占用的内存大小。

举个栗子，我想要压缩一段字符串aaabbc，这段字符串长度为6，算上最后的\0也就是占七个字节的空间，我们求出它所对应的哈夫曼编码，a：0  b:11 c:101。把其换成哈弗曼编码储存为00011101，只占用八个二进制位，也就是一个字节，明显减少了储存这段字符串需要的内存大小。

三.实现主要步骤

1.哈夫曼树的建立以及哈夫曼编码的获取

哈夫曼树

哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

结点的路径长度：两结点间路径上的分支数。

树的路径长度：从树根到每一个结点的路径长度之和。记作TL

结点树目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

创建图解

哈夫曼编码

哈夫曼编码的原理

哈夫曼编码的原理可以通过以下步骤来解释：

统计频率：首先，需要统计待编码数据中每个符号的出现频率。符号可以是字符、字节或其他数据单元。统计频率可以通过遍历整个数据集来完成，并记录每个符号出现的次数。

构建编码树：根据符号的频率构建一个特殊的二叉树，称为哈夫曼树（Huffman Tree）或编码树。构建编码树的方法是将频率最低的两个符号合并为一个新节点，该节点的频率为两个节点频率之和。将新节点插入到已有节点的集合中，重复这个步骤，直到只剩下一个节点，即根节点为止。在构建过程中，可以使用优先队列或最小堆来维护频率最低的节点。

分配编码：从根节点开始，沿着左子树走为0，沿着右子树走为1，将0和1分别分配给左右子节点。重复这个过程，直到遍历到每个叶子节点为止。每个叶子节点的路径上的0和1的序列就是对应符号的哈夫曼编码。

生成编码表：将每个符号及其对应的哈夫曼编码存储在一个编码表中，以备后续的编码和解码使用。

进行编码：将原始数据中的每个符号替换为其对应的哈夫曼编码，生成压缩后的编码数据。由于频率高的符号具有较短的编码，而频率低的符号具有较长的编码，所以整个编码后的数据长度会相对减小。

哈夫曼编码的优点是没有冗余和歧义性，即每个编码都不是其他编码的前缀，这种性质被称为前缀码。这使得编码和解码过程都是非常高效的。然而，对于哈夫曼编码的最佳性能，符号的频率应该是根据数据集的统计特征进行调整的。

2.将字符串进行压缩和解压

压缩过程

在这里我并没有真实地去压缩和解压一个文件，我只是将一串字符串压缩后的二进制编码进行打印，压缩的原理很简单，就是遍历我所输入的字符串，找到每个字符对应的哈夫曼编码，依次将哈夫曼编码打印出来

解压过程

解压过程的原理其实和压缩过程大差不差，也是通过遍历去实现，举个栗子，我要解压这么一段二进制编码：01110100，哈夫曼树中字符与二进制码对应为：a：0  b:11 c:101，这里我实现的过程中创建了一个start指针和一个end指针，刚开始的时候我的start指针和end指针都指向第一位，这时候就只读取一位‘0’，看一看有没有字符对应的哈夫曼编码长度也是1？有a:0，判断一下是不是我读取的，是，那我就输入字符'a'，读取成功之后end指针向后移动一位，start指针指向end指针指向的位置，读取后面的二进制码，现在读取一位‘1’，重复上述操作，没有字符哈夫曼编码是1，那就让end指针后移一位，读取两位‘11’读取出来字符'b'。以此类推知道将整段二进制码都读取完。

四. 主要步骤的代码具体实现

1.哈夫曼树的建立

//在创建哈夫曼树的时候，首先需要找到最小的两个数，先“结合”在一起；
//在这里huffsort函数就是用来找出最小的两个数并将他们的值的位置s1，s2返回；
void huffsort(huffman& ht, int& s1, int& s2, int n)
{
	int min;
	int i;
//这里我的min没有进行初始化，就先找第一个值的位置赋值给min；
	for (i = 1; i