第三讲 - 顺序表基本操作

2023/2/1滨州学院信息工程系第二章线性表线性表概述、顺序表的存储及基本操作2023/2/12本讲内容线性表的概念和定义逻辑结构特点基本术语ADT定义线性表的顺序存储实现顺序存储方法C语言描述类型定义基本操作实现与分析2023/2/13一、线性表的概念和定义线性表的逻辑结构特点线性表的基本术语ADT定义2023/2/14集合中必存在唯一的一个“第一元素”；集合中必存在唯一的一个“最后元素”；除最后元素在外，每个元素均有唯一的后继；除第一元素之外，每个元素均有唯一的前驱。是一个数据元素的有序(次序)集。线性表是一种最简单的线性结构,

1.线性表的逻辑结构特点2023/2/152.线性表的基本术语线性表可描述为n（n≥0）个具有相同特性的数据元素组成的有限序列.常表示为：L={a1,…,ai-1,ai,ai+1,…,an}

ai必须具有相同特性，即属于同一数据对象。ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素；数据元素ai在线性表中有确定的位置i，i称为位序；线性表中数据元素的个数n称为线性表的长度，n=0时，线性表称为空表。2023/2/163.线性表的ADT定义ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

{设线性表为(a1，a2,...，ai，...，an),

称i为ai

在线性表中的位序。}2023/2/17

结构初始化操作结构销毁操作引用型操作

加工型操作

}ADTList基本操作：2023/2/18GetElem(L,i,&e)初始条件：

线性表L已存在，且1≤i≤LengthList(L)。操作结果：

用

e返回L中第i个元素的值。2023/2/19LocateElem(L,e,compare())初始条件：线性表L已存在，e为给定值，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。2023/2/110

ListTraverse(L,visit())初始条件：线性表L已存在，visit()为某个访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。2023/2/111PutElem(&L,i,&e)初始条件：

线性表L已存在,且1≤i≤LengthList(L)。操作结果：

L中第i个元素赋值同e的值。2023/2/112ListInsert(&L,i,e)初始条件：

线性表L已存在，且1≤i≤LengthList(L)+1操作结果：

在L的第i个元素之前插入新的元素e，L的长度增1。2023/2/113ListDelete(&L,i,&e)初始条件：

线性表L已存在且非空，

1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。2023/2/114顺序映象(存储)方式顺序表的C语言描述线性表的基本操作在顺序表中的实现二、线性表的顺序存储实现—顺序表2023/2/1151.顺序存储（映像）方式以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。2023/2/116

用一组地址连续的存储单元依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址称作线性表的基地址2023/2/117以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址2023/2/1182.顺序表的C语言描述#defineMAXSIZE100

//线性表存储空间的分配量，即数组容量typedefstruct{ElemType

*elem;

//存放线性表的数组空间基地址int

length;//当前长度（实际元素个数）int

listsize;//当前分配的容量}SqList;//称顺序表2023/2/119顺序表的基本形态

定义：SqListL;空表L.length==0可插入不可删除表满L.length>=L.listsize可删除不可插入(空间再分配)表不空不满0<L.length<L.listsize可删除可插入2023/2/1203.线性表的基本操作在顺序表中的实现初始化查找插入元素删除元素2023/2/121StatusInitList_Sq(SqList&L){

//构造一个空的顺序表L（初始化）

}

//InitList_Sq算法时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;2023/2/122

O(n)算法的时间复杂度：根据元素值查找位置int

Locate(SqListL,

ElemType

e)

{//在顺序表L中查询第一个等于e的数据元素，//若存在，则返回它的位序，否则返回0

i=1;

//i的初值为第1元素的位序for(i<=L.length;i++)if(L.elem[i-1]==e)returni;return0;}//Locate2023/2/123Statussearch_i(SqListL,inti,ElemType&e)

{//在顺序表L中查找第i个元素，若存在用e返回其//值并返回OK,否则返回ERRORif(i>0&&i<=L.length){e=L.elem[i-1];returnOK;}elsereturnERROR;}根据元素位置查询值2023/2/124线性表插入操作

ListInsert(&L,i,e)的实现：分析:插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为

(a1,…,

ai-1,e,ai,…,an)<ai-1,ai><ai-1,e>,<e,ai>2023/2/125a1a2

…ai-1ai

…ana1a2

…ai-1

…ai

ean表的长度增加存储空间（顺序表）中的变化：2023/2/126需考虑的问题（步骤）当前表是否已满？输入（插入位置）是否有效？插入元素2023/2/127

StatusListInsert(SqList&L,inti,ElemTypee)

{

//在顺序表L的第i个元素之前插入新的元素e,//i的合法范围为1≤i≤L.length+1if(L.length>=L.listsize){//空间再分配newbase=(ElemType*)

realloc(L.elem

,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

//基地址更新L.listsize+=LISTINCREMENT;//表容量更新}if(i<1||i>L.length+1)returnERROR;

2023/2/128算法时间复杂度:O(n)for

(j=L.length;j>i;j--)L.elem[j]=L.elem[j-1];

//插入位置及之后的元素右移L.elem[i-1]=e;

//插入e++L.length;

//表长增1returnOK;}//ListInsert_Sq2023/2/129线性表操作

ListDelete(&L,i,&e)的实现：分析：删除元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,

ai-1,ai+1,…,an)<ai-1,ai>,<ai,ai+1><ai-1,ai+1>2023/2/130ai+1…an表的长度减少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

存储空间（顺序表）中的变化2023/2/131StatusListDelete_Sq(SqList&L,inti,ElemType&e)

{//在顺序表L中删除第i个元素，以引用参数e返回其值//若删除成功返回ok；否则返回ERROR

if(i<1||i>L.length)returnERROR;//i值不合法

e=L.elem[i-1];for(j=i;j<L.length;j++)L.elem[j-1]=L.elem[j];//元素前移--L.length;returnOK;}//ListDelete_Sq算法时间复杂度:

O(n)2023/2/132顺序表操作的效率分析

时间效率分析:

算法时间主要耗费在移动元素的操作上，而移动元素的个数取决于插入或删除元素的位置。

注意：以插入为例分析若插入在尾元素之后，则根本无需移动（特别快）；若插入在首元素之前，则表中元素全部要后移（特别慢）；

2023/2/133

假定在每个元素位置上插入x的可能性都一样（即概率P相同）则应这样来计算平均执行时间：

将所有位置的执行时间相加，然后取平均

若在首元素前插入，需要后移n次；若在a1后面插入，要后移n-1个元素；

……

若在an-1后面插入，要后移1个元素；若在尾元素an之后插入，则后移0个元素。推导过程：2023/2/134所有可能的元素移动次数合计：

0+1+…+n=n(n+1)/2共有多少种插入形式?

——连头带尾有n+1种!

故插入时的平均移动次数为：

n(n+1)/2÷（n+1）＝n/2

即插入、删除算法的平均时间复杂度为O(n)

推导过程2023/2/135顺序表----算法分析算法插入删除基本操作移动元素移动元素平均移动次数时间复杂度O(n)O(n)最好情况在n+1处插入，不需移动