第2章 線性表_1

1、數據結構數據結構2015-2016-2渭南師范學院渭南師范學院 2015級級第第2章章 線性表線性表n2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義 n2.2 線性表的順序存儲線性表的順序存儲n小結小結2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構圖圖2.1 線性表的邏輯結構線性表的邏輯結構 2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構 線性表(Linear List)是由n (n0)個類型相同的數據元素a1, a2, ，

2、an組成的有限序列，記作（a1, a2, ，ai-1，ai，ai+1， ，an）。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構 線性表中相鄰數據元素之間存在著序偶關系，即對于非空的線性表（a1, a2, ，ai-1, ai, ai+1, , an）， 表中ai-1 領先于ai，稱ai-1 是ai的直接前驅直接前驅，而稱ai是 ai-1的直接后繼直接后繼。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構第一個元素a1無直接前驅，最后一個元素an無直接后繼

3、，其余元素有且僅有一個直接前驅和直接后繼。 線性表中元素的個數n被定義為線性表的長度，被定義為線性表的長度，n=0時稱為空表時稱為空表。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構例如： 英文字母表(A, B, , Z)就是一個簡單的線性表。在較為復雜的線性表中，數據元素可由若干數據項組成。如學生成績表中，每個學生及其各科成績是一個數據元素，它由學號、姓名、各科成績及平均成績等數據項(item) 組成。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.1 線性表的邏輯結構線性表的邏輯結構線

4、性表的特點：數據元素同類型。：數據元素有限，表長即數據元素個數。：線性表中相鄰數據元素之間存在著序偶關系。 矩陣、數組、字符串、堆棧、 隊列等都符合線性條件。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類型定義線性表的抽象數據類型定義ADT LinearList 數據元素數據元素：D=ai| aiD0, i=1, 2, ，n, n0 ， D0為某一數據對象 關系：關系： | ai, ai+1D0，i=1, 2, , n-1 基本操作：基本操作：2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的

5、抽象數據類型定義線性表的抽象數據類型定義InitList(L)操作前提：L為未初始化線性表。 操作結果：將L初始化為空表。ListLength(L)操作前提：線性表L已存在。 操作結果：如果L為空表則返回0，否則返回表中的元素個數。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類型定義線性表的抽象數據類型定義GetData(L, i)操作前提：表L存在，且i值合法，即1iListLength(L)。操作結果：返回線性表L中第i個元素的值。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據

6、類型定義線性表的抽象數據類型定義InsList(L, i, e)操作前提：表L已存在，e為合法元素值且1iListLength(L)+1。 操作結果：在L中第i個位置前插入新的數據元素e，L的長度加1。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類型定義線性表的抽象數據類型定義DelList(L, i, &e)操作前提：表L已存在且非空，1iListLength(L)。 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類

7、型定義線性表的抽象數據類型定義Locate(L, e)操作前提：表L已存在，e為合法數據元素值。操作結果：如果L中存在元素e，則將“當前指針”指向元素e所在位置并返回TRUE，否則返回FALSE。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類型定義線性表的抽象數據類型定義DestroyList(L)操作前提：線性表L已存在。 操作結果：將L銷毀。ClearList(L)操作前提：線性表L已存在 。 操作結果：將表L置為空表。2.1 線性表的概念及其抽象數據類型定義線性表的概念及其抽象數據類型定義n2.1.2 線性表的抽象數據類型定義線性

8、表的抽象數據類型定義EmptyList(L)操作前提：線性表L已存在。 操作結果：如果L為空表則返回TRUE，否則返回FALSE。 ADT LinearList2.2 線性表的順序存儲線性表的順序存儲n2.2.1 線性表的順序存儲結構線性表的順序存儲結構線性表的順序存儲是指用一組地址連續(xù)的存儲單指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，單元中，即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系。采用順序存儲結構的線

9、性表通常稱為。2.2 線性表的順序存儲線性表的順序存儲n2.2.1 線性表的順序存儲結構線性表的順序存儲結構假設線性表中有n個元素，每個元素占k個單元，第一個元素的地址為Loc(a1)，則可以通過如下公式計算出第i個元素的地址Loc(ai)： Loc(ai) =Loc(a1)+(i-1)k其中Loc(a1)稱為基地址。2.2 線性表的順序存儲線性表的順序存儲內存空間狀態(tài)a1a2aianLoc(a1)Loc(a1)+k存儲(物理)地址邏輯地址12in空閑Loc(a1)+(i-1)kLoc(a1)+(n-1)k圖圖2.2 順序表存儲示意圖順序表存儲示意圖2.2 線性表的順序存儲線性表的順序存儲n2

