数据结构-哈夫曼文档

数据结构实验报告

题目1:哈夫曼编码/译码器

1. 问题定义

2. 需求分析

3. 概要设计说明书

4. 详细设计说明书

5. 软件开发计划

6. 编码

7. 软件测试报告

8. 软件总结积累

关键词：编码、译码、压缩、解压缩、哈夫曼编码、哈夫曼树、前缀码、数据结构（ADT）、编码过程数据流图（DFD）、

1. 问题定义

1.1编码：信息从一种形式或格式转换为另一种形式的过程。

1.2压缩：利用某种算法将源文件有损或无损的地处理，以达到保留最多文件的信息，而文件的体积变小。

1.3译码：编码的逆过程。

1.4解压缩：压缩的逆过程。

1.5哈夫曼树：它是由n个带权值叶子节点构成的所有二叉树中带权路径长度最短的二叉树。

1.6哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，个分支的复制分别构成一个二进制串，该二进制串就成为哈夫曼编码。

1.7前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统为前缀码。

二、需求分析

2.1实验目的

a.学会使用哈夫曼进行对文本文件的编码与译码。

b.通过对哈夫曼的编码与译码，能够理解通信领域中的数据传输的压缩原理。

c.通过对哈夫曼的编码/译码器的研究与分析，能够彻底的理解软件设计的一般步骤和方法，灵活地运用各种数据结构进行操作，熟练地把所学地数据结构应用地软件开发当中，提高软件设计水平，增强程序设计能力。

2.2软件主要功能

a.压缩：实现对文本文件的压缩，生成一个比原文件还小的压缩文件。

b.解压：能够对已经压缩的这个文件进行解压，恢复原来的文本文件。

2.3实验主要目标

a.读取文本文件，并统计文件中字符个数

b.建立Huffman树

c.对文件进行Huffman编码

2.4功能扩展

a.在实现对文本文件进行编码与译码功能完成后，实现对文本文件中的任意字符进行编码，包括汉字。

b.实现a功能后，实现对其他的如PDF等文件进行编码与译码。

三、概要设计说明书

说明这个程序的主要功能模块的划分，详细说明各个模块的程序流程。

3.1编码过程

文本文件→统计文件当中每个字符出现的概率→根据字符出现的概率建立哈夫曼树→对文件进行编码→生成一个文本文件→生成一个非文本压缩文件

3.2解码过程

压缩文件→生成一个文本文件→对该文件根据哈夫曼树进行译码→将解码后字符存入新的文件→生成解压后的文件

3.3程序流程图

3.4程序流程文字描述

根据题目要求，哈夫曼解压缩软件工可以分为两个主要过程，现就这两个过程进行描述：

a、压缩：首先从源文本文件当中读取数据，统计出字符各自出现的概率；在此基础上，根据统计出的概率建立哈夫曼树，并将该哈夫曼树的存储结果用文件保存；哈夫曼树建立好后，然后进行哈夫曼编码，并且将各个字符编码后的0、1码存储在文件当中；再一次读取源文件，对源文件进行压缩，将压缩后的二进制代码存储再文本文件中，生成一个文本文件；最后，对这个文本文件进行处理，生成一个二进制文件，其中一个字节代表上一个文件的8个0、1码。

 b、解压：首先根据二进制文件生成一个文本文件，这个文本文件比那个二进制文件要大，其中一个字节代表压缩文件的1位；按照哈夫曼树，将哈夫曼文件当中的哈夫曼编码生成对应的字符，存储在一个文本文件当中。

至此，哈夫曼的编码/译码器就实现了。

四、详细设计说明书

说明程序当中对哈夫曼编码与译码所用的数据结构（ADT），说明各个模块的函数关系，说明各个函数所使用的算法，画出函数关系图，说明输入与输出。

4.1编码过程数据流图（DFD）

4.2编码具体过程

a.统计原文本文件的字符出现的概率算法描述：

使用数据结构：

typedef struct {

char letter; //记录该字符是what

int count; //统计该字符出现的次数

float probability; //记录该字符的概率

}Letter;

