应用数据结构课程设计(哈夫曼树).doc

学 号：
0120803490117

课 程 设 计

题 目
Huffman编／译码器
学 院
管理学院
专 业
信息管理与信息系统
班 级
0801
姓 名
王涛
指导教师
燕翔

2010
年
07
月
09
日

课程设计任务书

学生姓名： 王涛 专业班级： 信管0801
指导教师： 燕翔 工作单位： 管理学院
题 目： Huffman编／译码器
初始条件：
利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个Huffman码的编／译码系统。

要求完成的主要任务: （包括课程设计工作量及其技术要求、说明书撰写等具体要求）
一个完整的系统应具有以下功能：
（l）I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：编码。利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：译码。利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50 个代码。
（5）T：印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
时间安排：
序号
设计内容
所用时间
1
问题分析和任务定义
0.5天
2
数据类型和系统设计
0.5天
3
编码实现和静态检查
3天
4
上机准备和上机调试
2天
5
总结和整理设计报告
1天
合 计
7天

指导教师签名： 2010年 07月02日
系主任（或责任教师）签名： 2010年 07月02日

1. 需求分析
1.1 程序的任务：
利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。此程序就是为这样的信息收发站写一个Huffman码的编／译码系统。
1.2 程序的输入和输出：
从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
1.3 程序要达到的功能：
用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。
1.4 测试数据如下表：
（l）利用教材中的数据调试程序。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码："THIS PROGRAM IS MY FAVORITE"。
字符

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
57
63
15
1
48
51
80
23
8
18
1
16
1

选择E，输入THIS PROGRAM IS MY FAVORITE，屏幕上显示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010
同时文件codefile里面也出现相应的代码
选择D，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，并且文件textfile中也相应的存入了这段话。
选择P，文件CodeFile以紧凑格式显示在终端上。
选择T，将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
选择其他的字母，将出现出错提示，并重新回到选择菜单。

