第三講 - 順序表基本操作

2023/2/1濱州學(xué)院信息工程系第二章線性表線性表概述、順序表的存儲及基本操作2023/2/12本講內(nèi)容線性表的概念和定義邏輯結(jié)構(gòu)特點基本術(shù)語ADT定義線性表的順序存儲實現(xiàn)順序存儲方法C語言描述類型定義基本操作實現(xiàn)與分析2023/2/13一、線性表的概念和定義線性表的邏輯結(jié)構(gòu)特點線性表的基本術(shù)語ADT定義2023/2/14集合中必存在唯一的一個“第一元素”；集合中必存在唯一的一個“最后元素”；除最后元素在外，每個元素均有唯一的后繼；除第一元素之外，每個元素均有唯一的前驅(qū)。是一個數(shù)據(jù)元素的有序(次序)集。線性表是一種最簡單的線性結(jié)構(gòu),

1.線性表的邏輯結(jié)構(gòu)特點2023/2/152.線性表的基本術(shù)語線性表可描述為n（n≥0）個具有相同特性的數(shù)據(jù)元素組成的有限序列.常表示為：L={a1,…,ai-1,ai,ai+1,…,an}

ai必須具有相同特性，即屬于同一數(shù)據(jù)對象。ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素；數(shù)據(jù)元素ai在線性表中有確定的位置i，i稱為位序；線性表中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度，n=0時，線性表稱為空表。2023/2/163.線性表的ADT定義ADTList{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n為線性表的表長;稱n=0時的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai

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

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作引用型操作

加工型操作

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

線性表L已存在，且1≤i≤LengthList(L)。操作結(jié)果：

用

e返回L中第i個元素的值。2023/2/19LocateElem(L,e,compare())初始條件：線性表L已存在，e為給定值，compare()是元素判定函數(shù)。操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。2023/2/110

ListTraverse(L,visit())初始條件：線性表L已存在，visit()為某個訪問函數(shù)。操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。2023/2/111PutElem(&L,i,&e)初始條件：

線性表L已存在,且1≤i≤LengthList(L)。操作結(jié)果：

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

線性表L已存在，且1≤i≤LengthList(L)+1操作結(jié)果：

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

線性表L已存在且非空，

1≤i≤LengthList(L)。操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。2023/2/114順序映象(存儲)方式順序表的C語言描述線性表的基本操作在順序表中的實現(xiàn)二、線性表的順序存儲實現(xiàn)—順序表2023/2/1151.順序存儲（映像）方式以x的存儲位置和y的存儲位置之間某種關(guān)系表示邏輯關(guān)系<x,y>。最簡單的一種順序映象方法是：

令y的存儲位置和x的存儲位置相鄰。2023/2/116

用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址稱作線性表的基地址2023/2/117以“存儲位置相鄰”表示有序?qū)?lt;ai-1，ai>

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

一個數(shù)據(jù)元素所占存儲量↑所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置

LOC(ai)=

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

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

//線性表存儲空間的分配量，即數(shù)組容量typedefstruct{ElemType

*elem;

//存放線性表的數(shù)組空間基地址int

length;//當(dāng)前長度（實際元素個數(shù)）int

listsize;//當(dāng)前分配的容量}SqList;//稱順序表2023/2/119順序表的基本形態(tài)

定義：SqListL;空表L.length==0可插入不可刪除表滿L.length>=L.listsize可刪除不可插入(空間再分配)表不空不滿0<L.length<L.listsize可刪除可插入2023/2/1203.線性表的基本操作在順序表中的實現(xiàn)初始化查找插入元素刪除元素2023/2/121StatusInitList_Sq(SqList&L){

//構(gòu)造一個空的順序表L（初始化）

}

//InitList_Sq算法時間復(fù)雜度：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)算法的時間復(fù)雜度：根據(jù)元素值查找位置int

Locate(SqListL,

ElemType

e)

{//在順序表L中查詢第一個等于e的數(shù)據(jù)元素，//若存在，則返回它的位序，否則返回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;}根據(jù)元素位置查詢值2023/2/124線性表插入操作

ListInsert(&L,i,e)的實現(xiàn)：分析:插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,…,an)改變?yōu)?/p>

(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需考慮的問題（步驟）當(dāng)前表是否已滿？輸入（插入位置）是否有效？插入元素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算法時間復(fù)雜度: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)的實現(xiàn)：分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(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個元素，以引用參數(shù)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算法時間復(fù)雜度:

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

時間效率分析:

算法時間主要耗費在移動元素的操作上，而移動元素的個數(shù)取決于插入或刪除元素的位置。

注意：以插入為例分析若插入在尾元素之后，則根本無需移動（特別快）；若插入在首元素之前，則表中元素全部要后移（特別慢）；

2023/2/133

假定在每個元素位置上插入x的可能性都一樣（即概率P相同）則應(yīng)這樣來計算平均執(zhí)行時間：

將所有位置的執(zhí)行時間相加，然后取平均

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

……

若在an-1后面插入，要后移1個元素；若在尾元素an之后插入，則后移0個元素。推導(dǎo)過程：2023/2/134所有可能的元素移動次數(shù)合計：

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

——連頭帶尾有n+1種!

故插入時的平均移動次數(shù)為：

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

即插入、刪除算法的平均時間復(fù)雜度為O(n)

推導(dǎo)過程2023/2/135順序表----算法分析算法插入刪除基本操作移動元素移動元素平均移動次數(shù)時間復(fù)雜度O(n)O(n)最好情況在n+1處插入，不需移動