哈夫曼树课程设计报告样本.doc

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

数据结构
课程设计报告

设计题目: 哈夫曼树应用

专 业 : 软件工程
班 级 : 软件
学 生 :
学 号 :
指导教师 : 罗作民 / 张翔
起止时间 : -07-04— -07-08

年 春季 学期

目 录
一．具体任务 …..2
1功能……………………………………………………………………………...2
2分步实施………………………………………………………………………...2.
3要求……………………………………………………………………………...2
二．哈夫曼编码 2
1问题描述 2
2.基本要求 3
3实现提示 3
三．设计流程图 4
1建立哈夫曼树…………………………………………………………………...4
2编码……………………………………………………………………………...5
3译码……………………………………………………………………………...6
4主程序…………………………………………………………………………...7
四．设计概要 8
1问题哈夫曼的定义..............................................................................................8..
2所实现的功能函数如下………………………………………………………..8
3功能模块………………………………………………………………………..8
五．源程序 9
六．调试分析 15
七．心得与体会 18
八．参考文献 18

一、 任务
题目: 哈夫曼树应用
1.功能:
1．从终端读入字符集大小n, 以及n个字符和n个权值, 建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式( 比如树) 显示在终端上;
2．利用已经建好的哈夫曼树( 如不在内存, 则从文件htmTree中读入) , 对文件ToBeTran中的正文进行
编码, 然后将结果存入文件CodeFile中, 并输出结果, 将文件CodeFile以紧凑格式先是在终端上, 每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码, 结果存入文件TextFile中, 并输出结果。

2.分步实施:
1） 初步完成总体设计, 搭好框架, 确定人机对话的界面, 确定函数个数;
2） 完成最低要求: 完成功能1;
3） 进一步要求: 完成功能2和3。有兴趣的同学能够自己扩充系统功能。
3.要求:
1) 界面友好, 函数功能要划分好
2) 总体设计应画一流程图
3) 程序要加必要的注释
4） 要提供程序测试方案
5） 程序一定要经得起测试, 宁可功能少一些, 也要能运行起来, 不能运行的程序是没有价值的。

二、 哈夫曼编码
1. 问题描述
利用赫夫曼编码进行通信能够大大提高信道利用率, 缩短信息传输时间, 降低传输成本。这要求在发送端经过一个编码系统对待传输数据预先编码, 在接收端将传来的数据进行译码( 复原) 。对于双工信道( 即能够双向传输信息的信道) , 每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
2. 基本要求
一个完整的系统应具有以下功能:
(1) I: 初始化( Initialization) 。从终端读入字符集大小n, 以及n个字符和n个权值, 建立赫夫曼树, 并将它存于文件hfmTree中。
(2) E: 编码( Encoding) 。利用已建好的赫夫曼树( 如不在内存, 则从文件hfmTree中读入) , 对文件ToBeTran中的正文进行编码, 然后将结果存入文件CodeFile中。
(3) D: 译码( Decoding) 。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码, 结果存入文件Textfile中。
3. 实现提示
(1) 编码结果以文本方式存储在文件Codefile中。
(2) 用户界面能够设计为”菜单”方式: 显示上述功能符号, 再加上”Q”, 表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单, 直至某次用户选择了”Q”为止。
(3) 在程序的一次执行过程中, 第一次执行I, D或C命令之后, 赫夫曼树已经在内存了, 不必再读入。每次执行中不一定执行I命令, 因为文件hfmTree可能早已建好。
三、 设计流程图
建立哈夫曼树:

开始
n,<=1
Renturn 0
m=2*n-1
i=1;i<=n;++i
While(getchar()=”/n”
输入字符与权值
HT[i].ch=z
HT[i].weight=w
HT[i].parent=0
HT[i].lchild=0
HT[i].rchild=0

编码:

开始
cd[start]=”1”

i=1;i<=n;++i
start=n-1
cd[start]=”0”
c=I;f=HT[i].parent; f!=0;f=HT[f].parent
HT[f].child==l
结束

译码:
开始
L=k

!output_file
!cout”cant open file”
Return 1
Cout”can’t open file”
Strcmp(H[i].hlchild==0
结束
i=1;i<n;i++

while(h[k]!=”0”)

j=0;j<strlen(h[i]);j++;l++

K=0

h[j]=”\0”
输出译码

主程序:
开始
main
建立哈夫曼树
choice==”I”||choice==”I”
结束
编码

return 0
choice==”E”||choice==”e”
choice==”D”||choice==”d”
choice==”Q”||choice==”q”
编码

四、 概要设计
1) 问题哈夫曼的定义:
1.哈夫曼树节点的数据类型定义为:
typedef struct{ //赫夫曼树的结构体
char ch;
int weight; //权值
int parent,lchild,rchild;
}htnode,*hfmtree;
2) 所实现的功能函数如下
1、 void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树, 处理InputHuffman(Huffman Hfm)函数得到的数据, 按照哈夫曼规则建立2叉树。此函数块调用了Select( ) 函数。
2、 void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数, 选出HT树到a为止, 权值最小且parent为0的2个节点
3、 int main()
主函数: 利用已建好的哈夫曼树( 如不在内存, 则从文件hfmtree.txt中读入)
对文件中的正文进行编码, 然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符, 则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容, 将编码好的哈夫曼编码存储到CodeFile中。
4、 Encoding
编码功能: 对输入字符进行编码
5、 Decoding
译码功能: 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码, 结果存入文件textfile.dat 中。
Print() 打印功能函数: 输出哈夫曼树, 字符, 权值, 以及它对应的编码。
6.主函数的简要说明, 主函数主要设计的是一个分支语句, 让用户挑选所实现的功能。
使用链树存储, 然后分别调用统计频数函数, 排序函数, 建立哈夫曼函数, 编码函数, 译码函数来实现功能。
3) 功能模块:
哈夫曼编码/译码器
初始化哈夫曼树
编码
译码
打印哈夫曼树
打印编码

