數據結構C語言 線性表

會計學1數據結構數據結構C語言語言線性表線性表 2.1 2.1 2.1 2.1 線性表的類型定義線性表的類型定義線性表的類型定義線性表的類型定義 2.2 2.2 2.2 2.2 線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現 2.3 2.3 2.3 2.3 線性表的鏈式表示和實現線性表的鏈式表示和實現線性表的鏈式表示和實現線性表的鏈式表示和實現 2.4 2.4 2.4 2.4 線性表的應用線性表的應用線性表的應用線性表的應用第1頁/共123頁2.1 2.1 線性表的類型定義線性表的類型定義線性表的類型定義線性表的類型定義線性結構的線性結構的基本特征基本特征:n n 集合中必存在唯一的一個集合中必存在唯一的一個集合中必存在唯一的一個集合中必存在唯一的一個“第一元素第一元素第一元素第一元素”；n n 集合中必存在唯一的一個集合中必存在唯一的一個集合中必存在唯一的一個集合中必存在唯一的一個“最后元素最后元素最后元素最后元素”；n n 除最后元素之外，均有唯一的除最后元素之外，均有唯一的除最后元素之外，均有唯一的除最后元素之外，均有唯一的后繼后繼后繼后繼；n n 除第一元素之外，均有唯一的除第一元素之外，均有唯一的除第一元素之外，均有唯一的除第一元素之外，均有唯一的前驅前驅前驅前驅。從邏輯上：數據之間的關系可以分從邏輯上：數據之間的關系可以分從邏輯上：數據之間的關系可以分從邏輯上：數據之間的關系可以分4 4類類類類：線性結構線性結構線性結構線性結構,樹型結構樹型結構樹型結構樹型結構,圖狀結構圖狀結構圖狀結構圖狀結構,集合集合集合集合線性結構線性結構線性結構線性結構:是一個數據元素的是一個數據元素的是一個數據元素的是一個數據元素的有序（次序）有序（次序）有序（次序）有序（次序）集合。集合。集合。集合。僅指在數據元素之間存在一個 領先 或 落后 的次序關系，而非指數據元素 值 的大小可比性。第2頁/共123頁n n線性表最簡單的一種線性結構線性表最簡單的一種線性結構線性表最簡單的一種線性結構線性表最簡單的一種線性結構n n一個線性表是一個線性表是一個線性表是一個線性表是n n個數據元素的有限序列個數據元素的有限序列個數據元素的有限序列個數據元素的有限序列n n比如比如比如比如 A BZ A BZ 英文字母表英文字母表英文字母表英文字母表n n比如比如比如比如001高等數學華羅庚S01002線性代數鑾汝書L01003高等數學鄭杭生 S01004離散數學耿素云S02線性表中每個數據元素的具體含義，各不相同，數據元素是基線性表中每個數據元素的具體含義，各不相同，數據元素是基線性表中每個數據元素的具體含義，各不相同，數據元素是基線性表中每個數據元素的具體含義，各不相同，數據元素是基本單位，一個數據元素由若干個數據項組成本單位，一個數據元素由若干個數據項組成本單位，一個數據元素由若干個數據項組成本單位，一個數據元素由若干個數據項組成2.1 2.1 線性表的類型定義線性表的類型定義線性表的類型定義線性表的類型定義第3頁/共123頁n n線性表記為線性表記為線性表記為線性表記為（a a1 1,a ai i-1-1,a ai i,a ai i+1+1,a an n）n na ai-1i-1 在在在在a ai i 之前之前之前之前 稱稱稱稱 a ai i-1-1是是是是 a ai i 的的的的 前驅前驅前驅前驅n na ai i 在在在在 a ai i-1-1之后之后之后之后 稱稱稱稱 a ai i 是是是是 a ai i-1-1的的的的 后繼后繼后繼后繼n n序列中數據元素的個數序列中數據元素的個數序列中數據元素的個數序列中數據元素的個數 n n 定義為線性表的表長定義為線性表的表長定義為線性表的表長定義為線性表的表長 n n稱稱稱稱 i i 為為為為a ai i在線性表中的位序在線性表中的位序在線性表中的位序在線性表中的位序 n n i i=2=2，,n nn n線性表的元素個數稱為的線性表的元素個數稱為的線性表的元素個數稱為的線性表的元素個數稱為的表長表長表長表長，n n0 0時稱為時稱為時稱為時稱為空表空表空表空表2.1 2.1 線性表的類型定義線性表的類型定義線性表的類型定義線性表的類型定義第4頁/共123頁線性表的抽象數據類型線性表的抽象數據類型線性表的抽象數據類型線性表的抽象數據類型(ADT)(ADT)(ADT)(ADT)定義如下：定義如下：定義如下：定義如下：ADTADT ListList 數據對象數據對象數據對象數據對象：D=aD=ai i|a|ai i ElemSet,i=1,2,.,n,n=0 ElemSet,i=1,2,.,n,n=0 數據關系數據關系數據關系數據關系：R1=aR1=|a|ai-1i-1,a,ai iD,i=2,.,n D,i=2,.,n /表示為相鄰元素的有序對表示為相鄰元素的有序對表示為相鄰元素的有序對表示為相鄰元素的有序對 基本操作基本操作基本操作基本操作：InitList(&L)InitList(&L)操作結果：構造一個空的線性表操作結果：構造一個空的線性表操作結果：構造一個空的線性表操作結果：構造一個空的線性表L L。DestroyList(&L)DestroyList(&L)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：銷毀線性表操作結果：銷毀線性表操作結果：銷毀線性表操作結果：銷毀線性表L L，將原表中各結點所，將原表中各結點所，將原表中各結點所，將原表中各結點所 占的內存空間釋放。占的內存空間釋放。占的內存空間釋放。占的內存空間釋放。任何數據結構在被使用之前都必須進行“初始化”，它類似于編程中使用的變量都必須先有定義。任何數據結構不再使用時都必須進行“結構銷毀”，其實質為釋放它所占有的存儲空間。第5頁/共123頁引用型操作ListEmpty(L)ListEmpty(L)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：若操作結果：若操作結果：若操作結果：若L L為空表，則返回為空表，則返回為空表，則返回為空表，則返回TRUETRUE，否則，否則，否則，否則FALSEFALSE。ListLength(L)ListLength(L)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：返回操作結果：返回操作結果：返回操作結果：返回L L中元素個數中元素個數中元素個數中元素個數。PriorElem(L,cur_e,&pre_e)PriorElem(L,cur_e,&pre_e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：若操作結果：若操作結果：若操作結果：若cur_ecur_e是是是是L L的元素，但不是第一個，則用的元素，但不是第一個，則用的元素，但不是第一個，則用的元素，但不是第一個，則用pre_epre_e返回它的前驅，否則操作失敗，返回它的前驅，否則操作失敗，返回它的前驅，否則操作失敗，返回它的前驅，否則操作失敗，pre_epre_e無定義。無定義。無定義。無定義。NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：若操作結果：若操作結果：若操作結果：若cur_ecur_e是是是是L L的元素，但不是最后一個，則用的元素，但不是最后一個，則用的元素，但不是最后一個，則用的元素，但不是最后一個，則用next_enext_e返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，next_enext_e無定義無定義無定義無定義。第6頁/共123頁LocateElem(L,e,compare()LocateElem(L,e,compare()初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在，已存在，已存在，已存在，compare()compare()是元素判定函數。是元素判定函數。是元素判定函數。是元素判定函數。操作結果：返回操作結果：返回操作結果：返回操作結果：返回L L中第中第中第中第1 1個與個與個與個與e e滿足關系滿足關系滿足關系滿足關系compare()compare()的元素的的元素的的元素的的元素的位序。若這樣的元素不存在，則返回值為位序。若這樣的元素不存在，則返回值為位序。若這樣的元素不存在，則返回值為位序。若這樣的元素不存在，則返回值為0 0。ListTraverse(L,visit()ListTraverse(L,visit()初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：依次對操作結果：依次對操作結果：依次對操作結果：依次對L L的每個元素調用函數的每個元素調用函數的每個元素調用函數的每個元素調用函數visit()visit()。一旦。一旦。一旦。一旦visit()visit()失敗，則操作失敗。失敗，則操作失敗。失敗，則操作失敗。失敗，則操作失敗。GetElem(L,i,&e)GetElem(L,i,&e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在，已存在，已存在，已存在，1iLengthList(L)1iLengthList(L)操作結果：用操作結果：用操作結果：用操作結果：用e e返回返回返回返回L L中第中第中第中第i i個元素的值。個元素的值。個元素的值。個元素的值。函數參數函數參數 compare()作為判定的條件，參數作為判定的條件，參數 e 和線性表中數據元素具有相同類型。較和線性表中數據元素具有相同類型。較多場合是以多場合是以“相等相等”作為判定條件，此時可省略函數參數，且操作結果為：若線作為判定條件，此時可省略函數參數，且操作結果為：若線性表中存在與性表中存在與 e 值相同的數據元素，則返回第一個這樣的元素在表中的位序，值相同的數據元素，則返回第一個這樣的元素在表中的位序，否則返回函數值為否則返回函數值為0。visit()亦為函數參數，常見的情況是亦為函數參數，常見的情況是“依次輸出表中元素的值依次輸出表中元素的值”，同樣在這種情，同樣在這種情況下，通常的寫法也是省略函數參數。況下，通常的寫法也是省略函數參數。第7頁/共123頁 PutElem(&L,i,e)PutElem(&L,i,e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在，已存在，已存在，已存在，1iLengthList(L)1iLengthList(L)操作結果：操作結果：操作結果：操作結果：L L中第中第中第中第i i個元素賦個元素賦個元素賦個元素賦e e的值。的值。的值。的值。ListDelete(&L,i,&e)ListDelete(&L,i,&e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在且非空，已存在且非空，已存在且非空，已存在且非空，1iLengthList(L)1iLengthList(L)操作結果：刪除操作結果：刪除操作結果：刪除操作結果：刪除L L的第的第的第的第i i個元素，并用個元素，并用個元素，并用個元素，并用e e返回其值，返回其值，返回其值，返回其值，L L的長度減的長度減的長度減的長度減1 1。ListInsert(&L,i,e)ListInsert(&L,i,e)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在，已存在，已存在，已存在，1iLengthList(L)+11iLengthList(L)+1操作結果：在操作結果：在操作結果：在操作結果：在L L的第的第的第的第i i個元素之前插入新的元素個元素之前插入新的元素個元素之前插入新的元素個元素之前插入新的元素e e，L L的長度增的長度增的長度增的長度增1 1。ADT List ADT ListClearList(&L)ClearList(&L)初始條件：線性表初始條件：線性表初始條件：線性表初始條件：線性表L L已存在。已存在。已存在。已存在。操作結果：將操作結果：將操作結果：將操作結果：將L L重置為空表。重置為空表。重置為空表。重置為空表。加工型操作第8頁/共123頁 算法2.1利用兩個線性表利用兩個線性表LALA和和LBLB分別表示兩個集合分別表示兩個集合A A和和B B，現要求一個新的集合現要求一個新的集合A=AA=AB B。從集合的觀點看，此問題求解的方法很簡單，只要對集合從集合的觀點看，此問題求解的方法很簡單，只要對集合 B B 中中的所有元素一個一個地檢查，看看在集合的所有元素一個一個地檢查，看看在集合 A A 中是否存在相同元素，若中是否存在相同元素，若不存在，則將該元素插入到集合不存在，則將該元素插入到集合 A A，否則舍棄之。，否則舍棄之。要在計算機中求解，首先要確定要在計算機中求解，首先要確定“如何表示集合如何表示集合”。集合可以。集合可以有多種表示方法，對上述集合求并的問題可以用線性表表示集合?，F有多種表示方法，對上述集合求并的問題可以用線性表表示集合?，F假設以線性表假設以線性表 LA LA 和和 LB LB 分別表示集合分別表示集合 A A 和和 B B，即構造兩個線性表，即構造兩個線性表 LA LA 和和 LBLB，它們的數據元素分別為集合，它們的數據元素分別為集合 A A 和和 B B 中的成員。中的成員。由此，上述集合求并的問題便可演繹為：要求對線性表作如下由此，上述集合求并的問題便可演繹為：要求對線性表作如下操作：擴大線性表操作：擴大線性表 LALA，將，將存在于線性表存在于線性表存在于線性表存在于線性表 LB LB 中中中中而而不存在于線性表不存在于線性表不存在于線性表不存在于線性表 LA LA 中中中中的數據元素的數據元素插入到線性表插入到線性表插入到線性表插入到線性表 LA LA 中中中中去。去。第9頁/共123頁具體操作步驟為：具體操作步驟為：1 1從線性表從線性表 LB LB 中取出一個數據元素；中取出一個數據元素；2 2依值在線性表依值在線性表 LA LA 中進行查詢；中進行查詢；3 3若不存在，則將它插入到若不存在，則將它插入到 LA LA 中。中。重復上述三步直至重復上述三步直至 LB LB 為空表止。為空表止。那么，其中的每一步能否利用上述線性表類那么，其中的每一步能否利用上述線性表類型中定義的基本操作來完成呢？型中定義的基本操作來完成呢？容易看出，上述的每一步恰好對應線性表的容易看出，上述的每一步恰好對應線性表的一個基本操作：一個基本操作：1.ListDelete(LB,1,e);1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)3.ListInsert(LA,n+1,e)第10頁/共123頁void union(List&Lavoid union(List&La，List&Lb)List&Lb)while(!ListEmpty(Lb)while(!ListEmpty(Lb)ListDelete(Lb,1,e);ListDelete(Lb,1,e);if(!LocateElem(La,e,equal()if(!LocateElem(La,e,equal()ListInsert(La,1,e);ListInsert(La,1,e);DestroyList(Lb);DestroyList(Lb);/union/union時間復雜度O(ListLength(La)ListLength(Lb)第11頁/共123頁void union(List&Lavoid union(List&La，List Lb)List Lb)La_len=ListLength(La);La_len=ListLength(La);Lb_len=ListLength(Lb);Lb_len=ListLength(Lb);for(for(i i=1;=1;i i=lb_len;=lb_len;i i+)+)GetElem(lbGetElem(lb，i i，e);e);if(!LocateElem(la,e,equal()if(!LocateElem(la,e,equal()ListInsert(la,+la_en,e);ListInsert(la,+la_en,e);/union/union時間復雜度O(ListLength(La)ListLength(Lb)第12頁/共123頁 算法2.2巳知線性表LA和線性表LB中的數據元素按值非遞減有序排列，現要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算法如下：第13頁/共123頁void mergelist(List lavoid mergelist(List la，List lbList lb，List&lc)List&lc)InitList(lc);InitList(lc);i i=j j=1;=1;k k=0;=0;la-len=ListLength(la);la-len=ListLength(la);lb-len=ListLength(lb);lb-len=ListLength(lb);while(while(i i=la-len)&(=la-len)&(j j=lb-len)=lb-len)GetElem(laGetElem(la，i i，a ai i););GetElem(lbGetElem(lb，j j，b bj j););if(aif(ai i=b=bj j)ListInsert(lc)ListInsert(lc，+k k，a ai i);+);+i i;else ListInsert(lcelse ListInsert(lc，+k k，b bj j);+);+j j;while(while(i i=la-len)=la-len)GetElem(laGetElem(la，i i+，a ai i););ListInsert(lcListInsert(lc，+k k，a ai i););while(while(j j=lb-len)=lb-len)GetElem(lb GetElem(lb，j j+，b bj j););ListInsert(lc ListInsert(lc，+k k，b bj j););時間復雜度O(ListLength(La)+ListLength(Lb)第14頁/共123頁思思考考1已知一個已知一個“非純集合非純集合”B，試構造一個集合，試構造一個集合 A，使，使 A 中只包含中只包含 B 中所有值各不相同的數據元素。中所有值各不相同的數據元素。分析分析:將每個從將每個從 B 中取出的元素和已經加入到集合中取出的元素和已經加入到集合 A 中的元素相比較。中的元素相比較。void purge(List&LA,List LB)/構造線性表LA，使其只包含LB中所有值不相同的數據元素,算法不改變線性表LBInitList(LA);/創(chuàng)建一個空的線性表 LALa_len=0;Lb_len=ListLength(LB);/求線性表 LB 的長度for(i=1;i=Lb_len;i+)/處理 LB 中每個元素 GetElem(LB,i,e);/取LB中第 i 個數據賦給 e /當 LA 中沒有和 e 值相同的數據元素時進行插入 if(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/for/purge第15頁/共123頁思思考考2判別兩個集合是否相等。判別兩個集合是否相等。分析分析:首先判別兩者的表長是否相等；在表首先判別兩者的表長是否相等；在表長相等的前提下，對于一個表中的所有元素，長相等的前提下，對于一個表中的所有元素，是否都能在另一個表中找到和它相等的元素是否都能在另一個表中找到和它相等的元素.第16頁/共123頁boolbool isEqual(List LA,List LB)isEqual(List LA,List LB)/若線性表若線性表 LA LA 和和 LB LB 不僅長度相等，且所含數據元素也相同，不僅長度相等，且所含數據元素也相同，/則返回則返回 TRUETRUE，否則返回，否則返回 FALSEFALSE。La_len=Listlength(LA);La_len=Listlength(LA);Lb_len=Listlength(LB);Lb_len=Listlength(LB);/如果如果 集合集合 中的元素不能保證都相異，那么這個問題的算法應如何寫？中的元素不能保證都相異，那么這個問題的算法應如何寫？ifif(La_len!=Lb_len)(La_len!=Lb_len)returnreturn FALSEFALSE;/兩表的長度不兩表的長度不等等 i=1;i=1;whilewhile(i=La_len)(i=La_len)GetElem(LA,i,e);GetElem(LA,i,e);/取得取得 LA LA 中一個元素中一個元素 ifif(LocateElem(LB,e,equal()(LocateElem(LB,e,equal()i+;i+;/依次處理下一個依次處理下一個 elseelse return FALSE return FALSE;/LB/LB中沒有和該元素相同的元素中沒有和該元素相同的元素 /while/whilereturn truereturn true;/isEqual/isEqual 第17頁/共123頁JJ這個算法是否在任何情況下都正確，會不會有例外的情況？當然，這個算法思想還有一個前提是，已知集合符合當然，這個算法思想還有一個前提是，已知集合符合集合論中的約定集合論中的約定 集合中的元素都是彼此相異的集合中的元素都是彼此相異的。JJ如果“集合”中的元素不能保證都相異，那么這個問題的算法應如何寫？除了判別每個除了判別每個 LA LA 中的元素在中的元素在 LB LB 中都存在之外，還應中都存在之外，還應反過來判別反過來判別 LB LB 中每個元素都能在中每個元素都能在 LA LA 中找到相同者。中找到相同者。第18頁/共123頁若要在實際的程序設計中真正引用線性表的基本操作，首先必須實現線性表類型。即在計算機中確定它的存儲結構并在此存儲結構上實現類型中定義的所有基本操作。本節(jié)將討論它的順序存儲結構以及在順序存儲結構中基本操作的實現。第19頁/共123頁 2.1 2.1 線性表的類型定義線性表的類型定義 2.2 2.2 線性表的順序表示和線性表的順序表示和實現實現 2.3 2.3 線性表的鏈式表示和線性表的鏈式表示和實現實現 2.4 2.4 線性表的應用線性表的應用第20頁/共123頁2.2 2.2 線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現n n線性表的起始地址，稱作線性表線性表的起始地址，稱作線性表線性表的起始地址，稱作線性表線性表的起始地址，稱作線性表的的的的基地址基地址基地址基地址n n特點特點特點特點：用一組：用一組：用一組：用一組 地址連續(xù)地址連續(xù)地址連續(xù)地址連續(xù) 的存儲單的存儲單的存儲單的存儲單元依次存放線性表中的數據元素元依次存放線性表中的數據元素元依次存放線性表中的數據元素元依次存放線性表中的數據元素用一組地址連續(xù)的存儲單元依次存放線性表中的數據用一組地址連續(xù)的存儲單元依次存放線性表中的數據用一組地址連續(xù)的存儲單元依次存放線性表中的數據用一組地址連續(xù)的存儲單元依次存放線性表中的數據元素元素元素元素 順序表順序表順序表順序表線性表：（線性表：（線性表：（線性表：（3,9,6,8,1,3,9,6,8,1,7 7）順序存儲順序存儲順序存儲順序存儲第21頁/共123頁順序存儲結構的特點順序存儲結構的特點（1）利用數據元素的存儲位置表示線性表中相鄰數據元素之間的前后關系，即線性表的邏輯結構與存儲結構（物理結構）一致（2）在訪問線性表時，可以利用數學公式，快速地計算出任何一個數據元素的存儲地址。第22頁/共123頁1 13 32 2i-i-1 1i iC C以以以以“存儲位置相鄰存儲位置相鄰存儲位置相鄰存儲位置相鄰”表示有序對表示有序對表示有序對表示有序對a即：即：即：即：loc(aloc(ai i)=loc(a)=loc(ai-1i-1)+C)+C loc(a loc(ai i)=loc(a)=loc(a1 1)+(i-1)*C)+(i-1)*C其中其中其中其中 C C 為每個數組元素的大小為每個數組元素的大小為每個數組元素的大小為每個數組元素的大小2.2 2.2 線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現例：有一線性表（例：有一線性表（例：有一線性表（例：有一線性表（a,b,c,d,e,a,b,c,d,e,a,b,c,d,e,a,b,c,d,e,，x,y,zx,y,zx,y,zx,y,z），），），），用順序存儲的方式存儲該線性表，如已知線性表用順序存儲的方式存儲該線性表，如已知線性表用順序存儲的方式存儲該線性表，如已知線性表用順序存儲的方式存儲該線性表，如已知線性表的基地址為的基地址為的基地址為的基地址為200200200200，請問，請問，請問，請問h h h h的存儲地址？的存儲地址？的存儲地址？的存儲地址？207207第23頁/共123頁pp用用C語言描述順序映像的語言描述順序映像的線性表線性表#definedefine LIST_INIT_SIZELIST_INIT_SIZE 8080/線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define#define LISTINCREMENTLISTINCREMENT 1010/線性表存儲空間的分配增量線性表存儲空間的分配增量LelemLength 3Listsize 8661583typedef structtypedef struct ElemType *elem;ElemType *elem;/存儲空間基址存儲空間基址int length;int length;/當前長度當前長度int listsize;int listsize;/當前分配的存儲容當前分配的存儲容量量 SqListSqList;/俗稱俗稱 順序表順序表sequence list2.2 2.2 線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示和實現typedeftypedef?ElemType;ElemType;/根據實際需要定義根據實際需要定義第24頁/共123頁InitList_SqInitList_Sq (SqList&L)(SqList&L)DestroyList_SqDestroyList_Sq(SqList&L)(SqList&L)ListLength_SqListLength_Sq(SqList L)(SqList L)IsEmptyIsEmpty(SqList L)(SqList L)GetElem_SqGetElem_Sq(SqList L,int pos,&e)(SqList L,int pos,&e)LocateElem_Sq LocateElem_Sq(SqList(SqList L,L,ElemType e)ElemType e)LocateElem_Sq LocateElem_Sq(SqList(SqList L,L,ElemType e,status compare(ElemType,ElemType)ElemType e,status compare(ElemType,ElemType)ClearList_SqClearList_Sq(SqList&L)(SqList&L)ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(SqList&L,int pos,ElemType e)ListDelete_Sq ListDelete_Sq(SqList&L,int pos,ElemType&e)(SqList&L,int pos,ElemType&e)線性表的基本操作：線性表的基本操作：線性表的基本操作：線性表的基本操作：第25頁/共123頁思考思考如果你已經學習了如果你已經學習了如果你已經學習了如果你已經學習了C+C+語言，那么你認為這里討論的順序表類型語言，那么你認為這里討論的順序表類型語言，那么你認為這里討論的順序表類型語言，那么你認為這里討論的順序表類型和和和和C+C+語言中的語言中的語言中的語言中的“類類類類”有何聯(lián)系？有何聯(lián)系？有何聯(lián)系？有何聯(lián)系？抽象數據類型是程序設計的理論基礎。如果以順序存儲結構來實現抽象數據類型線性表，則抽象數據類型是程序設計的理論基礎。如果以順序存儲結構來實現抽象數據類型線性表，則用面向對象的程序設計語言編程時就可以實現一個用面向對象的程序設計語言編程時就可以實現一個“順序表類順序表類”。這里對順序表類型的結構。這里對順序表類型的結構定義即為順序表類私有的數據成員，所定義的基本操作即為順序表類中的成員函數。定義即為順序表類私有的數據成員，所定義的基本操作即為順序表類中的成員函數。如果用如果用結構化語言，也很容易地用結構體表示抽線數據類型中的數據和結構，用定義在結構體上的結構化語言，也很容易地用結構體表示抽線數據類型中的數據和結構，用定義在結構體上的一組函數來表示抽象數據類型的基本操作。一組函數來表示抽象數據類型的基本操作。第26頁/共123頁pp 順序表的初始化順序表的初始化順序表的初始化順序表的初始化Status Status InitList_Sq InitList_Sq(SqList&L)(SqList&L)/構造一個空的順序表構造一個空的順序表構造一個空的順序表構造一個空的順序表L L L.elem=(ElemType*)malloc(L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)LIST_INIT_SIZE*sizeof(ElemType););if(!L.elem)exit(OVERFLOW);if(!L.elem)exit(OVERFLOW);/存儲分配失敗存儲分配失敗存儲分配失敗存儲分配失敗 L.length=0;L.length=0;/長度為長度為長度為長度為0 0 L.listsize=LIST_INIT_SIZE;L.listsize=LIST_INIT_SIZE;/初始存儲容量初始存儲容量初始存儲容量初始存儲容量 return OK;return OK;/InitList_Sq/InitList_SqLelemLength 0Listsize80順序表操作第27頁/共123頁pp 順序表的銷毀順序表的銷毀順序表的銷毀順序表的銷毀void DestroyList_Sq(SqList&L)if(L-item)free(L-item);/釋放線性表占據的所有存儲空間釋放線性表占據的所有存儲空間/DestroyList_Sq順序表操作第28頁/共123頁pp 順序表的長度順序表的長度順序表的長度順序表的長度Status ListLength_Sq(SqList L)return(L.length);/ListLength_Sq順序表操作第29頁/共123頁pp 順序表是否為空順序表是否為空順序表是否為空順序表是否為空Status IsEmpty_Sq(SqList L)if(L.length=0)return TRUE;else return FALSE;/IsEmpty_Sq順序表操作第30頁/共123頁pp 順序表的數據獲取順序表的數據獲取順序表的數據獲取順序表的數據獲取Status Status GetElem_SqGetElem_Sq(SqLIST L,int pos,EntryType&e)(SqLIST L,int pos,EntryType&e)if(posL.length)return ERROR;/判判斷斷i i值值是是否否合合理理，若若不不合合理理，返回返回ERRORERROR e=L.itempos-1;/數組中第數組中第數組中第數組中第i-1i-1i-1i-1的單元存儲著線性表中第的單元存儲著線性表中第的單元存儲著線性表中第的單元存儲著線性表中第i i i i個數據元素的內容個數據元素的內容個數據元素的內容個數據元素的內容 return OK;/GetElem_Sq順序表操作第31頁/共123頁StatusStatus LocateElem_SqLocateElem_Sq(SqList(SqList L,L,ElemType e)ElemType e)/*/*在順序線性表在順序線性表在順序線性表在順序線性表L L中查找第中查找第中查找第中查找第1 1個值與個值與個值與個值與e e相等的元素的相等的元素的相等的元素的相等的元素的位序。若找到，則返回其在位序。若找到，則返回其在位序。若找到，則返回其在位序。若找到，則返回其在L L中的位序，否則返回中的位序，否則返回中的位序，否則返回中的位序，否則返回0 0。*/p=L.elem;p=L.elem;/指針指針指針指針p p從順序表基地址開始從順序表基地址開始從順序表基地址開始從順序表基地址開始 while(p-L.elem)L.length&while(p-L.elem)L.length&*p!=e*p!=e)p+;p+;if(*p=e)return(p-L.elem+1);if(*p=e)return(p-L.elem+1);else return 0;else return 0;/LocateElem_Sq/LocateElem_Sqpp 順序表的定位順序表的定位順序表的定位順序表的定位(按值查找按值查找按值查找按值查找)V1.0()V1.0(指針法指針法指針法指針法)第32頁/共123頁p 順序表的定位順序表的定位順序表的定位順序表的定位(按值查找按值查找按值查找按值查找)V2.0()V2.0(下標下標下標下標法法法法)StatusStatus LocateElem_SqLocateElem_Sq (SqList L,ElemType x)(SqList L,ElemType x)int i=0 int i=0；for(;i L.length;i+)for(;i L.length;i+)if(if(L.elemi=xL.elemi=x )return i+1;)return i+1;if(i=L.length)return 0;if(i=L.length)return 0;注意：數組元素的兩種標識方法：指針法和下標法注意：數組元素的兩種標識方法：指針法和下標法注意：數組元素的兩種標識方法：指針法和下標法注意：數組元素的兩種標識方法：指針法和下標法例：例：例：例：p=L.elemp=L.elemp=L.elemp=L.elem；*p p p p 和和和和L.elem0L.elem0L.elem0L.elem0指同一個元素指同一個元素指同一個元素指同一個元素p=p+1;*p p=p+1;*p p=p+1;*p p=p+1;*p 和和和和L.elem1L.elem1L.elem1L.elem1指同一個元素指同一個元素指同一個元素指同一個元素順序表操作第33頁/共123頁StatusStatus LocateElem_SqLocateElem_Sq(SqList(SqList L,ElemType e,StatusL,ElemType e,Status compare(ElemType,ElemType)compare(ElemType,ElemType)int i=0 int i=0；for(;i L.length;i+)for(;ib;return ab;/*/*/Status Status LocateElem_SqLocateElem_Sq(SqList L,ElemType e,Status(SqList L,ElemType e,Status compare(ElemType,ElemType)compare(ElemType,ElemType)for(;i L.length;i+)for(;ilength=0;/將線性表的長度置為將線性表的長度置為0 0/ClearList_Sq順序表操作第36頁/共123頁順序表的插入順序表的插入線性表的插入運算是指在表的線性表的插入運算是指在表的i i(1(1 i i n n+1+1個位個位置上，插入一個新結點置上，插入一個新結點x x，使長度為，使長度為n n的線性的線性表表 (a a1 1，a a i i-1-1，a ai i，a an n)變成長度為變成長度為n n+1+1的線性表的線性表 (a a1 1，a a i i-1-1，x x，a ai i，a an n)第37頁/共123頁返回第38頁/共123頁pp 順序表插入操作順序表插入操作順序表插入操作順序表插入操作V1.0(下標法下標法)插入元素時，注意線性表的插入元素時，注意線性表的插入元素時，注意線性表的插入元素時，注意線性表的邏輯結構邏輯結構邏輯結構邏輯結構發(fā)生什么變化？發(fā)生什么變化？發(fā)生什么變化？發(fā)生什么變化？(a(a1 1,a,ai-1i-1,a,ai i,a,an n)改變?yōu)楦淖優(yōu)楦淖優(yōu)楦淖優(yōu)?(a(a1 1,a,ai-1i-1,e,a,e,ai i,a,an n)pospos的合法值為的合法值為的合法值為的合法值為1posL.length+11posL.length+1 if(pos L.length+1)return ERROR;/位置是否合位置是否合位置是否合位置是否合法法法法 if(L.length=L.Listsize)exit(OVERFLOW);/空間是否夠用空間是否夠用空間是否夠用空間是否夠用 for(j=L.length-1;j=pos-1;j-)for(j=L.length-1;j=pos-1;j-)/插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移 L.elemj+1=L.elemj;L.elemj+1=L.elemj;L.elempos-1=e;/插入插入插入插入e e e e L.length+;/表長增表長增表長增表長增1 1 1 1 return OK;/ListInsert_Sq/ListInsert_Sq StatusStatus ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(SqList&L,int pos,ElemType e)/在順序表在順序表在順序表在順序表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e e第39頁/共123頁Status Status ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(SqList&L,int pos,ElemType e)/在順序線性表在順序線性表在順序線性表在順序線性表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e e if(posL.length+1)return ERRORif(posL.length+1)return ERROR;/位置是否合法位置是否合法位置是否合法位置是否合法 if(L.length=L.listsize)exit(OVERFLOW);if(L.length=L.listsize)exit(OVERFLOW);/空間是否夠用空間是否夠用空間是否夠用空間是否夠用q=&(L.elempos-1);q=&(L.elempos-1);/q/q指示插入位置，注意指示插入位置，注意指示插入位置，注意指示插入位置，注意pospos值和下標差值和下標差值和下標差值和下標差1 1for(p=&(L.elemL.length-1);p=q;p-)for(p=&(L.elemL.length-1);p=q;p-)*(p+1)=*p;*(p+1)=*p;/插入位置后元素右移插入位置后元素右移插入位置后元素右移插入位置后元素右移 *q=e;q=e;/插入插入插入插入e e L.length+L.length+;/表長增表長增表長增表長增1 1 return OK;return OK;/ListInsert_Sq/ListInsert_Sq p順序表插入操作順序表插入操作V2.0(指針法指針法)第40頁/共123頁if(L.length=L.listsize)exit(if(L.length=L.listsize)exit(OVERFLOWOVERFLOW););if(L.length=L.listsize)if(L.length=L.listsize)newbase=(ElemType*)newbase=(ElemType*)reallocrealloc (L.elem,(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemTypeL.listsize+LISTINCREMENT)*sizeof(ElemType););/*/*分配一個大小為分配一個大小為分配一個大小為分配一個大小為(L.listsize+LISTINCREMENT)*sizeof(L.listsize+LISTINCREMENT)*sizeof(ElemType)(ElemType)的存儲空間，將原表元素填充到新空間中，把的存儲空間，將原表元素填充到新空間中，把的存儲空間，將原表元素填充到新空間中，把的存儲空間，將原表元素填充到新空間中，把首地址賦值給首地址賦值給首地址賦值給首地址賦值給newbase*/newbase*/if(!newbase)exit(OVERFLOW);if(!newbase)exit(OVERFLOW);/存儲分配失敗存儲分配失敗存儲分配失敗存儲分配失敗 L.elem=newbase;L.elem=newbase;/新基址新基址新基址新基址 L.listsize+=LISTINCREMENT;L.listsize+=LISTINCREMENT;/增加存儲容量增加存儲容量增加存儲容量增加存儲容量 插入時檢測到空間不夠時可以用插入時檢測到空間不夠時可以用插入時檢測到空間不夠時可以用插入時檢測到空間不夠時可以用reallocrealloc申請增加空間申請增加空間申請增加空間申請增加空間第41頁/共123頁n n 現在分析算法的復雜度。n n 這里的問題規(guī)模是表的長度，設它的值為這里的問題規(guī)模是表的長度，設它的值為n n。該算法的時間主要花費在循環(huán)的結點后移語句上，該。該算法的時間主要花費在循環(huán)的結點后移語句上，該語句的執(zhí)行次數（即移動結點的次數）語句的執(zhí)行次數（即移動結點的次數）不僅依賴于表的長度，而且還與插入位置有關不僅依賴于表的長度，而且還與插入位置有關。n n當當i i=n n+1+1時，由于循環(huán)變量的終值大于初值，結點后移語句將不進行；這是最好情況，其時間復雜度時，由于循環(huán)變量的終值大于初值，結點后移語句將不進行；這是最好情況，其時間復雜度O O（1 1）；）；n n當當i i=1=1時，結點后移語句將循環(huán)執(zhí)行時，結點后移語句將循環(huán)執(zhí)行n n次，需移動表中所有結點，這是最壞情況，其時間復雜度為次，需移動表中所有結點，這是最壞情況，其時間復雜度為O O（n n）。）。n n由于插入可能在表中任何位置上進行，因此需分析算法的平均復雜度由于插入可能在表中任何位置上進行，因此需分析算法的平均復雜度動畫第42頁/共123頁在長度為在長度為n n的線性表中第的線性表中第i i個位置上插入一個結點，令個位置上插入一個結點，令E Eis is(n n)表示移動結點的期望值（即移動的平均次數），表示移動結點的期望值（即移動的平均次數），則在第則在第i i個位置上插入一個結點的移動次數為個位置上插入一個結點的移動次數為n n-i i+1+1。故。故 E Eis is(n n)=)=p pi i(n n-i i+1)+1)不失一般性，假設在表中任何位置不失一般性，假設在表中任何位置(1 1i in n+1+1)上插入結點的機會是均等的，則上插入結點的機會是均等的，則 p p1 1=p p2 2=p p3 3=p p n n+1+1=1/(=1/(n n+1)+1)因此，在等概率插入的情況下，因此，在等概率插入的情況下，E Eis is(n n)=)=(n n-i i+1)/(+1)/(n n+1)=+1)=n n/2/2也就是說，在順序表上做插入運算，平均要移動表上一半結點。當表長也就是說，在順序表上做插入運算，平均要移動表上一半結點。當表長n n較大時，算法的效率相當低。較大時，算法的效率相當低。雖然雖然E Eis is(n n)中中n n的系數較小，但就數量級而言，它仍然是線性階的。因此算法的平均時間復雜度為的系數較小，但就數量級而言，它仍然是線性階的。因此算法的平均時間復雜度為O O(n n)。順序表操作第43頁/共123頁順序表的刪除順序表的刪除線性表的刪除運算是指將表的第i(1in)結點刪除，使長度為n的線性表：(a1，a i-1，ai，a i+1，an)變成長度為n-1的線性表 (a1，a i-1，a i+1，an)第44頁/共123頁返回第45頁/共123頁pp 順序表刪除操作順序表刪除操作順序表刪除操作順序表刪除操作V1.0(V1.0(指針法指針法指針法指針法)：刪除元素時，注意線性表的邏輯結構發(fā)生什么變化？刪除元素時，注意線性表的邏輯結構發(fā)生什么變化？刪除元素時，注意線性表的邏輯結構發(fā)生什么變化？刪除元素時，注意線性表的邏輯結構發(fā)生什么變化？(a a1 1,a ai i-1-1,a ai i,a ai i+1+1,a an n)變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)?(a a1 1,a ai i-1-1,a ai i+1+1,a an n)Status Status ListDelete_SqListDelete_Sq(SqList&L,int pos,ElemType&e)(SqList&L,int pos,ElemType&e)/在順序線性表在順序線性表在順序線性表在順序線性表L L中刪除第中刪除第中刪除第中刪除第pospos個元素，并用個元素，并用個元素，并用個元素，并用e e返回其值。返回其值。返回其值。返回其值。if(posL.length)return ERROR;if(posL.length)return ERROR;/刪除位置不合刪除位置不合刪除位置不合刪除位置不合法法法法 p=&L.elempos-1;p=&L.elempos-1;/p/p為被刪除元素的地址為被刪除元素的地址為被刪除元素的地址為被刪除元素的地址 e=*p;e=*p;/被刪除元素的值賦給被刪除元素的值賦給被刪除元素的值賦給被刪除元素的值賦給e e q=L.elem+L.length-1;q=L.elem+L.length-1;/表尾元素的地址表尾元素的地址表尾元素的地址表尾元素的地址 for(+p;p=q;p+)for(+p;p=q;p+)*(p-1)=*p;*(p-1)=*p;/被刪除位置后元素上移被刪除位置后元素上移被刪除位置后元素上移被刪除位置后元素上移 L.length-;L.length-;/表長減表長減表長減表長減1 1 return OK;return O