哈夫曼编码译码课程设计报告样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。

计算机与信息工程系

《实践环节名称》报告

专业: 计算机科学与技术
班级: ********
学号: *********
姓名: 杨明英
报告完成日期 : /6/10
指导教师: ***

评语:
成绩:

批阅教师签名: 批阅时间:

目录
1．问题描述……………………………………………………………1
2．基本要求……………………………………………………………1
3．数据结构……………………………………………………………1
4．总体设计……………………………………………………………1
5．详细设计……………………………………………………………2
5.1主函数 void main() ………………………………………………………2
5.2建立文件 void jianliwenjian()…………………………………………3
5.3输入原文 void luruyuanwen()…………………………………………4

5.4创立哈夫曼树 void chuangjian()………………………………………5
5.5编码 void bianma()……………………………………………………6
5.6对哈夫曼码译码 void yiwen()…………………………………………7
5.7保存译文 void baocunyiwen()……………………………………………8
5.8输出原文 void duquyuanwen() …………………………………………9
5.9输出原文编码 void duqubianma()…………………………………………10
5.10输出译文 void duquyiwen()……………………………………………11
6．测试与调试…………………………………………………………11
7．源程序清单…………………………………………………………8
8．实验心得……………………………………………………………28

1. 问题描述
打开一篇英文文章, 统计该文章中每个字符出现的次数, 然后以它们作为权值, 设计一个哈夫曼编/译码系统。
2. 基本要求
以每个字符出现的次数为权值, 建立哈夫曼树, 求出哈夫曼编码, 对文件yuanwen中的正文进行编码, 将结果存到文件yiwen中, 再对文件yiwen中的代码进行译码, 结果存到textfile中。
3. 数据结构
char CH[N]; //记录原文字符数组
char YW[N]; //记录译文字符数组
typedef char * Hcode[m+1]; //存放哈夫曼字符编码串的头指针的数组
typedef struct
{
char a;
int num;
}dangenode; //记录单个字符的类别和出现的次数
typedef struct
{
dangenode b[m];
int tag;
}jilunode; //统计原文出现的字符种类和数量
typedef struct node //静态三叉的哈夫曼树的定义
{
int weight; //结点的权值
int parent; //双亲的下标
int Lchild; //左孩子结点的下标
int Rchild; //右孩子结点的下标
}htnode,hn[M+1]; // hn是结构数组类型, 0号单元不用

4. 总体设计
功能函数模块划分
void main() //主函数
void jianliwenjian() //建立存储原文的文件yuanwen
void luruyuanwen() //经过程序录入原文到文件yuanwen中
void min_2(hn ht,int n,int *tag1,int *tag2) //选择权值较小的两个结点
void chuangjian(jilunode * jilu,hn ht) //建立哈夫曼树
void bianma(jilunode * jilu,hn ht,Hcode hc,int n) //对原文进行编码
void bianmabaocun(Hcode hc,jilunode * jilu) //保存编码在文件yiwen中
void yiwen(Hcode hc,jilunode * jilu) //读取yiwen中的编码, 并将其翻译为原文
void baocunyiwen() //将翻译的译文保存到文件textfile中
void duqubianma() //在编码文件yiwen中读取编码
void duquyiwen() //从文件textfile中读取译文
5. 详细设计
5.1 主函数 void main()
开始

Int tep=1;

N
tep=1

Y

a=1
N

Y

N
a=2
Y

jianliwenjian();

N
Y
a=3

luruyuanwen();
N

Y
c=1

chuangjian(jilu,humtree);
N

a=4
N
c=1
Y

Y
tep=0;

N
bianma(jilu,humtree,hc,jilu->tag);
hc,jilu);

Y

yiwen(hc,jilu);
tep=0;
a=5
system("cls");

Y

N
a=6

duquyuanwen();

Bianmabaoc
un(hc,jiolu);
system("cls");
break;

Y
baocunyiwen();

N
a=7
break;

N
N
c=1
c=1
N
c=1
duqubianma();

Y

N
Y
Y
duquyiwen();
c=1
tep=0;
tep=0;

N
Y

a=8
tep=0;
system("cls");

N
Y
c=1
tep=0;
system("cls");

Y

Y
break;
system("cls");

tep=0;
system("cls");
break;
IF
YES

break;

system("cls");
break;

结束

5.2建立文件 void jianliwenjian()