2. 概要设计
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素集合。
数据关系R：
若D为空，则R为空，称Huffmantree为空霍夫曼树；
若D不为空，则R={H}，H是如下的二元关系：
1、 H满足二叉树的所有要求；
2、 H中所有数乘以该数所在节点的深度值之后和最小。
基本操作P：
InputHuffman(Huffman Hfm)
操作结果：输入并存储字符和相应权值。
Select(HuffmanTree HT,int end,int *s1,int *s2)
初始条件：频率数组已经建立。
操作结果：选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2。
HuffmanCoding(Huffman Hfm)
初始条件：频率数组已经建立。
操作结果：w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC。
InitHuffman(Huffman Hfm)
初始条件：频率数组已经建立。
操作结果：要求用户输入字符和相应权值，初始化赫夫曼数
Encoding(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
Decoding(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
Print(Huffman Hfm)
初始条件：霍夫曼树HoffmanTree已经存在。
操作结果：将文件CodeFile以紧凑格式显示在终端上，每行50 个代码。
Treeprint(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
}ADT HuffmanTree

2. 2 主程序流程

Void main()
{
显示菜单；
Switch(k)
{
I：初始化
E：编码
D：译码
P：印代码文件
T：印哈夫曼树
Q：退出运行
}
}

2.3 程序调用模块

3. 详细设计
3.1数据类型：
typedef char **HuffmanCode;//动态分配数组存储霍夫曼表码表
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储霍夫曼树
typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//分配数组存储字符串及其对应的霍夫曼树
Huffman Hfm;
char k; /*控制循环的标志*/
3.2 伪码算法：
主程序
main()
{
InitHuffman(Huffman Hfm)；
Encoding(Huffman Hfm)；
Decoding(Huffman Hfm)；
Print(Huffman Hfm)；
Treeprint(Huffman Hfm)；
}
其他模块：

void Select(HuffmanTree HT,int end,int *s1,int *s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2

FOR (i=1;i<=end;i++)
{
IF(HT[i].parent是最小的)
THEN HT[i].parent——>*s1
IF(HT[i].parent是次最小的)
THEN HT[i].parent——>*s2
}

Huffman HuffmanCoding(Huffman Hfm) //w存放n个字符的权值（均〉0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC
{
FOR(i=n+1;i<=2*n-1;++i) //选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
{
Select(Hfm.HT,i-1,&s1,&s2);
修改父亲位置；
修改孩子位置；
父亲结点权值为左右孩子权值之和；
}

//从叶子结点到根逆向求每个字符的赫夫曼编码
FOR(i=1;i<=n;++i)
//逐个字符求赫夫曼编码
{ start=n-1;//编码结束符位置
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
//从叶子到根逆向求编码
{
IF(c==Hfm.HT[f].lchild) cd[--start]='0';
ELSE cd[--start]='1';
}
再从cd复制编码到Hfm.HC
}
RETURN Hfm;
}

Huffman InitHuffman(Huffman Hfm)//初始化赫夫曼数，要求用户输入字符和相应权值
{
对文件hfmTree以读文本的形式打开
IF(fp==NULL)
调用InputHuffman函数，用户输入字符和相应权值存入赫夫曼数中
ELSE
输出"The Huffmantree has already existed!\nPlease choose again!\n\n");
读入hfmTree中文本
FOR(i=1;i<=n;i++)
作为独立结点对结点的parent，lchild，rchild分别赋值0
FOR(;i<=2*n-1;++i)
作为独立结点对结点的weight，parent，lchild，rchild分别赋值0
Hfm=HuffmanCoding(Hfm);
RETURN Hfm;
}
void Encoding(Huffman Hfm)//利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
{
输出"\n\n*******************Encoding**************************\n\n"
IF((ffp=fopen("ToBeTran","rt"))==NULL)
提示输入"Please input the sentence: "
scanf("%s",ch);
printf("\n");
以写文本的形式打开CodeFile
ELSE
读入ToBeTran文件中的字符;
WHILE(ch[j])
FOR(i=1;i<=n;i++)
IF(ch[j]==Hfm.c[i])
分别在终端和文件CodeFile输入Hfm.HC[i]

void Decoding(Huffman Hfm)//利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
{ 定义char d[500]
输出"\n\n******************Decoding************************\n\n"
IF((fp=fopen("CodeFile","rt"))==NULL)
输出Please input the code:;
ELSE
将文件Codefile中的内容读到d数组中
输出The file is :
以写文本的方式打开TextFile
WHILE(d[j])
根到叶子结点遍历，并按照lchild——>0，rchild——>1来输出
入到文件TextFile中
关闭文件
}
void Print(Huffman Hfm)//将文件CodeFile以紧凑格式，示在终端上，每行50 个代码。
{
FOR(i=1;i<=n;i++)
输出Hfm.c[i]
输出Hfm.HT[i].weight
以只读二进制的方式打开CodeFile文件
while ( feof(fprint)==0 )
逐个输出
IF (m%50==0)
输出"\n"
关闭文件
}

void Treeprint(Huffman Hfm)//将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
{
打开hfmTree文件
将字符及其对应的代码赋给变量Hfm.c[i]和Hfm.c[i][j]
输出Hfm.c[i]，对Hfm.c[i][j]进行判断，不是\n则输出*，否则停止输出
}

3.3函数调用关系图
InputHuffman(Huffman Hfm)接收数据

Select（）供HuffmanCoding()调用
调用HuffmanCoding()构造哈夫曼树

编码调用Encoding()
译码调用Decoding（）

打印编码Print()
打印哈夫曼树Treeprint()
InitHuffman(Huffman Hfm)
初始化

4. 调试分析
4.1 调试过程中遇到的问题：
第一个问题是一直比较棘手的问题就是文件的调用与写入，因为文件方面的知识一直就掌握的不是很好，在写代码时产生很大困难，所以在解决这个问题的时候我把文件部分系统的看了一下，这才从自身角度解决了这个问题。而实际中遇到的问题就是如何判断已经有了hfmtree这个文件，并且怎么调用到内存中来。
解决方案：设置一个全局结构体变量来存放已经在文件中存放的霍夫曼树。
第二个问题是关于界面的美观设计方面，因为很多代码在文本中编辑时是比较整齐美观的，但是在程序运行中却出现很多问题，不对齐等等。还有就是换行符的使用，一不小心就会产生偏差。
解决方案：进入程序进行调试，检查每段输出代码的显示。
第三个问题是Huffman树的打印，方式为凹入式打印，由于在当时学习的时候这部分内容没有留意，根本没有概念，所以在编写程序过程中出现了严重的问题。导致该项功能无法完成。
解决方案：尚未完善解决，只是将内存中的哈夫曼树中各节点的值及其孩子输出。
4.2 算法的时空分析：
算法的时间复杂度：
Select(HuffmanTree HT,int end,int *s1,int *s2) O(n)
HuffmanCoding(Huffman Hfm) O(n2)
InputHuffman(Huffman Hfm) O(n)
InitHuffman(Huffman Hfm) O(n)
Encoding(Huffman Hfm) O(n)
Decoding(Huffman Hfm) O(n)
Print(Huffman Hfm) O(n)
4.3 经验与体会：
整个程序在编的时候思路是很明朗的，包括菜单的设置都是很清晰的，但是如何通过一个菜单将所有涉及到的文件与终端联系起来还有打印哈夫曼树都是比较困难的问题，由于文件这一章节我们以前学习的时候并没有很重视，所以在运用的时候遇到了很大的困难，同时通过这次的设计我也看到其实文件这一章是很重要的，我们做了一个程序，必须要把有些必要的数据进行保存，如果只是停留在内存中那就很难在以后被重复利用，会很大程度上提高我们调试的效率；另外凹入式打印哈夫曼树更是让我头疼了一整天的问题，由于根本不知道其概念是什么，更不用说去编写代码了。同时我也觉得有些细节问题是很重要的，不管是一个整型变量还是一个结构体变量，有时候对整个程序起着至关重要的作用。
5. 用户使用说明
1．本程序的运行环境为DOS操作系统，执行文件为：hfmtree.exe。
2. 运行程序后出现选择菜单。
3．根据提示选择相应的操作，初始化，编码，译码，印代码文件，印哈夫曼树
退出，每次选择完，都会再次弹出选择菜单供用户选择。结束符为回车键。
6. 测试结果
在进入系统以后，选择第一个初始化，按要求键入要求的字符及其频度
字符
—
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
57
63
15
1
48
51
80
23
8
18
1
16
1
截图如下所示：
图1
进入程序，显示的菜单界面
图2
输入I，选择进行初始化
图3
初始化时对字符的个数进行限制，不得少于2个。

图4、5
在字符个数处输入“27”，之后依次输入各字符及其权值。
图6

在菜单界面选择E，出现提示语句，要求输入句子。

图7

输入“THIS_PROGRAM_IS_MY_FAVORITE”，回车之后，显示出该句的哈夫曼编码。
（此处为求简捷，将空格用下划线“_”作为代替）

图8
在菜单界面选择D，则对文件中已有的哈夫曼编码进行反译，将译出的字符显示出来。
图9
在菜单界面选择P，将文件中的哈夫曼编码紧凑输出，每行50个。结果如下图：

图10、11
该程序中，我加入了将初始化的各字符的编码输出的语句，可以看到各个字符的哈弗曼编码。
图12
这3行数字便是紧凑输出哈夫曼编码的结果。
图13
同时，不同的人使用本程序进行不同的哈夫曼编码时，由于前一位使用者初始化的数据后一位不一定同样适用，为了避免这种情况，因此当已经初始化后再进行初始化时会出现提示是否重新初始化的信息提示，如上图所示。
图14
在菜单界面选择T，打印处内存中的哈夫曼树各节点的值及其双亲节点和子节点。
图15
TEXTFILE.TXT文本文件，记录用户输入的需要进行编码的句子。
图16
CODEFILE.TXT文本文件，记录TEXTFILE.TXT文本文件中字符的哈弗曼编码。
图17
HFMTREE.TXT文本文件，记录输入的各字符及其权值
7. 附录
源程序文件名清单：
TEXTFILE.TXT 记录待编码的句子
CODEFILE.TXT 记录哈夫曼编码
HFMTREE.TXT 记录字符个数、名称及权值

源代码：

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include<stdlib.h>
#include<ctype.h>

#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 32767
#define MAX 60

typedef char **HuffmanCode;//动态分配数组存储哈夫曼表码表

typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树

typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//全局结构体变量，来存储字符与代码

void Select(HuffmanTree HT,int end,int *s1,int *s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)//遍历查找权值最小的结点S1
{
if (HT[i].parent==0&&HT[i].weight<min1)
{
*s1=i;
min1=HT[i].weight;
}
}
min2=MAX_NUM;
for(i=1;i<=end;i++)//遍历查找除S1外权值最小的结点S2
{
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
{
*s2=i;
min2=HT[i].weight;
}
}
}

Huffman HuffmanCoding(Huffman Hfm) //存放n个字符的权值（均〉0），构造哈夫曼树HT，并求出n个字符的构造哈夫曼编码HC
{
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.length;
if(n<=1) return Hfm;
m=2*n-1;
for(i=n+1;i<=m;++i) //选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i;//修改父亲位置
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1;//修改孩子位置
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父亲结点权值为左右孩子权值之和
}
//从叶子结点到根逆向求每个字符的哈夫曼编码
Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';//编码结束符

for(i=1;i<=n;++i)//逐个字符求哈夫曼编码
{
start=n-1;//编码结束符位置
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//从叶子到根逆向求编码
{
if(c==Hfm.HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
}
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);//从cd复制编码到Hfm.HC
}
free(cd);//释放工作空间
return Hfm;
}

Huffman InputHuffman(Huffman Hfm)//输入函数，控制用户输入字符和相应权值
{
int i,n;

printf("\n\n********************Initialization*********************\n");
printf("The chars and weights will be saved in the file :\hfmTree\ \n");
printf("Please input the number of the chars: ");
scanf("%d",&n);
if(n<=1)
{printf("Only One Char!There Is No Need For Coding!");//若只有一个数值则无需编码
printf("\n");
printf("Please input the number of the chars: ");
scanf("%d",&n);}
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("Please input the char: ");
scanf("%s",&Hfm.c[i]);

printf("Please input the weight of the char: ");
scanf("%d",&Hfm.HT[i].weight);

Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.length=n;
return Hfm;
}

Huffman InitHuffman(Huffman Hfm)//初始化哈夫曼数，要求用户输入字符和相应权值
{
int n,i,x;
FILE *fp;
fp=fopen("hfmTree","rt");//对文件hfmTree以读文本的形式打开
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);//调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼数中
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.length);
for(i=1;i<=Hfm.length;i++)
fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}
else
{printf("The Huffmantree has already existed!\nDo You Want To Make A New One?('Y'or'N')\n\n");//询问是否重新初始化
scanf("%s",&x);
if(x=='Y')
{ Hfm=InputHuffman(Hfm);//调用InputHuffman函数，用户输入字符和相应权值存入哈弗曼数中
fp=fopen("hfmTree","w+");
fprintf(fp,"%d\n",Hfm.length);
for(i=1;i<=Hfm.length;i++)
fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}

else
{fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d ",&Hfm.c[i],&Hfm.HT[i].weight);//将已经在文件中的字符和其对应的权重输入到Hfm.c[i]和&Hfm.HT[i].weight中
for(i=1;i<=n;i++)//对每个节点初始化
{
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.length=n;
}
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;

}
void Encoding(Huffman Hfm)//利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*fw;
n=Hfm.length;
printf("\n\n*******************Encoding**************************\n\n");
if((fw=fopen("ToBeTran","r+"))==NULL)//尝试打开ToBeTran
{
printf("\nPlease input the sentence: ");
scanf("%s",ch);
printf("\n");
fp=fopen("CodeFile","wt+");
}
else
{
fscanf(fw,"%s",ch);
fclose(fw);
}
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
{
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
}
j++;
}
printf("\n");
rewind(fp);
fclose(fp);
}

void Decoding(Huffman Hfm)//利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
{
HuffmanTree p;
int i,n;
int j=0;
char d[500];
FILE *fp;
n=Hfm.length;
printf("\n\n******************Decoding************************\n\n");
if((fp=fopen("CodeFile","r+"))==NULL)
{
printf("Please input the code:");
scanf("%s",d);
}
else
{
fscanf(fp,"%s",d);//将文件中的字符输入到数组d中
fclose(fp);
}
printf("\nThe file is : ");
fp=fopen("TextFile","wt+");//以写入文件的形式打开TextFile
while(d[j])
{
p=&Hfm.HT[2*n-1];
while(p->