数据结构实验指导(3)

实验1 线性表的顺序存储结构的实现及其应用

实验目的

1． 熟悉C语言的上机环境，掌握使用VC环境上机调试程序的基本方法； 2． 会定义线性表的顺序存储结构。

3． 熟悉对顺序表的一些基本操作和具体的函数定义。 4． 理解利用基本操作进行一些实际的应用型程序设计。

实验要求

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 #include

typedef ElemType; //填空1 #define MAXSize 10 #include \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(\ ClearList(myList); }

2.应用题

（1）求集合A、B的并集C。

（2）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。 要求：把该函数添加到文件SqList.h中，并在主函数文件SqList.cpp中添加相应语句进行测试。

6

实验步骤参考：

1.打开Visual C++6.0，“文件”菜单——>“新建”——>“工程”——>“win32 Console Application”——>输入“工程名称”和存储“位置”——>“确定”。

2.默认创建“一个空工程”——>“完成”——>“确定”。

3. “文件”菜单——>“新建”——>“文件” ——>“C/C++ Header File”——>输入文件名SqList.h（默认为.h类型，可省去.h）——>“确定”

7

4.“文件”菜单——>“新建”——>“文件” ——>“C++ Source File”——>输入文件名SqList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。

5.打开FileView双击SqList.h，完成头文件的编写。SqList.h主要含结构体的定义和函数的实现。

8