數(shù)據(jù)結(jié)構(gòu)線性表順序表

關(guān)于數(shù)據(jù)結(jié)構(gòu)線性表順序表第1頁，講稿共48頁，2023年5月2日，星期三線性結(jié)構(gòu)四大特點(diǎn)第一個(gè)元素?zé)o直接前驅(qū)最后一個(gè)元素?zé)o直接后繼除第一個(gè)元素外，其他每個(gè)數(shù)據(jù)元素都有唯一一個(gè)直接前驅(qū)除最后一個(gè)元素外，其他每個(gè)數(shù)據(jù)元素都有唯一一個(gè)直接后面第2頁，講稿共48頁，2023年5月2日，星期三線性表定義記法特點(diǎn)結(jié)構(gòu)基本術(shù)語空表、表長(zhǎng)直接前驅(qū)、直接后繼位序最基本、最常用的線性結(jié)構(gòu)。若n(n≥0)個(gè)數(shù)據(jù)特性相同的數(shù)據(jù)元素組成的有限序列。（a1,a2,…,ai-1,ai,ai+1,…,an)1.同一線性表中的數(shù)據(jù)元素必須具有相同特性2.具有線性結(jié)構(gòu)的四大特性3.數(shù)據(jù)元素之間存在序偶關(guān)系邏輯結(jié)構(gòu)（1對(duì)1）、物理結(jié)構(gòu)（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)）第3頁，講稿共48頁，2023年5月2日，星期三線性表的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象數(shù)據(jù)關(guān)系操作集初始化、銷毀、查找、插入、刪除、求前驅(qū)（后繼）、遍歷線性表中的數(shù)據(jù)元素具有相同特性相鄰數(shù)據(jù)元素之間存在序偶關(guān)系線性表的基本操作聲明僅是模型定義，不涉及模型實(shí)現(xiàn)，參數(shù)不必考慮具體數(shù)據(jù)類型，實(shí)際應(yīng)用中，具體問題具體分析。第4頁，講稿共48頁，2023年5月2日，星期三順序表定義特點(diǎn)C描述基本形態(tài)基本操作實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素。采用這種存儲(chǔ)結(jié)構(gòu)的線性表叫做順序表。

a1a2

…ai-1ai

…an基地址1.數(shù)據(jù)元素在“邏輯關(guān)系上的相鄰”用“物理地址相鄰”來表示。2.順序表中任一元素都可“隨機(jī)存取”。第5頁，講稿共48頁，2023年5月2日，星期三typedefstruct{

}SqList;//俗稱順序表#defineMAXSIZE100//線性表存儲(chǔ)空間的分配量，即數(shù)組長(zhǎng)度ElemTypeelem[MAXSIZE];int

length;//當(dāng)前長(zhǎng)度順序表的C描述第6頁，講稿共48頁，2023年5月2日，星期三順序表空：條件L.length==0

不允許刪除操作順序表滿：條件L.length==MAXSIZE