首先, 要建立一个文件来存储原文, 在这里文件的名称按要求默认为yuanwen, 文件建立时有可能成功, 有可能失败, 建立失败时输出”Cannot open file”, 成功后会提示: ”文件已建立, 名称为yuanwen”。
N
Y

5.3输入原文 void luruyuanwen()

输入原文时首先要打开原文件, 成功打开文件后逐个读取输入的字符存放到文件中, 直到遇到结束标志‘^’, 然后关闭文件。
Y
N
N
Y

5.4创立哈夫曼树 void chuangjian()
打开存储原文的文件yuanwen, 将字符逐个读出, 然后统计字符的种类, 类别和数量, 最后建立静态的三叉链表来建立哈夫曼树, 树中的叶子结点对应出现的个字符。
Y
N
Y
N

5.5编码 void bianma()
该函数实现对哈夫曼树的编码, 先申请一个能存储字符编码的临时空间cd, 编码从哈夫曼树的叶子结点开始, 寻找其父母结点, 然后根据父母结点判断孩子结点的左右位置, 左边置1, 右边置0, 并将1,0这样的字符从后往前逆序存放在cd中, 每求得一个叶子结点的编码, 就将其复制到存储哈夫曼编码的头指正数组中, 找完叶子结点的编码后就释放临时空间cd。
N
Y

5.6对哈夫曼码译码 void yiwen()
打开文件yiwen, 打开成功后, 逐个读取存放在里边的编码字符, 并与先前的编码相匹配, 直到找到编码对应的原字符, 当找完编码后就关闭文件。
N
Y
Y
N
Y
N

5.7保存译文 void baocunyiwen()
打开文件textfile, 打开成功后, 将译文保存到文件中, 然后关闭文件。

Y
N

5.8输出原文 void duquyuanwen()
打开文件yuanwen, 将里边的原文输出, 以便查看。

Y
N

5.9输出原文编码 void duqubianma()
打开文件yiwen, 打开成功后, 将文件中存放的编码输出, 然后关闭文件

。

Y
N

5.10输出译文 void duquyiwen()
打开文件textfile, 打开成功后, 输出里边的译文, 然后关闭文件。

N
Y

6. 测试与调试
程序调试采用Microsoft Visual Studio , 程序在调试过程中遇到了各种问题, 首先在建立哈夫曼树时我是用静态三叉链表实现的, 但里边的参数parent, Lchild, Rchild定义为指针类型, 在原理上是可行, 但调试时总得不到正确结果, 后来改为书中用基本类型整型后就很好的得到了满意结果, 其它一些小错误在不断地调试, 不断地改进后, 基本达到可满意的效果。各模块的调试结果截屏如下:
6.1主函数菜单

6.2建立文件

6.3经过程序输入原文

6.4直接将原文存放到文件yuawen中

6.5对原文编码

6.6对编码译码

6.7输出原文

6.8输出编码

6.9输出译文

