(5)--第2章 线性表-线性表及顺序存储（顺序表）.ppt

-线性表及顺序存储;1.了解线性结构的特点

2.掌握顺序表的定义、查找、插入和删除

3.掌握链表的定义、创建、查找、插入和删除

4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

;（a1,a2,…ai-1，ai,ai＋1，…,an）

;线性表L=(a1，a2,……an)，下列说法正确的是（）。;ADTList{;为了存储线性表，至少要保存两类信息：

1）线性表中的数据元素；

2）线性表中数据元素的顺序关系；;;元素n;顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。;#defineMAXSIZE100//最大长度

typedefstruct{

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

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

}SqList；;#defineMAXSIZE10000 //图书表可能达到的最大长度

typedefstruct //图书信息定义

{

charno[20]; //图书ISBN

charname[50]; //图书名字

floatprice; //图书价格

}Book;

typedefstruct

{

Book*elem; //存储空间的基地址

intlength; //图书表中当前图书个数

}SqList; //图书表的顺序存储结构类型为SqList;初始化线性表L（参数用引用）

StatusInitList_Sq(SqListL){

returnOK;

};初始化线性表L（参数用指针）

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

L-elem=newElemType[MAXSIZE];//为顺序表分配空间

if(!L-elem)exit(OVERFLOW);//存储分配失败

L-length=0; //空表长度为0

returnOK;

};intGetElem(SqListL,inti,ElemTypee)

{

if(i1||iL.length)returnERROR;

//判断i值是否合理，若不合理，返回ERROR

e=L.elem[i-1];//第i-1的单元存储着第i个数据

returnOK;

};3.查找（根据指定数据获取数据所在的位置）;;intLocateELem(SqListL,ElemTypee)

{

};插入99;4.在线性表L第个位置插入一个新元素e

StatusListInsert_Sq(SqListL,inti,ElemTypee){

//i值不合法

//当前存储空间已满

returnOK;

};若插入在尾结点之后，则根本无需移动（特别快）；

若插入在首结点之前，则表中n个元素全部后移（特别慢）；

若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？;向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。;在顺序表的最后一个元素后插入一个数据元素，时间复杂度为：;在顺序表的第一个元素前插入一个数据元素，时间复杂度为：;在顺序表的第i个元素前插入一个数据元素，时间复杂度为：;4.删除（删除第i(1≤i≤n)个结点）;5.将线性表L中第i个数据元素删除

StatusListDelete_Sq(SqListL,inti){

returnOK;

};若删除尾结点，则根本无需移动（特别快）；

若删除首结点，则表中n-1个元素全部前移（特别慢）；

若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？;向一个有127个元素的