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

1、第二章 線性表 順序表 線性結(jié)構(gòu)四大特點(diǎn) 第一個(gè)元素?zé)o直接前驅(qū)第一個(gè)元素?zé)o直接前驅(qū) 最后一個(gè)元素?zé)o直接后繼最后一個(gè)元素?zé)o直接后繼 除第一個(gè)元素外，其他每個(gè)數(shù)據(jù)元素除第一個(gè)元素外，其他每個(gè)數(shù)據(jù)元素 都有唯一一個(gè)直接前驅(qū)都有唯一一個(gè)直接前驅(qū) 除最后一個(gè)元素外，其他每個(gè)數(shù)據(jù)元除最后一個(gè)元素外，其他每個(gè)數(shù)據(jù)元 素都有唯一一個(gè)直接后面素都有唯一一個(gè)直接后面 線性表 定義定義 記法記法 特點(diǎn)特點(diǎn) 結(jié)構(gòu)結(jié)構(gòu) 基本術(shù)語基本術(shù)語 空表、表長 直接前驅(qū)、直接后繼 位序 最基本、最常用的線性結(jié)構(gòu)。若最基本、最常用的線性結(jié)構(gòu)。若n(nn(n0) )個(gè)個(gè) 數(shù)據(jù)特性相同的數(shù)據(jù)元素組成的有限序列數(shù)據(jù)特性相同的數(shù)據(jù)元素組成的

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

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

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

5、、插入、刪除而遍歷算法、查找表中元素的存在、插入、刪除 等操作，時(shí)間復(fù)雜度均為等操作，時(shí)間復(fù)雜度均為O(n)。 （1）初始化 空表 時(shí)間復(fù)雜為：O(1) 順序表- 基本算法 L.length=0； （2）判空 時(shí)間復(fù)雜為：O(1) 順序表- 基本算法 if(L.length=0) return OK; else return ERROR; （3）求表長 時(shí)間復(fù)雜為：O(1) 順序表- 基本算法 return L.length； （4）取元素（取第i個(gè)元素e） 時(shí)間復(fù)雜為：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 ); 時(shí)間復(fù)雜為：O(L.length) 順序表- 基本算法 （6）查找 搜索順序表中是否存在指定 的數(shù)據(jù)元素。存在，查找成 功；否則，查找失敗。 例如：順序表 23 75 41 38 54 62 17 L.elem0 L.length-1 e =38 i 1 2 3 4 1 8 50 可見，基本操作是： 將順序表中的元素 逐個(gè)和給定值 e 相比較。 算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為：為： 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）插入 在順序表中插入指定的數(shù)據(jù)元素， 插入成功，表長增1。 線性表操作 ListInsert( j- ) /元素后移 L.elemj = L.elemj-1; L.elemi-1 = e; / 插入e L.length+; / 表長增1 return OK; / 插入成功 else return ERROR; 插入算法時(shí)間復(fù)雜度分析：插入算法時(shí)間復(fù)雜度分析： 考慮移動(dòng)元素的平均情況考慮移動(dòng)元素的平均情況 插入位置插入位

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

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

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

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

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

13、和LB中的數(shù)據(jù)元素按值非遞 減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè) 新的線性表LC，且LC中的數(shù)據(jù)元素仍按值 非遞減有序排列。 不去掉重復(fù)元素不去掉重復(fù)元素 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 中順序后移。 問題分析問題分析： void MergeList(List La, List Lb, List / 構(gòu)造空的線性表 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) / 當(dāng)La不空時(shí) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 當(dāng)Lb不空時(shí) GetElem(Lb

15、, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素 算法分析 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度： O(O(ListLength(LA)ListLength(LA)+ +ListLength(LBListLength(LB) ) ) 空間復(fù)雜度：空間復(fù)雜度： 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+; 一元多項(xiàng)式 Pn(x)=p0+p1x+p2x2+p3x3+pnxn Qn(x)=q0+q1x+q2x2+q3x3+