第三讲顺序表课件

第二章线性表线性表概述顺序表的存储及基本操作2023/7/211滨州学院计算机科学技术系本讲内容一、线性表的逻辑结构特点二、线性表的ADT定义三、线性表的顺序存储----顺序表2滨州学院计算机科学技术系线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”

；3．除最后元素之外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。是一个数据元素的有序(次序)集线性表是一种最简单的线性结构

一、线性表的逻辑结构3滨州学院计算机科学技术系线性表的基本术语定义：

n（n>=0）个具有相同特性的数据元素组成的有限序列；表示：L={a1,…,ai-1,ai,ai+1,…,an}

ai必须具有相同特性，即属于同一数据对象

ai-1是ai的直接前驱，ai+1是ai的直接后继

数据元素ai在线性表中有确定的位置i，i称为位序（除有特别说明外，一般从1开始计数）线性表中数据元素的个数n称为线性表的长度,n=0时，线性表称为空表4滨州学院计算机科学技术系（抽象数据类型定义）抽象数据类型线性表的定义如下：

二、线性表的ADT定义5滨州学院计算机科学技术系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在线性表中的位序。}6滨州学院计算机科学技术系

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList7滨州学院计算机科学技术系GetElem(L,i,&e)

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

e返回L中第i

个元素的值。（求线性表中某个数据元素）8滨州学院计算机科学技术系LocateElem(L,e,compare())初始条件：操作结果：线性表L已存在，e为给定值，

compare()是元素判定函数。返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）9滨州学院计算机科学技术系

ListTraverse(L,visit())初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）10滨州学院计算机科学技术系PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）11滨州学院计算机科学技术系

ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)+1。在L的第i个元素之前插入新的元素e，L的长度增1。（插入数据元素）12滨州学院计算机科学技术系ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，

1≤i≤LengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）13滨州学院计算机科学技术系三、线性表的顺序存储实现顺序存储(映象)顺序表的C语言描述线性表的基本操作在顺序表中的实现14滨州学院计算机科学技术系最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。1.顺序存储——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。15滨州学院计算机科学技术系

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址线性表的顺序存储16滨州学院计算机科学技术系以“存储位置相邻”表示有序对<ai-1，ai>

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

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

LOC(ai)=

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

↑基地址17滨州学院计算机科学技术系2.顺序存储的

C语言描述typedefstruct{

}SqList;//俗称顺序表#defineLIST_INIT_SIZE100

//线性表存储空间的初始分配量#defineLISTINCREMENT10

//线性表存储空间的分配增量

ElemType*elem;

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

int

length;

//当前表的长度int

listsize;

//当前分配的容量18滨州学院计算机科学技术系顺序表的基本形态

定义：SqListL;空表

L.length=0可插入不可删除表满

L.length>=L.listsize

可删除不可插入(空间需再分配)表不空不满0<L.length<L.listsize

可删除可插入19滨州学院计算机科学技术系3.线性表的基本操作在顺序表中的实现结构初始化查找插入元素删除元素20滨州学院计算机科学技术系Status

InitList_Sq(SqList&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;21滨州学院计算机科学技术系

int

Locate(SqListL,

ElemType

e)

{

//

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

O(n)算法的时间复杂度为：i=1;

//i的初值为第1元素的位序for(;i<=L.length;++i)if(L.elem[i-1]==e)returni;return0;根据元素值查找位置22滨州学院计算机科学技术系

int

Locate(SqListL,

inti,ElemType

&e)

{

//

在顺序表中查询位序为i的数据元素，用e返回其值//若存在，返回OK；若不存在，返回ERROR

}//Locate根据元素位置查询值

if(i>0&&i<=L.length){e=L.elem[i-1];returnOK;}elsereturnERROR;23滨州学院计算机科学技术系线性表插入操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？24滨州学院计算机科学技术系

(a1,…,ai-1,ai,…,an)改变为

(a1,…,

ai-1,e,ai,…,an)a1a2

…ai-1

ai

…ana1a2

…ai-1

…ai

ean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加25滨州学院计算机科学技术系需考虑的问题（步骤）当前表是否已满？输入（插入位置）是否有效？移动元素并插入26滨州学院计算机科学技术系

StatusListInsert(SqList&L,inti,ElemTypee){

//

在顺序表L的第i个元素之前插入新的元素e,

//i的合法范围为1≤i≤L.length+1

if(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;

27滨州学院计算机科学技术系算法时间复杂度为: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_Sq28滨州学院计算机科学技术系线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？29滨州学院计算机科学技术系

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,

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

…ai-1

ai

ai+1

…ana1a2

…ai-1

30滨州学院计算机科学技术系Status

ListDelete_Sq(SqList

&L,inti,ElemType

&e){if(i<1||i>L.length)returnERROR;//i值不合法e=L.elem[i-1];

for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j];//元素前移--L.length;returnOK;}//ListDelete_Sq算法时间复杂度为:

O(n)31滨州学院计算机科学技术系顺序表操作的效率分析

时间效率分析:

算法时间主要耗费在移动元素的操作上，而移动元素的个数取决于插入或删除元素的位置。以插入为例分析：若插入在尾元素之后，则根本无需移动（特别快）；若插入在首元素之前，则表中元素全部要后移（特别慢）；

32滨州学院计算机科学技术系推导：

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

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

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

若在an-1后面插入，要后移1个元素；若在尾元素an之后插入，则后移0个元素；33滨州学院计算机科学技术系所有可能的元素移动次数合计：0+1+…+n=n(n+1)/2

共有多少种插入形式?——连头带尾有n+1种!

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

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