哈夫曼算法及其应用
- 格式：doc
- 大小：455.00 KB
- 文档页数：12
哈夫曼算法及其应用
一、问题描述
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼编码是一种根据哈夫曼树对文件进行编码的方式。哈夫曼编码是可变字长编码的一种。本次课程设计是对一个已建文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。压缩文件即读文件，统计文件中的字符个数，对文件进行哈夫曼编码和译码，并将编码译码后的字符存储在文件中。
二、基本要求
程序要求实现以下功能：
1．统计文本文件中各字符的出现次数（涉及读文件，统计字符个数）；
2．对文件中的字符进行哈夫曼编码，并存储入字符编码文件；
3．根据字符编码文件对文本文件内容进行编码；
4．根据字符编码文件和已编码文件的内容进行译码；
5．能够输出原文、编码表、文本文件编码、译文。
三、测试数据
In its medical literature, the Food and Drug Administration states that hot water
comfortable enough for washing hands is not hot enough to kill bacteria, but is more
effective than cold water because itremoves oils from the hand that can harbor
bacteria.
四、算法思想
1、哈夫曼树建立算法：
1）根据给定的n个权值{ W1，W2，W3……Wn } 构成n棵二叉树的集合{T1， T2， ……
Tn}，其中Ti中只有一个权值为Wi的根结点，左右子树均为空。
2）在F中选取两棵根结点的权值最小的树作为左、右子树一构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
3）在F中删除这两棵中权值最小的树，同时将新得到的二叉树加入F中。
4）重复2）3）直到F中仅剩一棵树为止，这棵树就是哈夫曼树。
2、哈夫曼编码算法： 通过从哈夫曼树根结点开始，对左子树分配代码“1”，右子树分配代码“0”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
3、对文件字符编码算法：
逐一读取文件中字符，在哈夫曼编码表查找对应字符，读取其编码并写入文件，如此循环直至结束。
4、哈夫曼译码算法：
根据编码用的哈夫曼树，从根结点出发，逐个读入电文中的二进制码；若代码为“1”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。
五、模块划分
1．Void InitHT(HuffmanT T)
初始化Huffman树。
2．Void SelectMin(HuffmanT T, int n, int &p1, int &p2)
找到权重最小的叶子。
3．Void LoadHuffmanFile(HuffmanT T)
加载文件。
4．Void CreatHT(HuffmanT T)
构造Huffman树。
5．Void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)
根据Huffman树求Huffman编码表。
6．Void EncodingHuffmanT(HuffmanT T, HuffmanCode H)
对文件编码。
7．Void DecdingHuffmanT(HuffmanT T, HuffmanCode H)
根据Huffman编码、译码。
8．Void PrintHuffmanT(HuffmanT T)
打印Huffman权重表。
9．Void PrintHuffmanH(HuffmanT T, HuffmanCode H)
打印Huffman编码表。
10．Void MainMenue（）
主菜单。提供相关的操作提示。
11．Int main（）
主函数。用个while循环和switch选择结构进行进行循环交互性操作。
六、数据结构//(ADT) 1、哈夫曼树的存储结构：
typedef struct {
char ch; //字符
int weight; //字符权重
int lchild; //左子
int rchild; //右子
int parent; //双亲
} THNODE;
2、哈夫曼编码表的存储结构：
typedef struct {
char ch; //存储字符
char bits[MAX_C + 1]; //字符编码位串
} CodeNode;
七、源程序
//Huffman.cpp 源代码如下：
#include
#include
#include
#define MAX_C 256 //定义最大字符数
#define MAX_N 512 //定义最大Huffman节点个数
#define N 50
/*Huffman Tree 结构*/
typedef struct
{ char ch; //字符
int weight; //字符权重
int lchild; //左子
int rchild; //右子
int parent; //双亲
}THNODE;
typedef THNODE HuffmanT[MAX_N];
/******Huffman 编码表结构*****/
typedef struct
{ char ch; //存储字符
char bits[MAX_C + 1]; //字符编码位串
}CodeNode;
typedef CodeNode HuffmanCode[MAX_C];
HuffmanCode H;
/*********全局变量**********/ int n; //指示待编译文件的字长
char filename[20];
/*初始化Huffman树*/
void InitHT(HuffmanT T)
{ int i;
for (i = 0; i < MAX_N; i++)
{ T[i].ch = '\0';
T[i].weight = 0;
T[i].lchild = -1;
T[i].rchild = -1;
T[i].parent = -1;
}
}
/*找到权重最小的叶子*/
void SelectMin(HuffmanT T, int n, int &p1, int &p2)
{ int i;
int j;
for (i = 0; i < 2 * n -1; i++)
{
if (T[i].parent == -1 && T[i].weight > 0)
{
p1 = i;
break;
}
}
for (j = i + 1; j < 2 * n - 1; j++)
{
if (T[j].parent == -1 && T[j].weight > 0)
{
p2 = j;
break;
}
}
for (i = 0; i < 2 * n - 1; i++)
{
if ((T[p1].weight > T[i].weight) && (T[i].parent == -1) && (p2 != i) &&
(T[i].weight > 0))
p1 = i;
}
for (j = 0; j < 2 * n - 1; j++)
{
if ((T[p2].weight > T[j].weight) && (T[j].parent == -1) && (p1 != j) &&
(T[j].weight > 0)) p2 = j;
}
}
/*******加载文件*******/
void LoadHuffmanFile(HuffmanT T)
{ unsigned int i;
int j = 0;
char c;
int a[MAX_C];
FILE *fp;
printf("Input file name: ");
scanf("%s", filename);
if ((fp = fopen(filename, "rb")) == NULL)
{ printf("Can't open %s\n", filename);
exit( 0 );
}
for (i = 0; i < MAX_C; i++)
a[i] = 0;
fseek(fp, 0, SEEK_SET);
while ( 1 )//( !feof(fp) )
{
fread(&c, sizeof(unsigned char), 1, fp);
if (feof(fp)) break;
a[(unsigned int)c]++;
}
fclose(fp);
/*统计输入文件的字符及其权重并存放到树T[]*/
for (i = 0; i < MAX_C; i++)
