《算法与数据结构》实验指导书文档格式.docx
《《算法与数据结构》实验指导书文档格式.docx》由会员分享，可在线阅读，更多相关《《算法与数据结构》实验指导书文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
//当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList；
实现的基本操作：
InitList（&
L）
操作结果：
构造一个空的线性表L。
DestroyList（&
初始条件：
线性表L已存在。
操作结果：
销毁线性表L。
ListEmpty（L）
线性表L已存在。
若L为空表，则返回TRUE，否则返回FALSE。
ListLength（L）
返回L中元素个数。
PriorElem（L,cur_e,&
pre_e）
若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem（L,cur_e,&
next_e）
若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重置为空表。
PutElem（&
L,i,&
线性表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已存在且非空，1≤i≤LengthList（L）。
删除L的第i个元素，并用e返回其值，L的长度减1。
2．线性表链式存储基本操作
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
【测试数据及实验结果】
（自己设计测试数据验证算法的正确性）
【实验小结】
1.线性表的顺序存储和链式存储各有何优缺点？
2.各举一两个例子说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好。
【源代码说明】
1．文件名：
2．操作说明：
实验二集合的并、交和差运算
【实验项目名称】集合的并、交和差运算
1掌握有序链表的基本操作；
2掌握集合的基本操作；
3学会采用抽象数据分层设计程序。
（1）本演示程序中，集合的元素限定为小写字母字符[‘a’.’z’],集合的大小n<
27.集合输入的形式为一个以“回车符”为结束标志的字符串顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。
输出的运算结果字符串中将不含重复字符或非法字符。
（2）演示程序以用户和计算机的对话形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘输入演示程序中规定的运算命令；
相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
（3）程序执行的命令包括：
1）构造集合1；
2）构造集合2；
3）求并集；
4）求交集；
5）求差集；
6）结束。
“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。
为实现上述程序功能，应以有序链表表示集合。
为次，需要两个抽象数据类型：
有序表和集合。
1有序链表的基本操作
LinkTypehead,tail;
//分别指向线形表的头结点和尾结点
Intsize;
//指示链表当前的长度
}OrderedList;
InitList（&
L）
构造一个空的的有序表L。
DestroyList（&
初试条件：
有序表L已存在。
销毁有序表L。
ListLength（L）
结果操作：
返回有序表L的长度。
ListEmpty（L）
若有序L为空表，则返回True,否则返回False,
GetElem（L,pos）
1≤pos≤Length（L）,则返回表中第pos个数据元素
LocateElem（L,e，&
q）
若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值TRUE；
否则q指示第一个大于e的元素的前驱的位置，并返回函数值FALSE
Append（&
L,e）
在有序表L的末尾插入元素e
InsertAfter（&
L,q,e）
有序表L已存在，q指示L中一个元素
在有序表L中q指示的元素之后插入元素e
ListTraverse（q,visit（））
依次对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（&
生成一个由S1和S2的交集构成的集合T
Difference（&
生成一个由S1和S2的差集构成的集合T
PrintSet（T）
按字母次序顺序显示集合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学会设计实验数据验证算法
1．二叉树的二叉链表存储结构定义：
typedefstructBiTNode{//结点定义
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
２．实现的基本操作：
InitBiTree（&
T）;
构造空二叉树T。
CreateBiTree（&
T,definition）;
definition给出二叉树T的定义。
按definition构造二叉树T。
DestroyBiTree（&
二叉树T存在。
销毁二叉树T。
BiTreeEmpty（T）;
若T为空二叉树，则返回TRUE，否则返回FALSE。
BiTreeDepth（T）;
返回T的深度。
Root（T）;
返回T的根。
Value（T,e）;
二叉树T存在，e是T中某个结点。
返回e的值。
Parent（T,e）;
若e是T的非根结点，则返回它的双亲，否则返回"
空"
。
LeftChild（T,e）;
返回e的左孩子。
若e无左孩子，则返回"
RightChild（T,e）;
返回e的右孩子。
若e无右孩子，则返回"
LeftSibling（T,e）;
返回e的左兄弟。
若e是其双亲的左孩子或无左兄弟，则返回"
RightSibling（T,e）;
二叉树T存在，e是T的结点。
返回e的右兄弟。
若e是其双亲的右孩子或无右兄弟，则返回"
PreOrderTraverse（T,visit（））;
二叉树T存在，visit是对结点操作的应用函数。
先序遍历T，对每个结点调用函数visit一次且仅一次。
一旦visit（）失败，则操作失败。
InOrderTraverse（T,vsit（））;
中序遍历T，对每个结点调用函数Visit一次且仅一次。
PostOrderTraverse（T,visit（））;
二叉树T存在，visit是对结点操作的应用函数。
后序遍历T，对每个结点调用函数visit一次且仅一次。
LevelOrderTraverse（T,visit（））;
层序遍历T，对每个结点调用函数visit一次且仅一次。
ClearBiTree（&
将二叉树T清为空树。
Assign（&
T,&
e,value）;
结点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.初始化：
（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
20
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
63
48
51
80
23
8
18
16
升级会员 