數據結構第二章線性表

1、單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級1第二章第二章 線性表線性表2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示與實現線性表的順序表示與實現2.3 線性表的鏈式表示與實現線性表的鏈式表示與實現2.4 一元多項式的表示及相加一元多項式的表示及相加單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級2學習目標學習目標 了解線性表的邏輯結構特性是數據元素之間存在著線

2、性了解線性表的邏輯結構特性是數據元素之間存在著線性關系。在計算機中表示這種關系的兩類不同的存儲結構關系。在計算機中表示這種關系的兩類不同的存儲結構是是順序存儲結構順序存儲結構和和鏈式存儲結構。鏈式存儲結構。 熟練掌握這兩類存儲結構的描述方法以及線性表的基本熟練掌握這兩類存儲結構的描述方法以及線性表的基本操作在這兩種存儲結構上的實現。操作在這兩種存儲結構上的實現。 能夠從時間和空間復雜度的角度綜合比較線性表兩種存能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合。儲結構的不同特點及其適用場合。 結合線性表類型的定義增強對抽象數據類型的理解。結合線性表類型的定義增強對抽象

3、數據類型的理解。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級3重點難點重點難點 鏈表鏈表 指針操作和內存動態(tài)分配的編程技術；指針操作和內存動態(tài)分配的編程技術； 鏈表中指針鏈表中指針 p 和結點和結點 *p 之間的對應關系；之間的對應關系； 頭結點、頭指針和首元結點的不同；頭結點、頭指針和首元結點的不同； 循環(huán)鏈表、雙向鏈表的特點。循環(huán)鏈表、雙向鏈表的特點。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四

4、級第四級 第五級第五級4線性結構的特點線性結構的特點 在數據元素的在數據元素的非空有限集中非空有限集中存在唯一一個被稱做存在唯一一個被稱做“第一個第一個”的數據元素；的數據元素； 存在唯一一個被稱做存在唯一一個被稱做“最后一個最后一個”的數據元素；的數據元素；除第一個數據元素之外，每個元素都除第一個數據元素之外，每個元素都只有一個只有一個前驅前驅； 除最后一個數據元素之外，每個元素都除最后一個數據元素之外，每個元素都只有一只有一個后繼個后繼。 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五

5、級52.1線性表的類型定義線性表的類型定義 線性表：是線性表：是n個數據元素的個數據元素的有限序列。有限序列。 除了第一個元素沒有直接前驅和最后一個元素沒有直接除了第一個元素沒有直接前驅和最后一個元素沒有直接后繼之外，其余的每個數據元素只有一個后繼之外，其余的每個數據元素只有一個直接前驅直接前驅和一和一個個直接后繼直接后繼。niaaaa,21如例例學號姓名年齡001張三18002李四19數據元素數據元素單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級6線性表的特征線性表的特征 有窮性：由有

6、限個元素組成，元素個數有窮性：由有限個元素組成，元素個數n表長度，表長度，n=0空空表表。 設線性表為設線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱稱 i 為為 ai 在線性在線性表中的表中的位序位序。 有序性：線性表元素之間存在序偶關系，有序性：線性表元素之間存在序偶關系，1in時時 ai的直接前驅是的直接前驅是ai-1，a1無直接前驅無直接前驅 ai的直接后繼是的直接后繼是ai+1，an無直接后繼無直接后繼 同一性：線性表由同類數據元素組成，每一個元素都屬于同同一性：線性表由同類數據元素組成，每一個元素都屬于同一數據對象一數據對象單擊此處編輯母版標題樣式單擊此處

7、編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級7線性表抽象數據類型定義：線性表抽象數據類型定義： ADT List 數據對象：數據對象：D ai | ai ElemSet, i=1,2,.,n, n0 數據關系：數據關系：R1 |ai-1 ,aiD, i=2,.,n 基本操作：基本操作：（1）InitList（&L） 操作結果：將操作結果：將L初始化為空表。初始化為空表。（2）DestroyList(&L) 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：將操作結果：將L銷毀。銷毀。單擊此處編輯母版標題樣

