《算法与数据结构》实验指导书.docx
《《算法与数据结构》实验指导书.docx》由会员分享，可在线阅读，更多相关《《算法与数据结构》实验指导书.docx（15页珍藏版）》请在冰点文库上搜索。
《算法与数据结构》实验指导书
《算法与数据结构》实验指导书
（适用于计算机科学与技术）
目录
前言1
实验一、线性表基本操作的实现2
实验二、集合的并、交、差运算7
实验三、二叉树的基本操作的实现12
实验四、哈夫曼编/译码器16
前言
《算法与数据结构》是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。
本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。
《算法与数据结构》是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。
实验一线性表基本操作的实现
姓名_________座号________级本科______________专业________班
日期:
【实验课程名称】算法与数据结构
【实验项目名称】线性表基本操作的实现
【实验目的】
1掌握线性表顺序存储基本操作；
2掌握线性表链式存储基本操作；
3学会设计实验数据验证程序。
【实验仪器及环境】计算机，windowxp操作系统，VC++6.0
【实验内容及步骤】
1．线性表顺序存储基本操作
存储结构定义：
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间的分配增量
typedefstruct{
ElemType*elem;//存储空间基址
intlength；//当前长度
intlistsize;//当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList；
实现的基本操作：
InitList（&L）
操作结果：
构造一个空的线性表L。
DestroyList（&L）
初始条件：
线性表L已存在。
操作结果：
销毁线性表L。
ListEmpty（L）
初始条件：
线性表L已存在。
操作结果：
若L为空表，则返回TRUE，否则返回FALSE。
ListLength（L）
初始条件：
线性表L已存在。
操作结果：
返回L中元素个数。
PriorElem（L,cur_e,&pre_e）
初始条件：
线性表L已存在。
操作结果：
若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem（L,cur_e,&next_e）
初始条件：
线性表L已存在。
操作结果：
若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义。
GetElem（L,i,&e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）。
操作结果：
用e返回L中第i个元素的值。
LocateElem（L,e,compare（））
初始条件：
线性表L已存在，compare（）是元素判定函数。
操作结果：
返回L中第1个与e满足关系compare（）的元素的位序。
若这样的元素不存在，则返回值为0。
ListTraverse（L,visit（））
初始条件：
线性表L已存在，visit（）为元素的访问函数。
操作结果：
依次对L的每个元素调用函数visit（）。
一旦visit（）失败，则操作失败。
ClearList（&L）
初始条件：
线性表L已存在。
操作结果：
将L重置为空表。
PutElem（&L,i,&e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）。
操作结果：
L中第i个元素赋值同e的值。
ListInsert（&L,i,e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）+1。
操作结果：
在L的第i个元素之前插入新的元素e，L的长度增1。
ListDelete（&L,i,&e）
初始条件：
线性表L已存在且非空，1≤i≤LengthList（L）。
操作结果：
删除L的第i个元素，并用e返回其值，L的长度减1。
2．线性表链式存储基本操作
存储结构定义：
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
实现的基本操作：
InitList（&L）
操作结果：
构造一个空的线性表L。
DestroyList（&L）
初始条件：
线性表L已存在。
操作结果：
销毁线性表L。
ListEmpty（L）
初始条件：
线性表L已存在。
操作结果：
若L为空表，则返回TRUE，否则返回FALSE。
ListLength（L）
初始条件：
线性表L已存在。
操作结果：
返回L中元素个数。
PriorElem（L,cur_e,&pre_e）
初始条件：
线性表L已存在。
操作结果：
若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem（L,cur_e,&next_e）
初始条件：
线性表L已存在。
操作结果：
若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义。
GetElem（L,i,&e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）。
操作结果：
用e返回L中第i个元素的值。
LocateElem（L,e,compare（））
初始条件：
线性表L已存在，compare（）是元素判定函数。
操作结果：
返回L中第1个与e满足关系compare（）的元素的位序。
若这样的元素不存在，则返回值为0。
ListTraverse（L,visit（））
初始条件：
线性表L已存在，visit（）为元素的访问函数。
操作结果：
依次对L的每个元素调用函数visit（）。
一旦visit（）失败，则操作失败。
ClearList（&L）
初始条件：
线性表L已存在。
操作结果：
将L重置为空表。
PutElem（&L,i,&e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）。
操作结果：
L中第i个元素赋值同e的值。
ListInsert（&L,i,e）
初始条件：
线性表L已存在，1≤i≤LengthList（L）+1。
操作结果：
在L的第i个元素之前插入新的元素e，L的长度增1。
ListDelete（&L,i,&e）
初始条件：
线性表L已存在且非空，1≤i≤LengthList（L）。
操作结果：
删除L的第i个元素，并用e返回其值，L的长度减1。
【测试数据及实验结果】
（自己设计测试数据验证算法的正确性）
【实验小结】
1.线性表的顺序存储和链式存储各有何优缺点？
2.各举一两个例子说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好。
【源代码说明】
1．文件名：
2．操作说明：
实验二集合的并、交和差运算
姓名_________座号________级本科______________专业________班
日期:
【实验课程名称】算法与数据结构
【实验项目名称】集合的并、交和差运算
【实验目的】
1掌握有序链表的基本操作；
2掌握集合的基本操作；
3学会采用抽象数据分层设计程序。
【实验仪器及环境】计算机，windowxp操作系统，VC++6.0
【实验内容及步骤】
（1）本演示程序中，集合的元素限定为小写字母字符[‘a’.’z’],集合的大小n<27.集合输入的形式为一个以“回车符”为结束标志的字符串顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。
输出的运算结果字符串中将不含重复字符或非法字符。
（2）演示程序以用户和计算机的对话形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
（3）程序执行的命令包括：
1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）结束。
“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。
为实现上述程序功能，应以有序链表表示集合。
为次，需要两个抽象数据类型：
有序表和集合。
1有序链表的基本操作
存储结构定义：
typedefstruct{
LinkTypehead,tail;//分别指向线形表的头结点和尾结点
Intsize;//指示链表当前的长度
}OrderedList;
实现的基本操作：
InitList（&L）
操作结果：
构造一个空的的有序表L。
DestroyList（&L）
初试条件：
有序表L已存在。
操作结果：
销毁有序表L。
ListLength（L）
初试条件：
有序表L已存在。
结果操作：
返回有序表L的长度。
ListEmpty（L）
初试条件：
有序表L已存在。
结果操作：
若有序L为空表，则返回True,否则返回False,
GetElem（L,pos）
初试条件：
有序表L已存在。
结果操作：
1≤pos≤Length（L）,则返回表中第pos个数据元素
LocateElem（L,e，&q）
初试条件：
有序表L已存在。
结果操作：
若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回函数值FALSE
Append（&L,e）
初试条件：
有序表L已存在。
结果操作：
在有序表L的末尾插入元素e
InsertAfter（&L,q,e）
初试条件：
有序表L已存在，q指示L中一个元素
结果操作：
在有序表L中q指示的元素之后插入元素e
ListTraverse（q,visit（））
初试条件：
有序表L已存在，q指示L中一个元素
结果操作：
依次对L中q指示的元素开始的每个元素调用函数visit（）
2集合的基本操作
存储结构定义：
typedefOrderedListOrderedSet;
实现的基本操作：
CreateSet（&T,Str）
初始条件：
Str为字符串
操作结果：
生成一个由Str中小写字母构成的集合T
DestroySet（&T）
初始条件：
集合T已存在
操作结果：
销毁集合T的结构
Union（&T,S1,S2）
初始条件：
集合S1和S2存在
操作结果：
生成一个由S1和S2的并集构成的集合T
Intersection（&T,S1,S2）
初始条件：
集合S1和S2存在
操作结果：
生成一个由S1和S2的交集构成的集合T
Difference（&T,S1,S2）
初始条件：
集合S1和S2存在
操作结果：
生成一个由S1和S2的差集构成的集合T
PrintSet（T）
初始条件：
集合S1和S2存在
操作结果：
按字母次序顺序显示集合T的全部元素
3主程序：
（1）主程序模块：
voidmain（）{
do{
接受命令；
处理命令；
}while（“命令”=“退出”）；
}
（2）集合单元模块——实现集合的抽象数据类型；
（3）有序表单元模块——实现有序表的抽象数据类型；
（4）结点结构单元模块——定义有序表的结点结构‘
各模块之间的调用关系如下：
主程序模块
↓
集合单元模块
↓
有序表单元模块
↓
结点结构单元模块
【测试数据及实验结果】
（1）Set1=”magazine”,Set2=”paper”,
Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”。
（2）Set1=”012oper4a6tion89”,Set2=”errordata”,
Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”,Set1-Set2=”inp”。
【实验小结】
1为什么要选择有序链表存储结构？
2分析你的集合并、交、差运算算法的时间复杂度。
【源代码说明】
1文件名：
2操作说明：
实验三二叉树基本操作的实现
姓名_________座号________级本科______________专业________班
日期:
【实验课程名称】算法与数据结构
【实验项目名称】二叉树基本操作的实现
【实验目的】
1掌握二叉树的存储结构定义；
2掌握二叉树基本操作；
3学会设计实验数据验证算法
【实验仪器及环境】计算机，windowxp操作系统，VC++6.0
【实验内容及步骤】
1．二叉树的二叉链表存储结构定义：
typedefstructBiTNode{//结点定义
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
２．实现的基本操作：
InitBiTree（&T）;
操作结果：
构造空二叉树T。
CreateBiTree（&T,definition）;
初始条件：
definition给出二叉树T的定义。
操作结果：
按definition构造二叉树T。
DestroyBiTree（&T）;
初始条件：
二叉树T存在。
操作结果：
销毁二叉树T。
BiTreeEmpty（T）;
初始条件：
二叉树T存在。
操作结果：
若T为空二叉树，则返回TRUE，否则返回FALSE。
BiTreeDepth（T）;
初始条件：
二叉树T存在。
操作结果：
返回T的深度。
Root（T）;
初始条件：
二叉树T存在。
操作结果：
返回T的根。
Value（T,e）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
返回e的值。
Parent（T,e）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
若e是T的非根结点，则返回它的双亲，否则返回"空"。
LeftChild（T,e）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
返回e的左孩子。
若e无左孩子，则返回"空"。
RightChild（T,e）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
返回e的右孩子。
若e无右孩子，则返回"空"。
LeftSibling（T,e）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
返回e的左兄弟。
若e是其双亲的左孩子或无左兄弟，则返回"空"。
RightSibling（T,e）;
初始条件：
二叉树T存在，e是T的结点。
操作结果：
返回e的右兄弟。
若e是其双亲的右孩子或无右兄弟，则返回"空"。
PreOrderTraverse（T,visit（））;
初始条件：
二叉树T存在，visit是对结点操作的应用函数。
操作结果：
先序遍历T，对每个结点调用函数visit一次且仅一次。
一旦visit（）失败，则操作失败。
InOrderTraverse（T,vsit（））;
初始条件：
二叉树T存在，visit是对结点操作的应用函数。
操作结果：
中序遍历T，对每个结点调用函数Visit一次且仅一次。
一旦visit（）失败，则操作失败。
PostOrderTraverse（T,visit（））;
初始条件：
二叉树T存在，visit是对结点操作的应用函数。
操作结果：
后序遍历T，对每个结点调用函数visit一次且仅一次。
一旦visit（）失败，则操作失败。
LevelOrderTraverse（T,visit（））;
初始条件：
二叉树T存在，visit是对结点操作的应用函数。
操作结果：
层序遍历T，对每个结点调用函数visit一次且仅一次。
一旦visit（）失败，则操作失败。
ClearBiTree（&T）;
初始条件：
二叉树T存在。
操作结果：
将二叉树T清为空树。
Assign（&T,&e,value）;
初始条件：
二叉树T存在，e是T中某个结点。
操作结果：
结点e赋值为value。
InsertChild（&T,p,LR,c）;
初始条件：
二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。
操作结果：
根据LR为0或1，插入c为T中p所指结点的左或右子树。
p所指结点原有左或右子树成为c的右子树。
DeleteChild（&T,p,LR）;
初始条件：
二叉树T存在，p指向T中某个结点，LR为0或1。
操作结果：
根据LR为0或1，删除T中p所指结点的左或右子树。
【测试数据及实验结果】
（自己设计测试数据验证算法的正确性）
【实验小结】
【源代码说明】
1文件名：
2操作说明：
实验四哈夫曼编/译码器
姓名_________座号________级本科______________专业________班
日期:
【实验课程名称】算法与数据结构
【实验项目名称】哈夫曼编/译码器
【实验目的】
1掌握哈夫曼编码、译码的实现；
2学会设计一个完整的编/译码系统
【实验仪器及环境】计算机，windowxp操作系统，VC++6.0
【实验内容及步骤】
1.初始化：
（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入文件hfmTree.txt中。
２.编码：
（Edcoding）。
利用建好的哈夫曼树（如不在内存则从文件hamTree.txt中读入），对文件TobeTran.txt中的正文进行编码，然后将结果存入文件CodeFile.txt中。
3.译码：
（Decoding）。
利用已建好的哈夫曼树将文件CodeFile.txt中的代码进行译码，结果存入文件TextFile.txt中。
4.打印代码文件（Print）。
将文件CodeFile.txt以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
5.打印哈夫曼树（Treeprinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
【测试数据及实验结果】
（1）利用教科书例6-2中的数据调试程序。
（2）利用下表给出的字符集合频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：
“THISPROGRAMISMYFAVORITE”。
字符
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操作说明：
升级会员 