数据结构.徐孝凯.数据结构 看-.pptxVIP

第二章线性表;一个线性表可以用一个标识符来命名，如用L命名上面的线性表，则L=(a1,a2,…,ai,ai+1,…,an);初始化线性表L，即置L为一个空表voidInitList(L)

清除线性表L中的所有元素，使之成为一个空表

voidClearList(L)

返回线性表L的长度，若L为空则返回0intSizeList(L)

判断线性表L是否为空，若为空则返回1，否则返回0

intEmptyList(L)

返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行ElemTypeGetElem(L,pos)

顺序扫描（即遍历）输出线性表L中的每个元素

voidTraverseList(L)

从线性表L中查找其值与x相等的元素，若查找成功则返回其位置，否则返回-1intFindList(L,x)

把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0

intUpdatePosList(L,pos,x);向线性表L的表头插入元素xvoidInsertFirstList(L,x)

向线性表L的表尾插入元素x

voidInsertLastList(L,x)

向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0intInsertPosList(L,pos,x)

向有序线性表L中插入元素x，使得插入后仍然有序

voidInsertOrderList(L,x)

从线性表L中删除表头元素并返回它，若删除失败则停止程序运行ElemTypeDeleteFirstList(L)

从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行

ElemTypeDeleteLastList(L)

从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行ElemTypeDeletePosList(L,pos)

从线性表L中删除值为x的第一个元素，若删除成功返回1否则返回0

intDeleteValueList(L,x);线性表的顺序存储结构和操作实现

线性表的顺序存储

在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用list[MaxSize]表示，整型变量用size表示，则元素类型为ElemType的线性表的顺序存储类型可描述为：

ElemTypelist[MaxSize];

intsize;

为了便于进行线性表的操作，可以把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中，假定该记录类型用List表示，则定义如下：

structList{

ElemTypelist[MaxSize];intsize;

};

若要对存储线性表的数组空间采用动态分配，并且其数组长度能够按需要增加，则可以定义出如下的List类型：

structList{;当初始化此类型的一个线性表时，要使list指针指向大小为MaxSize的动态数组空间。

2.2.2顺序存储下的线性表的操作实现

1.初始化线性表L，即进行动态存储空间分配并置L为一个空表voidInitList(structList*L,intms)

{

/*检查ms是否有效，若无效则退出运行*/if(ms=0){printf(ms值非法!\n);exit(1);}

/*置线性表空间大小为ms*/

L-MaxSize=ms;

/*动态存储空间分配，若分配失败则退出运行*/L-list=malloc(ms*sizeof(ElemType));if(!L-list){

printf(动态存储分配失败!\n);

exit(1);/*执行此函数则中止程序运行，此函数在stdlib.h中有定

}

/*初始置线性表为空*/

L-size=0;

};2.清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表voidClearList(structList*L)

{

if(L-list!=NULL){

free(L-list);/*释放存储空间*/L-list=0;

L-size=L-MaxSize=0;

}

}

9.向线性表L的表头插入元素x该操作过程分为以下四步：

检查线性表的存储空间是否已被占满，若是则重新分配更大的动态存储空间；

从表尾元素向前至表头元素止，使每一个元素均后移一个存储位置，把下标为0的位置空出，以便插入新元素；

将新元素写入到表头，即下标为0的位置；

修改线性表的长度，使其增1。;用C语言描述如下：

voidInsertFirstList(structList*L,ElemTypex)

{

inti;

if(L-size==L-Max