数据结构与算法专业课程设计格式要求.doc

《 数据结构和算法 》课程设计
（/第二学期第20周）

指导老师： 孙麒 郭奕亿

班级： 09计算机科学和技术1班
学号： E0968
姓名：倪建鹤

《数据结构和算法》课程设计任务书
《数据结构和算法》是计算机专业关键关键课程之一，在计算机专业学习过程中占有很关键地位。《数据结构和算法课程设计》就是要利用本课程和到现在为止相关课程中知识和技术来处理实际问题。尤其是面临非数值计算类型应用问题时，需要选择合适数据结构，设计出满足一定时间和空间限制有效算法。
本课程设计要求同学独立完成一个较为完整应用需求分析。并在设计和编写含有一定规模程序过程中，深化对《数据结构和算法》课程中基础概念、理论和方法了解；训练综合利用所学知识处理实际问题能力，强化面向对象程序设计理念；使自己程序设计和调试水平有一个显著提升。
赫夫曼编码/译码器
1. 问题描述
利用赫夫曼编码进行通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端经过一个编码系统对待传输数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编/译码系统。试为这么信息收发站编写一个赫夫曼码编/译码系统。
2. 基础要求
一个完整系统应含有以下功效：
(1) I：初始化（Initialization）。从终端读入字符集大小n，和n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。
(2) E：编码（Encoding）。利用已建好赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码（Decoding）。利用已建好赫夫曼树将文件CodeFile中代码进行译码，结果存入文件Textfile中。
以下为选做：
(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式编码文件写入文件CodePrin中。
(5) T：印赫夫曼树（Tree printing）。将已在内存中赫夫曼树以直观方法（比如树）显示在终端上，同时将此字符形式赫夫曼树写入文件TreePrint 中。
3. 测试要求
(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。
(2) 用下表给出字符集和频度实际统计数据建立赫夫曼树，并实现以下报文编码和译码：“THIS PROGRAME IS MY FAVORITE”。

字符

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

频度
57
63
15
1
48
51
80
23
8
18
1
16
1

4. 实现提醒
(1) 编码结果以文本方法存放在文件Codefile中。
(2) 用户界面能够设计为“菜单”方法：显示上述功效符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功效符。此功效实施完成后再显示此菜单，直至某次用户选择了“Q”为止。
(3) 在程序一次实施过程中，第一次实施I，D或C命令以后，赫夫曼树已经在内存了，无须再读入。每次实施中不一定实施I命令，因为文件hfmTree可能早已建好。
具体要求：
课程设计结果内容必需由以下四个部分组成，缺一不可。
(1) 上交源程序：学生根据试验题目标具体要求所开发全部源程序（应该放到一个文件夹中）；
(2) 上交程序说明文件：（保留在.txt中）在说明文档中应该写明上交程序所在目录，上交程序主程序文件名，假如需要安装，要有程序安装使用说明；
(3) 设计汇报：（保留在word 文档中，文件名要求： 根据“姓名_学号_设计题目”起名，如文件名为“ 张三_XXX_赫夫曼编码 ”.doc。打印稿用A4纸）。
其中包含:
¨ 题目；
¨ 试验目标；
¨ 需求分析：在该部分中叙述实现功效要求；
¨ 概要设计：
在此说明每个部分算法设计说明（能够是描述算法步骤图），每个程序中使用存放结构设计说明（假如指定存放结构请写出该存放结构定义）；
¨ 具体设计
各个算法实现源程序，对每个题目要有对应源程序（能够是一组源程序，每个功效模块采取不一样函数实现）。源程序要根据写程序规则来编写。要结构清楚，关键函数关键变量，关键功效部分要加上清楚程序注释；
¨ 调试分析
测试数据，测试输出结果，时间复杂度分析，和每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想；
¨ 总结：
总结能够包含 : 设计过程收获、碰到问题及处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在设计过程中对《数据结构》课程认识等内容。

三、工作内容及工作计划：一周（20）
时间
地点
工作内容
指导老师
7月 11日
早晨
10-414
试验要求，需求分析；
孙麒、郭奕亿
下午
10-414
查找资料，总体结构设计；
孙麒、郭奕亿
7月
12日
早晨
10-414
算法设计、用户界面设计
孙麒、郭奕亿
下午
10-414
算法设计、用户界面设计
孙麒、郭奕亿
7月
13日
早晨
10-414
具体设计
孙麒、郭奕亿
下午
10-414
具体设计
孙麒、郭奕亿
7月
14日
早晨
10-414
具体设计
孙麒、郭奕亿
下午
10-414
具体设计
孙麒、郭奕亿
7月
15日
早晨
10-414
上机检验、答辩
孙麒、郭奕亿
下午
10-414
上机检验、答辩
孙麒、郭奕亿

四、考评成绩评定标准：
本课程设计评价由三部分组成，包含程序演示（50%），课程设计汇报（30%），回复老师提问（20%）。

1．程序演示：
Ø 优 功效完善，全部测试正确，而且能够对局部进行完善。
Ø 良 功效完善，但测试欠缺。
Ø 中 功效基础完善，但程序还有部分错误。
Ø 及格 完成内存中赫夫曼编码/译码，但不包含文件操作。
Ø 不及格 功效不完善，且程序错误较多，无法运行。

2．课程设计汇报：
Ø 优 包含设计内容，设计思想，已经完成任务及达成目标，设计思绪清楚、书写条理清楚，源程序结构合理、清楚，注释说明完整，有对此次课程设计心得体会。
Ø 良 包含设计内容，设计思想，已经完成任务及达成目标，设计思绪基础清楚、书写条理基础清楚，源程序结构合理、清楚，注释说明基础完整，有对此次课程设计心得体会。
Ø 中 课程设计汇报内容基础完整，思绪较清楚，书写基础清楚，源程序结构尚可，有注释说明但不完整。
Ø 及格 课程设计汇报内容基础完整，思绪较差，书写尚清楚。
Ø 不及格 课程设计汇报内容不完整，书写没有条理。

3．回复老师提问：
Ø 优 能回复老师提出全部问题，并完全正确，思绪清楚
Ø 良 基础能回复老师提出全部问题，有些小错误
Ø 中 基础能回复老师提出问题，少数问题回复错误或不清楚
Ø 及格 能回复老师提出问题，但较多问题回复错误或不能回复
Ø 不及格 基础不能回复老师提出问题

《数据结构和算法》课程设计
目 录

一、 题目
二、 需求分析
三、 概要设计
四、 程序说明
五、 具体设计
六、 试验心得和体会

赫夫曼编\译码器
一、题目
问题描述
利用赫夫曼编码进行通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端经过一个编码系统对待传输数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编/译码系统。试为这么信息收发站编写一个赫夫曼码编/译码系统。
基础要求
一个完整系统应含有以下功效：
(1) I：初始化（Initialization）。从终端读入字符集大小n，和n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。
(2) E：编码（Encoding）。利用已建好赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码（Decoding）。利用已建好赫夫曼树将文件CodeFile中代码进行译码，结果存入文件Textfile中。
（以下为选做：）
(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式编码文件写入文件CodePrin中。
(5) T：印赫夫曼树（Tree printing）。将已在内存中赫夫曼树以直观方法（比如树）显示在终端上，同时将此字符形式赫夫曼树写入文件TreePrint 中。
测试要求
(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。
(2) 用下表给出字符集和频度实际统计数据建立赫夫曼树，并实现以下报文编码和译码：“THIS PROGRAME IS MY FAVORITE”。

字符

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

频度
57
63
15
1
48
51
80
23
8
18
1
16
1

二、需求分析
（1）初始化哈夫曼数
（2）输入字符保留至tobetran.txt中
（3）对字符编码
（4）编码结果以文本方法存放在文件Codefile中。
（5）在对codefile中编码进行译码
（6）打印编码和哈夫曼树
用户界面能够设计为“菜单”方法：显示上述功效符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功效符。此功效实施完成后再显示此菜单，直至某次用户选择了“Q”为止。
在程序一次实施过程中，第一次实施I，D或C命令以后，赫夫曼树已经在内存了，无须再读入。每次实施中不一定实施I命令，因为文件hfmTree可能早已建好。

三、概要设计
函数间关系图3.1所表示：

主函数
显示表头
初始化树
输入字符
编码
译码
打印编码
打印赫夫曼树
选最小两个权值
Select()

图3.1 函数间关系
数据结构和算法设计

赫夫曼编\译码器关键功效是先建立赫夫曼树，然后利用建好赫夫曼树生成赫夫曼编码后进行译码 。
在数据通信中，常常需要将传送文字转换成由二进制字符0、1组成二进制串，称之为编码。结构一棵赫夫曼树，要求赫夫曼树中左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过路径分支组成0和1序列便为该节点对应字符编码，称之为赫夫曼编码。
最简单二进制编码方法是等长编码。若采取不等长编码，让出现频率高字符含有较短编码，让出现频率低字符含有较长编码，这么可能缩短传送电文总长度。赫夫曼树课用于结构使电文编码总长最短编码方案。
其关键步骤图图3.2所表示。

开始
结点数是否大于1
将data和权值赋给ht
输出根结点和权值
调用SELECT函数
计算根结点函数
父结点为两子结点之和
输出两子结点和已结构结点
是否为根结点？
左子是否为空？
此时编码为0
I<2*N?
I++
编码为1
结束
否
否
否
右子是否为空
是
是
否
否
是
是
是

四、程序说明
1．赫夫曼树抽象数据类型定义
ADT HuffmanCoding{
数据对象T：含有相同特征数据元素集合
数据关系R：满足最优二叉树关系
基础操作P：
Init（&t）
操作结果：结构一个空赫夫曼树t。
encode()
操作结果：利用赫夫曼树进行编码
Decode（）
操作结果：利用赫夫曼树进行译码
}
2. 主函数
Void mian（）
{打印表头；
While(选择项不为q){
输入选择项；
Switch(选择项)
{
Case i： 初始化；break;
Case w： 输入要编码字符； break；
Case e： 编码字符； break；
Case d； 译码操作；break；
Case p； 打印代码；break；
Case t； 打印赫夫曼树； break；
Default：输入错误，重新选择；
}

五、具体设计
源程序：
#include <iomanip.h>
#include <malloc.h>
#include <stdio.h>
const int UINT_MAX=1000;
typedef struct
{
int weight; //权值
int parent,lchild,rchild; //父节点，左孩子结点，右孩子结点
}HTNode,* HuffmanTree;
typedef char **HuffmanCode;
//定义全局变量
HuffmanTree HT; //代表赫夫曼树
HuffmanCode HC; //代表赫夫曼编码
int *w,i,j,n;
char *z;
int flag=0;
int numb=0;

int min(HuffmanTree t,int i)
{//选出叶子结点
int j,flag;
int k=UINT_MAX; //取k为足够大值
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag; //返回标识符
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{//排序两个叶子结点
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2) // s1为最小两个值中序号小那个
{
j=s1;
s1=s2;
s2=j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{//w存放n个字符权值（均>0），结构哈夫曼树HT并求出n个字符哈夫曼编码HC
int m,i,s1,s2,start;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1; //结点数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=0;
for(i=n+1;i<=m;++i) // 建赫夫曼树
{
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}

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]); //复制cd到HC
}
free(cd);
}

void InitHuffman()
{ //初始化赫夫曼链表
flag=1;
int num;
int num2;
cout<<"赫夫曼链表初始化"<<endl<<"结点个数n= ";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));//分配权值空间
z=(char*)malloc(n*sizeof(char));//分配字符空间
cout<<"\n请依次输入"<<n<<"个字符"<<endl;
char temp[2];
for(i=0;i<n;i++)
{//输入字符
cout<<"字符"<<i+1<<":"<<endl;
gets(temp);
*(z+i)=*temp;
}

cout<<"\n请依次输入"<<n<<"个字符权"<<endl;
for(i=0;i<=n-1;i++)
{//输入权
cout<<endl<<i+1<<":";
cin>>num2;
*(w+i)=num2;
}
//输入部分结束 编码
HuffmanCoding(HT,HC,w,n);
cout<<"字符对应编码为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"字符"<<*(z+i-1)<<"编码为：";
puts(HC[i]); //输出编码
}
//将赫夫曼编码写入文件
cout<<"赫夫曼编码写入文件htmTree.txt中"<<endl;
FILE *htmTree;
char r[]={' ','\0'};
if((htmTree=fopen("htmTree.txt","w"))==NULL)
{
cout<<"文件打开失败"<<endl;
return;
}

fputs(z,htmTree); //文件中输入z字符串
cout<<endl;//不加这个代码文件输入有误
fputc('\n',htmTree);//换行

for(i=0;i<n;i++)
{//文件中输入权
fprintf(htmTree,"%d ",*(w+i));
fputs(r,htmTree);

}
fprintf(htmTree,"\n");//换行
for(i=1;i<=n;i++)
{//文件中输入编码
fputs(HC[i],htmTree);
fputs(r,htmTree);
}
fclose(htmTree);
}//init
//获取字符并写入文件创建待编码文件
void inputcode()
{
FILE *virttran,*tobetran;
char str;
if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
cout<<"请输入你想要编码字符并以#号结束"<<endl;
str=getchar();// 用来初始化
str=getchar();//此语句用来接收输入第一个字符
while(str!='#')
{
fputc(str,tobetran);
str=getchar();
}
cout<<"写入成功！"<<endl;
fclose(tobetran);
}

void encode()
{//完成编码功效
cout<<"下面对目录下文件tobetran.txt中字符进行编码"<<endl;
FILE *tobetran,*codefile;
if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char)); //为tran分配100个字节
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打开文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{//对tobetran文件中字符经过初始化哈夫曼编码进行编码
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
puts(HC[j]);
if(j>n)
{
cout<<"字符错误，无法编码!"<<endl;
break;
}
}
}
}
}
cout<<"完成！"<<endl<<"编码已写入codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}

