Haffman编码实现文本压缩-C语言-万字长文，绝对详细

目录

前言

一、实验目的

二、实验要求

三、设计思想

1 编码

1.1 生成Haffman编码

（1）统计字符频率

（2）构造Haffman树

1.2 文本编码

2 译码

2.1 读入译码信息

2.2 文本译码

2.3 测试结果

四、源码

前言：

这是我在CSDN的第一篇文章，第一次不知道怎么写，所以直接把实验报告搬上来了。但是目前这篇文章的阅读量很高，并且有帮到了好几位小伙伴，同时也得到了他们对我创作内容的认可，我受宠若惊，所以决定更新一下这篇文章，以更好地帮助大家解决问题。

我猜测许多小伙伴也是要写报告，所以我并不打算修改文章的整体框架，依旧以一份报告的格式来呈现，仅做小部分的改动：将图片型代码转为可以直接复制的代码块；修改部分措辞，便于理解；增加更多解释性语言，尽量把整个流程阐述地更加清楚。

由于当初使用的是富文本编辑器来写的文章，所以无法使用Markdown的相关语法，排版方面可能有些许粗糙，还请见谅。

我希望达到的目的是，仅仅通过这一篇博客，你便可以完全理解使用Haffman编码实现文本压缩中生成编码、压缩并写入二进制文件、读取文件并解码的整体流程，并能够轻易地在我的框架指导下写出自己的程序，不会出现修改时无从下手的情况。

目前有好几位小伙伴反馈了一些问题，汇总如下：

程序没有输出怎么办？

1. 程序仅支持ASCII码字符，即英文文档。如果出现控制台没有任何输出，可以先去排查下文章中是否有中文的，。、？【】（）；等字符。可以在文章末尾源码部分下载我上传的测试文本，如果程序正常的话，那应该就是你源文本有中文字符了（目前有好几位小伙伴都是因为这个原因）。
2. 如果控制台输出 “Failed to open files!” ，则需要检查一下在main函数开始是否修改了文件路径。相对路径注意将源文本与程序放在同目录下；绝对路径注意是否含有中文，某些编译器可能会出问题。同时，仅需创建”original_text.txt”源文本即可，压缩后的文本与解码后生成的文本会自动生成在同目录下。

压缩后的文件如何打开？

压缩后生成的”compressed_text.txt”文件，虽然后缀是txt文本文档，但其实是二进制文件，无法通过普通的文本编辑器打开。大家可以自行去网上查询有关的二进制文本编辑器来打开（推荐以十六进制显示）。

我使用的是VScode中的Hex Editor编辑器，十分方便。

如果有其他问题，或者说上述问题的其他情况，可以随时评论区、私信我交流，一起解决问题。

同时我的主页还有更有优质文章，希望可以帮到你，感谢大家的点赞、收藏和关注~

以下为正文部分：

一、实验目的

哈夫曼编码是一种以哈夫曼树（最优二叉树，带权路径长度最小的二叉树）为基础变长编码方法。其基本思想是：将使用次数多的代码转换成长度较短的编码，而使用次数少的采用较长的编码，并且保持编码的唯一可解性。在计算机信息处理中，经常应用于数据压缩。是一种一致性编码法（又称”熵编码法”），用于数据的无损压缩。

要求实现一个完整的哈夫曼编码与译码系统。

二、实验要求

1. 从文件中读入任意一篇英文文本文件，分别统计英文文本文件中各字符（包括标点符号和空格）的使用频率；
2. 根据已统计的字符使用频率构造哈夫曼编码树，并给出每个字符的哈夫曼编码（字符集的哈夫曼编码表）；
3. 将文本文件利用哈夫曼树进行编码，存储成二进制压缩文件（哈夫曼编码文件）；
4. 计算哈夫曼编码文件的压缩率；
5. 将哈夫曼编码文件译码为文本文件，并与原文件进行比较。

三、设计思想

程序主要分为编码与译码两部分，总体思路如下：

相关存储结构及函数定义如下：

表3.1 函数定义

1 编码

1.1 生成Haffman编码

对一棵具有n个叶子结点的Haffman树，将树中的每个左分支赋0，右分支赋1，则从根到每个叶子的通路上各个分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。哈夫曼编码是最优前缀编码，能使各种报文对应的二进制串的平均长度最短。