8、式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級8（3）ClearList(&L) 初始條件：線性表初始條件：線性表L已存在已存在 。 操作結果：將表操作結果：將表L置為空表。置為空表。（4）EmptyList（L） 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：如果操作結果：如果L為空表則返回真，否則返回為空表則返回真，否則返回假。假。（5）ListLength（L） 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：如果操作結果：如果L為空表則返回為空表則返回0，否則返回，否則返

9、回表中的元素個數。表中的元素個數。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級9（6）GetItem(L,i,&e) 初始條件：初始條件： 表表L已存在，已存在，1=i=ListLength(L)。 操作結果：操作結果： 用用e返回返回L中第中第i個元素的值。個元素的值。（7）LocateElem(L,e) 初始條件：初始條件： 表表L已存在，已存在，e為合法元素值。為合法元素值。 操作結果：操作結果： 如果如果L中存在元素中存在元素e，則將，則將“當前指針當前指針”指向第一個這樣的元

10、素指向第一個這樣的元素e所在位置并返回真，否則返所在位置并返回真，否則返回假?；丶?。（8）ListInsert(&L,i,e) 初始條件：表初始條件：表L已存在，已存在，e為合法元素值且為合法元素值且1iListLength(L)+1。 操作結果：在操作結果：在L中第中第i個位置之前插入新的數據元素個位置之前插入新的數據元素e，L的長度加的長度加1。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級10（9）ListDelete(&L,i,&e) 初始條件：表初始條件：表L已存在且非空已存在

11、且非空 ，1iListLength(L)。 初始條件：刪除初始條件：刪除L的第的第i個數據元素，并用個數據元素，并用e返回其值，返回其值，L的長度減的長度減1。ADT List 利用上述定義的線性表類型，可以實現其它更復雜的利用上述定義的線性表類型，可以實現其它更復雜的操作，例如：歸并、拆分、復制、排序操作，例如：歸并、拆分、復制、排序單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級11算法舉例：算法舉例：例例2-1 假設有兩個集合假設有兩個集合A和和B分別用兩個線性表分別用兩個線性表LA

12、和和LB表示表示（即：線性表中的數據元素即為集合中的成員），現要求一個新（即：線性表中的數據元素即為集合中的成員），現要求一個新的集合的集合AAB。要求對線性表作如下操作：擴大線性表。要求對線性表作如下操作：擴大線性表LA，將存在于線性表將存在于線性表LB中而不存在于線性表中而不存在于線性表LA中的數據元素插入到中的數據元素插入到線性表線性表LA中去。中去。(注：注： 并集，屬于并集，屬于A或者屬于或者屬于B) 思路：思路： 1從線性表從線性表LB中依次取得每個數據元素中依次取得每個數據元素; GetElem(LB, i)e 2依值在線性表依值在線性表LA中進行查訪中進行查訪; LocateE

13、lem(LA, e, equal( ) ) 3. 若不存在，則插入之。若不存在，則插入之。 ListInsert(LA, n+1, e)算法實現：算法實現：void union(List &La, List Lb) / 將所有在線性表將所有在線性表Lb中但不在中但不在La中的數據元素插入到中的數據元素插入到La中中 La_len = ListLength(La); Lb_len = ListLength(Lb); / 求線性表的長度求線性表的長度 for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第i個數據元素賦給個數據元素賦給e

