数据结构专业课程设计哈夫曼编码.doc

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

指导老师： 王老师

班级：计算机科学和技术（3）班
学号：
姓名：

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

一、 序言
1． 摘要
2． 《数据结构和算法》课程设计任务书
二、试验目标
三、题目--赫夫曼编码/译码器
1． 问题描述
2． 基础要求
3． 测试要求
4． 实现提醒
四、 需求分析--具体要求
五、 概要设计
六、 程序说明
七、 具体设计
八、 试验心得和体会

序言
1． 摘要
伴随计算机普遍应用和日益发展，其应用早已不局限于简单数值运算，而包含到问题分析、数据结构框架设计和设计最短路线等复杂非数值处理和操作。算法和数据结构学习就是为以后利用计算机资源高效地开发非数值处理计算机程序打下坚实理论、方法和技术基础。
算法和数据结构意在分析研究计算机加工数据对象特征，方便选择合适数据结构和存放结构，从而使建立在其上处理问题算法达成最优。
数据结构是在整个计算机科学和技术领域上广泛被使用术语。它用来反应一个数据内部组成，即一个数据由那些成份数据组成，以什么方法组成，呈什么结构。数据结构有逻辑上数据结构和物理上数据结构之分。逻辑上数据结构反应成份数据之间逻辑关系，而物理上数据结构反应成份数据在计算机内部存放安排。数据结构是数据存在形式。
《数据结构》关键介绍部分最常见数据结构，说明多种数据结构内在逻辑关系，讨论其在计算机中存放表示，和在其上进行多种运算时实现算法，并对算法效率进行简单分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间一门计算机专业关键课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等关键基础，广泛应用于信息学、系统工程等多种领域。
学习数据结构是为了将实际问题中所包含对象在计算机中表示出来并对它们进行处理。经过课程设计能够提升学生思维能力，促进学生综合应用能力和专业素质提升。

2． 《数据结构和算法》课程设计任务书
《数据结构和算法》是计算机专业关键关键课程之一，在计算机专业学习过程中占有很关键地位。《数据结构和算法课程设计》就是要利用本课程和到现在为止相关课程中知识和技术来处理实际问题。尤其是面临非数值计算类型应用问题时，需要选择合适数据结构，设计出满足一定时间和空间限制有效算法。
本课程设计要求同学独立完成一个较为完整应用需求分析。并在设计和编写含有一定规模程序过程中，深化对《数据结构和算法》课程中基础概念、理论和方法了解；训练综合利用所学知识处理实际问题能力，强化面向对象程序设计理念；使自己程序设计和调试水平有一个显著提升。

二、试验目标
数据结构作为一门学科关键研究数据多种逻辑结构和存放结构，和对数据多种操作。所以，关键有三个方面内容：数据逻辑结构；数据物理存放结构；对数据操作（或算法）。通常，算法设计取决于数据逻辑结构，算法实现取决于数据物理存放结构。数据结构是信息一个组织方法，其目标是为了提升算法效率，它通常和一组算法集合相对应，经过这组算法集合能够对数据结构中数据进行某种操作。
在当今信息时代，信息技术己成为现代知识经济关键技术。我们时刻全部在和数据打交道。比如大家在外出工作时找最短路径，在银行查询存款、经过互联网查新闻、和远程教育报名等，全部这些全部在和数据发生关系。实际上，现实世界中实体经过抽象以后，就能够成为计算机上所处理数据。
数据结构课程关键是研究非数值计算程序设计问题中所出现计算机操作对象和它们之间关系和操作学科。数据结构是介于数学、计算机软件和计算机硬件之间一门计算机专业关键课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等关键基础，广泛应用于信息学、系统工程等多种领域。
学习数据结构是为了将实际问题中所包含对象在计算机中表示出来并对它们进行处理。经过课程设计能够提升学生思维能力，促进学生综合应用能力和专业素质提升。经过此次课程设计关键达成以下目标：
¨ 了解并掌握数据结构和算法设计方法，含有初步独立分析和设计能力；
¨ 初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基础方法和技能；
¨ 提升综合利用所学理论知识和方法独立分析和处理问题能力；
¨ 训练用系统见解和软件开发通常规范进行软件开发，培养软件工作者所应含有科学工作方法和作风。

三、题目--赫夫曼编码/译码器
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纸）。
其中包含:
¨ 题目；
¨ 试验目标；
¨ 需求分析：在该部分中叙述实现功效要求；
¨ 概要设计：
在此说明每个部分算法设计说明（能够是描述算法步骤图），每个程序中使用存放结构设计说明（假如指定存放结构请写出该存放结构定义）；
¨ 具体设计
各个算法实现源程序，对每个题目要有对应源程序（能够是一组源程序，每个功效模块采取不一样函数实现）。源程序要根据写程序规则来编写。要结构清楚，关键函数关键变量、关键功效部分要加上清楚程序注释；
¨ 调试分析
测试数据，测试输出结果，时间复杂度分析，和每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想；

¨ 总结：
总结能够包含 : 设计过程收获、碰到问题及处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在设计过程中对《数据结构》课程认识等内容。

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

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

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

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

四、 概要设计
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为02个节点

2、 int main()
主函数： 利用已建好哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）
对文件中正文进行编码，然后将结果存入文件codefile.txt中。假如正文中没有要编码字符，则键盘读入并存放到ToBeTran文件中。读入ToBeTran中将要编码内容，将编码好哈夫曼编码存放到CodeFile中。
3、Encoding
编码功效：对输入字符进行编码
4、Decoding
译码功效： 利用已建好哈夫曼树将文件codefile.txt中代码进行译码，结果存入文件textfile.dat 中。
Print() 打印功效函数：输出哈夫曼树，字符，权值，和它对应编码。
5.主函数简明说明，主函数关键设计是一个分支语句，让用户挑选所实现功效。
使用链树存放，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功效。
2) 系统结构图（功效模块图）

五． 程序说明
1） .哈夫曼编码/译码器源代码
#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为02个节点
{
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<<" "<<"计算机（3）班"<<" "<<"Q07620307"<<" "<<"XXX\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 oen 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("ToBeTran.txt");
if(!output_file)
{
cout<<"can't oen file!"<<endl;
return 1;
}
output_file<<str<<endl;
output_file.close();
output_file.open("CodeFile.txt");
if(!output_file){
cout<<"can't oen 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 oen 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 oen file!"<<endl;
return 1;
}
input_file>>h;
input_file.close();
output_file.open("Textfile.txt");
if(!output_file)
{
cout<<"can't oen 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 oen 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;
}

六． 调试分析

编码

、译码

、退出

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

经过此次数据结构课程设计，我学习了很多在上课没懂知识，并对求哈夫曼树及哈夫曼编码/译码算法有了愈加深刻了解，更巩固了课堂中学习有相关哈夫曼编码知识，真正学会一个算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大约了解，接着再具体地分析每一步怎么做，不管自己以前是否有处理过相同问题，只要根据以上步骤，肯定会顺利地做出来。
这次课程设计，我在编辑中犯了不应有错误，设计统计字符和合并时忘记应该怎样保留数据，对文件操作也很生疏。在不停分析后明确并更正了错误和疏漏，我程序有了更高质量。

考评成绩评定表
指导老师考评成绩

答辩成绩

总成绩

签字：
年 月 日