因此，为生成Haffman编码，首先要对文本中每个字符出现的频率进行统计，并利用堆的结构构造Haffman树，并生成编码。

Haffman树结点的结构定义如下。

/* 字符Haffman结点 */typedef struct HaffmanNode{char character; // 字符long count; // 出现频数char code[MAXBIT];// 编码struct HaffmanNode *lchild; // 左孩子struct HaffmanNode *rchild; // 右孩子struct HaffmanNode *parent; // 父结点} HaffmanNode, *HaffmanTree;

由于ASCII码值有128个字符，因此创建一个大小为128的Haffman结点指针数组，其下标分别对应各个字符的ASCII码值，并创建全局变量dic作为字典。

/* 存放字符及其编码结果的结构体 */typedef struct Dic{HaffmanTree charNode[128]; // 字符结点数组，起到字典的作用(只适用于ASCII码表)} Dic;

（1）统计字符频率

使用countChFrequency函数进行统计，具体流程如下：

（2）构造Haffman树

最小堆的根节点为所有元素中最小值，操作简单，时间复杂度低，用于构造Haffman树十分合适，因此使用最小堆的存储结构来构造。（没有学过堆的小伙伴可以采用别的方案，这里不是重点）

构造哈夫曼树的算法步骤如下：

① 预处理操作：由所有在文本中出现过的字符节点生成最小堆，并以各字符出现的频率(count)作为其权重。

② 依次从最小堆里取出两个结点(孩子结点)，并生成一个新的父结点，将其插入最小堆中。其中父结点的count值为两孩子的count值求和。

③ 重复操作②，直至最小堆中只有一个结点为止。

④ 取出最小堆中结点，即为Haffman树的根节点root。

（3）生成Haffman编码

下面对各个字符进行编码，编码原则是：从树的根节点开始，进入左子树则编码加0，进入右子树则编码加1，就可以得到对应字符的二进制编码。

具体编程实现采用从叶子结点逆向遍历至根结点的方法：

即对于每一个叶子结点来说，如果它是父结点的左儿子，则将’0’存入临时字符数组中，如果是右儿子，则存入’1’，如此循环直至到达根节点。

最后将临时字符数组逆置，便得到字符的编码，将其存入对应结点的code字符数组中。

结果示例(部分)：

1.2 文本编码

接下来便是将source文件里的文本按照编码规则以二进制的形式写入到output文件中。

采取以下策略：

将存储内容分为三部分：

1. 文件基本信息

2. 正文

3. 字典(Haffman编码表)

结构如图所示，其中每一个小方格代表一个字节。

（1）写入操作

三部分内容写入方式大同小异，以正文内容写入为例。

首先需要一个暂存编码的字符数组tempCode。读取正文内容，不断地将字符对应的编码追加到tempCode的末尾。当发现tempCode的长度大于8位时，将进行写入(逐字节写入)操作。

声明一个char类型字符ch(大小为1个字节)，首先将其置为0，即将二进制码置为0000 0000。从tempCode的首字符开始读取8位，如果是’1’，则将ch左移一位，然后+1；如果是’0’，则仅将ch左移一位。然后将ch写入output文件中即可，同时将tempCode中的内容向前移动8位，如此循环。

当文本读取完毕，发现tempCode中还有不足8位的编码，则在后面补0至8位，然后写入。

这里用到了位操作，估计有部分小伙伴不太理解，这里稍加解释，并不严谨，仅用于更好地辅助理解。（理解的小伙伴可以直接看代码）

我们采用的方案是逐字节写入，首先我们便需要获得一个1字节大小的“容器”，其实在计算机的眼里，没有什么int型、char型，不过是不同的连续大小的空间而已，int型就是4个字节，char型就是1个字节。

不知道怎么往文本中写二进制编码？但我们会写入char类型的字符呀。此处我们声明一个char类型的字符ch = 0，其对应的编码就是0000 0000。此时我们将这个char字符写入文本时，其实就是写入了8个为0的比特位。

那么现在我们就有办法写入0、1比特位了，如何将ch修改为我们想要的形式呢？这里就要用到左移和加1的操作了。

ch << 1代表将整个字节的二进制位向左移动1位，溢出的舍弃，右边补0；ch +1 中加的是二进制下的1。这样，我们便可以在二进制串中写入0和1，也就可以构造我们的Haffman编码了。

即将ch“改造”成我们想要的二进制形式，再按照普通的文本写入方式即可。

此部分核心代码如下：

// 写入文本char ch = fgetc(source);while (ch != EOF){strcat(tempCode, dic.charNode[ch]->code); // 将字符的编码追加给tempCode暂存lenTempCode = strlen(tempCode);ch = 0;//二进制为00000000，作为写入文本的二进制编码的临时容器while (lenTempCode >= 8) // 暂存编码位数大于8时，执行写入操作{for (i = 0; i < 8; i++) // 八位二进制数写入文件一次{if (tempCode[i] == '1') // ch的二进制数左移并加1{ch = ch << 1;ch = ch + 1;}elsech = ch < 0) // 若最后不满8位，则补0{ch = 0;strcat(tempCode, "00000000");for (i = 0; i < 8; i++){if (tempCode[i] == '1') // ch的二进制数左移并加1{ch = ch << 1;ch = ch + 1;}elsech = ch << 1; // ch的二进制数左移}fwrite(&ch, sizeof(char), 1, output); // 将最后一个字符写入lenCompressedFile++;}

同理，将文本基本信息以及字典也写入output文件中（原理相同，代码详细，不多赘述），最终得到二进制文本，实现了压缩的目的，示例如下。

2 译码

想要知道如何译码，就要知道是如何进行编码的，此时我们刚才在文件中存储的字典便派上了用场，就可以像人查字典一样，将二进制序列逐个与字典匹配，进行“翻译”。

2.1 读入译码信息

首先需要构造字典，将字符、对应Haffman编码存入。

字典结构如下图所示：

操作如下：

首先读入文本开头12个字节的3个文件基本信息，依据信息定位至字典存储位置，进行读取。对于每一个字符结点来说，首先读入1个字节，值就是其ASCII码值。然后读取其编码长度，并在编码中读取对应位数，然后转换为字符数组并存入对应结点即可。

核心代码如下：

// 读取相关文本信息int textLen, binLen, types, biFileLen, codeLen, byteNum;fseek(source, 0, SEEK_END);biFileLen = ftell(source); // 二进制文件总大小fseek(source, 0, SEEK_SET);fread(&textLen, sizeof(int), 1, source); // 源文本大小fread(&binLen, sizeof(int), 1, source);// 压缩后的文件大小(不含字典)fread(&types, sizeof(int), 1, source); // 字符种类数// 读取字典并转换成二进制码(char数组)fseek(source, binLen, SEEK_SET);for (i = 0; i character, 1, 1, source); // 读取字符(ASCII码)fread(&ch, 1, 1, source);dic_decode.charNode[i]->count = (long)ch;// 读取字符编码长度 strlen(code)if (dic_decode.charNode[i]->count % 8 > 0) // 当前字符的编码占了几个字节byteNum = dic_decode.charNode[i]->count / 8 + 1;elsebyteNum = dic_decode.charNode[i]->count / 8;for (j = 0; j  temp; k--){strcat(dic_decode.charNode[i]->code, "0"); //位数不足，执行补零操作}strcat(dic_decode.charNode[i]->code, tempCode);}dic_decode.charNode[i]->code[dic_decode.charNode[i]->count] = 0; // 放上/0}

如此，便根据文本内存储的基本信息与字典，还原了该文本Haffman编码。

2.2 文本译码

由于Haffman编码不等长，所以编码的匹配策略对匹配效率影响很大。首先对字典进行按照编码长度升序排序，在之后遍历时便可以以最小代价匹配出正确字符。

采用如下的匹配策略：

首先找出各字符编码中的最长编码数maxLen，声明字符数组codeToBeDecoded存放待译码编码。逐字节将二进制文件中的内容读取到codeToBeDecoded数组中(其中需要进行十进制转二进制字符串，并补0操作)。当发现codeToBeDecoded数组的长度大于maxLen时，将其编码与字典各字符的编码进行逐个内存匹配。匹配成功后，将译码得到的字符写入output文件，并将codeToBeDecoded中编码向前覆盖，如此循环。

当写入的字符数与原文本字符数相同时，则译码完成，此时再往后读取便是字典的信息。

如此，我们便得到了译码后的结果。匹配过程的流程图如下：

同时，将Haffman编码读入至字典中后，我们可以按照其长度对其进行升序排序，这样在译码查找的时候就可以从小到大依次匹配，方便处理、提高效率。

我的代码中使用的是冒泡排序，其时间复杂度为O(n^2)，大家可以根据自己需要进行优化。

相关的核心代码如下：

int maxLen = strlen(dic_decode.charNode[types - 1]->code); // 最长编码数fseek(source, 12, SEEK_SET); // 指向正文开头tempCode[0] = 0;while (1){while (strlen(codeToBeDecoded)  temp; k--) // 转十进制再转二进制会丢掉0，进行补0操作strcat(codeToBeDecoded, "0");strcat(codeToBeDecoded, tempCode);}// Haffman码与字符的匹配for (i = 0; i code, codeToBeDecoded, dic_decode.charNode[i]->count) == 0)break;}strcpy(codeToBeDecoded, codeToBeDecoded + dic_decode.charNode[i]->count); // 将已经解译的编码覆盖ch = dic_decode.charNode[i]->character;fwrite(&ch, 1, 1, output); //写入解码的文件writeCount++;if (writeCount == textLen) // 限定写入只写到正文内容，再往后存储的就是字典break;}

此处匹配方案使用的是memcmp函数，进行内存匹配。

2.3 测试结果

以”瓦尔登湖(英文版).txt”为例，运行结果如下：

对于一篇59w个字符的小说，压缩为55.65%，压缩耗时0.064秒，译码耗时0.069秒。

四、源码

在此给出整个程序的源代码，同时我也将.c文件与文章中”瓦尔登湖(英文版).txt”一同打包上传到CSDN资源板块，感兴趣的小伙伴可以直接下载下来直接使用。

资源地址：

Haffman编码实现文本压缩的源码及文本示例-C文档类资源-CSDN文库https://download.csdn.net/download/m15253053181/87166548程序全部源代码：

/** 程序：使用Haffman编码进行英文文档的编码、压缩、译码全过程* 作者：友人帐_* 文章地址：https://blog.csdn.net/m15253053181/article/details/127457700?spm=1001.2014.3001.5501* 个人主页：https://blog.csdn.net/m15253053181?type=blog* 希望可以帮助到大家，也欢迎进入我的主页查看更多优质文章~*/#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #define MAXSIZE 100#define MAXBIT 256/* 字符Haffman结点 */typedef struct HaffmanNode{char character; // 字符long count; // 出现频数char code[MAXBIT];// 编码struct HaffmanNode *lchild; // 左孩子struct HaffmanNode *rchild; // 右孩子struct HaffmanNode *parent; // 父亲} HaffmanNode, *HaffmanTree;/* 存放字符及其编码结果的结构体 */typedef struct Dic{HaffmanTree charNode[128]; // 字符结点数组，起到字典的作用(只适用于ASCII码表)} Dic;/* 堆的结构 */typedef struct HeapStruct{HaffmanTree *elem; // 存放堆元素(Haffman结点)的数组int size;// 当前元素个数int capacity;// 存储容量} HeapStruct, *Heap;HaffmanTree createHaffmanNode();// 生成Haffman树结点HaffmanTree createHaffmanTree();// 构造Haffman树Heap createHeap(int maxsize); // 创建容量为maxsize的堆void traverseHeap(Heap H);// 堆的遍历void insertMinHeap(Heap H, HaffmanTree data); // 最小堆的插入HaffmanTree deleteMinHeap(Heap H);// 最小堆的删除int countChFrequency(FILE *fp); // 统计字符出现频率void genHaffmanCode(HaffmanTree root);// 生成Haffman编码void encoded(FILE *source, FILE *output); // 编码void decoded(FILE *source, FILE *output); // 解码Dic dic; // 字典，全局变量，用于编码压缩int main(){float begintime, endtime;// 编码FILE *originalText = fopen("./original_text.txt", "rb"); // 源文件FILE *compressedText = fopen("./compressed_text.txt", "wb"); // 压缩后的二进制文件if (!(originalText && compressedText))printf("Failed to open files!\n ");else{begintime = clock(); //计时开始encoded(originalText, compressedText);endtime = clock(); //计时结束printf("Program time consuming: %fs\n\n", (endtime - begintime) / ((double)CLOCKS_PER_SEC));}fclose(originalText);fclose(compressedText);// 解码FILE *binText = fopen("./compressed_text.txt", "rb");// 压缩后的二进制文件FILE *decodedText = fopen("./decoded_text.txt", "wb"); // 解码后的文件if (!(binText && decodedText))printf("Failed to open files!\n");else{begintime = clock(); //计时开始decoded(binText, decodedText);endtime = clock(); //计时结束printf("Program time consuming: %fs\n\n", (endtime - begintime) / ((double)CLOCKS_PER_SEC));}fclose(binText);fclose(decodedText);system("pause");return 0;}/*---------------------------------------- 编码 ----------------------------------------*/void encoded(FILE *source, FILE *output){int i, j;int types = 0;int textLength = countChFrequency(source); // 计算字符频率HaffmanTree root = createHaffmanTree();// 由字符频率构造Haffman树genHaffmanCode(root);// 编码// 输出编码结果printf(" *------------> Huffman Code Table <-----------*\n");printf("____________________________________________\ncharcater |frequency| code\n");printf("____________|_____________|_________________\n");for (i = 0; i count > 0){if (dic.charNode[i]->character == 10) // 换行符printf(" \\n\t|%8ld | %s\n", dic.charNode[i]->count, dic.charNode[i]->code);else if (dic.charNode[i]->character == 0) // 结束符printf(" \\0\t|%8ld | %s\n", dic.charNode[i]->count, dic.charNode[i]->code);else if (dic.charNode[i]->character == 9) // 制表符printf(" \\t\t|%8ld | %s\n", dic.charNode[i]->count, dic.charNode[i]->code);else if (dic.charNode[i]->character == 13) // 回车printf(" \\r\t|%8ld | %s\n", dic.charNode[i]->count, dic.charNode[i]->code);else if (dic.charNode[i]->character == 32) // 空格printf(" space|%8ld | %s\n", dic.charNode[i]->count, dic.charNode[i]->code);elseprintf(" %c\t|%8ld | %s\n", dic.charNode[i]->character, dic.charNode[i]->count, dic.charNode[i]->code);types++;}printf(" _____________|_____________|_________________\n\n");// 压缩文件准备操作fseek(source, 0, SEEK_SET);// 找到源文件开头fseek(output, 12, SEEK_SET); // 找到输出文件的12个字节后的位置，前12字节存相关信息int lenCompressedFile = 12;// 压缩文件的长度，单位字节char tempCode[MAXBIT] = {0}; // 临时存放字符编码int lenTempCode = 0; // 暂存的字符编码长度// 写入文本char ch = fgetc(source);while (ch != EOF){strcat(tempCode, dic.charNode[ch]->code); // 将字符的编码追加给tempCode暂存lenTempCode = strlen(tempCode);ch = 0;//二进制为00000000，作为写入文本的二进制编码的临时容器while (lenTempCode >= 8) // 暂存编码位数大于8时，执行写入操作{for (i = 0; i < 8; i++) // 八位二进制数写入文件一次{if (tempCode[i] == '1') // ch的二进制数左移并加1{ch = ch << 1;ch = ch + 1;}elsech = ch < 0) // 若最后不满8位，则补0{ch = 0;strcat(tempCode, "00000000");for (i = 0; i < 8; i++){if (tempCode[i] == '1') // ch的二进制数左移并加1{ch = ch << 1;ch = ch + 1;}elsech = ch << 1; // ch的二进制数左移}fwrite(&ch, sizeof(char), 1, output); // 将最后一个字符写入lenCompressedFile++;}// 写入源文件大小、压缩后文件大小和字符种类数(bytes)fseek(output, 0, SEEK_SET); // 输出文件指针指向开头，写入参数fwrite(&textLength, sizeof(int), 1, output);// 写入源文件大小fwrite(&lenCompressedFile, sizeof(int), 1, output); // 写入压缩后文件大小(包括12字节的文本信息及正文，不包括字典)fwrite(&types, sizeof(int), 1, output); // 写入字符种类数// 写入字典fseek(output, lenCompressedFile, SEEK_SET); // 找到output的末尾HaffmanTree tempNode;char codeLenBit;for (i = 0; i count > 0){tempNode = dic.charNode[i];lenTempCode = strlen(tempNode->code);fwrite(&(tempNode->character), 1, 1, output); // 写入字符ASCII码lenCompressedFile++;codeLenBit = lenTempCode;fwrite(&codeLenBit, 1, 1, output); // 写入字符编码的长度-1个字节就够了lenCompressedFile++;while (lenTempCode % 8 != 0) // 当编码不够整数字节时，补0{strcat(tempNode->code, "0");lenTempCode = strlen(tempNode->code);}while (tempNode->code[0] != 0){ch = 0;for (j = 0; j code[j] == '1'){ch = ch << 1;ch += 1;}elsech = ch <code, tempNode->code + 8);fwrite(&ch, 1, 1, output); // 将所得的编码信息写入文件lenCompressedFile++;}}}printf("\n>>> Original File Information\n");printf("- filename: original_text.txt\n- file length: %ld bytes\n", textLength);printf("\n>>> Compressed File Information\n");printf("- filename: decoded_text.txt\n- file length: %ld bytes\n", lenCompressedFile);printf("\nThe compress has finished! Compression ratio: %.2f%%\n", (float)lenCompressedFile / (float)textLength * 100);}/*---------------------------------------- 解码 ----------------------------------------*/void decoded(FILE *source, FILE *output){int i, j, k;int temp;unsigned char ch;int writeCount = 0; // 写入字符数的统计char tempCode[MAXBIT] = {0};// 临时存放字符编码char codeToBeDecoded[MAXBIT] = {0}; // 存放待译码的二进制序列(1个char)Dic dic_decode; // 解码用字典// 对dic进行初始化for (i = 0; i character = 0; // 此时下标无含义dic_decode.charNode[i]->count = 0; // 此时用于存放编码长度 strlen(code)dic_decode.charNode[i]->lchild = NULL;dic_decode.charNode[i]->rchild = NULL;dic_decode.charNode[i]->parent = NULL;dic_decode.charNode[i]->code[0] = 0;}// 读取相关文本信息int textLen, binLen, types, biFileLen, codeLen, byteNum;fseek(source, 0, SEEK_END);biFileLen = ftell(source); // 二进制文件总大小fseek(source, 0, SEEK_SET);fread(&textLen, sizeof(int), 1, source); // 源文本大小fread(&binLen, sizeof(int), 1, source);// 压缩后的文件大小(不含字典)fread(&types, sizeof(int), 1, source); // 字符种类数// 读取字典并转换成二进制码(char数组)fseek(source, binLen, SEEK_SET);for (i = 0; i character, 1, 1, source); // 读取字符(ASCII码)fread(&ch, 1, 1, source);dic_decode.charNode[i]->count = (long)ch;// 读取字符编码长度 strlen(code)if (dic_decode.charNode[i]->count % 8 > 0) // 当前字符的编码占了几个字节byteNum = dic_decode.charNode[i]->count / 8 + 1;elsebyteNum = dic_decode.charNode[i]->count / 8;for (j = 0; j  temp; k--){strcat(dic_decode.charNode[i]->code, "0"); //位数不足，执行补零操作}strcat(dic_decode.charNode[i]->code, tempCode);}dic_decode.charNode[i]->code[dic_decode.charNode[i]->count] = 0; // 放上/0}// 按Haffman码长度从小到大排序，便于译码时查找 - 冒泡HaffmanTree tmp;for (i = 0; i < types; i++){for (j = 0; j code) > strlen(dic_decode.charNode[j + 1]->code)){tmp = dic_decode.charNode[j];dic_decode.charNode[j] = dic_decode.charNode[j + 1];dic_decode.charNode[j + 1] = tmp;}}}int maxLen = strlen(dic_decode.charNode[types - 1]->code); // 最长编码数fseek(source, 12, SEEK_SET); // 指向正文开头tempCode[0] = 0;while (1){while (strlen(codeToBeDecoded)  temp; k--) // 转十进制再转二进制会丢掉0，进行补0操作strcat(codeToBeDecoded, "0");strcat(codeToBeDecoded, tempCode);}// Haffman码与字符的匹配for (i = 0; i code, codeToBeDecoded, dic_decode.charNode[i]->count) == 0)break;}strcpy(codeToBeDecoded, codeToBeDecoded + dic_decode.charNode[i]->count); // 将已经解译的编码覆盖ch = dic_decode.charNode[i]->character;fwrite(&ch, 1, 1, output); //写入解码的文件writeCount++;if (writeCount == textLen) // 限定写入只写到正文内容，再往后存储的就是字典break;}printf("The decoded has finish!\n");}/*---------------------------------------- 编码所需操作 ----------------------------------------*//* 统计字符频率 */int countChFrequency(FILE *fp){int i;int length = 0; // 统计文本的长度// 对dic进行初始化for (i = 0; i character = i; // 将下标与ASCII码对应dic.charNode[i]->count = 0;dic.charNode[i]->lchild = NULL;dic.charNode[i]->rchild = NULL;dic.charNode[i]->parent = NULL;}// 对字符进行统计char ch = fgetc(fp);while (ch != EOF){dic.charNode[(int)ch]->count++;ch = fgetc(fp);length++;}return length;}/* 生成Haffman编码 */void genHaffmanCode(HaffmanTree root){int i, j;int count = 0;char tempCode[256]; // 临时存放字符编码HaffmanTree pMove = NULL;// 生成Haffman编码for (i = 0; i count > 0) // 对于出现过的字符，即Haffman树的叶子结点{pMove = dic.charNode[i];// 从叶子逆序到根，将编码逆序存放在tempCode中while (pMove->parent){if (pMove->parent->lchild == pMove)tempCode[count] = '0'; // 左子树为0elsetempCode[count] = '1'; // 右子树为1count++;pMove = pMove->parent;}// 将tempCode编码逆序存放在字符结点中for (j = 0; j code[j] = tempCode[count - j - 1];dic.charNode[i]->code[j] = '\0';count = 0;}}}/* 生成Haffman树结点 */HaffmanTree createHaffmanNode(){HaffmanTree node = (HaffmanTree)malloc(sizeof(HaffmanNode));node->character = 0;node->count = 0;node->lchild = NULL;node->rchild = NULL;node->parent = NULL;return node;}/* 构造Haffman树 */HaffmanTree createHaffmanTree(){int i;// 由字典构造最小堆Heap H = createHeap(MAXSIZE);for (i = 0; i count > 0){insertMinHeap(H, dic.charNode[i]);}}// 构造Haffman树while (H->size > 1){// 创建新结点，值为两最小结点的和HaffmanTree newNode = createHaffmanNode();HaffmanTree left = deleteMinHeap(H);HaffmanTree right = deleteMinHeap(H);newNode->count = left->count + right->count;newNode->lchild = left;newNode->rchild = right;left->parent = newNode;right->parent = newNode;// 将新结点插入堆中insertMinHeap(H, newNode);}HaffmanTree root = deleteMinHeap(H);return root;}/* 创建容量为maxsize的堆 */Heap createHeap(int maxsize){Heap H = (Heap)malloc(sizeof(struct HeapStruct));H->elem = (HaffmanTree *)malloc(sizeof(HaffmanTree) * (maxsize + 1)); // 从下标为1存放堆元素H->size = 0;H->capacity = maxsize;return H;}/* 堆的遍历 */void traverseHeap(Heap H){int i;if (H->size == 0){printf("Heap is empty!\n");return;}for (i = 1; i size; i++){printf("%d ", H->elem[i]->count);}printf("\n");}/* 最小堆的插入 */void insertMinHeap(Heap H, HaffmanTree data){int i;if (H->size == H->capacity) // 堆满{printf("Min heap is full!\n");return;}i = H->size + 1; // i指向插入元素后堆中最后一个元素的位置H->size++;while (1){if (i elem[i / 2]->count > data->count)) // 已经找到位置break;H->elem[i] = H->elem[i / 2]; // 如果插入位置的父结点大于其值，则将其插入位置与父结点交换i /= 2;}H->elem[i] = data; // 将data插入}/* 最小堆的删除 */HaffmanTree deleteMinHeap(Heap H){int parent, child;HaffmanTree min, temp;if (H->size == 0){printf("Heap is empty!\n");return NULL;}min = H->elem[1]; // 取出最小值-根节点// 将堆最后一个元素作为树根，然后调整树的结构temp = H->elem[H->size]; // 存放堆的最后一个元素H->size--;for (parent = 1; parent * 2 size; parent = child){child = parent * 2; // 先指向左子结点// child指向左右子结点的较小者if ((child != H->size) && (H->elem[child]->count > H->elem[child + 1]->count))child++;if (temp->count elem[child]->count) //找到位置了break;else // 将temp移动到下一层H->elem[parent] = H->elem[child];}H->elem[parent] = temp;return min;}

CSDN统计整篇文章共18906字符，码字不易，如果这篇文章对你有用的话，麻烦留下一个大大的赞吧~非常感谢！