哈夫曼编码译码器课程设计报告中英文界面样本.doc

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

数据结构 课程设计报告

课 题: 哈夫曼编码译码器
专业班级: 信 息 06102班
学 号: 16020208
姓 名: 李 宇 光
指导教师: 屠 添 翼
评阅意见:

评定成绩:

指导老师签名:

年 月 日

目 录

目 录

目录 1
1 课程设计的目的和意义 2
2 需求分析 3
3 系统( 项目) 设计 5
①设计思路及方案………………………………………………5
②模块的设计及介绍……………………………………………5
③主要模块程序流程图…………………………………………8
4 系统实现 11
①主调函数…………..…………………………..……………..12
②建立HuffmanTree……………………………………………12
③生成Huffman编码并写入文件……………………………..15
④电文译码……………………………………………………..16
5 系统调试 17
参考文献 20
附录 源程序 21

1 课程设计的目的和意义
在当今信息爆炸时代, 如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
哈夫曼编码的应用很广泛, 利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径, 对路径上的各分支约定: 指向左子树的分支表示”0”码, 指向右子树的分支表示”1”码, 取每条路径上的”0”或”1”的序列作为和各个对应的字符的编码, 这就是哈夫曼编码。
一般我们把数据压缩的过程称为编码, 解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时, 总希望总长度尽可能最短, 即采用最短码。
作为信息管理专业的学生, 我们应该很好的掌握这门技术。在课堂上, 我们能过学到许多的理论知识, 但我们很少有过自己动手实践的机会! 课程设计就是为解决这个问题提供了一个平台。
在课程设计过程中, 我们每个人选择一个课题, 认真研究, 根据课堂讲授内容, 借助书本, 自己动手实践。这样不但有助于我们消化课堂所讲解的内容, 还能够增强我们的独立思考能力和动手能力; 经过编写实验代码和调试运行, 我们能够逐步积累调试C程序的经验并逐渐培养我们的编程能力、 用计算机解决实际问题的能力。
在课程设计过程中, 我们不但有自己的独立思考, 还借助各种参考文献来帮助我们完成系统。更为重要的是, 我们同学之间加强了交流, 在对问题的认识方面能够交换不同的意见。同时, 师生之间的互动也随之改进, 我们能够经过具体的实例来从老师那学到更多的实用的知识。
数据结构课程具有比较强的理论性, 同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节, 可是容易忽略实验的总结, 忽略实验报告的撰写。经过这次实验让我们明白: 作为一名大学生必须严格训练分析总结能力、 书面表示能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样, 我们的综合素质才会有好的提高。
2 需求分析
课 题: 哈夫曼编码译码器系统
问题描述: 打开一篇英文文章, 统计该文章中每个字符出现的次数, 然后以它们作为权值, 对每一个字符进行编码, 编码完成后再对其编码进行译码。
问题补充: 1. 从硬盘的一个文件里读出一段英语文章;
2. 统计这篇文章中的每个字符出现的次数;
3. 以字符出现字数作为权值, 构建哈夫曼树, 并将哈夫曼树的存储结构的初态和终态进行输出;
4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。
具体介绍: 在本课题中, 我们在硬盘E盘中预先建立一个file1.txt文档, 在里面编辑一篇文章(大写)。然后运行程序, 调用fileopen()函数读出该文章, 显示在界面; 再调用jsq()函数对该文章的字符种类进行统计, 并对每个字符的出现次数进行统计, 而且在界面上显示; 然后以每个字符出现次数作为权值, 调用ChuffmanTree()函数构建哈夫曼树; 并调用print1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出。然后调用HuffmanEncoding()函数对哈夫曼树进行编码, 调用coding()函数将编码写入文件; 再调用decode()对编码进行译码, 再输出至界面。至此, 整个工作就完成了。
测试数据: 例如从文本中读到文章为: IAMASTUDENT。
则效果如下:
IAMASTUDENT
--------------------------------------
HuffmanTree的初态:
2 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
2 0 0 0
1 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
--------------------------------------
字符A次数:2
字符D次数:1
字符E次数:1
字符I 次数:1
字符M次数:1
字符N 次数:1
字符S 次数:1
字符T次数:2
字符U次数:1
--------------------------------------
HuffmanTree的终态:
2 13 0 0
1 10 0 0
1 10 0 0
1 11 0 0
1 11 0 0
1 12 0 0
1 12 0 0
2 14 0 0
1 13 0 0
2 14 2 3
2 15 4 5
2 15 6 7
3 16 9 1
4 16 8 10
4 17 11 12
7 17 13 14
11 0 15 16
--------------------------------------
译码后的字符串:
IAMASTUDENT
**********************************************************
Press any key to continue