五、 源程序
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
typedef struct{ //哈夫曼树的结构体
char ch;
int weight; //权值
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;

void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数, 选出HT树到a为止, 权值最小且parent为0的2个节点
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight<HT[x].weight&&HT[i].parent==0){
x=i; //选出最小的节点
}
}
for(j=1;j<=a;++j) {
if(HT[j].parent==0&&x!=j)
{
y=j;
break;
}
}
for(i=j+1;i<=a;++i)
{
if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)
{
y=i; //选出次小的节点
}
}
if(x>y){
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建哈夫曼树HT, 并求出n个字符的哈夫曼编码HC
{
int i,start,c,f,m,w;
int p1,p2;
char *cd,z;
if(n<=1){
return;
}
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i) //初始化n个叶子结点
{
printf("请输入第%d字符信息和权值: ",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
{
continue;
}
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='0';
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建立哈夫曼树
{
Select(HT,i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}

HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';

for(i=1;i<=n;++i) //给n个字符编码
{
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);
}

int main(){
char code[100],h[100],hl[100];
int n,i,j,k,l;
ifstream input_file; //文件输入输出流
ofstream output_file;
char choice,str[100];
hfmtree HT;
hfmcode HC;
cout<<"\n";
cout<<" "<<"软件092班"<<" "<<"姓名:张耀飞"<<" "<<"学号: \n" ;
while(choice!='Q'&&choice!='q') //当choice的值不为q且不为Q时循环
{
cout<<" "<<"*************************哈夫曼编码/译码器*************************\n";
cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";
cout<<"请输入您要操作的步骤: ";
cin>>choice;
if(choice=='I'||choice=='i') //初始化赫夫曼树
{
cout<<"请输入字符个数: ";
cin>>n;
hfmcoding(HT,HC,n);
for(i=1;i<=n;++i)
{
cout<<HT[i].ch<<":"<<HC[i]<<endl;
}
output_file.open("hfmTree.txt");
if(!output_file){
cout<<"can't open file!"<<endl;
return 1;
}
for(i=1;i<=n;i++)
{
output_file<<"("<<HT[i].ch<<HC[i]<<")";
}
output_file.close();
cout<<"哈夫曼树已经创立完毕, 而且已经放入hfmTree.txt文件中!"<<endl;
}
else if(choice=='E'||choice=='e') //进行编码, 并将字符放入ToBeTran.txt, 码值放入CodeFile.txt中
{
printf("请输入字符: ");
gets(str);
output_file.open("ToBeTree.txt");
if(!output_file)
{
cout<<"can't open file!"<<endl;
return 1;
}
output_file<<str<<endl;
output_file.close();
output_file.open("CodeFile.txt");
if(!output_file){
cout<<"can't open file!"<<endl;
return 1;
}
for(i=0;i<strlen(str);i++){
for(j=0;j<=n;++j)
{
if(HT[j].ch==str[i])
{
output_file<<HC[j];
break;
}
}
}
output_file.close();
cout<<"\n";
cout<<"编码完毕, 而且已经存入CodeFile.txt文件! \n";
input_file.open("CodeFile.txt"); //从CodeFile.txt中读入编码, 输出在终端
if(!input_file)
{
cout<<"can't open file!"<<endl;
return 1;
}
input_file>>code;
cout<<"编码码值为: "<<code<<endl;
input_file.close();
}
else if(choice=='D'||choice=='d') //读入CodeFile.txt中的编码进行译码, 将译出来的字符放入Textfile.txt中
{
input_file.open("CodeFile.txt");
if(!input_file){
cout<<"can't open file!"<<endl;
return 1;
}
input_file>>h;
input_file.close();
output_file.open("Textfile.txt");
if(!output_file)
{
cout<<"can't open file!"<<endl;
return 1;
}
k=0;
while(h[k]!='\0') //先用编码中的前几个和字符的编码相比较, 然后往后移
{
for(i=1;i<=n;i++){
l=k;
for(j=0;j<strlen(HC[i]);j++,l++){
hl[j]=h[l];
}
hl[j]='\0';
if(strcmp(HC[i],hl)==0)
{
output_file<<HT[i].ch;
k=k+strlen(HC[i]);
break;
}
}
}
output_file.close();
input_file.open("Textfile.txt");
if(!input_file){
cout<<"can't open file!"<<endl;
return 1;
}
input_file>>h;
cout<<h<<endl;
input_file.close();
cout<<"译码结束, 字符已经存入Textfile.txt文件中! "<<endl;
}
else if(choice=='Q'||choice=='q') //退出程序
{
exit(0);
}
else //如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤, 请重新输入! "<<endl;
}
cout<<endl;
}
return 0;
}
六、 调试分析

编码

译码

退出

七、 实验心得与体会

在我自己课程设计中, 就在编写好源代码后的调试中出现了不少的错误, 遇到了很多麻烦及困难, 我的调试及其中的错误和我最终找出错误, 修改为正确的能够执行的程序中, 经过分析, 我学到了:
在定义头文件时可多不可少, 即我们可多写些头文件, 肯定不会出错, 可是若没有定义所引用的相关头文件, 必定调试不经过;
在执行译码操作时, 不知什么原因, 总是不能把要编译的二进制数与编译成的字符用连接号连接起来, 而是按顺序直接放在一起, 视觉效果不是很好。还有就是, 很遗憾的是, 我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能, 这是我们设计的失败之处。

经过本次数据结构的课程设计, 我学习了很多在上课没懂的知识, 并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解, 更巩固了课堂中学习有关于哈夫曼编码的知识, 真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做, 而是首先要先对它有个大概的了解, 接着再详细地分析每一步怎么做, 无论自己以前是否有处理过相似的问题, 只要按照以上的步骤, 必定会顺利地做出来。
这次课程设计, 我在编辑中犯了不应有的错误, 设计统计字符和合并时忘记应该怎样保存数据, 对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏, 我的程序有了更高的质量。
八．参考文献:

[1 ] 　谭浩强. C 程序设计(第二版) [M] . 北京:清华大学出版社,1999. 161 - 163.
[2 ] 　谭浩强,张基温,唐永炎. C 语言程序设计教程(第二版) [M] . 北京:高等教育出版社,1998. 113 - 115.
[3 ] 　严蔚敏,吴伟民. 数据结构(C 语言版) [M] . 北京:清华大学出版社, . 55 - 58.
[4] 　李士峰,张谢华,孙清滇. ActiveX文档技术在《VB 程序设计》网络课件制作中的应用 [5 ] 　王　颖,王正洲. 汉诺塔问题迭代算法实现和分析[J ] . 合肥联合大学学报,1999 ,

考核成绩评定:

签字:
年 月 日