14、if(!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同相同的數據元素，則插入之的數據元素，則插入之 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級12算法舉例：算法舉例： 例例2-2 歸并兩個歸并兩個“其數據元素按值非遞減有序排列其數據元素按值非遞減有序排列”的有序表的有序表 La 和和 Lb，求得有序表，求得有序表 Lc 也具有同樣特性。也具有同樣特性。問題分析：問題分析： La =

15、(a1, , ai, , an), Lb = (b1, , bj, , bm), Lc = (c1, , ck, , cm+n) 且已由且已由(a1, , ai-1)和和(b1, ,bj-1)歸并得歸并得 (c1, , ck-1)jijjiikbabbaack = 1, 2, , m+n單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級13算法基本思路算法基本思路初始化初始化 Lc 為空表；為空表；分別從分別從 La和和Lb中取得當前元素中取得當前元素 ai 和和 bj ； GetElem(

16、La, i, ai); GetElem(Lb, j, bj); 若若 aibj，則將，則將 ai 插入到插入到 Lc 中，否則將中，否則將 bj 插插入到入到 Lc 中；中； ListInsert(Lc, +k, ai); ListInsert(Lc, +k, bj); 重復重復 2 和和 3 兩步，直至兩步，直至 La 或或 Lb 中元素中元素 被取完為止；被取完為止；將將 La 表或表或 Lb表中剩余元素復制插入到表中剩余元素復制插入到Lc 表表中。中。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四

17、級 第五級第五級14void MergeList(List La, List Lb, List &Lc) InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb)； while (i = La_len) & (j = Lb_len) / La和和Lb均非空均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; 單擊