不允許插入操作不空也不滿：可以插入，刪除操作順序表的基本形態(tài)第7頁，講稿共48頁，2023年5月2日，星期三順序表----基本算法根據(jù)順序表的實(shí)現(xiàn)形式，表長(zhǎng)length是類型定義的屬性，可以實(shí)現(xiàn)求表長(zhǎng)、初始化、取值、判空等操作，時(shí)間復(fù)雜度均為O(1)。而遍歷算法、查找表中元素的存在、插入、刪除等操作，時(shí)間復(fù)雜度均為O(n)。第8頁，講稿共48頁，2023年5月2日，星期三（1）初始化空表時(shí)間復(fù)雜為：O(1)順序表----基本算法L.length=0；第9頁，講稿共48頁，2023年5月2日，星期三（2）判空時(shí)間復(fù)雜為：O(1)順序表----基本算法if(L.length==0) returnOK;else returnERROR;第10頁，講稿共48頁，2023年5月2日，星期三（3）求表長(zhǎng)時(shí)間復(fù)雜為：O(1)順序表----基本算法 returnL.length；第11頁，講稿共48頁，2023年5月2日，星期三（4）取元素（取第i個(gè)元素e）時(shí)間復(fù)雜為：O(1)順序表----基本算法e=L.elem[i-1];i合法if(i>=1&&i<=L.length){ e=L.elem[i-1]; returnOK;}else{ returnERROR;}第12頁，講稿共48頁，2023年5月2日，星期三順序表----基本算法（5）遍歷for(i=1;i<=L.length;i++)visit(L.elem[i-1]);時(shí)間復(fù)雜為：O(L.length)第13頁，講稿共48頁，2023年5月2日，星期三順序表----基本算法（6）查找搜索順序表中是否存在指定的數(shù)據(jù)元素。存在，查找成功；否則，查找失敗。第14頁，講稿共48頁，2023年5月2日，星期三例如：順序表23754138546217L.elem[0]L.length-1e=38i12341850可見，基本操作是：將順序表中的元素逐個(gè)和給定值e相比較。第15頁，講稿共48頁，2023年5月2日，星期三算法的時(shí)間復(fù)雜度為：

O(L.length)intLocateElem(SqListL,Elemtypee){ for(i=1;i<=L.length;i++){ if(e==L.elem[i-1]){ returni; } } return0;}第16頁，講稿共48頁，2023年5月2日，星期三順序表----基本算法（7）插入在順序表中插入指定的數(shù)據(jù)元素，插入成功，表長(zhǎng)增1。第17頁，講稿共48頁，2023年5月2日，星期三線性表操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？第18頁，講稿共48頁，2023年5月2日，星期三

(a1,…,ai-1,ai,…,an)改變?yōu)?/p>

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

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長(zhǎng)度增加第19頁，講稿共48頁，2023年5月2日，星期三必備條件：表存在且不滿i值的合法性檢查：1~L.length+1將第i個(gè)到最后1個(gè)元素依次后移一個(gè)位置；在i個(gè)位置插入元素；表長(zhǎng)增加1。分析：第20頁，講稿共48頁，2023年5月2日，星期三2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-1087564266第21頁，講稿共48頁，2023年5月2日，星期三O(L.length)算法的時(shí)間復(fù)雜度為：StatusListInsert(SqList&L,inti,ElemTypee){if(i>=1&&i<=L.length+1){ for(j=L.length;j>=i;j--)//元素后移

L.elem[j]=L.elem[j-1]; L.elem[i-1]=e;//插入e L.length++;//表長(zhǎng)增1 returnOK;//插入成功

}else{ returnERROR;}}第22頁，講稿共48頁，2023年5月2日，星期三插入算法時(shí)間復(fù)雜度分析：考慮移動(dòng)元素的平均情況插入位置需要移動(dòng)的結(jié)點(diǎn)次數(shù)1n2n-1……n1n+10平均次數(shù):(1+2+…+n-1+n)/(n+1)=n/2T(n)=O(n)第23頁，講稿共48頁，2023年5月2日，星期三順序表----基本算法（8）刪除在順序表中刪除指定位置的數(shù)據(jù)元素，刪除成功，表長(zhǎng)減1。第24頁，講稿共48頁，2023年5月2日，星期三線性表操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？第25頁，講稿共48頁，2023年5月2日，星期三

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長(zhǎng)度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

第26頁，講稿共48頁，2023年5月2日，星期三必備條件：表非空i值的合法性檢查：1~L.length取出第i個(gè)元素；第i個(gè)元素以后的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減小1。分析：第27頁，講稿共48頁，2023年5月2日，星期三2118307542568721183075L.length-10pppq8756例如：ListDelete_Sq(L,5,e)

p第28頁，講稿共48頁，2023年5月2日，星期三算法時(shí)間復(fù)雜度為:

O(L.length)StatusListDelete(SqList&L,inti,ElemType&e){if(i>=1&&i<=L.length){ e=L.elem[i-1]; for(j=i+1;j<=L.length;j++)//元素前移

L.elem[j-2]=L.elem[j-1]; L.length--;//表長(zhǎng)減1 returnOK;//刪除成功

}else{ returnERROR;}}第29頁，講稿共48頁，2023年5月2日，星期三

刪除算法時(shí)間復(fù)雜度分析：考慮移動(dòng)元素的平均情況刪除位置需要移動(dòng)的結(jié)點(diǎn)次數(shù)1n-12n-2……n0平均次數(shù):(0+1+…+n-11)/n=(n-1)/2T(n)=O(n)第30頁，講稿共48頁，2023年5月2日，星期三時(shí)間復(fù)雜度為O(1)順序表----基本算法（9）求前驅(qū)pre=L.elem[i-2];在順序表中查找元素cur_e，位序?yàn)閕i=LocateElem(L,cur_e);cur_e是順序表中元素，但不是第一個(gè)元素便有直接前驅(qū)pre第31頁，講稿共48頁，2023年5月2日，星期三

順序表----基本算法（10）求后繼next=L.elem[i];在順序表中查找元素cur_e，位序?yàn)閕i=LocateElem(L,cur_e);cur_e是順序表中元素，但不是最后一個(gè)元素便有直接后繼next時(shí)間復(fù)雜度為O(1)第32頁，講稿共48頁，2023年5月2日，星期三順序表----經(jīng)典算法分析算法插入刪除基本操作移動(dòng)元素移動(dòng)元素平均移動(dòng)次數(shù)時(shí)間復(fù)雜度O(n)O(n)最好情況在n+1處插入，不需移動(dòng)刪除第n個(gè)，不需移動(dòng)第33頁，講稿共48頁，2023年5月2日，星期三線性表應(yīng)用舉例例1：合并線性表例2：歸并線性表第34頁，講稿共48頁，2023年5月2日，星期三例1：合并線性表假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合A＝A∪B?！サ糁貜?fù)元素第35頁，講稿共48頁，2023年5月2日，星期三擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。問題分析：第36頁，講稿共48頁，2023年5月2日，星期三1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)操作步驟：第37頁，講稿共48頁，2023年5月2日，星期三

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之voidunion(List&La,ListLb){La_len=ListLength(La);//求線性表的長(zhǎng)度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union第38頁，講稿共48頁，2023年5月2日，星期三算法分析時(shí)間復(fù)雜度：

O(ListLength(LA)*ListLength(LB))空間復(fù)雜度：

O(1)第39頁，講稿共48頁，2023年5月2日，星期三例2：歸并線性表已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的數(shù)據(jù)元素仍按值非遞減有序排列?！蝗サ糁貜?fù)元素第40頁，講稿共48頁，2023年5月2日，星期三LC中的數(shù)據(jù)元素或是LA中的數(shù)據(jù)元素，或是LB中的數(shù)據(jù)元素。則先設(shè)LC為空表，然后將LA或LB中的元素逐個(gè)插入到LC中。為使LC表按值非遞減有序排列，可設(shè)兩個(gè)整型變量i、j，分別指向LA和LB，比較i、j所指元素的大小，決定哪個(gè)元素插入LC。插入后，在LA或LB中順序后移。問題分析：第41頁，講稿共48頁，2023年5月2日，星期三voidMergeList(ListLa,ListLb,List&Lc){

//本算法將非遞減的有序表La和Lb歸并為L(zhǎng)c}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{……//La和Lb均不空

}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);第42頁，講稿共48頁，2023年5月2日，星期三GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}

第43頁，講稿共48頁，2023年5月2日，星期三

while(i<=La_len){//當(dāng)La不空時(shí)

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//當(dāng)Lb不空時(shí)

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素第44頁，講稿共48頁，2023年5月2日，星期三算法分析時(shí)間復(fù)雜度：O(ListLength(LA)+ListLeng