數據結構線性表(順序表)講解

1、第二章 線性表 順序表 線性結構四大特點 第一個元素無直接前驅第一個元素無直接前驅 最后一個元素無直接后繼最后一個元素無直接后繼 除第一個元素外，其他每個數據元素除第一個元素外，其他每個數據元素 都有唯一一個直接前驅都有唯一一個直接前驅 除最后一個元素外，其他每個數據元除最后一個元素外，其他每個數據元 素都有唯一一個直接后面素都有唯一一個直接后面 線性表 定義定義 記法記法 特點特點 結構結構 基本術語基本術語 空表、表長 直接前驅、直接后繼 位序 最基本、最常用的線性結構。若最基本、最常用的線性結構。若n(nn(n0) )個個 數據特性相同的數據元素組成的有限序列數據特性相同的數據元素組成的

2、有限序列 。 （a1,a2,ai-1,ai,ai+1,an) 1.同一線性表中的數據元素必須具有相同特性 2.具有線性結構的四大特性 3.數據元素之間存在序偶關系 邏輯結構（1對1）、物理結構（順序存儲和鏈式存儲） 線性表的抽象數據類型 數據對象數據對象 數據關系數據關系 操作集操作集 初始化、銷毀、查找、插入、刪除、求前驅（后繼）、遍歷 線性表中的數據元素具有相同特性線性表中的數據元素具有相同特性 相鄰數據元素之間存在序偶關系相鄰數據元素之間存在序偶關系 線性表的基本操作聲明線性表的基本操作聲明 僅是模型定義，不涉及模型實現，參數不必考慮具僅是模型定義，不涉及模型實現，參數不必考慮具 體數據

3、類型，實際應用中，具體問題具體分析。體數據類型，實際應用中，具體問題具體分析。 順序表 定義定義 特點特點 C C描述描述 基本形態(tài)基本形態(tài) 基本操作實現基本操作實現 用一組地址連續(xù)地址連續(xù)的存儲單元依次存放依次存放線性表中的數 據元素。采用這種存儲結構的線性表叫做順序表順序表。 a1 a2 ai-1 ai an 基地址基地址 1.數據元素在“邏輯邏輯關系上的相鄰相鄰”用“物理地址相鄰物理地址相鄰”來 表示。 2.順序表中任一元素都可“隨機存取隨機存取”。 typedef struct SqList; / 俗稱 順序順序 表表 #define MAXSIZE 100 / 線性表存儲空間的分配量

4、，即數組長度 ElemType elemMAXSIZE; int length; / 當前長度 順序表的C描述 順序表空：條件順序表空：條件 L.length=0 不允許刪除操作 順序表滿：順序表滿： 條件 L.length=MAXSIZE 不允許插入操作 不空也不滿：不空也不滿： 可以插入，刪除操作 順序表的基本形態(tài) 順序表- 基本算法 根據順序表的實現形式，表長根據順序表的實現形式，表長length是類型定義是類型定義 的屬性，可以實現求表長、初始化、取值、判空的屬性，可以實現求表長、初始化、取值、判空 等操作，時間復雜度均為等操作，時間復雜度均為O(1)。 而遍歷算法、查找表中元素的存在