void decode()
{//完成译码功效

cout<<"下面对根目录下文件codefile.txt中字符进行译码"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("Textfile.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *tbdc,*outext,i2;
int io=0,i,m;
unsigned long length=10000;
tbdc=(char*)malloc(length*sizeof(char)); //分配空间
fgets(tbdc,length,codef); //codefile中提取编码
outext=(char*)malloc(length*sizeof(char)); //分配空间

m=2*n-1;
for(i=0;*(tbdc+i)!='\0';i++) //进入循环依次译码
{
i2=*(tbdc+i);
if(HT[m].lchild==0)
{
*(outext+io)=*(z+m-1);
io++;
m=2*n-1;
i--;
}
else if(i2=='0') m=HT[m].lchild;
else if(i2=='1') m=HT[m].rchild;
}
*(outext+io)=*(z+m-1);
*(outext+io+1)='\0';
fputs(outext,txtfile);//译码完成将译码放入文件
cout<<"完成！"<<endl<<"结果已写入txtfile.txt中"<<endl<<endl;
free(tbdc);
free(outext);
fclose(txtfile);
fclose(codef);
}

void printcode() //打印代码
{
cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl<<"-----------------------------------------------------------------\n";
FILE * CodePrin,* codefile;
if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *work3;
work3=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work3,51,codefile)==NULL)
{
cout<<"不能读取文件"<<endl;
break;
}
fputs(work3,CodePrin);//放入
puts(work3);
}while(strlen(work3)==50);
free(work3);

