C语言实现哈夫曼树的编码

您所在的位置：网站首页 › c语言哈夫曼编码程序及运行结果是什么 › C语言实现哈夫曼树的编码

C语言实现哈夫曼树的编码

2024-07-09 09:47| 来源: 网络整理| 查看: 265

哈夫曼树的概念以及算法简述 1.相关名词概念：

路径和路径长度：从树中的一个节点到达另外一个节点的之间的分支为路径，其长度为路径长度。树的路径长度定义为从根节点开始到达每一个节点的路径长度之和。

权值：节点的权值为该节点在所有节点中占的比重，拿一个文本文件来说，某个字符的节点权重即为该字符出现的次数与该文本文件中所有字符出现的次数的比值。

带权路径长度：树中某个节点的带权路径长度为该节点的路径长度与该节点的权重的乘积。一颗树的带权路径长度（WPL）为该树中的所有叶节点的带权路径长度之和。

带权路径长度最小的树二叉树即为哈夫曼树（最优二叉树）！

哈夫曼树的算法描述：

1.根据给定的n个权值，构成n棵二叉树的集合：F = {T1,T2,T3,T4,…}。其中每棵二叉树中只有一个带权值为Wi的根节点，其左右孩子都为空。 2，在F中选取两棵权值最小的树，作为一个新节点的左右子树，构造出一课新的二叉树，且置新的树的权值为两棵左右子树的权值之和。 3，在F中删除这两棵左右子树，并将新的二叉树加入F中。 4，重复2,3过程，直到F只含有一棵二叉树。（这里即为树中根节点）

哈夫曼树的抽象数据类型的定义 /* 哈夫曼树节点 */ typedef struct _haffman { char data; //用来存放节点字符的数据域 int weight; //权重 struct _haffman *leftChild; //左孩子节点 struct _haffman *rightChild; //右孩子节点 }HaffNode;

宏定义

#define MAX_SIZE 256 //编码数量 #define HALF_MAX 128 //一半的数量 #define ASCII_SIZE 128 //ASCII码的数量

定义一些需要用到的全局变量

/* 以顺序结构存储的树节点--编码解码的字符映射表 --即存储原数据*/ HaffNode node[MAX_SIZE]; /* 用来保存所有左孩子节点--为总节点数的一半 */ HaffNode left[HALF_MAX]; /* 用来保存所有右孩子节点 --为总节点数的一半*/ HaffNode right[HALF_MAX]; /** 创建一个二维数组，用来保存每一个叶节点的编码 */ char code[MAX_SIZE][HALF_MAX]; 构造哈夫曼树的代码实现： /* 构造哈夫曼树 @param node 哈夫曼树的根节点 @param length 节点数组的长度 */ void CreatHaffmanTree(HaffNode * node, int length) { if (length leftChild == NULL || node->rightChild == NULL) { //使用字符数组，将编码形式保存 tempnode[index] = '\0'; //字符串结束的标志 strcpy(code[node->data - 0], tempnode); //这里叶节点的值使用的是字母，可以使用ASCII码的形式确认存储的位置，也可以用强制类型转换 } tempnode[index] = '0'; //左支路的编码为0 Coding(node->leftChild, tempnode, index + 1); //先递归调用左支路， tempnode[index] = '1'; //右支路的编码为1 Coding(node->rightChild, tempnode, index + 1); //再递归调用右支路 } 哈夫曼树的解码过程：

过程：对于一段由编码0/1构成的二进制文件，在同个树而言，重第一个开始，遇到0则访问左子树，遇到1则访问右子树。直到该节点没有了左右节点为止，即这段01字符即可解码为该叶子节点所对应的字符。代码实现

/** 解码过程 -- flag 0/1 来表示往哪边走，左走0，右走1 */ HaffNode *Unziped(HaffNode *node, int flag) { if (flag == 1) return node->rightChild; //右子树 else if(flag == 0) return node->leftChild; //左子树 return NULL; }

下面是所有的代码实现: main.c

#include #include #include #include "HaffmanTree.h" #include /** 进行哈夫曼树编码的过程 1，打开文件，进行文件的字符读取，并进行哈夫曼编码，将压缩的数据保存另外一个文件ziped.txt中 2，解码文件，对二进制文件进行解码，将解码的结果保留在另外一个文件result.txt中 */ int main() { //保存到二进制文件中的无符号字符，即解码过后对应的字符，这里即为00000000 unsigned char saveChar = 0; //中间变量 unsigned char tempchar = 0; printf("使用哈夫曼树实现文件的压缩，（只支持ASCII字符）\n"); //以只读的形式打开文本文件，该文件就是要进行压缩的源文件 FILE * inputFile = fopen("input.txt", "r"); //以二进制的形式写入该文本文件，相当于压缩包 FILE * zipedFile = fopen("ziped.txt","wb"); //文件中保存的字符个数，源文件 int fileLength = 0; //定义一个数组，用来保存每个ASCII码的权重 int asciicount[128] = { 0}; //保留读取到的字符 char readChar; while ((readChar = fgetc(inputFile)) != EOF) { //逐个读取字符，并累加 fileLength++; //将读取到的字符作为下标，统计每个字符出现的次数 asciicount[readChar - 0]++; } //字符种类计数器 int cnt = 0; for (int i = 0; i < 128; i++) { if(asciicount[i] != 0) { //统计节点的数量，即文件中出现多少种字符 node[cnt].data = i; // 将字符出现的次数当成权重 node[cnt].weight = asciicount[i]; //节点数量累加 cnt++; } } CreatHaffmanTree(node, cnt); //创建哈夫曼树 char tempcode[10]; //编码的值 0/1 Coding(node, tempcode, 0); //编码，从零开始 cnt = 0; //计数器置零 fseek(inputFile, 0L, 0); //将文件定位于文件头，偏移0个字节长度 int zipedLength = 0; while ((readChar = fgetc(inputFile)) != EOF) { //逐位将编码保存到文件中 for (int i = 0; i < strlen(code[(int)readChar]); i++) { saveChar |= (code[(int)readChar][i] - '0'); //将saveChar的最后一位赋值为0/1 cnt++; //累加计数器 if (cnt == 8) { //如果计数累加到8，8位一个字符，则写入文件 //在文件中写入一个unsigned char 大小的字符 fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile); cnt = 0; saveChar = 0; zipedLength++; //压缩文件字符大小累加，方便算出压缩比 } else { //saveChar的值左移一位，为下次给最低位赋值做好准备 saveChar rightChild == NULL) { //使用字符数组，将编码形式保存 tempnode[index] = '\0'; //字符串结束的标志 //这里叶节点的值使用的是字母，可以使用ASCII码的形式确认存储的位置，也可以用强制类型转换 strcpy(code[node->data - 0], tempnode); } tempnode[index] = '0'; //左支路的编码为0 Coding(node->leftChild, tempnode, index + 1); //先递归调用左支路， tempnode[index] = '1'; //右支路的编码为1 Coding(node->rightChild, tempnode, index + 1); //再递归调用右支路 } /** 解码过程 -- flag 0/1 来表示往哪边走，左走0，右走1 */ HaffNode *Unziped(HaffNode *node, int flag) { if (flag == 1) return node->rightChild; //右子树 else if(flag == 0) return node->leftChild; //左子树 return NULL; }

注意上面程序只能编码ASCII码的文件，如果文件中有中文字符的存在会存在乱码的情况，默认输入文件为input.txt，压缩文件为ziped.txt,解压文件为result.txt

【本文地址】

C语言实现哈夫曼树的编码

C语言实现哈夫曼树的编码

今日新闻

推荐新闻