线性表的顺序存储结构.docVIP

实验报告

学院:信息工程学院专业:计算机

信息工程学院计算机实验中心制

《数据结构》实验报告

姓名张文楚学号409109070515日期2011.4.17-8节

实验室计算机基础实验室指导教师张有华设备编

号

实验题实验二线性表的顺序存储结构

目

一实验内容

1.进一步熟悉C语言的上机环境，掌握C语言的基本结构。

2.会定义线性表的顺序存储结构。

3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的

函数定义。

二实验目的

掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基

本算法。

三需求设计

线性表抽象数据类型的描述及实现

ADTList{

DaaElemSeti12nn,,,,{|,,,,,0}数据对象:ii

RaaaaDi2n,,,,,{,|,,,,}数据关系:i1ii1i,,

基本操作:构造一个空的线性表LInitList();

销毁线性表LDestroyList();

将L重置为空表ClearList();

判断L是否为空ListEmpty();

求表长

ListLength();

查找元素

LocateElem();

求前驱PriorElem();

求后继NextElem();

插入元素

ListInsert();

删除元素

ListDelete();

元素调用visit()函数ListTraverse(L,visit())

}ADTList;

程序具体实现要求:

1.创建一个线性表

2.能输出所有数据元素

3.能求线性表长度

4.能插入删除元素

5.能查找元素

6.能求元素的前驱和后继

7.用户操作界面如下:

**********************************

*1.构造线性表

*2.插入元素

*3.删除元素

*4.查找元素

*5.显示表长

*6.求后继

*7.求前驱

*8.输出所有元素

*0.结束程序运行

***********************************

请输入您的选择(0,1,...,8):

四详细设计

步骤1:给出线性表的抽象数据类型的定义。

ADTList{

DaaElemSeti12nn,,,,{|,,,,,0}数据对象:ii

RaaaaDi2n,,,,,{,|,,,,}数据关系:i1ii1i,,

基本操作:

InitList(L);

操作结果:构造一个空的线性表L。

DestroyList(L)

初始条件:线性表L已存在。

操作结果:销毁线性表L。

ClearList(L)

初始条件:线性表L已存在。

操作结果:将L重置为空表。

ListEmpty(L)

初始条件:线性表L已存在。

操作结果:若L为空表，则返回TRUE,否则返回FALSE。

ListLength(L)

初始条件:线性表L已存在。

操作结果:返回L中数据元素个数。

GetElem(L,i,e)

初始条件:线性表L已存在,1?i?ListLength(L)。

操作结果:用e返回L中第i数据个元素的值。

LocateElem(L,e,compare())

初始条件:线性表L已存在,compare()是数据元素

判定函数。

操作结果:返回L中第1个与e满足关系compare()

的数据元素的位序。若这样的数据元素不

存在，则返回值为0。

PriorElem(L,cur_e,pre_e)

初始条件:线性表L已存在。

操作结果:若cur_e是L的数据元素，且不是第一个，

则用pre_e返回它的前驱，否则操作失败，

pre_e无定义

NextElem(L,cur_e,next_e)

初始条件:线性表L已存在。

操作结果:若cur_e是L的数据元素，且不是最后一

个，则用next_e返回它的后继，否则操作

失败，next_e无定义。

ListInsert(L,i,e)

初始条件:线性表L已存在,1?i?ListLength(L)+1。

操作结果:在L中第i个位置之前插入新的数据元素

e，L的长度加1。

ListDelete(L,i,e)

初始条件:线性表L已存在且非空,1?i?

ListLength(L)。

操作结果:删除L的第i个数据元素，并用e返回其

值，L的长度减1。

ListTraverse(L,visit())

初始条件:线性表L已存在。

操作结果:依次对L的每个数据元素调用函数

visit()。一旦visit()失败，则操作失败。

}ADTList;

步骤2:用C语言给出线性表的