cout<<"打印完成！"<<endl<<endl;
fclose(CodePrin);
fclose(codefile);
}
//打印赫夫曼树函数
void coprint(HuffmanTree start,HuffmanTree HT)
{char t=' ';

if(start!=HT)
{
FILE * TreePrint;
if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
{
cout<<"创建文件失败"<<endl;
return;
}
numb++;//该变量为已被申明为全局变量
coprint(HT+start->rchild,HT);
if(start->lchild&&start->rchild) t='<';
cout<<setw(5*numb)<<start->weight<<t<<endl;
fprintf(TreePrint,"%d\n",start->weight);
coprint(HT+start->lchild,HT);
numb--;
fclose(TreePrint);
}
}
void printree(HuffmanTree HT,int w) //打印赫夫曼树
{
HuffmanTree p;
p=HT+w;
cout<<"打印赫夫曼树"<<endl; // 输出"打印赫夫曼树"语句
coprint(p,HT);
cout<<"打印完成！"<<endl; //输出"打印工作结束"
}
void printhead()
{ cout<<"\n\t\t";
cout<<" 　　欢迎使用赫夫曼编码解码系统 　　　 \n\t\t";
cout<<"============================================\n\t\t";
cout<<" 　　 i.初始化赫夫曼链表 \n\t\t";
cout<<" 　 w.输入字符保留在对应文件中 　　\n\t\t";
cout<<" 　　 e.编 码 　 　 　　 \n\t\t";
cout<<" 　　 d.译 码　 　 　　 \n\t\t";
cout<<" 　　 p.打印编码 　 　　 　 \n\t\t";
cout<<" 　　 t.打印赫夫曼树　 \n\t\t";
cout<<" 　　 q.退 出 　 　　　 \n\t\t";
cout<<endl;
if(flag==0)
{cout<<"链表还未初始化,输入'i'进行初始化\n\t\t"<<endl;}
cout<<"请选择:";
}
/*2．主程序*/
void main()
{
char choice;
while(choice!='q')
{ printhead();

cin>>choice;
switch(choice)
{
case 'i':