【正文】 順序表 L中查找第一個與 x值相等的元素。 //順序表長度減 1 } 時間復(fù)雜度： O(n) 刪除元素 : 2022/10/23 18 順序表刪除元素算法分析 ? 主要操作是移動元素。j++) [j1]=[j]。} //檢查空表及刪除位置的合法性 for(j=i。 ???????11)1(niiii n s inpE時間復(fù)雜度： O(n) 2022/10/23 16 順序表上基本運算的實現(xiàn) (3) 刪除運算 :刪除第 i 個元素 e 思想： 把第 i＋ 1個位置開始的元素，依次前移 步驟： ； ； 1。在第 i （ 1≤i≤n+1）個位置上插入 x，需要移動 ni+1個元素。 ∥ 順序表長度增 1 ? return(L)。 ? ∥ 第 i個位置后的數(shù)組元素逐一后移 ? [i1]=x。j=i1。 exit(0)。 exit(0)。 } 順序表的初始化 : 2022/10/23 13 順序表上基本運算的實現(xiàn) (2) 插入運算 :在第 i 個位置，插入元素 e 思想： 把從第 i個位置開始的元素，依次后移 步驟： ？ ？ 。 2022/10/23 12 順序表上基本運算的實現(xiàn) (1) SeqList SeqListInit(SeqList L) {//構(gòu)造一個空的順序表 =0。 ∥ 存放線性表的數(shù)組 int last。 ? 算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu) 2022/10/23 11 線性表的順序表示和實現(xiàn) 線性表的順序表示 :線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為 順序表 。 （ 2）邏輯結(jié)構(gòu)與數(shù)據(jù)元素的 相對位置 無關(guān)。 } return(Lc)。 } while(j=Lb_len) {//La已空，將 Lb表的剩余部分復(fù)制到新表 bj=ListGet (Lb,j++)。} } （ 接下頁 ） 2022/10/23 9 （接上頁） while(i=La_len) {//Lb已空，將 La表的剩余部分復(fù)制到新表 ai=ListGet(La,i++)。} else {ListInsert(Lc,++k,bj)。 if(ai=bj) {ListInsert(Lc,++k,ai)。(j=Lb_len))//La和 Lb均非空 {ai=ListGet(La,i)。 while((i=La_len)amp。 La_len=ListLength(La)。 i=j=1。i++) visit(ListGet(L,i))； } 2022/10/23 8 例 合并線性表 List ListMerge(List La,List Lb) {//La和 Lb是兩個非遞減有序的線性表 ， 將線性表 La和 Lb合并成一個新的線性表 Lc， Lc也非遞減有序 。 else for(i=1。 10. ListDelete(L,i)。 5. ListClear (L) 。第二章 線性表 陳守孔 孟佳娜 陳卓 2022/10/23 2 本章目錄 ? 線性表的類型定義 ? 線性表的概念 ? 線性表的抽象數(shù)據(jù)類型 ? 線性表的順序表示和實現(xiàn) ? 線性表的順序表示 ? 順序表上基本運算的實現(xiàn) ? 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) ? 單鏈表的表示 ? 單鏈表操作的實現(xiàn) ? 線性表實現(xiàn)方法的比較 ? 循環(huán)鏈表 ? 雙鏈表 ? 靜態(tài)鏈表 （ * 算法設(shè)計舉例） 2022/10/23 3 主要內(nèi)容 ?知識點 ? 線性表的定義 ? 順序表 ? 單鏈表 ? 雙鏈表 ? 靜態(tài)鏈表 ?重點難點 ? 順序表操作的實現(xiàn) ? 單鏈表操作的實現(xiàn) ? 順序表和鏈表操作時間復(fù)雜度的分析 ? 靜態(tài)鏈表 2022/10/23 4 線性結(jié)構(gòu) ?在數(shù)據(jù)元素的非空的有限集合中： ? 存在唯一的一個被稱為“ 第一個 ”的數(shù)據(jù)元素； ? 存在唯一的一個被稱為“ 最后一個 ”的數(shù)據(jù)元素； ? 除第一個元素外，集合中每個元素都有且僅有 一個前驅(qū) ； ? 除最后一個元素外，集合中每個元素都有且僅有 一個后繼 ； 2022/10/23 5 線性表 (Linear List)定義 ? 定義： n個具有相同特性的數(shù)據(jù)元素組成的 有限序列； ? 表示： {a1,…,a i1,ai,ai+1,…,a n} ? ai必須具有相同特性，即屬于同一數(shù)據(jù)對象 ? ai1是 ai的直接前驅(qū)元素， ai+1是 ai的直接后繼元素 ? 數(shù)據(jù)元素 ai在線性表中有確定的位置 i， i稱為 位序 ? 線性表中數(shù)據(jù)元素的個數(shù) n稱為線性表的長度 ,n=0時，線性表稱為 空表 2022/10/23 6 抽象數(shù)據(jù)類型定義 ADT List{ 數(shù)據(jù)對象： D={ai|ai∈ ElemSet,i=1,2,…,n,n≥0} 數(shù)據(jù)關(guān)系： R={ai1,ai|ai,ai1∈ D,i=2,…,n} 基本操作： 1. ListInit (L) ； 2. ListLength (L) ； 3. ListGet(L,i) 。 4. ListLocate (L,x) 。 6. ListEmpty (L) ； 7. ListPrior (L,e) ； 8. ListNext(L,e) ； 9. ListInsert(L,i,e) 。 }ADT List 2022/10/23 7 例如 遍歷線性表 L ListTraverse(List L， visit()) {//遍歷線性表 if(ListEmpty(L)) printf(“空表 \n”)。i=ListLength(L)。 ListInit(Lc)。k=0。Lb_len=ListLength(Lb)。amp。 bj=ListGet(Lb,j)。++i。++j。 ListInsert(Lc,++k,ai)。 ListInsert(Lc,++k,bj)。 }//ListMerge 例 合并線性表 2022/10/23 10 邏輯結(jié)構(gòu)是本質(zhì) 通過上面兩個例子可以看出： ? 邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西 ： （ 1）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的 形式、內(nèi)容 無關(guān)。 （ 3）邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的 個數(shù) 無關(guān)。 設(shè) a１ 的存儲地址為 Loc(a１ )，每個數(shù)據(jù)元素占 L個存儲單元，則第 i個數(shù)據(jù)元素的地址為： Loc(ai)=Loc(a1)+(i1)*L 1≤ i≤ n 0 1 i1 i n1 MAXSIZE1 a1 a2 … ai … an … data ai1 ai+1 順序存儲結(jié)構(gòu)的線性表的類型定義如下： define MAXSIZE 100 ∥ 順序表的最大容量 typedef struct {ElemType data[MAXSIZE]。 ∥ last是線性表的長度 }SeqList。 //初始化順序表為空表 return L。 2022/10/23 14 順序表上基本運算的實現(xiàn) (2) ? SeqList SeqListInsert(SeqList L， int i， ElemType x) ? {∥ 在順序表中的第 i 個位置插入元素 x ? if(==MAXSIZE) ? {printf(＂表滿 \n＂ )。 } ∥ 表滿，退出 ? if(i1 || i+1) ? {printf(＂插入位置錯 \n＂ )。 } ∥ 插入位置錯，退出 ? for(j=。j) ? [j+1]=[j]。 ∥ 新元素插入到第 i個位置 ?