《数据结构》试验指导书（信管13用）

本文格式为Word版，下载可任意编辑——《数据结构》试验指导书（信管13用）韶关学院信息科学与工程学院

数据结构试验指导书

（龙腾芳编）

试验一顺序表实现及应用

[试验目的]

1．了解顺序表的结构特点及有关概念，把握顺序表建立、插入、删除的基本操作算法。[试验内容]

试验1．顺序表的实践。

在参考程序的main()函数的注解部分有试验的要求，请按要求完成试验[试验要点及说明]

线性表（linearlist）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。寻常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不可怜况下是不同的，即它的数据类型可以根据具体状况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。

顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，其次个元素紧跟着第一个之后，其余依此类推。

可定义顺序表如下：

typedefstruct{

ElemType*elem;//指向数据元素的基地址

intlength;//线性表的当前长度}SqList;

[参考程序]//

/******************试验一、顺序表的操作************************///以下程序已有基本的函数，可以运行，先细心阅读以下代码段及注解，//然后请按要求补充完整，完成其余要求的操作。//2023信管（1）（2）用

//教材：邮电出版的严蔚敏《数据结构》（C语言版）#include#include

#defineMAXSIZE100//最大长度

1

#defineOK1#defineERROR0

#defineOVERFLOW-2

/*****************************************************************/typedefintStatus;typedefintElemType;

/************************表的结构*********************************/typedefstruct{

ElemType*elem;//指向数据元素的基地址

intlength;//线性表的当前长度}SqList;

StatusInitList_Sq1(SqList//为顺序表分派空间if(!L.elem)exit(OVERFLOW);//存储分派失败L.length=0;//空表长度为0returnOK;}

StatusInitList_Sq2(SqList*L){//构造一个空的顺序表L

L->elem=newElemType[MAXSIZE];//为顺序表分派空间if(!L->elem)exit(OVERFLOW);//存储分派失败L->length=0;//空表长度为0returnOK;}

/******************************撤销表***************************/voidDestroyList(SqList//释放存储空间}

/********************************清空表***********************/voidClearList(SqList//将线性表的长度置为0}

/*************************求表的长度*****************************/intGetLength(SqListL){

return(L.length);

2

}

/***************************判表是否为空*******************/intIsEmpty(SqListL){

if(L.length==0)return1;elsereturn0;}

/*******************取第i个元素****************************/intGetElem(SqListL,inti,ElemType

//判断i值是否合理，若不合理，返回ERRORe=L.elem[i-1];//第i-1的单元存储着第i个数据returnOK;}

/***************顺序表的查询**************************/intLocateELem(SqListL,ElemTypee){inti;

for(i=0;i=i-1;j--)

L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移

L.elem[i-1]=e;//将新元素e放入第i个位置++L.length;//表长增1returnOK;}

//将线性表L中第i个数据元素删除

StatusListDelete_Sq(SqList//i值不合法

e=L.elem[i-1];//将欲删除的元素保存在e中

3

for(intj=i;j>n;L.length=n;//表长度=元素个数for(i=0;i>L.elem[i];}

/*******************取元素操作***********************/cout>i;

if(GetElem(L,i,element))cout0时称为非空表。寻常将非空的线性表记为（a1，