哈夫曼编译码器课程设计报告(完整版).doc

XXX学院本科
数据结构课程设计总结报告

设计题目：实验一、哈夫曼编/译码器
学生姓名：XXX
系 别：XXX
专 业:XXX
班 级:XXX
学 号：XXX
指导教师:XXX XXX

2012年 6 月 21日

xxx学院
课 程 设 计 任 务 书

题目 一、赫夫曼编译码器
专业、班级 xxx
学号 xxx 姓名 xxx
主要内容、基本要求、主要参考资料等：
1. 主要内容
利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）.对于双工信道(既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。
2。 基本要求
系统应具有以下功能：
（1）C：编码（Coding)。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中
（2）D：解码(Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。
(3)P：打印代码文件（Print)。将文件codefile以紧凑格式显示在终端上,每行50个代码.同时将此字符形式的编码文件写入文件codeprint中。
（4）T：打印哈夫曼树（Tree Printing).将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。
3。 参考资料:数据结构（C语言版) 严蔚敏、吴伟民编著；
数据结构标准教程 胡超、闫宝玉编著
完 成 期 限： 2012年6月21 日
指导教师签名：
课程负责人签名:
2012年 6月 21 日
一、设计题目(任选其一）
实验一、哈夫曼编/译码器

二、 实验目的
1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；
2 深化对算法课程中基本概念、理论和方法的理解；
3 巩固构造赫夫曼树的算法；
4 设计试验用程序实验赫夫曼树的构造。

三、运行环境(软、硬件环境）
Windows xp sp3,Visual C++ 6。0英文版

四、算法设计的思想
（1）初始化赫夫曼树，输入文件tobetrans。txt中各字符及其权值，并保存于hfmtree.txt文件中
（2)编码（Coding)。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中
（3）D：解码(Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。
（4)P：打印代码文件（Print）.将文件codefile以紧凑格式显示在终端上，每行50个代码.同时将此字符形式的编码文件写入文件codeprint中.
(5）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

五、 流程图

六、 算法设计分析

1.赫夫曼树节点的数据类型定义为:
typedef struct{ //赫夫曼树的结构体
char ch;
int weight; //权值
int parent，lchild,rchild；
｝ HTNode,*HuffmanTree；
2。 void HuffmanCoding(HuffmanTree ＆，char ＊，int *，int）；建立赫夫曼树的算法,此函数块调用了Select（）函数。void select（HuffmanTree HT，int j,int *x,int *y);从已建好的赫夫曼树中选择parent为0,weight最小的两个结点。
3．利用已建好的哈夫曼树从文件hfmtree。txt中读入,对文件中的正文进行编码，然后将结果存入文件codefile.txt中。
4。 coding
编码功能:对输入字符进行编码
5。 Decoding
译码功能： 利用已建好的哈夫曼树将文件codefile。txt中的代码进行译码,结果存入文件textfile。txt 中。
6。 Print（） 打印功能函数：输出哈夫曼树以及对应的编码。
七、源代码

//////////////////////////////////////////////////////////////////////////////////////////
#include 〈stdio.h>
#include <stdlib.h>
#include 〈string。h>

//定义赫夫曼树结点的结构体
typedef struct{
char ch； //增加一个域,存放该节点的字符
int weight;
int parent，lchild,rchild；
｝HTNode，*HuffmanTree；
typedef char ＊*HuffmanCode； //指向赫夫曼编码的指针

void tips（）; //打印操作选择界面
void HuffmanCoding（HuffmanTree &，char *，int ＊,int）； //建立赫夫曼树的算法
void select（HuffmanTree HT,int j,int *x，int *y）； //从已建好的赫夫曼树中选择parent为0，weight最小的两个结点
void Init（)；
void Coding（); //编码
void Decoding（）； //译码
void Print_code(); //打印译码好的代码
void Print_tree(）； //打印哈夫曼树
int Read_tree（HuffmanTree &）; //从文件中读入赫夫曼树
void find（HuffmanTree &HT,char ＊code，char *text，int i,int m）； //译码时根据01字符串寻找相应叶子节点的递归算法
void Convert_tree（unsigned char T[100］［100］，int s,int *i，int j）； //将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树

HuffmanTree HT; //全局变量
int n=0； //全局变量，存放赫夫曼树叶子结点的数目

int main（)
{
char select；

while（1）
｛
tips(）;
scanf(”%c"，&select);
switch(select) //选择操作，根据不同的序号选择不同的操作
{

case '1’:Init();
break；

case ’2':Coding();
break;

case '3'：Decoding（）;
break；

case ’4'：Print_code(）;
break；

case '5’：Print_tree（);
break；

case ’0’：exit(1);

default ：printf("Input error！\n”);
｝
getchar()；
}
return 0;
｝

void tips(） //操作选择界面
{
printf(" ---—--————-—-———--—---—------—-——--—————--——--—--————\n"）;
printf(" -— 请选择操作 -—\n"）;
printf(” -----——---—-—-—————————---——-——--—--—------———--—---—\n");
printf（” \n");
printf(" ——------———-—---————-1初始化赫夫曼树 ——-—-—-—-——————\n”)；
printf（" -———-—--——-----—-----2编码 ——-—---——-—-———\n"）；
printf（" -————-----——-——---——-3译码 ——————----—----\n");
printf(” ———-—-—-————---—————-4打印代码文件 -----—-—--————-\n")；
printf（" --—------——-——-————--5打印赫夫曼树 --—--—-———-——-—\n"）；
printf(" -—-------——-—-————-——0退出 ---—-—-—---——--\n"）;
printf(” ———-—--—-—--—-—————----—----——————--——--——-—-——-—---—\n"）;
｝

//初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树,并将其存于文件hfmtree中
void Init(）
｛
FILE ＊fp；
int i,n，w［52]; //数组存放字符的权值
char character［52]； //存放n个字符
printf（"\n输入字符个数 n:”）；
scanf（”％d”，＆n）; //输入字符集大小
printf("输入%d个字符及其对应的权值：\n”，n）;
for （i=0；i〈n；i++)
｛
char b=getchar(）；
scanf("%c”,&character[i]）；
scanf（”%d"，＆w[i])； //输入n个字符和对应的权值
}
HuffmanCoding(HT,character，w,n)； //建立赫夫曼树

if（(fp=fopen（”hfmtree.txt”,”w"））==NULL)
printf(”Open file hfmtree.txt error！\n"）；
for (i=1；i〈=2*n—1；i++）
｛
if（fwrite（&HT[i］,sizeof（HTNode），1,fp）！=1) //将建立的赫夫曼树存入文件hfmtree。txt中
printf(”File write error！\n”)；
}
printf（”\n赫夫曼树建立成功，并已存于文件hfmtree.txt中\n")；
fclose（fp）;

}

//建立赫夫曼树的算法
void HuffmanCoding（HuffmanTree ＆HT，char *character，int *w，int n）
｛
int m,i，x,y;
HuffmanTree p；
if（n〈=1） return;
m=2＊n—1;
HT=（HuffmanTree）malloc(（m+1）＊sizeof(HTNode)）；
for(p=HT+1,i=1；i<=n;++i，++p，++character,++w）
{p—>ch=＊character；p-〉weight=＊w；p—〉parent=0;p->lchild=0;p-〉rchild=0；｝
for(；i〈=m;++i，++p） ｛p->ch=0;p—〉weight=0;p->parent=0;p-〉lchild=0;p—〉rchild=0;｝
for(i=n+1；i〈=m;++i）
｛
select（HT,i—1,＆x，&y）；
HT[x］。parent=i；HT［y]。parent=i;
HT［i］。lchild=x；HT［i].rchild=y；
HT［i］。weight=HT［x］.weight+HT[y］。weight;
}

｝

//从HT[1］到HT[j]中选择parent为0，weight最小的两个结点，用x和y返回其序号
void select（HuffmanTree HT,int j，int ＊x，int *y）
｛
int i;
//查找weight最小的结点
for (i=1；i<=j；i++）
if (HT[i］.parent==0)
{*x=i；break；}
for (;i<=j;i++）
if （（HT［i]。parent==0）&＆（HT［i].weight〈HT[＊x］。weight））
*x=i;
HT［*x]。parent=1；
//查找weight次小的结点
for (i=1；i〈=j；i++)
if (HT[i].parent==0）
{＊y=i;break；}
for （;i<=j；i++）
if (（HT［i］.parent==0）&&（i!=＊x)＆&（HT[i］。weight<HT［*y］。weight)）
＊y=i;

}

//对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中
void Coding（)
｛
FILE *fp,*fw；
int i,f，c,start；
char *cd；
HuffmanCode HC；
if（n==0）
n=Read_tree（HT)；//从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数

//求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
｛
HC=（HuffmanCode）malloc(（n+1）＊sizeof（char*));
cd=(char *）malloc（n＊sizeof(char)）;
cd［n-1]='\0’；
for(i=1;i〈=n；++i）
{
start=n-1；
for（c=i,f=HT［i]。parent;f!=0；c=f，f=HT［f］。parent）
if（HT［f］。lchild==c）
cd［--start］=’0';
else cd[——start］='1'；
HC［i]=（char *)malloc（（n-start)*sizeof(char)）;
strcpy(HC［i］，＆cd［start])；
}
free(cd);
}

if((fp=fopen(”tobetrans。txt","rb"）)==NULL）
printf("Open file tobetrans。txt error！\n”)；
if（（fw=fopen（”codefile。txt”,”wb+"))==NULL）
printf（"Open file codefile。txt error!\n");
char temp；
fscanf(fp，”％c"，&temp); //从文件读入第一个字符
while（!feof（fp))
｛
for（i=1；i<=n；i++）
if（HT[i］。ch==temp） break； //在赫夫曼树中查找字符所在的位置
for（int r=0;HC[i］［r]！=’\0’;r++) //将字符对应的编码存入文件
fputc(HC[i][r］，fw）;
fscanf（fp,”％c",＆temp）； //从文件读入下一个字符

｝
fclose（fw）；
fclose(fp）;
printf("\n已将文件hfmtree。txt成功编码,并已存入codefile.txt中！\n\n")；
｝

//将文件codefile中的代码进行译码，结果存入文件textfile中
void Decoding()
{
FILE ＊fp，＊fw；
int m，i;
char ＊code，*text,＊p;

if(n==0)
n=Read_tree(HT）；//从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数

if((fp=fopen（"codefile.txt”，”rb"）)==NULL)
printf("Open file codefile。txt error!\n")；
if((fw=fopen("textfile。txt”，"wb+”))==NULL）
printf("Open file textfile.txt error!\n"）;
code=（char *)malloc（sizeof(char));
fscanf（fp,"％c"，code)； //从文件读入一个字符
for(i=1；！feof（fp）;i++)
{
code=(char *）realloc(code,（i+1）＊sizeof(char）)； //增加空间
fscanf(fp,"%c”,＆code[i]）； //从文件读入下一个字符
}
code[i-1］='\0’;
// codefile。txt文件中的字符已全部读入，存放在code数组中
text=(char *)malloc(100＊sizeof(char））；
p=text；
m=2＊n—1;
if（*code=='0’)
find(HT，code,text，HT［m]。lchild，m); //从根节点的左子树去找
else
find（HT，code，text,HT［m].rchild，m）; //从根节点的右子树去找

for（i=0；p[i］!=’\0’;i++） //把译码好的字符存入文件textfile.txt中
fputc（p[i］,fw);

fclose（fp);
fclose(fw);

printf(”\n已将codefile。txt文件成功译码，兵已存入textfile。txt文件!\n\n"）;
｝

//将文件codefi1e以紧凑格式显示在终端上，每行50个代码.同时将此字符形式的编码文件写入文件codeprint中。
void Print_code(）
｛
FILE *fp，*fw；
char temp;
int i;

if((fp=fopen("codefile.txt"，”rb”）)==NULL）
printf（”Open file codefile.txt error！\n”）;
if(（fw=fopen(”codeprint.txt”,"wb+"）)==NULL)
printf（”Open file codeprint.txt error!\n"）；

printf(”\n文件codefi1e显示如下:\n”）;
fscanf(fp,"%c”，＆temp）； //从文件读入一个字符
for (i=1；！feof(fp）;i++）
｛
printf（"％c"，temp）;
if（i％50==0） printf("\n"）;
fputc（temp，fw)； //将该字符存入文件codeprint.txt中
fscanf（fp,"％c",＆temp); //从文件读入一个字符
｝
printf(”\n\n已将此字符形式的编码写入文件codeprint.txt中!\n\n"）；

fclose（fp);
fclose(fw)；

}

//将已在内存中的哈夫曼树显示在屏幕上,并将此字符形式的哈夫曼树写入文件treeprint中。
void Print_tree（）
｛
unsigned char T［100]［100]；
int i，j,m=0；
FILE *fp;
if（n==0）
n=Read_tree(HT)； //从文件hfmtree。txt中读入赫夫曼树，返回叶子结点数

Convert_tree（T,0,＆m,2*n—1)； //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中

if（（fp=fopen(”treeprint。txt”,”wb+”）)==NULL)
printf(”Open file treeprint.txt error!\n"）;
printf("\n打印已建好的赫夫曼树：\n”）;
for(i=1;i〈=2*n—1；i++）
｛
for (j=0；T［i］[j］!=0；j++）
｛
if（T［i]［j]==’ '） {printf（" ");fputc(T[i]［j],fp)；｝
else
{printf（”％d”，T［i]［j]）；fprintf（fp，”%d\n",T[i］［j］）；｝
｝
printf(”\n");
｝
fclose(fp);
printf("\n已将该字符形式的哈夫曼树写入文件treeprint.txt中!\n\n”）;

}

//从文件hfmtree。txt中读入赫夫曼树，返回叶子节点数
int Read_tree（HuffmanTree ＆HT)
｛
FILE *fp;
int i，n;
HT=(HuffmanTree)malloc(sizeof（HTNode)）;
if（(fp=fopen（"hfmtree.txt","r”）)==NULL）
printf("Open file hfmtree.txt error！\n")；
for （i=1;!feof(fp）;i++）
{
HT=(HuffmanTree)realloc（HT，（i+1）＊sizeof（HTNode)）; //增加空间
fread(&HT[i］,sizeof(HTNode)，1,fp）; //读入一个节点信息
}
fclose（fp);
n=（i—1)/2；
return n;
}

//译码时根据01字符串寻找相应叶子节点的递归算法
void find（HuffmanTree ＆HT，char ＊code,char ＊text,int i,int m）
｛

if(*code！=’\0’） //若译码未结束
{
code++；
if（HT[i]。lchild==0&&HT[i］.rchild==0） //若找到叶子节点
｛

＊text=HT［i]。ch； //将叶子节点的字符存入text中

text++；
if((*code=='0'））
find(HT，code,text,HT［m］.lchild,m）; //从根节点的左子树找
else
find（HT，code，text,HT[m］。rchild，m）； //从根节点的右子树找
}
else //如果不是叶子节点
if(*code=='0')
find（HT,code，text,HT［i]。lchild,m)； //从该节点的左子树去找
else
find（HT,code，text，HT［i］。rchild，m）； //从该节点的右子树去找

}
else
＊text='\0'; //译码结束

｝

//将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来
void Convert_tree（unsigned char T[100][100］,int s,int *i，int j）
｛
int k,l；
l=++(*i）；
for(k=0；k<s；k++)
T[l］[k]=' ’;
T［l］[k］=HT［j].weight；
if（HT[j]。lchild）
Convert_tree（T,s+1，i，HT［j]。lchild)；
if(HT[j］。rchild)
Convert_tree（T,s+1，i，HT[j]。rchild)；
T[l]［++k]=’\0'；
｝
//////////////////////////////////////////////////////////////////////////////////////////////////
八、运行结果分析
截图说明：

1、运行后界面如图（1）：

图(1）
选择要选择的操作序号可以运行各个步骤；
2、初始化赫夫曼树:
输入tobetrans.txt中各元素及其出现频率，如图（2）

图(2）

3、编码及译码，如图(3)

图(3)
4、打印编码文件，如图（4）

图（4）
5、打印赫夫曼树,如图（5）

图（5）
6、各步骤所存的文件内容如图(6)

图（6)

九、收获及体会
课程设计是让我们充分利用我们专业课程所学知识的机会,也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步,也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。
我的课程设计题目是赫夫曼编译码器.最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料,在写这个程序的时候也参考了网上的设计流程,写完刚运行时出现了很多问题。尤其是编码错误，导致内存无法read,通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。 通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法,更是解决问题的思想.课程设计本身也是一种相互学习的过程，///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdio。h>
#include <stdlib.h〉 //为exit（)提供原型
＃include <string。h〉

//哈夫曼树结点的结构
typedef struct ｛
char ch； //该字符域用于存放节点的关键字
int weight；
int parent, lchild, rchild；
}HTNode, ＊HuffmanTree; //动态分配数组存储哈夫曼树
typedef char ＊＊HuffmanCode； //动态分配数组存储哈夫曼编码表

void Menu(）; //显示菜单
void HuffmanCoding(HuffmanTree &HT, char ＊character， int * w， int n）; //建立哈夫曼树
void select(HuffmanTree HT， int j， int *x, int *y）; //从已建好的赫夫曼树中选择parent为0,weight最小的两个结点
void Init（）;
void Coding(); //编码
void Decoding(）; //译码
void Print_code（）; //打印译码好的代码
void Print_tree（); //打印哈夫曼树
int Read_tree（HuffmanTree ＆); //从文件中读入赫夫曼树
void find(HuffmanTree ＆HT， char *code, char ＊text, int i, int m）； //译码时根据01字符串寻找相应叶子节点的递归算法
void Convert_tree（unsigned char T[100］［100]， int s， int *i, int j）; //将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树

HuffmanTree HT; //全局变量
int n = 0; //全局变量，存放赫夫曼树叶子结点的数目

int main（）
｛
char select；

while （1)
｛
Menu(）;
scanf（"％c"， &select）；
switch （select) //选择操作,根据不同的序号选择不同的操作
｛

case '1’:Init();
break；

case '2':Coding（);
break;

case '3':Decoding（)；
break；

case ’4'：Print_code（);
break；

case ’5':Print_tree（)；
break；

case '0'：exit（1);

default:printf("Input error！\n”）;
}
getchar(）;
}
return 0；
}

void Menu（) //操作选择界面
{
printf(" -————-—--—-—-—-—————-———-——————--—--———————-——--——--—\n”);
printf(" -- 请选择操作 ——\n");
printf（” ——-—----—-—————-——-—-----—----—-—--—————--———————-—--\n"）；
printf（” \n”)；
printf(” ——--——---—-—-———-———-1初始化赫夫曼树 —--------—-——-—\n"）；
printf(" -—--————---—-—---———-2编码 --——-----——-———\n"）；
printf(” ———-—-——----—————-——-3译码 ———-—---————---\n”);
printf（" —-————-——-—-----———-—4打印代码文件 --—-——--—---——-\n”)；
printf(" —-——--——-—-——-------—5打印赫夫曼树 —-————-—-----—-\n”）；
printf(” —----———-—--—-——-—-——0退出 --—----—----——-\n")；
printf(” -—--—---—--—-----———-————----———----————-—-———--——-——\n”）；
｝

//初始化函数，输入n个字符及其对应的权值,根据权值建立哈夫曼树，并将其存于文件hfmtree中
void Init（）
｛
FILE *fp；
int i, n, w[52］; //数组存放字符的权值
char character[52]； //存放n个字符
printf（”\n输入字符个数 n:”);
scanf(”%d”， ＆n）; //输入字符集大小
printf（”输入%d个字符及其对应的权值:\n", n）;
for （i = 0; i〈n； i++)
{
char b = getchar（）；
scanf（"%c”， ＆character［i］）;
scanf(”％d"， ＆w［i]）； //输入n个字符和对应的权值
}
HuffmanCoding（HT, character, w， n)； //建立赫夫曼树

if (（fp = fopen(”hfmtree.txt”, ”w")) == NULL)
printf("Open file hfmtree.txt error！\n”）；
for (i = 1； i 〈= 2 * n - 1； i++）
{
if （fwrite（＆HT[i]， sizeof(HTNode)， 1, fp） != 1） //将建立的赫夫曼树存入文件hfmtree。txt中
printf（"File write error!\n”）;
}
printf（"\n赫夫曼树建立成功,并已存于文件hfmtree。txt中\n")；
fclose（fp);

}

//构造哈夫曼树的算法
void HuffmanCoding(HuffmanTree &HT， char ＊character, int * w, int n)
｛ //w存放n个字符的权值(均>0），构造哈夫曼树HT
int m， i， x, y;
HuffmanTree p;
if (n 〈= 1) return；
m = 2 * n - 1；
HT = (HuffmanTree)malloc（（m + 1) ＊ sizeof(HTNode));
for (p = HT + 1， i = 1; i 〈= n； ++i， ++p， ++character， ++w）
｛
p-〉ch = ＊character; p—〉weight = ＊w; p—〉parent = 0； p->lchild = 0； p—〉rchild = 0；
｝
for （; i <= m; ++i， ++p) {