实验指导书
目 录
实验说明
A．每班学习委员或班长至少在上机实验前一周到软件学院教务室（软件学院大楼4楼教务室）购买上机实验报告
B．上机实验报告封面上要写完整：班级、姓名、指导老师姓名，学期、报告日期等。
C．其它
本学期上机实验一共16学时，大家需要完成8个实验。
上机前写好预习报告（即上机报告中调试分析之前的内容），准备好程序和测试数据。
报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。
请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。
请大家认真完成上机任务及上机报告，严禁抄袭。有任何问题可以及时跟任课教师联系！
希望在愉快的环境中完成本学期的学习，请大家积极配合，谢谢！
实验要求
一、实验步骤
⒈ 问题分析
充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。
⒉ 数据结构设计
针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。
⒊ 算法设计
算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。概要设计可以由模块的功能说明和模块之间的调用关系图完成。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。
⒋ 测试用例设计
准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌ 上机调试
对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
二、实验报告
每次上机实验前，应该写好预习报告。预习报告包括如下内容：
（1）问题描述：简述题目要做什么。
（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用关系图，存储结构的定义、基本操作的实现、其他模块的算法等。
（3）测试用例设计
每次实验结束后，在预习报告的基础上撰写完整的实验报告。实验报告应包括如下内容：
（1）、（2）同预习报告
（3）调试报告：调试过程中遇到的问题以及如何解决；对设计和编码的讨论和分析。
（4）测试结果。根据预习报告中设计的测试用例进行程序测试，可以贴相应的运行结果截图。
（5）算法分析与改进：重要算法的时间复杂度和空间复杂度分析；算法改进的设想。
（6）总结和体会
所有实验做完后，上交电子材料放在以本人名字命名的文件夹中，包括上机实验源程序（.h， .cpp）、可执行文件（.exe）和相应的运行结果截图。源程序要加注释。如果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。
上机实验报告（仅供参考）
【实验目的和要求】
见实验任务书
【实验题目】
线性表的链式存储结构的实现及其应用
【实验内容】
1．需求分析
题目要求完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③ 程序所能实现的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。
④ 测试数据：
A．插入操作中依次输入11，12，13，14，15，16，生成一个单链表
B．查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
C．删除操作中依次输入2，5，删除位于2和5的元素
2．概要设计
1）为了实现上述程序功能，先定义线性表的抽象数据类型：
ADT List {
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R={<ai,ai+1>|ai,ai+1 ∈D, i=1,2,…,n-1,n≥1}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L.
InsList(&L,pos,e)
初始条件：线性表L已存在
操作结果：将元素e插入到线性表L的pos位置
DelList(&L,pos,&e)
初始条件：线性表L已存在
操作结果：将线性表L中pos位置的元素删除，元素值置入e中返回
LocList(L,e)
初始条件：线性表L依存在
操作结果：线性表L中查找是否元素e，若存在，返回元素在表中的位置；
若不存在，返回-1.
Menu()
操作结果：在屏幕上显示操作菜单
}//ADT List
2）本程序包含7个函数：
① 主函数main()
② 初始化单链表函数InitLinkList()
③ 显示操作菜单函数menu()
④ 显示单链表内容函数dispLinkList()
⑤ 插入元素函数InsLinkList()
⑥ 删除元素函数DelLinkList()
⑦ 查找元素函数LocLinkList()
各函数间关系如下：
3．详细设计
实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
1) 结点类型和链表类型
typedef Elemtype int;
typedef struct node {
Elemtype data;
struct node *next;
}LNode,*LinkList;
2) 单链表的基本操作（只需写主要完成任务的伪码算法）
为了方便，在单链表中设头结点，头结点的data域没有意义。
bool InitLinkList(LinkList &L)
（伪码算法略 参考教材算法）
void DispLinkList(LinkList L)
（伪码算法略）
void menu()
（伪码算法略）
bool InsLinkList(LinkList &L,int pos,int e)
（伪码算法略）
bool DelLinkList(LinkList &L,int pos,int &e)
（伪码算法略）
int LocLinkList(LinkList L,int e)
（伪码算法略）
3) 其他模块伪码算法 略
4．调试分析
(此内容根据自己调试过程写出相应分析报告)
5．使用说明（可有可无）
程序名为LinkList.exe，运行环境为DOS。程序执行后显示
========================
0—-EXIT
1—-INSERT
2—-DELETE
3—-LOCATE
=======================
SELECT:
在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。
选择0：退出程序
选择1：显示“INSERT pos,e =” ，
要求输入要插入的位置和元素的值（都是整数）。
选择2：显示“DELETE pos =” ，
要求输入要删除元素的位置，执行成功后返回元素的值。
选择3：显示“LOCATE e = ” ，
要求输入要查找元素的值，执行成功后返回元素在表中的位置
6．测试结果
1） 建立单链表：
» 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到单链表（15，14，13，12，11）
2） 插入：
» 选择1输入（1，100），得到单链表（15，100，14，13，12，11）
» 选择1输入（-1，2），显示输入错误
» 选择1输入（7，2），显示输入错误
» 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2）
3） 删除：
» 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2）
» 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2）
» 选择2，输入4。返回e=2，得到单链表（14，13，12，11）
» 选择2，输入5。返回输入错误
4） 查找
» 选择3，输入14。返回pos=0
» 选择3，输入100。返回输入错误
7．小结
即心得体会，包括对算法的讨论、分析，改进设想和其它经验教训等
实验1 线性表的顺序存储结构的实现及其应用
实验目的
熟悉C语言的上机环境，掌握使用VC环境上机调试程序的基本方法；
会定义线性表的顺序存储结构。
熟悉对顺序表的一些基本操作和具体的函数定义。
理解利用基本操作进行一些实际的应用型程序设计。
实验要求
1． 独立完成。
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1、基础题：
编写应用程序（填空），实现可以在顺序表中插入任意给定数据类型数据的功能（定义为ElemType抽象数据类型）。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数），对它们求和并输出。请把主函数设计为一个文件SqList.cpp，其余函数设计为另一个文件SqList.h。
请填空完成以下给出的源代码并调试通过。
（1） 文件SqList.h:
typedef struct List{
ElemType *elem;
int length;
}SqList;
void InitList(SqList &L)
{ //构造一个空的顺序表
…………
}
void ClearList(SqList &L)
{ //清空线性表，不销毁
………………
}
int ListLength (SqList L)
{ //求线性表长度
………..
}
bool ListInsert (SqList &L, int i , ElemType e)
{ //在线性表L中第i个数据元素之前插入新数据元素e
…….
}
ElemType GetElem(SqList L, int i)
{ //在线性表L中求序号为i的元素，该元素作为函数返回值
…………..
}
（2）文件SqList.cpp：
#include <stdio.h>
#include <stdlib.h>
typedef ElemType; //填空1
#define MAXSize 10
#include “SqList.h”
void main(void)
{
SqList myList;
int i=1, x, sum=0, n;
InitList ( ); //填空2
scanf(“%d”, &x);
while ( x!= -1 )
{
if (ListInsert (myList, i, )==false) { //填空3
printf(“错误!\n”);
return ;
}
i++;
scanf(“%d”, &x);
}
n = ListLength (myList);
for (i=1; i<=n; i++) //求所有数据元素的和
{
x=GetElem(myList, i);
sum = + x; //填空4
}
printf(“%d\n “, sum);
ClearList(myList);
}
2.应用题
（1）求集合A、B的并集C。
（2）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。
要求：把该函数添加到文件SqList.h中，并在主函数文件SqList.cpp中添加相应语句进行测试。
实验步骤参考：
1.打开Visual C++6.0，“文件”菜单——>“新建”——>“工程”——>“win32 Console Application”——>输入“工程名称”和存储“位置”——>“确定”。
2.默认创建“一个空工程”——>“完成”——>“确定”。
3. “文件”菜单——>“新建”——>“文件” ——>“C/C++ Header File”——>输入文件名SqList.h（默认为.h类型，可省去.h）——>“确定”
4.“文件”菜单——>“新建”——>“文件” ——>“C++ Source File”——>输入文件名SqList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。
5.打开FileView双击SqList.h，完成头文件的编写。SqList.h主要含结构体的定义和函数的实现。
6.打开FileView双击SqList.cpp，完成源文件的编写和填空。SqList.cpp主要含main()函数的实现。
7.编译运行。
实验2 线性表的链式存储结构的实现及其应用
实验目的
掌握线性表的建立、插入、删除等基本操作的编程实现，进一步编程实现查找、排序等操作，存储结果采用顺序表存储结构。
理解利用基本操作进行一些实际的应用型程序设计。
实验要求
1． 可以依次完成主要功能来体现功能的正确性，也可以用菜单管理完成大部分功能，要求可以重复运行。
2． 准备好测试数据，程序调试正确，有执行结果。
3． 程序是自己开发的，在界面上注明***原创；参考或改写他人的，注明***参考他人版。
实验内容（基础题必做，应用题任选1个）
1、基础题：
线性表基本操作的实现(演示单链表的创建、插入、删除、查找、输出等操作)，通过简单实例测试各基本操作函数算法的正确性。基本操作函数如下：
Status InitList(LinkList &L)
//初始化只含有头结点的空的单链表，返回函数状态值
void DestroyList(LinkList &L) //销毁单链表
void ClearList(LinkList &L) //清空单链表，仅保留头结点
bool ListEmpty(LinkList L) //判断是否为空链表
int ListLength(LinkList L) //返回单链表的长度
void PrintList(LinkList L)
//遍历函数，顺序输出单链表中的各元素的值
Status GetElem(LinkList L,int i,ElemType &e)
//用参数e返回单链表L中第i个元素的值
Status ListInsert(LinkList &L,int i,ElemType e)
//在单链表L的第i个数据元素之前插入数据元素e
Status ListDelete(LinkList &L,int i,ElemType &e)
//删除单链表L中第i个结点，并用e返回其值
int LocateElem(LinkList L,ElemType e)
//返回e元素在单链表L中的位序，若不存在，返回0
2、应用题：
（1）将一个已知的单链表进行逆置运算，如（a1,a2,…,an）变为（an,…a2,a1）。
（2）求集合A、B的并集C。
（3）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。
实验步骤参考：
1.打开Visual C++6.0，“文件”菜单——>“新建”——>“工程”——>“win32 Console Application”——>输入“工程名称”和存储“位置”——>“确定”。
2.默认创建“一个空工程”——>“完成”——>“确定”。
3. “文件”菜单——>“新建”——>“文件” ——>“C/C++ Header File”——>输入文件名LinkList.h（默认为.h类型，可省去.h）——>“确定”
4.“文件”菜单——>“新建”——>“文件” ——>“C++ Source File”——>输入文件名LinkList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。
5.打开FileView双击LinkList.h，完成头文件的编写。LinkList.h主要含结构体的定义和函数的实现。
6.打开FileView双击LinkList.cpp，完成源文件的编写。LinkList.cpp主要含main()函数的实现。
7.编译运行。 运行结果如下图所示：
实验3 栈和队列的存储结构的实现
实验目的
掌握栈的存储结构及基本操作。
掌握队列的存储结构及基本操作。
通过具体的应用实例，进一步熟悉和掌握栈和队列的实际应用。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1. 基础题：
（1）按照教材中抽象数据类型栈的定义，采用顺序存储结构（用动态数组）或链式存储结构，编写主函数演示顺序栈/链栈的基本操作。
（2）按照教材中抽象数据类型队列的定义，采用顺序存储结构（循环队列）或链式存储结构，编写主函数演示循环队列/链队列的基本操作。
2. 应用题：
（1）算符优先算法为表达式求值
（2）舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。设计一个函数partner()，模拟上述舞伴配对问题。
基本要求：
1) 由键盘输入数据，每对数据包括姓名和性别；
2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；
实验步骤参考：
1.打开FileView双击stack.h，完成头文件的编写。stack.h主要含结构体的定义和函数的实现。
2.打开FileView双击stack.cpp，完成源文件的编写。stack.cpp主要含main()函数的实现。
3.编译运行。运行结果如下图所示：
队列：
1.打开FileView双击queue.h，完成头文件的编写。queue.h主要含结构体的定义和函数的实现。
2.打开FileView双击queue.cpp，完成源文件的编写。queue.cpp主要含main()函数的实现。
3.编译运行。运行结果如下图所示：
实验4 树和二叉树的存储结构的实现
实验目的
熟悉二叉树结点的结构和对二叉树的基本操作。
掌握对二叉树每一种操作的具体实现。
学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1. 基础题：
按照教材中抽象数据类型二叉树的定义，采用二叉链表存储结构，编写主函数演示二叉树的基本操作，如：
说明：二叉树的基本操作可包括：
(1) void InitBT( BTreeNode *&BT ) //初始化二叉树BT
(2) void CreateBT( BTreeNode *&BT, char *a )
//根据字符串a所给出二叉树的描述，建立二叉链表存储结构
(3) int EmptyBT( BTreeNode *BT)
//检查二叉树BT是否为空，空返回1，否则返回0
(4) int DepthBT( BTreeNode *BT) //求二叉树BT的深度并返回该值
(5) int FindBT( BTreeNode *BT, ElemType x)
//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
(6) void PreOrder( BTreeNode *BT) //先序遍历二叉树BT
(7) void InOrder( BTreeNode *BT) //中序遍历二叉树BT
(8) void PostOrder( BTreeNode *BT) //后序遍历二叉树BT
(9) void LevelOrder( BTreeNode *BT ) //按层次遍历二叉树BT
(10) void LeafCount(BTreeNode *BT , int & count) //求二叉树b的叶子结点个数
(11) int NodeCount(BTreeNode *BT) //求二叉树BT的总结点个数
(12) void ClearBTree( BTreeNode *&BT ) //清除二叉树BT
2．应用题
(1)输入n个叶子结点的权值，根据Huffman算法，构造一棵哈夫曼树。
(2)家谱管理：本题目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。
实验步骤参考：
1.打开FileView双击tree.h，完成头文件的编写。tree.h主要含结构体的定义和函数的实现。
2.打开FileView双击tree.cpp，完成源文件的编写。tree.cpp主要含main()函数的实现。
3.编译运行。运行结果如下图所示：
或者打开工程所在文件夹E:\tree\Debug\tree.exe，也可以直接运行。
实验5 图的存储结构的实现
实验目的
掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。
遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、基础题（至少做一个）
（1）图的邻接矩阵定义及实现：
定义图的邻接矩阵存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。以下图为例，建立一个验证操作实现的主函数进行测试。
（2）图的邻接表的定义及实现：
定义图的邻接表存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数中调用这些函数进行验证（以下图为例）。
实验步骤参考：
1.完成头文件的编写。queue.h主要含队列结构体的定义和必须要用到的队列函数的实现。
mgrapht.h主要含结构体的定义和函数的实现。
2. 完成源文件的编写，对mgraph.h里的函数进行测试。graph.cpp主要含main()函数的实现。
3. 编译运行。
实验6 图的简单应用
实验目的
1. 掌握图的最短路径概念。
2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）/克鲁斯卡尔算法。
3. 理解求最短路径的DijKstra算法（用邻接矩阵表示图）。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1、基础题
编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，主要包括：
① 初始化邻接矩阵表示的有向带权图
② 建立邻接矩阵表示的有向带权图 （即通过输入图的每条边建立图的邻接矩阵）
③ 输出邻接矩阵表示的有向带权图（即输出图的每条边）。
④ 编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组 path 和 dist 中。（可选）
⑤ 编写打印输出从源点到每个顶点的最短路径及长度的函数 void PrintPath(int dist[], edgenode *path[], int n)。（可选）
同时建立一个验证操作实现的主函数进行测试。
2、应用题
编写Prim算法函数 void Prim(adjmatrix G, edgset CT, int n)或者克鲁斯卡尔算法函数以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。编写主函数测试生成最小生成树并输出（即输出边集）。
测试数据如下：
实验步骤参考：
1.完成头文件的编写。graph.h主要含结构体的定义和函数的实现。
2. 完成源文件的编写，对mgraph.h里的函数进行测试。graph.cpp主要含main()函数的实现。
3. 编译运行。
实验7 查找算法的实现
实验目的
1． 掌握各种查找算法的思想。
2． 学会分析各种查找算法的效率。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1.基础题
实现教材中给出的查找算法。编写主函数以菜单形式测试各个查找算法。
2.应用题
编写程序，完成以下任务：
a) 通过键盘输入n个学生的考试成绩表(设计为一个线性表)，表中每个元素由学号、姓名与分数组成；
b) 统计各个分数段人数；
c) 按学号查找某个学生成绩信息。
实验提示：
1、 顺序查找算法
2、 折半查找
3、 二叉排序树的查找
4、 哈希查找
实验8 排序算法的实现
实验目的
1． 掌握各种排序算法的思想。
2． 学会分析各种排序算法的效率和稳定性。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1.基础题
实现教材中给出的排序算法。编写主函数以菜单形式测试各个排序算法。
2.应用题
编写程序，完成以下任务：
a) 通过键盘输入n个学生的考试成绩表(设计为一个线性表)，表中每个元素由学号、姓名与分数组成；
b) 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
c) 按名次打印出每个学生的姓名与分数。
实验提示：
1、 直接插入排序
2、 希尔排序
3、 冒泡排序
4、 快速排序
5、 简单选择排序
6、 堆排序
7、 二路归并