18、此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級15 while (i = La_len) GetElem(La, i+, ai);ListInsert(Lc, +k, ai); while (j = Lb_len) GetElem(Lb, j+, bj);ListInsert(Lc, +k, bj); / MergeList算法的時間復雜度算法的時間復雜度：O( ( ListLength(La) +ListLength(Lb)） 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯

19、母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級162.2 線性表的順序表示和實現線性表的順序表示和實現 順序映象順序映象 線性表的順序存儲是指線性表的順序存儲是指用一組地址連續(xù)的存儲用一組地址連續(xù)的存儲單元單元依次存儲線性表中的各個元素。依次存儲線性表中的各個元素。20 31 45 34 25 35 1 2 3 4 5 6 data用物理位置來表示邏輯結構。用物理位置來表示邏輯結構。 LOC(ai+1)=LOC(ai)+l ; LOC(ai)=LOC(a1)+(i-1)*l 特點：特點：是一種是一種隨機存隨機存取取的存儲結構，的存儲結構，只要確定了

20、起只要確定了起始位置，就可始位置，就可以訪問表中的以訪問表中的任何一個元素。任何一個元素。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級1720 12 33 45 35 54 23 65 76 78 1 2 3 4 5 6 7 8 9 10l l l l l l l l l l LOC(ai) = LOC(ai-1)+l = arr+(i-1)*larr+(i-1)*larr單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級

21、第三級第三級 第四級第四級 第五級第五級18線性表順序存儲結構的線性表順序存儲結構的 C語言定義語言定義#define LIST_INIT_SIZE 100#define LISTINCREAMENT 10typedef struct ElemType *elem； /* 線性表占用的數組空間。線性表占用的數組空間。*/ int length； /*線性表的長度線性表的長度*/ int listsize； /*當前分配的存儲容量當前分配的存儲容量(以以sizeof(ElemType)為單位為單位) /* SqList； elemlengthlistsizeSqListElemType單擊此處編

22、輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級19順序線性表的操作順序線性表的操作l 順序表容易實現訪問操作，可隨機存取元素。但插入順序表容易實現訪問操作，可隨機存取元素。但插入和刪除操作需要移動元素。和刪除操作需要移動元素。 初始化操作初始化操作 算法思想：構造一個空表。算法思想：構造一個空表。 設置表的起始位置、表長及可用空間。設置表的起始位置、表長及可用空間。0100La.019899單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第

23、二級 第三級第三級 第四級第四級 第五級第五級20初始化操作實現初始化操作實現Status InitList_Sq(SqList &L) /構造一個空的線性表構造一個空的線性表 L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType); if (! L.elem) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 L.length=0; /空表長度為空表長度為0 L.listsize= LIST_INIT_SIZE; /初始存儲容量初始存儲容量 return OK; /InitList_Sq 單擊此處編輯母版標題樣式單擊此處

24、編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級21（2）線性表的順序表插入操作）線性表的順序表插入操作 ListInsert(&L, i, e) 分析：分析：“插入元素插入元素”使線性表的邏輯結構發(fā)生什么變使線性表的邏輯結構發(fā)生什么變化？假設在線性表的第化？假設在線性表的第i個元素之前插入一個元素個元素之前插入一個元素e。插入元素時，線性表的邏輯結構由插入元素時，線性表的邏輯結構由 (a1,ai-1, ai,an) (a1, , ai-1, e, ai, , an), a1 a2 ai-1 ai ana1 a2 ai-

25、1 ai ean單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級22ListInsert(&La, 4, 29)221)(1)(1 0)1(11)(11=nnnnnn1inn1ni1AMN20 38 46 18 40 39 78 1 2 3 4 5 6 7 8La78平均移動次數：平均移動次數：39401829單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級23算法的基本思想算法的基本

26、思想檢查檢查i i值是否超出所允許的范圍值是否超出所允許的范圍（1in+11in+1），若超出，則進行），若超出，則進行“超出范超出范圍圍”錯誤處理；錯誤處理；將線性表的第將線性表的第i i個元素和它后面的所有元素個元素和它后面的所有元素均向后移動一個位置；均向后移動一個位置；將新元素寫入到空出的第將新元素寫入到空出的第i i個位置上；個位置上；使線性表的長度增使線性表的長度增1 1。 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級24Status ListInsert_Sq(SqLis

27、t &L, int i, ElemType e) / 在順序表在順序表L的第的第 i 個元素之前插入新的元素個元素之前插入新的元素e, / i 的合法范圍為的合法范圍為 1iL.length+1 ElemType *p,*q; if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法 if (length = listsize) . q = &(L.elemi-1); / q 指示插入位置指示插入位置 for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元

28、素右移 *q = e; / 插入插入e + length; / 表長增表長增1 return OK;/ ListInsert_Sq newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/當前存儲空間已滿當前存儲空間已滿 elem=newbase; listsize+=LISTINCREMENT; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第

29、四級第四級 第五級第五級25（3）線性表的順序表刪除操作）線性表的順序表刪除操作 ListDelete(&La, i, &e) 分析：分析： “刪除元素刪除元素” 線性表的邏輯結構發(fā)生什么變線性表的邏輯結構發(fā)生什么變化？假設刪除線性表的第化？假設刪除線性表的第i個元素保存在變量個元素保存在變量e中。中。刪除元素時，線性表的邏輯結構由刪除元素時，線性表的邏輯結構由 (a1,ai-1, ai,an) (a1, , ai-1, ai+1, , an)a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 ai+1 ean ai單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版

30、文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級26ListDelete(&La, 4, &e)20 38 46 18 40 39 78 1 2 3 4 5 6 7 8La78平均移動次數：平均移動次數：3940e18ninnnninn1AMN2121)(1)(1=單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級27算法的基本思想算法的基本思想檢查檢查i i值是否超出所允許的范圍（值是否超出所允許的范圍（1in1in），），若超出，則進行若超出，則進

31、行“超出范圍超出范圍”錯誤處理；錯誤處理；將線性表的第將線性表的第i i個元素后面的所有元素均向個元素后面的所有元素均向前移動一個位置；前移動一個位置；使線性表的長度減使線性表的長度減1 1。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級28 Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在順序線性表在順序線性表L中刪除第中刪除第i個元素，并用個元素，并用e返回其值。返回其值。 / i的合法值為的合法值為1iListLengt

32、h_Sq(L) if (i L.length) return ERROR; / 刪除位置不合法刪除位置不合法 p = &(L.elemi-1); / p為被刪除元素的位置為被刪除元素的位置 e = *p; / 被刪除元素的值賦給被刪除元素的值賦給e q = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置 for (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移被刪除元素之后的元素左移 - - L.length; return ok; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式

33、第二級第二級 第三級第三級 第四級第四級 第五級第五級29（4）線性表的順序表查找操作）線性表的順序表查找操作 LocateElem_Sq (La, e) Status LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType) / 在順序表中查詢第一個滿足判定條件的數據元素，在順序表中查詢第一個滿足判定條件的數據元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 int i; ElemType *p; i= 1; p=L.elem; while (i = L.length &

34、!(* compare(*p+, e) +i; if (i = L.length) return i; else return 0; / LocateElem_Sq 此算法的時間復雜度為此算法的時間復雜度為: O( ListLength(L) ) 平均比較次數為：平均比較次數為：(n+1)/2單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級30例如：順序表例如：順序表23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi1 2

35、 3 4 1 850p可見，基本操作是，可見，基本操作是，將順序表中的元素將順序表中的元素逐個和給定值逐個和給定值 e e 相比較。相比較。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級31順序存儲結構的優(yōu)缺點順序存儲結構的優(yōu)缺點 優(yōu)點優(yōu)點 邏輯相鄰，物理相鄰邏輯相鄰，物理相鄰 可隨機存取任一元素可隨機存取任一元素 存儲空間使用緊湊存儲空間使用緊湊 缺點缺點 插入、刪除操作需要移動大量的元素插入、刪除操作需要移動大量的元素 預先分配空間需按最大空間分配，利用不充分預先分配空間需按最大空間

36、分配，利用不充分 表容量難以擴充表容量難以擴充單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級32順序表的合并問題順序表的合并問題 例例1、已知順序表、已知順序表LA和和LB中的數據元素按值非遞減中的數據元素按值非遞減有有序排列序排列，現要將，現要將LA和和LB歸并為一個新表歸并為一個新表LC，且，且LC中的數據元素仍按非值遞減有序排序。中的數據元素仍按非值遞減有序排序。 例如：例如：LA（3,5,8,9） LB（2,6,8,9,11,15,20） 則則LC（2,3,5,6,8,8,9,1

37、1,11,15,20）85398210111520papbpc2356 688910111520單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級33void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+ Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType

38、);If(!Lc.elem) exit(OVERFLOW);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(pbdata 表示表示p指向結點的指向結點的數據域數據域(*p).next p-next 表示表示p指向結點的指向結點的指針域指針域LinkListLNodeLNodenextdata單擊此處編輯母版標題樣式單擊此處編輯母版標題

39、樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級39 生成一個生成一個LNode型新結點：型新結點： p=(LinkList)malloc(sizeof(LNode); 系統(tǒng)回收系統(tǒng)回收p結點：結點： free(p) 單鏈表特點單鏈表特點: 它是一種動態(tài)結構，整個存儲空間為多個鏈表共用它是一種動態(tài)結構，整個存儲空間為多個鏈表共用 不需預先分配空間不需預先分配空間 指針占用額外存儲空間指針占用額外存儲空間 插入、刪除方便插入、刪除方便 不能隨機存取，查找速度慢不能隨機存取，查找速度慢單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單

40、擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級40單鏈表基本操作的實現單鏈表基本操作的實現GetElem(L, i, &e) / 取第取第i個數據元素個數據元素ListInsert(&L, i, e) / 插入數據元素插入數據元素ListDelete(&L, i, &e) / 刪除數據元素刪除數據元素CreateList_L(&L, n) / 創(chuàng)建線性表創(chuàng)建線性表單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級41（1）單鏈表查找操作

41、）單鏈表查找操作 GetElem(L, i, &e)Lpj12 32017406034 實現實現GetElem(L, 3, &e) 實現實現GetElem(L, 6, &e)4 5單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級42算法的基本思想算法的基本思想令令p為指針變量，首先指向第一個結點，變?yōu)橹羔樧兞?，首先指向第一個結點，變量量j為計數器；為計數器；依次向后查找，循環(huán)結束的條件，依次向后查找，循環(huán)結束的條件，p為空或為空或者者j=i。如果如果p為空為空 或或 ji，出錯。，出錯。找

42、到了，用找到了，用e返回第返回第i個元素。個元素。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級43算法實現算法實現 Status GetElem_L(LinkList L, int i, ElemType &e) / L是帶頭結點的鏈表的頭指針，以是帶頭結點的鏈表的頭指針，以 e 返回第返回第 i 個元素個元素 p = L-next; / p指向第一個結點指向第一個結點 j = 1; / j為計數器為計數器 while (p & jnext; +j; if ( !p | ji ) re

43、turn ERROR; e = p-data;/ 取得第取得第 i 個元素個元素 return OK; / GetElem_L單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級44（2）單鏈表的插入操作）單鏈表的插入操作 ListInsert(&L, i, e) 分析：分析：“插入元素插入元素”使線性表的邏輯結構和物理結構使線性表的邏輯結構和物理結構發(fā)生什么變化？假設在線性表的第發(fā)生什么變化？假設在線性表的第i個元素之前插入一個元素之前插入一個元素個元素e。 (a1,ai-1, ai,an)

44、 (a1, , ai-1, e, ai, , an), ai-1anaia1Le單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級45第第i個元素之前插入元素個元素之前插入元素es = (LinkList)malloc(sizeof(LNode);/ 生成新結點生成新結點s-data = e; s-next = p-next; p-next = s；ai( (插入前插入前) () (插入后插入后) )aiai-1peai-1sp單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母

45、版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級46單鏈表插入操作單鏈表插入操作 ListInsert ( &L, i, e ) Lpj122017406034 實現實現ListInsert (L, 3, 10 )10s單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級47/ 帶頭結點的單鏈表帶頭結點的單鏈表L中第中第 i 個位置之前插入元素個位置之前插入元素 eLNode *p,*s; int j;p = L; j = 0;while ( p &

46、jnext; +j; if ( ! p | j i-1 ) return ERROR; s = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新結點生成新結點s-data = e; / 使新結點數據域的值為使新結點數據域的值為 es-next = p-next; / 將新結點插入到單鏈表將新結點插入到單鏈表 L 中中p-next = s; / 修改第修改第 i-1 個結點指針個結點指針return OK; / ListInsert_LStatus ListInsert_L ( LinkList &L, int i, ElemType e ) 時間復

47、雜度：時間復雜度： T(n)=O(n)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級48（3）單鏈表的刪除操作單鏈表的刪除操作 ListDelete(&L, i, &e) 分析：分析：“刪除元素刪除元素”使線性表的物理結構發(fā)生什么變使線性表的物理結構發(fā)生什么變化？化？ai-1anaia1Lai+1單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級49刪除第刪除第i個元素，并保存數據到元

48、素個元素，并保存數據到元素e中中 q = p-next; / 用指針用指針 q 指向被刪除結點指向被刪除結點 p-next = q-next; / 刪除第刪除第 i 個結點個結點*e=ai;free(q);pqpai+1aiai-1aie單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級50單鏈表的刪除操作單鏈表的刪除操作 ListDelete(&L, i, &e)Lpj122017406034 實現實現ListDelete(&L, 3, &e)q單擊此處編輯母版標題樣式單擊此處編輯母版標題

49、樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級51/ 刪除第刪除第 i 個元素，并由個元素，并由 e 返回其值返回其值LNode *p,*q;int j;p = L; j = 0;while ( p-next & jnext; +j; if ( !(p-next) | j i-1 ) return ERROR; / 刪除位置不合理刪除位置不合理 q = p-next; / 用指針用指針 q 指向被刪除結點指向被刪除結點p-next = q-next; / 刪除第刪除第 i 個結點個結點e = q-data; / 取出第取出第 i

50、個結點數據域值個結點數據域值free (q); / 釋放第釋放第 i 個結點個結點return OK; / LinkDelete_LStatus ListDelete_L ( LinkList L, int i, ElemType &e )時間復雜度：時間復雜度： T(n)=O(n)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級52 （4）創(chuàng)建單鏈表）創(chuàng)建單鏈表 CreateList_L(&L, n)Lp2017406034 已知線性表（已知線性表（20，17，40，60，34） 頭插法

51、創(chuàng)建帶有頭結點的單鏈表。頭插法創(chuàng)建帶有頭結點的單鏈表。pppp單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級53頭插法頭插法 創(chuàng)建單鏈表創(chuàng)建單鏈表執(zhí)行的語句組為:snextLnext；Lnexts；L(a) 建空表c1ss 指向新申請的結點sdatac1(b) 申請新結點并賦值Lci 1s(c) 插入第一個結點Lc2c1cic1s(d) 插入第 i個元素單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第

52、四級 第五級第五級54CreateList_L(LinkList &L, int n) L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof (LNode) ); scanf( &s-data); s-next = L-next; L-next = s; 頭插法頭插法 創(chuàng)建單鏈表創(chuàng)建單鏈表單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級5

53、5void CreateList_L ( LinkList &L, int n ) / 輸入輸入 n 個數據元素的值，建立帶頭結點的單鏈表個數據元素的值，建立帶頭結點的單鏈表 L LNode *p; int i; L = ( LinkList ) malloc ( sizeof ( LNode ) ); L-next = NULL; / 先建立一個帶頭結點的空鏈表先建立一個帶頭結點的空鏈表 for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); scanf (%d ,&p-data ); p-next =L-ne

54、xt; L-next = p; / CreateList_L單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級56 （4）創(chuàng)建單鏈表）創(chuàng)建單鏈表 CreateList_L(&L, n)Lp2017 已知線性表（已知線性表（20，17，40，60） 尾插法創(chuàng)建帶有頭結點的單鏈表。尾插法創(chuàng)建帶有頭結點的單鏈表。 思考：算法如何實現？思考：算法如何實現？pq40p60p單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第

55、四級第四級 第五級第五級57用尾插法建立線性單鏈表用尾插法建立線性單鏈表r s； r 始終指向單鏈表的表尾L(a) 建空表c1ss 指向新申請的結點空間s data c1(b) 申請新結點并賦值Lc1s(c) 插入第一個結點Lc2c1rrr next s；(d) 插入第二個結點sr單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級58用尾插法建立線性單鏈表用尾插法建立線性單鏈表CreateList_L(LinkList &L, int n) tail = L = (LinkList) mal

56、loc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof(LNode) ); scanf( &s-data); s-next = NULL; tail-next = s; tail = s; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級59線性表的合并問題線性表的合并問題 例例1、已知線性表、已知線性表Lc和和Lb中的數據元素按值非遞減中的數據元素按值非遞減有有序排列序排列

57、，現要將，現要將Lc和和Lb歸并為一個新的鏈表歸并為一個新的鏈表Lc，且，且Lc中的數據元素仍按非值遞減有序排序。中的數據元素仍按非值遞減有序排序。 例如：例如：La（3,5,8,11） Lb（2,6,9,15,20）La11853Lb2015962pcpbpaLc單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級60void MergeList_L ( LinkList &La, LinkList &Lb, LinkList &Lc ) / 歸并歸并 La 和和 Lb 得到新的單鏈表得到新

58、的單鏈表 Lc ，Lc 的元素也按非遞減排列的元素也按非遞減排列LNode *pa, *pb, *pc;pa = La-next; pb = Lb-next;Lc = pc = La; / 用用 La 的頭結點作為的頭結點作為 Lc 的頭結點的頭結點while ( pa & pb ) if ( pa-data data ) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段插入剩余段free (Lb); / 釋放釋放 Lb 的

59、頭結點的頭結點 / MergeList_L單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級612.3.2 循環(huán)鏈表循環(huán)鏈表 循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表是單鏈表的變形。 循環(huán)鏈表最后一個結點的指針域不為循環(huán)鏈表最后一個結點的指針域不為NULLNULL，而是指向，而是指向了表的前端。了表的前端。 為簡化操作，在循環(huán)鏈表中往往加入為簡化操作，在循環(huán)鏈表中往往加入頭結點頭結點。 循環(huán)鏈表的特點是：循環(huán)鏈表的特點是：只要知道表中某一結點的地址，只要知道表中某一結點的地址，就可搜尋到所有其他結點

60、的地址。就可搜尋到所有其他結點的地址。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級62循環(huán)鏈表示例循環(huán)鏈表示例帶頭結點的循環(huán)鏈表帶頭結點的循環(huán)鏈表 a1a2a3anHanHa2a1H( (空表空表) )( (非空表非空表) )單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級63H31481557搜索搜索15 pppH31481557搜索搜索25 pppp p思考整個搜索算法的條件是