5、、插入、刪除而遍歷算法、查找表中元素的存在、插入、刪除 等操作，時間復雜度均為等操作，時間復雜度均為O(n)。 （1）初始化 空表 時間復雜為：O(1) 順序表- 基本算法 L.length=0； （2）判空 時間復雜為：O(1) 順序表- 基本算法 if(L.length=0) return OK; else return ERROR; （3）求表長 時間復雜為：O(1) 順序表- 基本算法 return L.length； （4）取元素（取第i個元素e） 時間復雜為：O(1) 順序表- 基本算法 e=L.elemi-1; i合法 if(i=1 return OK; else return

6、ERROR; 順序表- 基本算法 （5）遍歷 for ( i=1; i=L.length; i+ ) visit( L.elemi-1 ); 時間復雜為：O(L.length) 順序表- 基本算法 （6）查找 搜索順序表中是否存在指定 的數據元素。存在，查找成 功；否則，查找失敗。 例如：順序表 23 75 41 38 54 62 17 L.elem0 L.length-1 e =38 i 1 2 3 4 1 8 50 可見，基本操作是： 將順序表中的元素 逐個和給定值 e 相比較。 算法的算法的時間復雜度時間復雜度為：為： O( L.length ) int LocateElem(SqLis

7、t L,Elemtype e) for(i=1 ;i=L.length;i+) if(e=L.elemi-1) return i; return 0; 順序表- 基本算法 （7）插入 在順序表中插入指定的數據元素， 插入成功，表長增1。 線性表操作 ListInsert( j- ) /元素后移 L.elemj = L.elemj-1; L.elemi-1 = e; / 插入e L.length+; / 表長增1 return OK; / 插入成功 else return ERROR; 插入算法時間復雜度分析：插入算法時間復雜度分析： 考慮移動元素的平均情況考慮移動元素的平均情況 插入位置插入位

8、置需要移動的結點次數需要移動的結點次數 1n 2 n-1 n1 n+10 平均次數平均次數: (1+2+n-1+n)/(n+1) =n/2 T(n)=O(n) 順序表- 基本算法 （8）刪除 在順序表中刪除指定位置的數據 元素，刪除成功，表長減1。 線性表操作 ListDelete( for ( j=i+1; j=L.length; j+ ) /元素前移 L.elemj-2 = L.elemj-1; L.length-; / 表長減1 return OK; / 刪除成功 else return ERROR; 刪除算法時間復雜度分析：刪除算法時間復雜度分析： 考慮移動元素的平均情況考慮移動元素的

9、平均情況 刪除位置刪除位置需要移動的結點次數需要移動的結點次數 1n-1 2 n-2 n0 平均次數平均次數: (0+1+n-11)/n =(n-1)/2 T(n)=O(n) 時間復雜度為O(1) 順序表- 基本算法 （9）求前驅 pre=L.elemi-2; 在順序表中查找元素cur_e，位序為i i=LocateElem(L,cur_e); cur_e是順序表中元素，但不是第一個元素 便有直接前驅pre 順序表- 基本算法 （10）求后繼 next=L.elemi; 在順序表中查找元素cur_e，位序為i i=LocateElem(L,cur_e); cur_e是順序表中元素，但不是最后一

10、個元 素便有直接后繼next 時間復雜度為O(1) 順序表- 經典算法分析 n n 1 1i i 2 2 1 1n n i i) )( (n n n n 1 1 算法插入刪除 基本操作移動元素移動元素 平均移動 次數 時間復雜 度 O(nO(n) )O(nO(n) ) 最好情況在n+1處插入，不需移動刪除第n個，不需移動 1 1n n 1 1i i 2 2 n n 1 1) )i i( (n n 1 1n n 1 1 線性表應用舉例 例例1 1：合并線性表：合并線性表 例例2 2：歸并線性表：歸并線性表 例1：合并線性表 假設有兩個集合 A 和 B 分別用兩個線性 表 LA 和 LB 表示，即

11、：線性表中的數據 元素即為集合中的成員。現要求一個新的 集合AAB。去掉重復元素去掉重復元素 擴大線性表LA，將存在于線性表LB 中而不存在于線性表LA中的數據元 素插入到線性表LA中去。 問題分析問題分析： 1從線性表LB中依次取得每個數據元素; 2依值在線性表LA中進行查訪; 3若不存在，則插入之。 GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e) 操作步驟：操作步驟： GetElem(Lb, i, e); / 取取Lb中第中第i個數據元素賦給個數據元素賦給e if (!LocateElem(La, e, e

12、qual( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數據元素，則插入之相同的數據元素，則插入之 void union(List / 求線性表的長度求線性表的長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 算法分析 時間復雜度：時間復雜度： O(O(ListLength(LAListLength(LA) )* *ListLength(LBListLength(LB) ) ) 空間復雜度：空間復雜度： O(O(1 1) ) 例2：歸并線性表 已知線性表LA

13、和LB中的數據元素按值非遞 減有序排列，現要求將LA和LB歸并為一個 新的線性表LC，且LC中的數據元素仍按值 非遞減有序排列。 不去掉重復元素不去掉重復元素 LC中的數據元素或是LA中的數據元素，或 是LB中的數據元素。則先設LC為空表，然 后將LA或LB中的元素逐個插入到LC中。為 使LC表按值非遞減有序排列，可設兩個整 型變量i、j，分別指向LA和LB，比較i、j 所指元素的大小，決定哪個元素插入LC。 插入后，在LA 或LB 中順序后移。 問題分析問題分析： void MergeList(List La, List Lb, List / 構造空的線性表 Lc i = j = 1; k

14、= 0; La_len = ListLength(La); Lb_len = ListLength(Lb); GetElem(La, i, ai); GetElem(Lb, j, bj); if(ai=bj) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i = La_len) / 當La不空時 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 當Lb不空時 GetElem(Lb

15、, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素 算法分析 時間復雜度：時間復雜度： O(O(ListLength(LA)ListLength(LA)+ +ListLength(LBListLength(LB) ) ) 空間復雜度：空間復雜度： O(O(ListLength(LA)ListLength(LA)+ +ListLength(LBListLength(LB) ) ) void MergeList(SqList La,SqList Lb,SqList pb=Lb.elem; Lc.length =La.length+Lb

16、.length; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last else *pc+ = *pb+; while(pa=pa_last)*pc+=*pa+; while(pb=pb_last)*pc+=*pb+; if( *pa*pb ) *pc+ =*pa+; else if(*pa=*pb) *pc+=*pa+;pb+; else *pc+ = *pb+; 一元多項式 Pn(x)=p0+p1x+p2x2+p3x3+pnxn Qn(x)=q0+q1x+q2x2+q3x3+