10、.2.1 線性表的順序存儲結構線性表的順序存儲結構順序存儲結構可以借助于高級程序設計語言中的一維數組來表示，一維數組的下標與元素在線性表中的序號相對應。2.2 線性表的順序存儲線性表的順序存儲n2.2.1 線性表的順序存儲結構線性表的順序存儲結構的C語言定義：#define MAXSIZE 100typedef struct ElemType elemMAXSIZE; /* 線性表占用的數組空間線性表占用的數組空間 */ int last; /* 指向線性表中最后一個元素指向線性表中最后一個元素,空表時置為空表時置為-1 */SeqList; /* 順序表類型名是順序表類型名是SeqList,

11、見教材見教材P40*/若有若有SeqList L;則元素則元素ai在內存中為在內存中為L.elemi-1若有若有SeqList *L;且且L有指向，則元素有指向，則元素ai在內存中為在內存中為L-elemi-12.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算1. 查找操作查找操作 線性表有兩種基本的查找運算。按序號查找GetData(L, i)：要求查找線性表L中第i個數據元素，其結果是L.elemi-1。按內容查找Locate(L, e)：要求查找線性表L中與給定值e相等的數據元素。若在表L中找到與e相等的元素，則返回該元素在

12、表中的序號；若找不到， 則返回一個“空序號”-1。2.2 線性表的順序存儲線性表的順序存儲【算法算法2.1 順序表的按內容查找運算順序表的按內容查找運算】/* 在順序表在順序表L中查找與中查找與e相等的元素，若相等的元素，若L.elemi=e，則找到該元素，并返回序號，則找到該元素，并返回序號i+1，若找不到，則返回，若找不到，則返回-1 */問題：該算法的參數有哪些?類型分別是什么？在順序表在順序表L中查找中查找，所以一個參數是L，其類型是？查找與查找與e相等的元素相等的元素，所以一個參數是e，其類型是？2.2 線性表的順序存儲線性表的順序存儲【算法算法2.1 順序表的按內容查找運算順序表的

13、按內容查找運算】/* 在順序表在順序表L中查找與中查找與e相等的元素，若相等的元素，若L.elemi=e，則找到該元素，并返回序號，則找到該元素，并返回序號i+1，若找不到，則返回，若找不到，則返回-1 */int Locate(SeqList L,ElemType e) i=0 ; /* i為掃描計數器，初值為為掃描計數器，初值為0，即從線性表第一個元素開始比較，即從線性表第一個元素開始比較 */while ( (i=L.last)&(L.elemi!=e) ) /* 順序掃描表順序掃描表L,直到找到值為直到找到值為e i+; 的元素的元素,或掃描到表尾而沒找到或掃描到表尾而沒找到 */ i

14、f (ilast+1，i的合法取值范圍是的合法取值范圍是 1iL-last+2 */#define OK 1#define ERROR 0int InsList(SeqList *L, int i, ElemType e) /*注意參數注意參數*/ int k; if(iL-last+2) /* 首先判斷插入位置是否合法首先判斷插入位置是否合法 */ printf(插入位置i值不合法); return(ERROR); 2.2 線性表的順序存儲線性表的順序存儲 if(L-last=MAXSIZE-1) printf(表已滿無法插入); return(ERROR); for(k=L-last;k=

15、i-1;k-) /* 從從n-1i-1的所有元素順次后移一個位置的所有元素順次后移一個位置 */ L-elemk+1=L-elemk; L-elemi-1=e; /* 在表在表L的第的第i個位置放入個位置放入e，第，第i個元素的下標為個元素的下標為i-1 */ L-last+; /* last后移一個元素，即表長增后移一個元素，即表長增1 */ return(OK); /* 算法算法2.2結束結束*/2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算【算法分析算法分析】在順序表中插入一個數據元素時，其時間主要耗在順序表中插入一個數

