數(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ù)元素組成的有限序列。（a1,a2,ai-1,ai

2、,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ǔ)）線性表的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象數(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ù)類型，實(shí)際應(yīng)用中，具體問題具體分析。體數(shù)據(jù)類型，實(shí)際應(yīng)用中，具體問題具

3、體分析。順序表定義定義特點(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ǔ)空間的分配量，即數(shù)組長度ElemType elemMAXSIZE; int length; / 當(dāng)前長度順序表的

4、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)。而遍歷算法、查找表中元素的存在、插入、刪除而遍歷算法、查找表中元素的存在、插入、刪除等操作，時(shí)間復(fù)雜度均為等操作，時(shí)間復(fù)雜度均為O(n)。（1）初始化空

5、表時(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&i=L.length)e=L.elemi-1;return OK;else return ERROR;順序表- 基本算法（5）遍歷for ( i=1; i=L.length; i+ ) visit(

6、L.elemi-1 );時(shí)間復(fù)雜為：O(L.length)順序表- 基本算法（6）查找搜索順序表中是否存在指定的數(shù)據(jù)元素。存在，查找成功；否則，查找失敗。例如：順序表23 75 41 38 54 62 17L.elem0L.length-1e =38i 1 2 3 4 1 850可見，基本操作是：將順序表中的元素逐個(gè)和給定值 e 相比較。算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為：為： O( L.length )int LocateElem(SqList L,Elemtype e)for(i=1 ;i=L.length;i+)if(e=L.elemi-1)return i;return 0;順序表-

7、基本算法（7）插入在順序表中插入指定的數(shù)據(jù)元素，插入成功，表長增1。線性表操作 ListInsert(&L, i, e)的實(shí)現(xiàn)：首先分析首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？ (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加 必備條件：表存在且不滿 i值的合法性檢查：1L.length+1 將第i個(gè)到最后1個(gè)元素依次后移一個(gè)位置； 在i個(gè)位置插入元素； 表長增加1 。分析分析：21 18 30 75 42 56 87

8、21 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-1087564266O( L.length )算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為：為：Status ListInsert ( SqList &L, int i, ElemType e) if ( i=1&i=i; j- ) /元素后移L.elemj = L.elemj-1; L.elemi-1 = e; / 插入e L.length+; / 表長增1 return OK; / 插入成功 elsereturn ERROR; 插入算法時(shí)間復(fù)雜度分析：插入算法時(shí)間復(fù)雜度分析： 考慮移動(dòng)元素的

9、平均情況考慮移動(dòng)元素的平均情況插入位置插入位置需要移動(dòng)的結(jié)點(diǎn)次數(shù)需要移動(dòng)的結(jié)點(diǎn)次數(shù)1n2n-1n1n+10平均次數(shù)平均次數(shù):(1+2+n-1+n)/(n+1)=n/2T(n)=O(n)順序表- 基本算法（8）刪除在順序表中刪除指定位置的數(shù)據(jù)元素，刪除成功，表長減1。線性表操作 ListDelete(&L, i, &e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1 an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai

10、-1 必備條件：表非空 i值的合法性檢查：1L.length 取出第i個(gè)元素； 第i個(gè)元素以后的元素向前移動(dòng)一個(gè)位置； 表長減小1 。分析分析：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756例如：ListDelete_Sq(L, 5, e) p算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: : O( L.length)Status ListDelete ( SqList &L, int i, ElemType &e) if ( i=1&i=L.length )e=L.elemi-1; for ( j=i+1; j=L.lengt

11、h; j+ ) /元素前移L.elemj-2 = L.elemj-1; L.length-; / 表長減1 return OK; / 刪除成功 elsereturn ERROR; 刪除算法時(shí)間復(fù)雜度分析：刪除算法時(shí)間復(fù)雜度分析： 考慮移動(dòng)元素的平均情況考慮移動(dòng)元素的平均情況刪除位置刪除位置需要移動(dòng)的結(jié)點(diǎn)次數(shù)需要移動(dòng)的結(jié)點(diǎn)次數(shù)1n-12n-2n0平均次數(shù)平均次數(shù):(0+1+n-11)/n=(n-1)/2T(n)=O(n)時(shí)間復(fù)雜度為O(1)順序表- 基本算法（9）求前驅(qū)pre=L.elemi-2; 在順序表中查找元素cur_e，位序?yàn)閕i=LocateElem(L,cur_e);cur_e是順序

12、表中元素，但不是第一個(gè)元素便有直接前驅(qū)pre 順序表- 基本算法（10）求后繼next=L.elemi;在順序表中查找元素cur_e，位序?yàn)閕i=LocateElem(L,cur_e);cur_e是順序表中元素，但不是最后一個(gè)元素便有直接后繼next時(shí)間復(fù)雜度為O(1)順序表- 經(jīng)典算法分析n n1 1i i2 21 1n ni i) )( (n nn n1 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 n1 1i i2 2n n1 1) )i i( (n n1 1n n1 1線性表

13、應(yīng)用舉例例例1 1：合并線性表：合并線性表例例2 2：歸并線性表：歸并線性表例1：合并線性表假設(shè)有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。現(xiàn)要求一個(gè)新的集合AAB。去掉重復(fù)元素去掉重復(fù)元素?cái)U(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)操作步驟：操作步驟：

14、 GetElem(Lb, i, e); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之void union(List &La, List Lb) La_len = ListLength(La); / 求線性表的長度求線性表的長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union算法分析時(shí)間復(fù)雜度：時(shí)間復(fù)雜

15、度：O(O(ListLength(LAListLength(LA) )* *ListLength(LBListLength(LB) ) )空間復(fù)雜度：空間復(fù)雜度：O(O(1 1) )例2：歸并線性表已知線性表LA和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è)元素插

16、入LC。插入后，在LA 或LB 中順序后移。問題分析問題分析：void MergeList(List La, List Lb, List &Lc) / 本算法將非遞減的有序表 La 和 Lb 歸并為 Lc / 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 = L

17、istLength(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, j+, bj); ListInsert(Lc, +k, bj); / 插入插

18、入 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 &Lc)pa=La.elem;pb=Lb.elem;Lc.length =La.length+Lb.length;pc=Lc.elem;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if( *pa=*pb )*pc+ =*pa+;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+;一