《数据结构实验指导》.doc

PAGE-90-

第１章上机实验内容及指导

上机实验是对学生的一种全面综合训练，是与课堂讲授的内容相辅相成的必不可少的一个教学环节。通过上机实验，既可以加深对讲授内容的理解、深化，也可以培养学生的思维能力和创造精神。在上机实验时，千万不要在已给出的源程序通过运行后就认为完成任务了，而要在所给的例子的基础上，完成每章的课后习题。
上机实验一般包括以下几个步骤：
（1）准备好上机所需的程序。为提高上机效率，上机前应认真检查手编程序，以减少错误率。
（2）上机输入和调试自己所编的程序。上机过程中，应该善于分析判断，尽量独立去处理出现的问题，这是提高调试程序能力的良好机会。
（3）程序调试通过后，要记录程序在不同条件下的运行结果，为实验报告作准备。
（4）上机结束后，要及时整理出实验报告。实验报告除了在开头写上班级、姓名、学号和完成日期外，还应该包括以下内容：
=1\*GB3①实验题目
=2\*GB3②实验内容
=3\*GB3③程序构思
=4\*GB3④程序清单
=5\*GB3⑤运行结果
最后，在每次上机后，自己应该对程序的运行情况作一下分析，总结本次上机调试程序所取得的经验。若程序未能通过，应分析其原因。

第2章线性表

实验一线性表的顺序存储结构
一、实验目的
通过本次实验，掌握线性表的顺序存储结构的基本操作及线性表存储结构所适用的范围。
二、实验内容与要求
(一)认真复习线性表顺序存储结构方面的知识，完成本实验的内容。
(二)实验内容为教材例2-1：假设利用两个线性表LA和LB分别表示两个集合A和B（即线性中的数据元素即为集合中的成员），现要求一个新的集合A=A∪B。
三、程序构思
从题意的要求可知，对线性表应作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。
四、程序源代码
/*c1.h(程序名)*/
#include<string.h>
#include<ctype.h>
#include<alloc.h>/*malloc()等*/
#include<limits.h>/*INT_MAX等*/
#include<stdio.h>/*EOF(=^Z或F6),NULL*/
#include<stdlib.h>/*atoi()*/
#include<io.h>/*eof()*/
#include<math.h>/*floor(),ceil(),abs()*/
#include<process.h>/*exit()*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/

/*c2-1.h线性表的动态分配顺序存储结构*/
#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/
#defineLISTINCREMENT2/*线性表存储空间的分配增量*/
typedefstruct
{
ElemType*elem;/*存储空间基址*/
intlength;/*当前长度*/
intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/
}SqList;

/*bo2-1.c顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个)*/
StatusInitList(SqList*L)/*算法2.3*/
{/*操作结果：构造一个空的顺序线性表*/
(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem)
exit(OVERFLOW);/*存储分配失败*/
(*L).length=0;/*空表长度为0*/
(*L).listsize=LIST_INIT_SIZE;/*初始存储容量*/
returnOK;
}

StatusDestroyList(SqList*L)
{/*初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L*/
free((*L).elem);
(*L).elem=NULL;
(*L).length=0;
(*L).listsize=0;