实
验
指
导
书
目 录
实验说明
A．每班学习委员或班长至少在上机实验前一周到软件学院教务室（软件学院大楼4楼教务室）购买上机实验报告
B．上机实验报告封面上要写完整：班级、姓名、指导老师姓名，学期、报告日期等。
C．其它
本学期上机实验一共16学时，大家需要完成8个实验。
上机前写好预习报告（即上机报告中调试分析之前的内容），准备好程序和测试数据。
报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。
请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。
请大家认真完成上机任务及上机报告，严禁抄袭。有任何问题可以及时跟任课教师联系！
希望在愉快的环境中完成本学期的学习，请大家积极配合，谢谢！
实验要求
一、实验步骤
⒈ 问题分析
充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。
⒉ 数据结构设计
针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。
⒊ 算法设计
算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。概要设计可以由模块的功能说明和模块之间的调用关系图完成。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。
⒋ 测试用例设计
准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌ 上机调试
对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
二、实验报告
每次上机实验前，应该写好预习报告。预习报告包括如下内容：
（1）问题描述：简述题目要做什么。
（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用关系图，存储结构的定义、基本操作的实现、其他模块的算法等。
（3）测试用例设计
每次实验结束后，在预习报告的基础上撰写完整的实验报告。实验报告应包括如下内容：
（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={
基本操作：
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)
{ //清空线性表，不销毁
………………
}