3 系统( 项目) 设计
(1)设计思路及方案
本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi, 编码长度为Li, 电文中有n种字符, 则电文编码总长度为(W1*L1)+(W2*L2)+…+(Wi*Li)。若将此对应到二叉树上, Wi为叶结点, Li为根结点到叶结点的路径长度。那么, (W1*L1)+(W2*L2)+…+(Wi*Li)恰好为二叉树上带权路径长度。
因此, 设计电文总长最短的二进制前缀编码, 就是以n种字符出现的频率作权, 构造一棵哈夫曼树, 此构造过程称为哈夫曼编码。
该系统将实现以下几大功能: 从硬盘读取字符串, 建立哈夫曼树, 输出哈夫曼树的存储结构的初态和终态, 输出各种字符出现的次数以及哈夫曼编码的译码等。
(2)模块的设计及介绍
①从硬盘读取字符串
fileopen(参数)
{
实现命令;
打印输出;
}
②建立HuffmanTree
经过三个函数来实现:
void select(参数)
{
初始化;
for
{
接受命令;
处理命令;
}
}
说明: 在ht[1....k]中选择parent为0且权值最小的两个根结点的算法
int jsq(参数)
{
初始化;
for
{
接受命令;
处理命令;
}
}
说明: 统计字符串中各种字母的个数以及字符的种类
void ChuffmanTree()
{
初始化;
for
{
接受命令;
处理命令;
}
输出字符统计情况;
}
说明: 构造哈夫曼树
③输出哈夫曼树的存储结构的初态和终态
分别调用print1()和print2()来实现
void print1(参数)
{
初始化;
输出初态;
}
说明: 输出哈夫曼树的初态
void print2(参数)
{
for
{
输出终态;
}
}
说明: 输出哈夫曼树的终态
④哈夫曼编码和译码
void HuffmanEncoding(参数)
{
定义变量;
{
处理命令;
}
}
说明: 哈夫曼编码
char*decode(参数)
{
定义变量;
while
{
接受命令;
处理命令;
}
}
说明: 哈夫曼译码
(3)主要模块程序流程图
下面介绍三个主要的程序模块流程图:
①主函数流程图:
结束
统计字符种类及频率
字符总数num
建立哈夫曼树
哈夫曼编码
哈夫曼译码
打开文件?
开始
否
是

图3.1
流程图注释:
该图比较简单, 主要是调用各个函数模块, 首先代开已经存在的文件, 然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树, 接着在哈夫曼树的基础上对其进行编码, 编码之后才是译码。最后输出结束。

②构造哈夫曼树:
开始
结束
第i个结点权值
i=num?
创立哈夫曼树
输出字符统计情况
第i个根结点
i=2*num-1?
i=num?

否
是
否
是
否
是

图3.2
流程图注释:
该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值, 当i=num是循环结束。然后进行哈夫曼树的构建, 当i=2*num-1是循环结束。最后输出所得到的字符统计情况。

③哈夫曼编码:
结束
开始
T[p].lchlid=c?
i<=num?
Cd[--start]=0,start=num
Cd[--start]=0
Cd[--start]=1
否
否
是
是

图3.3
流程图解释:
该流程图表四哈夫曼编码情况。首先初始化, Cd[--start]=0,start=num。然后进行
编码, 使用了一个三目运算符。cd[--start]=(T[p].lchild==c) ? '0' : '1', 即当cd[--start]=T[p].lchild= =c时, cd[--start]=0; 当cd[--start]=T[p].lchild! = =c时, cd[--start]=1。这个编码循环一直到i=num时结束。