16、據元素時，其時間主要耗費在移動數據元素上。費在移動數據元素上。對于插入算法而言，設對于插入算法而言，設Pi為在第為在第i個元素之前插入個元素之前插入元素的概率，并元素的概率，并假設在任何位置上插入的概率相等假設在任何位置上插入的概率相等，即即Pi=1/(n+1), i=1, 2, ，n+1。2.2 線性表的順序存儲線性表的順序存儲211) 1(11) 1(1111nkninninPEnkniniiinsn2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算設設Eins為在長度為為在長度為n的表中插入一個元素所需移動的表中插入一個元素所需移動元素的平均次數，則：元素的平均次數

17、，則：2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算3. 刪除操作刪除操作 DelList(L, i, &e)線性表的刪除運算是指將表的第i(1in)個元素刪去，使長度為n的線性表(e1，, ei-1，ei，ei+1，en)變成長度為n-1的線性表(e1，, ei-1， ei+1，en)，并將所刪除元素帶回。 算法返回刪除成功或失敗的標志。 故刪除成功時，被刪元素由參數帶回。2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算例如：線性表(4, 9, 15, 21,

18、 28, 30, 30, 42, 51, 62)刪除第5個元素28，則先臨時保存28，再將第6個元素到第10個元素依次向前移動一個位置即可。如圖2.4所示。2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算圖圖2.4 順序表中刪除元素順序表中刪除元素 2.2 線性表的順序存儲線性表的順序存儲【算法算法2.3 順序表的刪除運算順序表的刪除運算】 /*在順序表在順序表L中刪除第中刪除第i個數據元素，函數返回刪除成功與否的標志。個數據元素，函數返回刪除成功與否的標志。并用指針參數并用指針參數e返回已刪除元素的值。返回已刪除元素的值。i的

19、合法取值為的合法取值為1iL.last+1*/ 問題：該算法的參數有哪些?類型分別是什么？在順序表在順序表L中刪除中刪除，所以一個參數是L，其類型是？刪除第刪除第i個數據元素個數據元素，所以一個參數是i，其類型是？用參數用參數e返回已刪元素返回已刪元素，所以一個參數是e，其類型是？2.2 線性表的順序存儲線性表的順序存儲【算法算法2.3 順序表的刪除運算順序表的刪除運算】 /*在順序表在順序表L中刪除第中刪除第i個數據元素，函數返回刪除成功與否的標志。個數據元素，函數返回刪除成功與否的標志。并用指針參數并用指針參數e返回已刪除元素的值。返回已刪除元素的值。i的合法取值為的合法取值為1iL.la

20、st+1*/ int DelList(SeqList *L, int i, ElemType *e) int k; if(iL-last+1) printf(刪除位置不合法！); return(ERROR); 2.2 線性表的順序存儲線性表的順序存儲 *e=L-elemi-1; /* 將待刪的第將待刪的第i個元素存放到個元素存放到e所指向的變量中所指向的變量中 */ for(k=i;ilast;k+) /* 第第i+1個往后個往后(下標下標in)的元素順次前移的元素順次前移 */ L-elemk-1=L-elemk; L-last-; return(OK); 2.2 線性表的順序存儲線性表的順

21、序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算在順序表中刪除一個數據元素時，其時間主要耗費在移動數據元素上。對于刪除算法而言，設Qi為刪除第i個元素的概率，并假設在任何位置上刪除的概率相等，即Qi=1/n, i=1, 2, ，n。刪除一個元素所需移動元素的平均次數Edel為：1011211)(1)(nkniniidelnkninninQE2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算例例2.3:有兩個順序表LA和LB，其元素均為非遞減有序排列。編寫算法，將它們合并成一個順序表LC，要求LC也是

22、非遞減有序排列。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 則LC=(1, 2, 2, 3, 3, 3, 4)。2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算算法思想算法思想：設表LC是一個空表，指針k指向LC當前元素設兩個指針i、j分別指向表LA和LB中的當前元素若LA.elemiLB.elemj，則將LB.elemj插入到表LC中,并將j后移一個元素; k后移一個元素;若LA.elemiLB.elemj，則將LA.elemi插入到表LC ,并將i后移一個元素; k后移一個元素;重復該操作，直到其中一個

23、表被掃描完畢，然后再將未掃描完的表中剩余的所有元素依次放到表LC中。2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算問題問題：該算法的參數是什么？分別是什么類型？方法一：參數：LA，LB；返回值為LC；此時參數LA，LB可為SeqList 型或SeqList *型方法二：參數：LA，LB，LC；無返回值此時參數LA，LB可為SeqList 型或SeqList *型，LC必須為SeqList *型。2.2 線性表的順序存儲線性表的順序存儲【算法算法2.4 線性表的合并運算線性表的合并運算】 void mergeList(SeqLi

24、st *LA, SeqList *LB, SeqList *LC) int i, j, k; i=0; j=0; k=0; /* i,j,k分別指向分別指向LA，LB，LC的當前元素的當前元素*/ while(ilast&jlast) if(LA-elemielemj) LC-elemk=LA-elemi; i+; k+; else LC-elemk=LB-elemj; j+; k+; 2.2 線性表的順序存儲線性表的順序存儲 while(ilast) /* 表表LA未掃描完，將表未掃描完，將表LA剩余元素賦給表剩余元素賦給表LC */ LC-elemk=LA-elemi; i+; k+; w

25、hile(jlast) /* 表表LB未掃描完，將表未掃描完，將表LB剩余元素賦給表剩余元素賦給表LC */ LC-elemk=LB-elemj; j+; k+; LC-last=LA-last+LB-last+1; /* 更新表更新表LC最后一個元素指針，也可為最后一個元素指針，也可為k-1 */ 該算法的時間復雜度為該算法的時間復雜度為O(LA表長表長+LB表長表長)2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算線性表順序存儲的優(yōu)點是：線性表順序存儲的優(yōu)點是： 無需為表示結點間的邏輯關系而增加額外的存儲空間（因為邏輯上相鄰

26、的元素其存儲的物理位置也是相鄰的）； 可方便地隨機存取表中的任一元素。2.2 線性表的順序存儲線性表的順序存儲n2.2.2 線性表順序存儲結構上的基本運算線性表順序存儲結構上的基本運算其缺點是：其缺點是： 插入或刪除運算不方便，除表尾的位置外，在表的其它位置上插入或刪除操作都必須移動大量的元素，其效率較低； 順序表的存儲分配只能預先進行靜態(tài)分配，當表長變化較大時，難以確定合適的存儲規(guī)模。分配空間大，則可能造成一部分空間長期閑置；分配空間小，則插入操作可能使表長超過預先分配的空間而造成溢出。2.2 線性表的順序存儲線性表的順序存儲n有序順序表的合并運算的實現有序順序表的合并運算的實現 算法2.4

27、為有序順序表的合并算法，若實現該算法，則需要補充一些代碼。對照算法2.4，分析如下：算法2.4用到了數據類型SeqList ，所以定義它(P40)； 而定義SeqList時，用到了ElemType和MAXSIZE，定義它們；算法2.4是針對非空的順序表的操作，所以，得創(chuàng)建非空的順序表，所以，程序要包含算法2.2，即順序表的插入運算，用于建立非空順序表。2.2 線性表的順序存儲線性表的順序存儲n有序順序表的合并運算的實現有序順序表的合并運算的實現 算法2.4為有序順序表的合并算法，若實現該算法，則需要補充一些代碼。對照算法2.4，分析如下：當兩個有序表合并完成后,為了看到其合并前和合并后的結果,

28、得輸出有序表,故要增加一個算法,用于輸出順序表；設為 out(SeqList L)有輸出，所以加#include2.2 線性表的順序存儲線性表的順序存儲n有序順序表的合并運算的實現有序順序表的合并運算的實現 算法2.4為有序順序表的合并算法，若實現該算法，則需要補充一些代碼。對照算法2.4，分析如下：編寫main()函數:定義三個順序表:SeqList A,B,C;算法2.2是針對已經存在的順序表的插入，但此時A，B和C的值是不確定的，故要先將三個順序表置為空表A.last=-1;通過多次調用InsList(&A,i,待插元素)創(chuàng)建非空順序表A，B通過調用out(A)輸出表A，B 調用merg

29、eList(&A,&B,&C)生成表C調用out(C)輸出表C2.2 線性表的順序存儲線性表的順序存儲【線性表的合并運算的實現線性表的合并運算的實現】 #include#define MAXSIZE 100#define OK 1#define ERROR 0typedef int ElemType;typedef structElemType elemMAXSIZE; /* 線性表占用的數組空間線性表占用的數組空間 */int last; /* 指向線性表中最后一個元素，空表時置為指向線性表中最后一個元素，空表時置為-1 */SeqList;2.2 線性表的順序存儲線性表的順序存儲int I

30、nsList(SeqList *L,int i,ElemType e) /*算法算法2.2: 順序表插入順序表插入*/int k;if(iL-last+2) /* 首先判斷插入位置是否合法首先判斷插入位置是否合法 */printf(插入位置插入位置i值不合法值不合法);return(ERROR);if(L-last=MAXSIZE-1)printf(表已滿無法插入表已滿無法插入);return(ERROR);for(k=L-last;k=i-1;k-) /* 從從n-1i-1順次向后移動一個位置順次向后移動一個位置 */L-elemk+1=L-elemk;L-elemi-1=e; /* 在表在表L的第的第i個位置放入個位置放入e， 第第i個元素的下標為個元素的下標為i-1 */L-last+; /* last后移一個元素，即表長增后移一個元素，即表長增1 */return(OK); /* 算法算法2.2結束結束*/2.2 線性表的順序存儲線性表的順序存儲void out(SeqList L) /* 輸出函數輸出函數 */int i;for(i=0;i=L.last;i+)printf(%d ,L.elemi);printf(n);2.2 線性表的順序存儲線性表