7.源程序清单
#include
#include
#include
#define N 5000
#define m 128 //叶子结点个数, 即字符总类数
#define M 2*m-1 //哈夫曼树的节点数
char CH[N]; //记录原文字符数组
char YW[N]; //记录译文字符数组
typedef char * Hcode[m+1]; //存放哈夫曼字符编码串的头指针的数组
typedef struct
{
char a;
int num;
}dangenode; //记录单个字符的类别和出现的次数
typedef struct
{
dangenode b[129];
int tag;
}jilunode; //统计原文出现的字符种类数
typedef struct node
{
int weight; //结点权值
int parent; //双亲下标
int Lchild; //左孩子结点的下标
int Rchild; //右孩子的下标
}htnode,hn[M];//静态三叉的哈夫曼树的定义
void jianliwenjian()
{
printf("现在建立文件, 以存储原文( 文件名称默认为”yuanwen”) \n");
printf(" 文件建立中......\n");
FILE *fp;
if((fp=fopen("yuanwen","wb"))==NULL) //建立文件
{
printf("Cannot open file\n");
exit(0);
}
printf("文件已建立,名称为: yuanwen");
fclose(fp); //关闭文件
}
void luruyuanwen() //原文输入完后, 将其保存到文件yuanwen中
{
char ch;
FILE *fp;
if((fp=fopen("yuanwen","wb"))==NULL) //打开文件
{
printf("Cannot open file\n");
exit(0);
}

printf("请输入原文( 结束标志为: ”^”) \n");
do
{
ch=getchar();
fputc(ch,fp); //将字符保存到文件中
}while(ch!='^'); //判断结束
getchar(); //接收回车命令符
fclose(fp); //关闭文件
}
void min_2(hn ht,int n,int *tag1,int *tag2)//在建哈夫曼树的过程中, 选择权值小的两
{ 个结点
int i,min,s;
min=N;
for(i=1;i<=n;i++)
if(ht[i].weight最小的结点下标
}
min=N;
for(i=1;i<=n;i++)
if(ht[i].weight
(*tag2)=s;
}
}
void chuangjian(jilunode * jilu,hn ht) //建立哈夫曼树、 以及对原
{ 文字符的类别和数量统计
int i,j,s,tag1,tag2;
s=0;
i=-1;
char ch;
FILE *fp;
if((fp=fopen("yuanwen","rb"))==NULL) //以只读的方式打开文件
{
printf("Cannot open file\n");
exit(0);
}
while(!feof(fp)) //判断文件指示标志是否移动到了文件尾处
{
ch=fgetc(fp);
if(ch!='^') //判断字符是否是结束标志
{
++i;
CH[i]=ch;
for(j=1;j<=jilu->tag;j++)
{
if(CH[i]==jilu->b[j].a)
{
jilu->b[j].num++;
break;
}
}
if(j-1==jilu->tag&&CH[i]!=jilu->b[j-1].a)
{
jilu->tag++;
jilu->b[jilu->tag].a=CH[i];
jilu->b[jilu->tag].num=1;
}
}
}
jilu->tag--;
fclose(fp); //关闭文件
printf("原文中的各字符统计状况如下: \n");
printf("*^*^*^*^*^*^*^*^**^*^*^**^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n");
for(i=1;i<=jilu->tag;i++)
{
s++;
printf("‘%c’的个数为:%d ",jilu->b[i].a,jilu->b[i].num);
if(s%4==0) //每行放四个数据
printf("\n");
}

printf("\n");
for(i=1;i<=2*(jilu->tag)-1;i++)
{
if(i<=jilu->tag)
{
ht[i].weight=jilu->b[i].num; //初始化叶子结点权值
ht[i].Lchild=0; //初始化叶子结点左孩子
ht[i].parent=0; //初始化叶子结点父母
ht[i].Rchild=0; //初始化叶子结点右孩子
}
else
{
ht[i].Lchild=0; //初始化非叶子结点左孩子
ht[i].parent=0; //初始化非叶子结点父母

ht[i].Rchild=0; //初始化非叶子结点右孩子
ht[i].weight=0; //初始化非叶子结点权值
}
}
for(i=jilu->tag+1;i<=2*(jilu->tag)-1;i++)
{
min_2(ht,i-1,&tag1,&tag2); 需找权值小的两个父母为0的结点
ht[tag1].parent=i;
ht[tag2].parent=i;
ht[i].Lchild=tag1;
ht[i].Rchild=tag2;
ht[i].weight=ht[tag1].weight+ht[tag2].weight;
}
}
void bianma(jilunode * jilu,hn ht,Hcode hc,int n) //哈夫曼树建完后, 对叶
{ 子结点逐个编码
char * cd;
int start,i,p,c;
cd=(char *)malloc((n+1)*sizeof(char)); //申请存储字符的临时空间
cd[n-1]='\0'; //加结束标志

for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht[i].parent;
while(p!=0)
{
--start;
if(ht[p].Lchild==c)
cd[start]='1'; //结点在左边置1
if(ht[p].Rchild==c)
cd[start]='0'; //结点在右边置0
c=p;
p=ht[p].parent;
}
printf("%c的编码为: %s\n",jilu->b[i].a,&cd[start]);
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为字符数组分配空间
strcpy(hc[i],&cd[start]);//将临时空间中的编码复制到字符数组中
}
free(cd); //释放临时空间
}
void bianmabaocun(Hcode hc,jilunode * jilu) //将原文以编码的形式保存到
{ 文件yiwen中
int i,j;
FILE *fp;
if((fp=fopen("yiwen","wb"))==NULL) //以写的方式打开文件
{
printf("Cannot open file\n");
exit(0); //文件打开失败退出
}
for(i=0;i<=N&&CH[i]!='^';i++)
{
for(j=1;j<=jilu->tag;j++)
if(CH[i]==jilu->b[j].a)
{
fputs(hc[j],fp); //将文件中的字符输出到字符数组中
printf("%s",hc[j]);
}
}
fclose(fp); //关闭文件
}
void yiwen(Hcode hc,jilunode * jilu) //读取yiwen中的编码, 并将其翻译
{ 为原文存放到字符数组YW[N]中
int tag1,tag2,i,j,s=0;
FILE *fp; //文件指针
char *c;
if((fp=fopen("yiwen","rb"))==NULL) //以只读的方式打开文件
{
printf("cannot open file\n");
exit(0);
}
while(!feof(fp))
{
tag1=1; //结束for循环的辅助标志
tag2=1; //结束for循环的辅助标志
c=(char *)malloc(200*sizeof(char));
for(i=0;i<200&&tag1;i++)
{
c[i]=fgetc(fp); //将文件中的字符输出到数组中
c[i+1]='\0'; //加结束标志
for(j=1;(j<=jilu->tag)&&tag2;j++)
{
if(strcmp(hc[j],c)==0) //将编码与原文字符匹配
{
YW[s]=jilu->b[j].a; //匹配成功后将字符保存到数组YW中
tag1=0;
s++;
free(c); //释放临时字符存储空间
tag2=0;
}
}
}

}
YW[s]='\0';
}
void baocunyiwen() //将翻译的译文保存到文件textfile中
{
int i;
FILE *fp;
if((fp=fopen("textfile","wb"))==NULL)
{
printf("Cannot open file\n");
exit(0);
}
for(i=0;YW[i]!='\0';i++)
{
fputc(YW[i],fp); //将数组中的字符保存到文件中
putchar(YW[i]);
}
fclose(fp); //关闭文件
}
void duquyiwen() //从文件textfile中读取译文
{
char ch;
FILE *fp;
if((fp=fopen("textfile","rb"))==NULL) //以只读的方式打开文件
{
printf("cannot open file\n");
exit(0);
}
while(!feof(fp))
{
ch=fgetc(fp); //将文件中的字符赋给字符变量ch
printf("%c",ch); //输出字符
}
fclose(fp); //关闭文件
}
void duquyuanwen() //从文件yuanwen中读取原文
{
char ch;
FILE *fp;
if((fp=fopen("yuanwen","rb"))==NULL) //以只读的方式打开文件
{
printf("cannot open file\n");
exit(0);
}
while(!feof(fp))
{
ch=fgetc(fp); //将文件中的字符赋给字符变量ch
printf("%c",ch); //输出字符
}
fclose(fp); //关闭文件
}
void duqubianma() //从文件yiwen中读取原文
{
char ch;
FILE *fp;
if((fp=fopen("yiwen","rb"))==NULL)
{
printf("cannot open file\n");
exit(0);
}
while(!feof(fp))
{
ch=fgetc(fp); //将文件中的字符赋给字符变量ch
printf("%c",ch); //输出字符
}
fclose(fp); //关闭文件
}
void main()
{
int a,c,tep=1;
hn humtree; //定义用三叉链表方式实现的哈夫曼树
Hcode hc; //定义存放哈夫曼字符编码串的头指针的数组
jilunode ji; //定义存放字符种类数量的栈
jilunode *jilu;
jilu=&ji; //取指针
jilu->tag=0; //字符种类数标志初始化
while(tep)
{
printf(" (*^__^*) 哈夫曼编码系统欢迎您(*^__^*) \n");
printf("*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n");
printf(" 1——创立存贮原文件的文件\n");
printf(" 2——输入原文\n");
printf(" 3——对原文编码\n");
printf(" 4——对编码译码\n");
printf(" 5——输出原文\n");
printf(" 6——输出译码\n");
printf(" 7——输出译文\n");
printf(" 8——退出\n");
printf("注意: 如果您未创立原文件原文操作, 请不要进行后续项操作! \n");
printf("*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n");
printf("请输入服务选项( -8) :");
scanf("%d",&a);
getchar();
switch(a)
{
case 1:
jianliwenjian(); //建立存储字符的文件
printf("是否继续? ( .YES 2, NO ) : ");
scanf("%d",&c);
getchar();
if(c==1)tep=1;
else
tep=0;
system("cls");
break;
case 2:
system("cls");
luruyuanwen(); //将原文录入到文件中
printf("\n注意: 原文件将保存在名称为”yuanwen”的文件中! \n");
printf("是否继续? ( .YES 2, NO ) : ");
scanf("%d",&c);
getchar();