4 系统实现
各模块关键代码及算法的解释:
① 主调函数
代码解释: 这是main函数里的各个函数调用情况。
fileopen(string); //从硬盘中读取文件
num=jsq(string,cnt,str); //统计字符种类及各类字符出现的频率
DhuffmanTree(HT,cnt,str);
printf("HuffmanTree的初态:\n");
print1(HT); //输出哈夫曼树的初态
ChuffmanTree(HT,HC,cnt,str);//建立哈夫曼树
HuffmanEncoding(HT,HC); //生成哈夫曼编码
printf("HuffmanTree的终态:\n");
print2(HT); //输出哈夫曼树的终态
s=decode(HC); //读编码文件译码　
printf("译码后的字符串:\n");
printf("%s\n",s); //输出译码后的字符串
② 建立HuffmanTree
代码解释: 该函数为在ht[1....k]中选择parent为0且权值最小的两个根结点的算法, 其序号为s1和s2。
void select(HuffmanTree T,int k,int &s1,int &s2)
{
int i,j;
int min1=101;
for(i=1;i<=k;i++)
if(T[i].weight<min1 &&T[i].parent==0)
{
j=i;min1=T[i].weight;
}
s1=j;min1=32767;
for (i=1;i<=k;i++)
if(T[i].weight<min1 && T[i].parent==0 && i!=s1)
{
j=i;min1=T[i].weight;
}
s2=j;
}
代码解释: 下面函数用来统计字符串中各种字母的个数以及字符的种类。当字符在A和Z之间时即被计数, 并用str[j]保存字母到数组中, 用cnt[j]统计每种字符个数。j返回总共读取的字符数目。
int jsq(char *s,int cnt[],char str[])
{
int i,j,k;
char *p;
int temp[27];
for(i=1;i<=26;i++)
temp[i]=0;
for(p=s; *p!='\0';p++)
{
{　
if(*p>='A'&&*p<='Z')
k=*p-64;
temp[k]++;
}
} //统计各种字符的个数
for(i=1,j=0;i<=26;++i)
if(temp[i]!=0 )
{
j++;
str[j]=i+64; //送对应的字母到数组中
cnt[j]=temp[i]; //存入对应字母的权值
}
return j; //j是输入字母总数
}
代码解释: 下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树, 然后输入前面统计的各结点的权值, 用for循环来构造哈夫曼树。
void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])
{
int i,s1,s2;
for(i=1;i<=2*num-1;i++)//初始化HT, 2*num-1是指哈夫曼
//所有的结点数目
{
HT[i].lchild=0;HT[i].rchild=0;
HT[i].parent=0;HT[i].weight=0;
}
for(i=1;i<=num;i++) //输入num个叶结点的权值
HT[i].weight=cnt[i];
for(i=num+1;i<=2*num-1;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//在ht[1....k]中选择parent为0且权值最小
//的两个根结点,其序号为s1和s2,i为双亲
for(i=0;i<=num;i++) //输入字符集的中字符
HC[i].ch=str[i]; //字符的种类
i=1;while(i<=num)
printf("字符%c次数:%d\n",HC[i].ch,cnt[i++]);
} //输出统计的情况
③ 生成Huffman编码并写入文件
代码解释: 根据哈夫曼树T求哈夫曼编码H。
void HuffmanEncoding(HuffmanTree T,HuffmanCode H)
{
int c,p,i; //c和p分别指示t中孩子和双亲
char cd[n]; //临时存放编码串
int start; //指示码在cd中的起始位置
cd[num]='\0'; //最后一位( 第num个) 放上串结束符
for(i=1;i<=num;++i)
{
start=num; //初始位置
c=i; //从叶子结点t[i]开始上溯
while((p=T[c].parent)>0) //直至上溯到t[c]是树根为止
{
cd[--start]=(T[p].lchild==c) ? '0' : '1';
c=p;
} //若t[c]是t[p]的左孩子
//则生成0;否则生成底码１
strcpy(H[i].bits,&cd[start]);
H[i].len=num-start;
}
}
代码解释: 对str所代表的字符串进行编码并写入文件。将翻译的二进制码写入文本文件。
void coding(HuffmanCode HC ,char *str)
{
int i,j;
FILE *fp;
fp=fopen("codefile.txt","w");
while(*str)
{
for(i=1;i<=num;i++)
if(HC[i]. ch==*str){
for(j=0;j<=HC[i].len;j++)
fputc(HC[i].bits[j],fp);
break;
}
str++;
}fclose(fp);
}
④ 电文译码
代码解释: 代码文件codefile.txt的译码, 将翻译的二进制码译成原来的字符。
char*decode(HuffmanCode HC)
{ FILE *fp;
char str[254]; //假设远文本文件不超过254个字符
char *p;
static char cd[n+1];
int i,j,k=0,cjs;
fp=fopen("codefile.txt","r");//一只读的方式打开文本文档//codefile.txt
while(!feof(fp)) //feof(fp)判断文件是否真正结束,
//feof(fp)=1时文件结束
{
cjs=0;
for(i=0;i<num && cjs==0 && !feof(fp);i++)
{
cd[i]=' ';
cd[i+1]='\0';
cd[i]=fgetc(fp); //数组接受从fp指针所指向文件中读
//入的一个字符
for(j=1;j<=num;j++)
if(strcmp(HC[j].bits,cd)==0)
{
str[k]=HC[j].ch;
k++;
cjs=1;break;
} //haffman编码和密码译码相比较
}
}
str[k]='\0';
p=str;
return p;
}
5 系统调试
本次测试是在我的电脑的E盘中建立一个名为file1.txt的文本文档, 其中有大写字母IAMASTUDENT, 期望程序能将其读出至界面并实现其它相关的功能。
运行程序后, 我们能够见到一下的运行界面。
① 从硬盘中读出已有的文本文件(见图5.1):

图5.1

② 输出哈夫曼树存储结构的初态(见图5.2):

图5.2

③ 输出所读字符的种类和每种字符的个数(见图5.3):

图5.3

④ 输出哈夫曼树存储结构的终态(见图5.4):

图5.4

⑤ 输出译码后的字符(见图5.5)

图5.5

由此可见, 此次测试很成功。我们能够将文本文档file1.txt中的文段读出, 并将其统计并输出字符种类和每种字符出现的频率。同时输出哈夫曼树存储结构的初态和终态。然后输出译码后的字符。

小 结
经过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解, 也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。
首先我谈谈我在设计期间我遇到的难点。开始的时候, 代码中有许多的错误, 特别是有一个”无法找到文件”的错误让我束手无策, 最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时, 由于对文件不是太熟悉, 只好翻开C语言书本仿照其模式编写, 但后来进入了死循环, 最后的解决方式是把main函数里的一个do…while循环去掉。在程序中, 我还另外加了一个功能----输出哈夫曼树的存储结构的初态和终态。这使得我更加的明白了哈夫曼到底是怎么存储信息的。
许多的错误让我明白了一个道理---细心是非常重要的。同时, 对于编程者而言, 思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要, 因为毕竟我们是新手, 对于某些问题很难弄清楚。而且, 某些错误对于我们来说有时候想半天都弄不来, 但老师几下下就搞好了, 这样就更加有效地节约了时间。
这次课程设计不但让我学得了一些编程知识, 还学会了系统的做一份课程设计报告, 学会了如何截图, 学会了如何更好的画流程图, 明白了做事情只有认真, 才能真正做得更好!
这段时间里, 可谓是酸甜苦辣都尝过。有时, 为了一个错误而焦头烂额; 有时, 编程熬夜到凌晨两点; 有时, 连吃饭都是匆匆了事; 但一旦程序运行成功, 总会让我兴奋不已。
经过这次课程设计, 我看清楚了自己的编程功底和动手能力还不如人意, 这主要是平时实践太少的缘故。我想, 在未来的暑假中, 我会努力尝试编写一些程序。虽然我们信息管理专业的学生, 但现在编程的能力太差了, 毕竟多精通一门技术总是好事。
在这个程序中, 还有许多地方值得完善。比如, 读出文本只能是大写的文档, 空格和小写不能识别, 更不用说是任意的ASCⅡ码字符了。由于时间问题, 暂时不能实现了。我想在暑假里好好研究这个问题。

参考文献
[1] 严蔚敏.数据结构(C语言版).清华大学出版社,
[2] 苏仕华.数据结构课程设计.机械工业出版社,
[3] 谭浩强.C语言程序设计教程.高等教育出版社,

附录 源程序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<fstream.h>
//*************************类型相关变量的定义******************************
#define n 100 //叶子结点数
#define m 2*n-1 //哈夫曼树中的结点树
typedef struct{
char ch;
char bits[9]; //存放编码位串
int len;
}CodeNode;
typedef CodeNode HuffmanCode[n+1];
typedef struct {
int weight; //权值
int lchild,rchild,parent; //左右孩子几双亲指针
}HTNode;
typedef HTNode HuffmanTree[m+1]; //0号单元不用
int num;
//**********************************建立HuffmanTree*************************
void select(HuffmanTree T,int k,int &s1,int &s2)
{ //在ht[1....k]中选择parent为0且权值最小的两个根结点的算法
//其序号为s1和s2
int i,j;int min1=101;
for(i=1;i<=k;i++)
if(T[i].weight<min1 &&T[i].parent==0)
{
j=i;min1=T[i].weight;
}
s1=j;min1=32767;
for (i=1;i<=k;i++)
if(T[i].weight<min1 && T[i].parent==0 && i!=s1)
{
j=i;min1=T[i].weight;
}
s2=j;
}
int jsq(char *s,int cnt[],char str[])
{ //统计字符串中各种字母的个数以及字符的种类
int i,j,k;
char *p;
int temp[27];
for(i=1;i<=26;i++)
temp[i]=0;
for(p=s; *p!='\0';p++)
{
{ //统计各种字符的个数 　
if(*p>='A'&&*p<='Z')
k=*p-64;
temp[k]++;
}
}
for(i=1,j=0;i<=26;++i)
if(temp[i]!=0 )
{
j++;
str[j]=i+64; //送对应的字母到数组中
cnt[j]=temp[i]; //存入对应字母的权值
}
return j; //j是输入字母总数
}
void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])
{ //构造哈夫曼树HT
int i,s1,s2;
for(i=1;i<=2*num-1;i++)//初始化HT, 2*num-1是指哈夫曼树所有的结点数目
{
HT[i].lchild=0;HT[i].rchild=0;
HT[i].parent=0;HT[i].weight=0;
}
for(i=1;i<=num;i++) //输入num个叶结点的权值
HT[i].weight=cnt[i];
for(i=num+1;i<=2*num-1;i++)
{ //在ht[1....k]中选择parent为0且权值最小的两个根结点
//其序号为s1和s2
//i为双亲
select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
for(i=0;i<=num;i++) //输入字符集的中字符
HC[i].ch=str[i]; //字符的种类
i=1;while(i<=num)
printf("字符%c次数:%d\n",HC[i].ch,cnt[i++]);
}
//*************************生成Huffman编码并写入文件************************
void HuffmanEncoding(HuffmanTree T,HuffmanCode H)
{ //根据哈夫曼树T求哈夫曼编码H
int c,p,i; //c和p分别指示t中孩子和双亲
char cd[n]; //临时存放编码串
int start; //指示码在cd中的起始位置
cd[num]='\0'; //最后一位( 第num个) 放上串结束符
for(i=1;i<=num;++i)
{
start=num; //初始位置
c=i; //从叶子结点t[i]开始上溯
while((p=T[c].parent)>0) //直至上溯到t[c]是树根为止
{ //若t[c]是t[p]的左孩子,则生成0;否则生成底码１
cd[--start]=(T[p].lchild==c) ? '0' : '1';
c=p;
}
strcpy(H[i].bits,&cd[start]);
H[i].len=num-start;
}
}
void coding(HuffmanCode HC ,char *str)
{ //对str所代表的字符串进行编码 并写入文件
int i,j;
FILE *fp;
fp=fopen("codefile.txt","w");
while(*str)
{
for(i=1;i<=num;i++)
if(HC[i]. ch==*str){
for(j=0;j<=HC[i].len;j++)
fputc(HC[i].bits[j],fp);
break;
}
str++;
}fclose(fp);
}
//*************************电文译码****************************************
char*decode(HuffmanCode HC)
{ //代码文件codefile.txt的译码
FILE *fp;
char str[254]; //假设远文本文件不超过254个字符
char *p;
static char cd[n+1];
int i,j,k=0,cjs;
fp=fopen("codefile.txt","r");//一只读的方式打开文本文档codefile.txt
while(!feof(fp))//feof(fp)判断文件是否真正结束, feof(fp)=1时文件结束
{
cjs=0;
for(i=0;i<num && cjs==0 && !feof(fp);i++)