#define N_LETTER 123 //定义字符的种类个数

算法描述：

void CacuProbability(Letter *le) {

/*初始化统计字符的数组，让le中的letter存入一个变量，数组的编号与字符的ASCII码相同*/

for(i = 0; i < N_LETTER; i++) {

le[i].letter = i; //存入ASCII为0—122之间的所有字符

le[i].count = 0; //初始化字符个数为零

le[i].probability = 0; //初始化各个字符出现的概率为零

}

/*主要字符下表与ASCII码对应关系

…(48:0)(49:1)(50:2)(51:3)(52:4)(53:5)(54:6)(55:7)(56:8)(57:9)(58::)(59:;)(60:<)(61:=)(62:>)(63:?)(64:@)(65:A)(66:B)(67:C)(68:D)(69:E)(70:F)(71:G)(72:H)(73:I)(74:J)(75:K)(76:L)(77:M)(78:N)(79:O)(80:P)(81:Q)(82:R)(83:S)(84:T)(85:U)(86:V)(87:W)(88:X)(89:Y)(90:Z)(91:[)(92:\)(93:])(94:^)(95:_)(96:`)(97:a)(98:b)(99:c)(100:d)(101:e)(102:f)(103:g)(104:h)(105:i)(106:j)(107:k)(108:l)(109:m)(110:n)(111:o)(112:p)(113:q)(114:r)(115:s)(116:t)(117:u)(118:v)(119:w)(120:x)(121:y) (122:z)

*/

/*统计字符出现的个数*/

all_num = 0;

while(!feof(fp)) {

ch = read_a_letter(fp); //从原文件中读取一个字符

all_num = all_num + 1; //统计所有的字符个数

i = ch; //将ch强制转化为其对应的ASCII值

le[i].count = le[i].count + 1; //让对应的字符数量增加一个

}

/*计算频率*/

for(i = 0; i < N_LETTER; i++) {

le[i].probability = (float)le[i].count / (float)all_num;

}

b.使用静态三叉链表实现哈夫曼树，其数据结构类型定义如下：

#define N_LEAF 20 //叶子结点个数的最大值

#define M 2*N_LEAF – 1 //所有结点个数的最大值

typedef struct { //存储哈夫曼树的结构体定义

float weight; //存放结点的权值

int parent; //存放父亲结点的下标

int LChild; //存放左孩子结点的下标

int RChild; //存放右孩子结点的下标

}HTNode;

HTNode ht[M+1]; //把存放哈夫曼树的结构体定义为一个宏,0号单元不用

算法描述：

/*创建哈夫曼树ht[M+1],w[]存放的是N_LEAF个叶子结点的权值*/

void CreateHuffmanTree(int w[]) {

for(i = 1; i <= N_LEAF; i++) //1---N_LEAF号单元存放叶子结点，对其初始化

ht[i] = {w[i], 0, 0, 0};

for(i = N_LEAF + 1; i <= M; i++) //N_LEAF + 1---M号单元存放非叶子结点，对其初始化

ht[i] = {0, 0, 0, 0};

for(i = N_LEAF + 1; i <= M; i++) { //创建非叶子结点，建立哈夫曼树

/*在ht[1]---ht[i-1]之间找出两个权值最小并且其父结点是0的结点，返回单元序号，存

*在min1和min2

*/

select(i – 1, &min1, &min2);

ht[i].weight = ht[min1].weight + ht[min2].weight; //修改父结点的权值

ht[i].LChild = min1; //修改父结点的左孩子指向

ht[i].RChild = min2; //修改父结点的右孩子指向

ht[min1].parent = ht[min2].parent = i; //修改左右孩子的父亲结点

}

}

/*这个函数会被创建哈夫曼树的函数所调用，其功能是：选择ht[1]---ht[n]之间的两个权值

*最小并且其父结点是0的结点，并且将其所对应的序号存放在min1和min2当中

*/

void select(int n, int *min1, int *min2) {

int i, flag1 = 1, flag2 = 1; //flag1和flag2用来标记（*min1）和（*min2）是否赋值

float x; //x记录找到最小的权值

/*给(*min1)和(*min2)初始化*/

for(i = 1; i <= n; i++) {

if(ht[i].parent == 0 && flag1) {

*min1 = i;

flag1 = 0;

continue;

}

if(ht[i].parent == 0 && flag2) {

*min2 = i; flag2 = 0;

break;

}

}

/*确保在（*min1）与（*min2）当中，（*min1）存放的是最小的，(*min2）>(*min1)*/

if(ht[*min1].weight > ht[*min2].weight) {

(*min1) = (*min1) + (*min2);

(*min2) = (*min1) - (*min2);

(*min1) = (*min1) - (*min2);

}

/*找到最小的值给（*min1），用x记录（*min1）的权值并将（*min1）的权值改为一个较大的值*/

for(i = 1; i <= n; i++) {

if(ht[i].parent == 0 && ht[*min1].weight > ht[i].weight) {

*min1 = i;

}

}

x = ht[*min1].weight;

ht[*min1].weight = 2;

/*用同样的方法，找出权值最小的值，并将其赋给（*min2），实际当中这样（*min2）当中存放的权值次小的值*/

for(i = 1; i <= n; i++) {

if(ht[i].parent == 0 && ht[*min2].weight > ht[i].weight) {

*min2 = i;

}

}

/*将记录的（*min1）的原始值赋给原来的，这样（*min1）当中存放的是权值最小的，而（*min2）当中存放的是权值次小的值*/

ht[*min1].weight = x;

}

c.对哈夫曼树进行哈夫曼编码，并且将结果写到哈夫曼编码的文件当中

/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/

void CreateHuffmanCode(char hc[], int n) {

char ch[8];

int start, child, parent, i;

cd = (char *)malloc((n + 1) * sizeof(char));

cd[n] = '\0';

for(i = 1; i <= n; i++) {

start = n;

child = i;

parent = ht[i].parent;

while(parent != 0) {

start--;

if(ht[parent].LChild == child) {

cd[start] = '0';

} else {

cd[start] = '1';

}

child = parent;

parent = ht[parent].parent;

}

hc[i] = (char *)malloc((n - start) * sizeof(char));

strcpy(hc[i], &cd[start]);

}

free(cd);

}

4.3译码过程数据流图（DFD）

4.4译码详细过程

译码过程主要分为两步，第一步：将压缩的文件转化为01码的文件；第二步：将上一步转化生成的01码文件进行再次解压缩，生成源文件。

a.生成01码文件的函数具体算法

根据压缩过程中的压缩方案，将本文件解压生成含有01码的解压文件

/*name表示被压缩好的文件*/

void decompressfirst(char *name)

{

fp = fopen(name, "rt");

fp1 = fopen("sun1.txt.txt", "wt");

fscanf(fp, "%c", &ch);

while(!feof(fp)) {

sixteentochar(ch, num);//此函数表示将一个十六进制的数转化为一个01字符串

fscanf(fp, "%c", &ch);

if(feof(fp)) {

for(i = 3; i > 3 - ONE_NUM; i--) {

num[i] = 0;

}

fprintf(fp1, "%s", num);

break;

}

fprintf(fp1, "%s", num);

}

}

b.再次解压，生成原文件

使用的是压缩过程中生成的HuffmanCode.txt文件，根据其中的哈夫曼编码，对上一步生成的文件进行再次解压，最后生成源文件。

五、软件开发计划

5.1任务安排

2010-6-21：完成初始文档的编写

2010-6-22：完成哈夫曼的编码

2010-6-23：完成哈夫曼的译码

2010-6-24：完成哈夫曼的测试以及代码的功能完善

2010-6-25：补充完成实验报告

六、编码

6.1使用的语言

使用c语言进行编码。熟悉c语言的文件操作，位操作等，明白一些c语言的细节东西。

七、软件测试报告

7.1程序调试情况

熟悉Visual C++6.0的基本调试方法，以及建立工程进行文件的编写，规范源程序的写法，熟练的使用vc进行调试。

在调试中会遇到许多的细节性的问题，比如：数组小标越界，在读文件时，没有说明文件指针等。但是通过调试，让我更能用心去体会程序的设计，把握住程序设计当中的每一个细节，能够很好的使用vc进行程序的开发，很好地利用调试工具帮我解决程序设计及其编码过程地错误。

在有些时候，一些非逻辑地错误，编译器能够帮我们发现，我们能够很快地解决，但是当一些逻辑错误出现时，这时就需要我慢慢地静下心来，慢慢地去调试，去发现错误，发现自己在设计当中出现地错误。这才是最好地学习过程。

7.2测试

输入：本程序只有一个输入，也就是一个要压缩地文件。

输出：本程序都是以文件的形式进行输出的。输出包括7个文件。

”letter.txt”:对要压缩的文件的字符统计结果，包括出现的字符ASCII码，字符出现次数和频数；

“HuffmanTree.txt”：通过哈夫曼树的建立，生成的哈夫曼树文件，也就是利用三叉链表创建的哈夫曼树的结果。包括，字符ASCII码，出现频数，父亲节点，左孩子，右孩子；

“HuffmanCode.txt”：通过哈夫曼编码生成的哈夫曼编码文件，对文件字符编码后，将它与字符编成的码存放在一起，便于解压时的使用。包括，字符ASCII码和哈夫曼编码。

“XXX.txt.txt”：对原文件进行第一次压缩后生成的文件。里面全是01码。

“XXX.txt.txt.txt”：对上一步的压缩文件进行再次压缩，将压缩结果存放起来，生成最终的压缩文件。里面是按照十六进制的数进行存储的。

“XXX1.txt.txt”：对“XXX.txt.txt.txt”文件进行解压后生成的01码文件，如果程序运行没有错误的话，这个文件应该与“XXX.txt.txt”文件内容完全相同。

“XXX1.txt”：对上一步解压生成的文件进行再一次解压，生成源文件。如果程序运行正确的话，这个文件当中的东西应该与“XXX.txt”文件当中的内容完全一致。

这就是本程序的输出结果，全部是以文件的形式输入与输出的。

a.测试用例一：

输入：sun.txt: [email protected]

输出：

”letter.txt”: （部分）

……

108 1 0.041667

109 2 0.083333

110 4 0.166667

111 2 0.083333

……

“HuffmanTree.txt”：（部分）

……

176 0.000000 208 101 102

177 0.000000 209 104 112

178 0.000000 209 113 114

……

“HuffmanCode.txt”：（部分）

……

111 1110

112 01010000001

113 01010000010

114 01010000011

……

“sun.txt.txt”：

00110100101000011001001010111001010111011110000101011011110110011000010111101111111101101

“sun.txt.txt.txt”： 34a192b95de15bd985eff6f

“sun1.txt.txt”：

00110100101000011001001010111001010111011110000101011011110110011000010111101111111101101

“sun1.txt”： [email protected]

测试结果：生成的”sun1.txt”与原文件”sun.txt”完全相同，符合预期的结果。

b.测试用力二：

输入：sun.txt: 8*^&*(^&%^%&*

输出：sun1.txt: 8*^&*(^&%^%&*

测试结果：源文件与解压后的文件完全相同，符合预期的结果。

c.测试用例三：

……

八、软件总结积累

8.1完成过程总结

在开始本程序的编码之前，我先理清楚了编码的思路，然后通过上网的途径，把编码过程当中可能遇到的一些细节问题解决掉，等一切准备工作都做好之后，开始了文档的编写，完成了需求分析，概要设计说明书，详细设计说明书的部分内容，软件开发计划。然后才开始编码，等编码完成后，进行调试与测试之后，补充和完善了详细设计说明书和文档剩余的所有内容。

在本次的课程设计当中，没有按照原来先编码，再写文档的方法，按照软件工程要求的过程来规范自己进行程序的设计与编码。防止思路不清，先来编码，等到最后，程序很乱的那种情况的出现，避免浪费不必要的时间。

8.2程序的改进

8.3编码过程中遇到的问题