数据结构实验(1)线性表及其应用.pdf

计算机系数据结构实验报告（1）

实验目的：

帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的

操作和应用作为重点。

问题描述：

1、构造一个空的线性表L。

2、在线性表L的第i个元素之前插入新的元素e；

3、在线性表L中删除第i个元素，并用e返回其值。

实验要求：

1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线

性表的基本操作算法。

2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行

分析。

算法分析：

由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的

算法，如下：

-1-

v1.0可编辑可修改

实验内容和过程：

顺序存储结构线性表程序清单：

//顺序存储结构线性表的插入删除

#includeiostream

#include

usingnamespacestd;

#defineLISTSIZE100

#defineCREMENTSIZE10

typedefcharElemType;//定义数据元素类型为字符型

typedefstruct{

ElemType*elem;//数据元素首地址

intlen;//当前元素个数

intlistsize;//当前存储最大容量

}SqList;

//构造一个空的线性表L

-2-

intInitList(SqListL)

{

=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));

if(!exit(-2);//分配空间失败

=0;

=LISTSIZE;

}

//在顺序线性表L中第i个位置之前插入新的元素e

intListInsert(SqListL,inti,ElemTypee)

{

if(i1||i+1)return-1;//i值不合法

if=

{

ElemType*newelem=(ElemType*)realloc,+CREMENTSIZE)*sizeof(ElemType));

//存储空间已满，增加分配

if(!newelem)exit(-2);//分配失败

=newelem;

+=CREMENTSIZE;

}

ElemType*q=[i-1]);

for(ElemType*p=[]);p=q;--p)*(p+1)=*p;//插入位置及其后的元素后移

*q=e;++;

return1;

}

//在顺序线性表L中删除第i个元素，并用e返回其值

intListDelete(SqListL,inti,ElemTypee)

{

if(i1||ireturn-1;//i值不合法

ElemType*p=[i-1]);

e=*p;ElemType*q=+;

for(++p;p=q+1;++p)*(p-1)=*p;//被删除元素之后的元素前移

;

return1;

-3-

}

intmain()

{

SqListL;chare,ch;

inti,j,state;