第二章線性表PPT課件

1、浙江傳媒學院浙江傳媒學院All rights reserved. 胡智文胡智文, Ph.D, IEEE member第二章第二章 線性表線性表數(shù)據(jù)結構數(shù)據(jù)結構 DATA STRUCTURES2第二章線性表第二章線性表本章要求本章要求了解線性表的邏輯結構特性是數(shù)據(jù)元素之間存在著線性關了解線性表的邏輯結構特性是數(shù)據(jù)元素之間存在著線性關系，在計算機中表示這種關系的兩類不同的存儲結構是順系，在計算機中表示這種關系的兩類不同的存儲結構是順序存儲結構和鏈式存儲結構；序存儲結構和鏈式存儲結構；熟練掌握這兩類存儲結構的描述方法，以及線性表的各種熟練掌握這兩類存儲結構的描述方法，以及線性表的各種基本操作的實現(xiàn)；

2、基本操作的實現(xiàn)；能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合；結構的不同特點及其適用場合；掌握用線性表來表示一元多項式的方法及相應操作的實現(xiàn)。掌握用線性表來表示一元多項式的方法及相應操作的實現(xiàn)。 重點和難點重點和難點掌握單鏈表、循環(huán)鏈表、雙向鏈表掌握單鏈表、循環(huán)鏈表、雙向鏈表線性表在多項式中的應用線性表在多項式中的應用3第二章線性表第二章線性表線性表的概念及運算線性表的概念及運算 線性表的順序存儲線性表的順序存儲 線性表的鏈式存儲線性表的鏈式存儲單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 雙向鏈表雙向鏈表一元多項式的表示及相

3、加一元多項式的表示及相加 要點小結要點小結參考書目及網(wǎng)絡資源參考書目及網(wǎng)絡資源討論時間討論時間4知識回顧知識回顧-Pointers(a) declaring pointer variables; (b) pointing to statically allocating memory; (c) assigning a value; (d) allocating memory dynamically; (e) assigning a value5知識回顧知識回顧-Pointers(f) copying a pointer; (g) allocating memory dynamically an

4、d assigning a value; (h) assigning NULL to a pointer variable; (i) deallocating memory6第二章線性表第二章線性表線性表的概念及運算線性表的概念及運算 線性表的順序存儲線性表的順序存儲 線性表的鏈式存儲線性表的鏈式存儲單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 雙向鏈表雙向鏈表一元多項式的表示及相加一元多項式的表示及相加 要點小結要點小結參考書目及網(wǎng)絡資源參考書目及網(wǎng)絡資源討論時間討論時間7線性表的概念線性表的概念線性表線性表(Linear List)是由是由n(n0)個數(shù)據(jù)元素個數(shù)據(jù)元素(結結點點)a1,a2,an組成的

5、組成的有限序列有限序列。數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)n定義為定義為表的長度。表的長度。當當n=0時，稱時，稱為為空表空表。將非空的線性表將非空的線性表(n0)記作記作:(a1，a2，an)數(shù)據(jù)元素數(shù)據(jù)元素ai(1in)只是個只是個抽象符號抽象符號，其具體含義，其具體含義在不同情況下可以不同。它既可以是原子類型，在不同情況下可以不同。它既可以是原子類型，也可以是結構類型但同一線性表中的數(shù)據(jù)元素必也可以是結構類型但同一線性表中的數(shù)據(jù)元素必須屬于同一數(shù)據(jù)對象。須屬于同一數(shù)據(jù)對象。8線性表的概念線性表的概念線性表的邏輯結構線性表的邏輯結構除第一個元素外，其他每一個元素有且僅除第一個元素外，其他每一個元

6、素有且僅有一個有一個直接前驅直接前驅。除最后一個元素外，其他每一個元素有且除最后一個元素外，其他每一個元素有且僅有一個僅有一個直接后繼直接后繼。原則上講，線性表中元素的數(shù)據(jù)類型可以不相原則上講，線性表中元素的數(shù)據(jù)類型可以不相同。但采用的存儲表示可能會對其有限制。同。但采用的存儲表示可能會對其有限制。 9線性表的概念線性表的概念在較為復雜的線性表中，在較為復雜的線性表中，數(shù)據(jù)元素數(shù)據(jù)元素(data elements)可由若干可由若干數(shù)據(jù)項數(shù)據(jù)項組成。組成。含有大量含有大量記錄記錄的線性表稱為的線性表稱為文件文件(file)。數(shù)據(jù)對象數(shù)據(jù)對象(data object)是性質相同的是性質相同的數(shù)據(jù)元

7、素數(shù)據(jù)元素集合。集合。學號學號姓名姓名性別性別籍貫籍貫出生年月出生年月住址住址101趙紅玲趙紅玲女女河北河北1983.11北京北京數(shù)據(jù)項數(shù)據(jù)項記錄記錄10數(shù)組與記錄數(shù)組與記錄數(shù)組：元素類型相同數(shù)組：元素類型相同記錄：元素類型相同或不同，但記錄：元素類型相同或不同，但元素須相關元素須相關11線性表的特點線性表的特點同一性同一性：線性表由同類數(shù)據(jù)元素組成，每一：線性表由同類數(shù)據(jù)元素組成，每一個個ai必須屬于同一數(shù)據(jù)對象。必須屬于同一數(shù)據(jù)對象。有窮性有窮性：線性表由有限個數(shù)據(jù)元素組成，：線性表由有限個數(shù)據(jù)元素組成， 表表長度就是表中數(shù)據(jù)元素的個數(shù)。長度就是表中數(shù)據(jù)元素的個數(shù)。有序性有序性：線性表中表

8、中相鄰數(shù)據(jù)元素之間存：線性表中表中相鄰數(shù)據(jù)元素之間存在著序偶關系在著序偶關系。線性表是一種最簡單的數(shù)據(jù)結構，數(shù)據(jù)元素之線性表是一種最簡單的數(shù)據(jù)結構，數(shù)據(jù)元素之間是由一前驅一后繼的直觀有序的關系確定；間是由一前驅一后繼的直觀有序的關系確定；線性表是一種最常見的數(shù)據(jù)結構，矩陣、數(shù)組線性表是一種最常見的數(shù)據(jù)結構，矩陣、數(shù)組、字符串、堆棧、字符串、堆棧、 隊列等都符合線性條件。隊列等都符合線性條件。 12線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義ADT LinearList數(shù)據(jù)元素數(shù)據(jù)元素: D=ai| aiD0, i=1, 2, ,n,n0,D0為某一數(shù)據(jù)對象為某一數(shù)據(jù)對象關系關系: S= |

9、 ai, ai+1D0，i=1, 2, , n-1基本操作基本操作: InitList(L): 初始化初始化 DestroyList(L): 銷毀銷毀 ClearList(L): 置空表置空表 EmptyList(L): 判斷表是否為空判斷表是否為空 ListLength(L): 求表長求表長 Locate(L, e): 查找查找 GetData(L, i): 求第求第i個結點個結點 InsList(L, i, e): 插入插入 DelList(L, i, &e): 刪除刪除 ADT LinearList13線性表的運算線性表的運算在實際問題中對線性表的運算可能很多在實際問題中對線性表

10、的運算可能很多將兩個或兩個以上的線性表合并成一個線性表；將兩個或兩個以上的線性表合并成一個線性表；把一個線性表分拆成兩個或兩個以上的線性表；把一個線性表分拆成兩個或兩個以上的線性表；多種條件的合并、分拆、復制、排序等運算。多種條件的合并、分拆、復制、排序等運算。可利用基本運算的組合來實現(xiàn)復合運算。可利用基本運算的組合來實現(xiàn)復合運算。線性表的抽象數(shù)據(jù)類型定義中給出的各種操作線性表的抽象數(shù)據(jù)類型定義中給出的各種操作是定義在線性表的邏輯結構上的，用戶只需了是定義在線性表的邏輯結構上的，用戶只需了解各種操作的功能，而無須知道它的具體實現(xiàn)。解各種操作的功能，而無須知道它的具體實現(xiàn)。各種操作的具體實現(xiàn)與線

11、性表具體采用哪種存各種操作的具體實現(xiàn)與線性表具體采用哪種存儲結構有關。儲結構有關。14第二章線性表第二章線性表線性表的概念及運算線性表的概念及運算 線性表的順序存儲線性表的順序存儲 線性表的鏈式存儲線性表的鏈式存儲單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 雙向鏈表雙向鏈表一元多項式的表示及相加一元多項式的表示及相加 要點小結要點小結參考書目及網(wǎng)絡資源參考書目及網(wǎng)絡資源討論時間討論時間15線性表的順序存儲線性表的順序存儲指用一組地址連續(xù)的存儲單元依次存儲線性表指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在中的各個元素，使得線性表中在邏輯結構上相邏輯結構上相鄰鄰的數(shù)據(jù)元素的數(shù)據(jù)元素存儲

12、在相鄰的物理存儲單元存儲在相鄰的物理存儲單元中。中。即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系。元素之間邏輯上的相鄰關系。采用順序存儲結構的線性表通常稱為采用順序存儲結構的線性表通常稱為順序表順序表。假設線性表中有假設線性表中有n個元素，每個元素占個元素，每個元素占k個單元，個單元，第一個元素的地址為第一個元素的地址為loc(a1)，則可以計算出第，則可以計算出第i個個元素的地址元素的地址loc(ai)： loc(ai) =loc(a1)+(i-1)k 其中其中l(wèi)oc(a1) 稱為稱為基址基址。16順序表存儲示意圖順序表存儲示意

13、圖 17順序存儲結構的順序存儲結構的C語言定義語言定義#define maxsize=線性表可能達到的最大長度；線性表可能達到的最大長度；typedef struct/* 線性表占用的數(shù)組空間。線性表占用的數(shù)組空間。*/ ElemType elemmaxsize; /*記錄線性表中最后一個元素在數(shù)組記錄線性表中最后一個元素在數(shù)組elem 中中 的位置的位置(下標值下標值),空表置為空表置為-1*/ int last;SeqList; 區(qū)分元素的序號和數(shù)組的下標，如區(qū)分元素的序號和數(shù)組的下標，如a1的序號為的序號為1，而其對應的數(shù)組下標為，而其對應的數(shù)組下標為0。18線性表順序存儲結構的基本運算

14、線性表順序存儲結構的基本運算線性表的基本運算線性表的基本運算查找操作查找操作插入操作插入操作刪除操作刪除操作順序表合并算法順序表合并算法19查找操作查找操作-按序號查找按序號查找GetData(L,i) 按序號查找按序號查找GetData(L,i) 要求查找線性表要求查找線性表L中第中第i個數(shù)據(jù)元素，其結個數(shù)據(jù)元素，其結果是果是L.elemi-1或或L-elemi-1。20查找操作查找操作-按內(nèi)容查找按內(nèi)容查找Locate(L,e)要求查找線性表要求查找線性表L中與給定值中與給定值e相等的數(shù)據(jù)元素，其相等的數(shù)據(jù)元素，其結果是：若在表結果是：若在表L中找到與中找到與e相等的元素，則返回該相等的元

15、素，則返回該元素在表中的序號；若找不到，則返回一個元素在表中的序號；若找不到，則返回一個“空序空序號號”，如，如-1。21線性表的查找運算線性表的查找運算int Locate(SeqList L，ElemType e) i=0 ; /*i為掃描計數(shù)器，初值為為掃描計數(shù)器，初值為0，即從第一個元素開，即從第一個元素開始比較始比較*/ while (i=L.last)&(L.elemi!=e) ) i+; /*順序掃描表，直到找到值為順序掃描表，直到找到值為key的元素的元素,或掃描到表或掃描到表尾而沒找到尾而沒找到*/ if (i=L.last) return(i); /*若找到值為若找

16、到值為e的元素，則返回其序號的元素，則返回其序號*/ else return(-1); /*若沒找到，則返回空序號若沒找到，則返回空序號*/ 22插入操作插入操作線性表的插入運算是指在表的第線性表的插入運算是指在表的第i (1in+1)個個位置，插入一個新元素位置，插入一個新元素e，使長度為，使長度為n的線性表的線性表 (e1，ei-1，ei，en) 變成長度為變成長度為n+1的線的線性表性表(e1，,ei-1，e，ei，en)。 用順序表作為線性表的存儲結構時，用順序表作為線性表的存儲結構時， 由于結點的由于結點的物理順序必須和結點的邏輯順序保持一致，因此物理順序必須和結點的邏輯順序保持一致

17、，因此必須將原表中位置必須將原表中位置n， n-1， i上的結點，上的結點， 依依次后移到位置次后移到位置n+1，n，i+1上，空出第上，空出第i個位個位置，然后在該位置上插入新結點置，然后在該位置上插入新結點e。當當i=n+1時，時， 是指在線性表的末尾插入結點，所是指在線性表的末尾插入結點，所以無需移動結點，直接將以無需移動結點，直接將e插入表的末尾即可。插入表的末尾即可。23插入算法示意圖插入算法示意圖區(qū)分元素的序號和數(shù)組的下標，如區(qū)分元素的序號和數(shù)組的下標，如a1的序號為的序號為1，而其對應的數(shù)組下標為，而其對應的數(shù)組下標為0。24線性表的插入算法線性表的插入算法int InsList

18、(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) )/首先判斷插入位置是否合法首先判斷插入位置是否合法 printf(“插入位置插入位置i值不合法值不合法”)；return(ERROR); if(L-last=maxsize-1) printf(“表已滿無法插入表已滿無法插入”)；return(ERROR); for(k=L-last;k=i-1;k-) /為插入元素而移動位置為插入元素而移動位置 L-elemk+1=L-elemk; L-elemi-1=e; /C語言數(shù)組第語言數(shù)組第i個元素下標為個元素下標為i-1 L-last+; r

19、eturn(OK); 25線性表的插入運算演示線性表的插入運算演示26刪除操作刪除操作線性表的刪除運算是指將表的第線性表的刪除運算是指將表的第i(1in)個元個元素刪去，使長度為素刪去，使長度為n的線性表的線性表 (e1，,ei-1，ei，ei+1，en)，變成長度為，變成長度為n-1的線性表的線性表(e1，,ei-1， ei+1，en)。在順序表上實現(xiàn)刪除運算也必須移動結點，這樣在順序表上實現(xiàn)刪除運算也必須移動結點，這樣才能反映出結點間的邏輯關系的變化。才能反映出結點間的邏輯關系的變化。若若i=L-last+1， 則移位語句則移位語句L-elemk-1= L-elemk不執(zhí)行，因為循環(huán)變量的

20、初值大于終值，此時不不執(zhí)行，因為循環(huán)變量的初值大于終值，此時不需要移動元素，僅將表長度減需要移動元素，僅將表長度減1即可。即可。顯然，刪除算法中移位語句顯然，刪除算法中移位語句L-elemk-1= L-elemk的執(zhí)行頻度也與刪除位置的執(zhí)行頻度也與刪除位置i有關。有關。 27刪除操作示意圖刪除操作示意圖區(qū)分元素的序號和數(shù)組的下標，如區(qū)分元素的序號和數(shù)組的下標，如a1的序號為的序號為1，而其對應的數(shù)組下標為，而其對應的數(shù)組下標為0。28線性表的刪除算法線性表的刪除算法int DelList(SeqList *L,int i,ElemType *e) /刪除順序表刪除順序表L中第中第i個元素個元素

21、,并用指針參數(shù)并用指針參數(shù)e返回其值返回其值int k; if(iL-last+1) printf(“刪除位置不合法！刪除位置不合法！”); return(ERROR); *e= L-elemi-1; /將刪除的元素存放到將刪除的元素存放到e所指向的變所指向的變量中量中 for(k=i;ilast;k+) L-elemk-1= L-elemk;/后面的元素依次前移后面的元素依次前移 L-last-; return(OK); 29線性表的刪除運算演示線性表的刪除運算演示30合并算法合并算法已知：有兩個順序表已知：有兩個順序表LALA和和LBLB，其元素均為非遞減有，其元素均為非遞減有序排列，編寫

22、一個算法，將它們合并成一個順序表序排列，編寫一個算法，將它們合并成一個順序表LCLC，要求，要求LCLC也是非遞減有序排列。也是非遞減有序排列。 設表設表LC是一個空表，為使是一個空表，為使LC也是非遞減有序排也是非遞減有序排列，可設兩個指針列，可設兩個指針i、j分別指向表分別指向表LA和和LB中的元中的元素素若若LA.elemiLB.elemj，則當前先將，則當前先將LB.elemj插入到表插入到表LC中中若若LA.elemiLB.elemj ，當前先將，當前先將LA.elemi插插入到表入到表LC中中如此循環(huán)，直到其中一個表被掃描完畢，然后再如此循環(huán)，直到其中一個表被掃描完畢，然后再將未掃

23、描完的表中剩余的所有元素放到表將未掃描完的表中剩余的所有元素放到表LC中。中。 31合并算法合并算法To merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1.

24、 Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2l3 = 012345a36To merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then incre

25、ment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2l3 = 012345a360k0j0iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If

26、a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2l3 = 012345a360k0j0iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l

27、1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2

28、catl3 = 012345a361k1j0iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then in

29、crement j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345a361k1j0iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2.

30、If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowa362k1j1iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less

31、than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowa362k1j1iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set

32、 j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3

33、= 012345cowdoga363k2j1iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then in

34、crement j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowdoga363k2j1iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k

35、.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowdogfoxa364k3j1iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If

36、a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowdogfoxa364k3j1iTo merge a1l1r1 and a2l2r2 into a3l3:

37、1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:2.1. If a1i is less than or equal to a2j:2.1.1. Copy a1i into a3k, then increment i and k.2.2. If a1i is greater than or equal to a2j:2.2.1. Copy a2j into a3k, then increment j and k.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfo

38、xliontigera2catl3 = 012345cowdogfoxgoata365k3j2iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:3. If i r1, copy a1ir1 into a3kr3.4. If j r2, copy a2jr2 into a3kr3.5. Terminate.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3

39、 = 012345cowdogfoxgoata365k3j2iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:3. If i r1, copy a1ir1 into a3kr3.4. If j r2, copy a2jr2 into a3kr3.5. Terminate.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowdogfo

40、xgoatliontigera365k3j2iTo merge a1l1r1 and a2l2r2 into a3l3:1. Set i = l1, set j = l2, and set k = l3.2. While i r1 and j r2, repeat:3. If i r1, copy a1ir1 into a3kr3.4. If j r2, copy a2jr2 into a3kr3.5. Terminate.cowl1 = 01 = r1goata1catl2 = 01234 = r2dogfoxliontigera2catl3 = 012345cowdogfoxgoatlio

41、ntigera365k3j2i32順序表合并算法實現(xiàn)順序表合并算法實現(xiàn)void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast&jlast) if(LA-elemielemj) LC-elemk= LA-elemi; i+; k+; else LC-elemk=LB-elemj;j+; k+; while(ilast) /當當LA長長,則將表則將表LA余下元素賦給表余下元素賦給表LC LC-elemk= LA-elemi;i+;k+;while(jlast) /當當LB長長,則將表則將表LB余下

42、的元素賦給表余下的元素賦給表LC LC-elemk= LB-elemj;j+;k+;LC-last=LA-last+LB-last; 33順序存儲結構的優(yōu)缺點順序存儲結構的優(yōu)缺點 優(yōu)點優(yōu)點無需為表示結點間的邏輯關系而增加額外的存儲無需為表示結點間的邏輯關系而增加額外的存儲空間；空間；可方便地隨機存取表中的任一元素。可方便地隨機存取表中的任一元素。缺點缺點插入或刪除運算不方便，除表尾的位置外，在表插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大的其它位置上進行插入或刪除操作都必須移動大量的結點，其效率較低量的結點，其效率較低; ;由于順序表要求占用連續(xù)的存儲空

43、間，存儲分配由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預先進行靜態(tài)分配。因此當表長變化較大時，只能預先進行靜態(tài)分配。因此當表長變化較大時，難以確定合適的存儲規(guī)模。難以確定合適的存儲規(guī)模。34知識回顧知識回顧-變量的存儲類別變量的存儲類別用戶存儲空間可以分為三個部分：用戶存儲空間可以分為三個部分：動態(tài)存儲區(qū)動態(tài)存儲區(qū)靜態(tài)存儲區(qū)靜態(tài)存儲區(qū)程序區(qū)程序區(qū)35知識回顧知識回顧-變量的存儲類別變量的存儲類別動態(tài)存儲區(qū)動態(tài)存儲區(qū)靜態(tài)存儲區(qū)靜態(tài)存儲區(qū)程序區(qū)程序區(qū) 在程序執(zhí)行過程中，靜在程序執(zhí)行過程中，靜態(tài)變量占據(jù)固定的存儲單態(tài)變量占據(jù)固定的存儲單元，而不動態(tài)地進行分配元，而不動態(tài)地進行分配和釋放。和釋放。

44、 全局變量全部存放在靜全局變量全部存放在靜態(tài)存儲區(qū)，在程序開始執(zhí)態(tài)存儲區(qū)，在程序開始執(zhí)行時給全局變量分配存儲行時給全局變量分配存儲區(qū)，程序行完畢就釋放。區(qū)，程序行完畢就釋放。36知識回顧知識回顧-變量的存儲類別變量的存儲類別動態(tài)存儲區(qū)動態(tài)存儲區(qū)靜態(tài)存儲區(qū)靜態(tài)存儲區(qū)程序區(qū)程序區(qū)在函數(shù)開始調用時分配動在函數(shù)開始調用時分配動態(tài)存儲空間，函數(shù)結束時態(tài)存儲空間，函數(shù)結束時釋放這些空間。釋放這些空間。 函數(shù)形式參數(shù)；函數(shù)形式參數(shù)； 自動變量（未加自動變量（未加static 聲明的局部變量）；聲明的局部變量）； 函數(shù)調用時的現(xiàn)場保護函數(shù)調用時的現(xiàn)場保護和返回地址；和返回地址；37知識回顧知識回顧-動態(tài)存儲分

45、配動態(tài)存儲分配數(shù)組的長度是預先定義好的，在整個程序中固數(shù)組的長度是預先定義好的，在整個程序中固定不變。定不變。C語言中語言中不允許動態(tài)數(shù)組類型不允許動態(tài)數(shù)組類型。例如：例如：int n;scanf(%d,&n);int an;用變量表示長度，想對數(shù)組的大小作動態(tài)說明，這用變量表示長度，想對數(shù)組的大小作動態(tài)說明，這是錯誤的是錯誤的。但是在實際的編程中，往往會發(fā)生這種。但是在實際的編程中，往往會發(fā)生這種情況，即所需的內(nèi)存空間取決于實際輸入的數(shù)據(jù)，情況，即所需的內(nèi)存空間取決于實際輸入的數(shù)據(jù)，而無法預先確定。而無法預先確定。為了解決上述問題，為了解決上述問題，C語言提供了一些內(nèi)存管理函數(shù)，可語

46、言提供了一些內(nèi)存管理函數(shù)，可以按需要動態(tài)地分配內(nèi)存空間，也可把不再使用的空間回以按需要動態(tài)地分配內(nèi)存空間，也可把不再使用的空間回收待用，為有效地利用內(nèi)存資源提供了手段。收待用，為有效地利用內(nèi)存資源提供了手段。 38第二章線性表第二章線性表線性表的概念及運算線性表的概念及運算 線性表的順序存儲線性表的順序存儲 線性表的鏈式存儲線性表的鏈式存儲單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 雙向鏈表雙向鏈表一元多項式的表示及相加一元多項式的表示及相加 要點小結要點小結參考書目及網(wǎng)絡資源參考書目及網(wǎng)絡資源討論時間討論時間39鏈表的定義與分類鏈表的定義與分類鏈表定義鏈表定義采用鏈式存儲結構的線性表稱為采用鏈式存儲結構

47、的線性表稱為鏈表鏈表(Linked list)。鏈表分類鏈表分類從實現(xiàn)角度看，鏈表可分為從實現(xiàn)角度看，鏈表可分為動態(tài)鏈表動態(tài)鏈表靜態(tài)鏈表靜態(tài)鏈表從鏈接方式的角度看，鏈表可分為從鏈接方式的角度看，鏈表可分為單鏈表單鏈表循環(huán)鏈表循環(huán)鏈表雙鏈表雙鏈表40單鏈表單鏈表(Singly linked list)結點結點(Node)為了正確地表示結點間的邏輯關系，必須為了正確地表示結點間的邏輯關系，必須在存儲線性表的每個在存儲線性表的每個數(shù)據(jù)元素值數(shù)據(jù)元素值的同時，存的同時，存儲指示其儲指示其后繼結點的地址后繼結點的地址（或位置）信息，（或位置）信息，這兩部分信息組成的存儲映象叫做這兩部分信息組成的存儲映象

48、叫做結點結點（Node）。）。 41單鏈表單鏈表(Singly linked list)單鏈表單鏈表(Singly linked list)鏈表中的每個結點只有一個指針域，我們鏈表中的每個結點只有一個指針域，我們將這種鏈表稱為將這種鏈表稱為單鏈表單鏈表。單鏈表包括兩個域：單鏈表包括兩個域：數(shù)據(jù)域數(shù)據(jù)域用來存儲結點的值；用來存儲結點的值；指針域指針域用來存儲數(shù)據(jù)元素的直接后繼的地用來存儲數(shù)據(jù)元素的直接后繼的地址（或位置）。址（或位置）。 頭指針：指向鏈表頭結點的指針。頭指針：指向鏈表頭結點的指針。42單鏈表單鏈表(Singly linked list)帶頭結點的單鏈表帶頭結點的單鏈表 帶頭結點的

49、空單鏈表帶頭結點的空單鏈表43單鏈表的存儲結構描述單鏈表的存儲結構描述typedef struct Node / * 結點類型定義結點類型定義 * / ElemType data; struct Node * next;Node, *LinkList; /* LinkList為結構指針類型為結構指針類型*/ 44單鏈表上的基本運算單鏈表上的基本運算線性表的基本運算線性表的基本運算建立單鏈表建立單鏈表單鏈表查找單鏈表查找單鏈表插入操作單鏈表插入操作單鏈表刪除單鏈表刪除算法應用示例算法應用示例求單鏈表的長度求單鏈表的長度求兩個集合的差求兩個集合的差 45建立單鏈表建立單鏈表頭插法建表頭插法建表算法

50、描述：從一個空表開始，重復讀入數(shù)算法描述：從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭結點之后，直至讀入結束標志為止。的表頭結點之后，直至讀入結束標志為止。46建立單鏈表建立單鏈表47頭插法建表算法頭插法建表算法Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /設置標志設置標志,初值為初值為1,當輸入當輸入“$”時時,flag為為0,建表結束建表結束L=(Linklist)malloc(

51、sizeof(Node);/為頭結點分配空間為頭結點分配空間L-next=NULL; while(flag) c=getchar(); if(c!=$) /為讀入的字符分配存儲空間為讀入的字符分配存儲空間 s=(Node*)malloc(sizeof(Node); s-data=c;s-next=L-next; L-next=s; else flag=0;48頭插法建表算法頭插法建表算法49尾插法建表尾插法建表50分配內(nèi)存空間函數(shù)分配內(nèi)存空間函數(shù)malloc其函數(shù)原型為其函數(shù)原型為void *malloc(unsigned int size); 調用形式：調用形式：(類型說明符類型說明符*)m

52、alloc(size)“類型說明符類型說明符”表示把該區(qū)域用于何種數(shù)據(jù)類型。表示把該區(qū)域用于何種數(shù)據(jù)類型。(類型說明符類型說明符*)表示把返回值強制轉換為該類型指針。表示把返回值強制轉換為該類型指針?！皊ize”是一個無符號整數(shù)。是一個無符號整數(shù)。功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為size字節(jié)的連字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。例如：續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。例如：pc=(char *)malloc(100);表示分配表示分配100 個字節(jié)的內(nèi)存空間，并強制轉換為字符數(shù)組類型，個字節(jié)的內(nèi)存空間，并強制轉換為字符數(shù)組類型，函

53、數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針函數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針變量變量pc。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則返回空指針則返回空指針(NULL)。51釋放內(nèi)存空間函數(shù)釋放內(nèi)存空間函數(shù)free其函數(shù)原型為其函數(shù)原型為:void free (void *p);調用形式：調用形式：free (void *p);功能：釋放功能：釋放p所指向的一塊內(nèi)存空間，所指向的一塊內(nèi)存空間，p是一是一個任意類型的指針變量，它指向被釋放區(qū)域個任意類型的指針變量，它指向被釋放區(qū)域的首地址。被釋放區(qū)應是由的首地址。被釋放

54、區(qū)應是由malloc或或calloc函函數(shù)所分配的區(qū)域。數(shù)所分配的區(qū)域。free函數(shù)無返回值。函數(shù)無返回值。52尾插法建表算法尾插法建表算法Linklist CreateFromTail() LinkList L; Node *r, *s; int flag =1; L=(Node *)malloc(sizeof(Node);/為頭結點分配空間為頭結點分配空間 L-next=NULL; r=L; /r指針始終動態(tài)指向鏈表的當指針始終動態(tài)指向鏈表的當前表尾前表尾 while(flag) /輸入輸入“$”時時flag為為0，建表結束，建表結束 c=getchar(); if(c!=$) s=(No

55、de*)malloc(sizeof(Node); s-data=c;r-next=s;r=s else flag=0; r-next=NULL; 53尾插法建表尾插法建表54單鏈表查找單鏈表查找The effect of the assignment cur = cur-next55單鏈表查找單鏈表查找按序號查找按序號查找算法描述：設帶頭結點的單鏈表的長度為算法描述：設帶頭結點的單鏈表的長度為n，要查找表中第要查找表中第i個結點，則需要從單鏈表的個結點，則需要從單鏈表的頭指針頭指針L出發(fā)，從頭結點（出發(fā)，從頭結點（L-next）開始）開始順著鏈域掃描，用指針順著鏈域掃描，用指針p指向當前掃描到

56、的指向當前掃描到的結點結點,初值指向頭結點（初值指向頭結點（pL-next），用），用j做做記數(shù)器，累計當前掃描過的結點數(shù)（初值為記數(shù)器，累計當前掃描過的結點數(shù)（初值為0），當），當j = i 時，指針時，指針p所指的結點就是要找所指的結點就是要找的第的第i個結點個結點 。56按序號查找算法按序號查找算法/在帶頭結點的單鏈表在帶頭結點的單鏈表L中查找第中查找第i個結點個結點,若找到若找到(1in),則返回該結點的存儲位置則返回該結點的存儲位置;否則返回否則返回NULLNode *Get(LinkList L, int i) Node *p; p=L; j=0; /從頭結點開始掃描從頭結點開始掃

57、描 while (p-next!=NULL)&(jnext; /掃描下一結點掃描下一結點 j +; /已掃描結點計數(shù)器已掃描結點計數(shù)器 if (i=j) return p; /找到了第找到了第i個結點個結點 else return NULL;/找不到，找不到，i0或或in57單鏈表查找單鏈表查找按值查找按值查找算法描述：按值查找是指在單鏈表中查找是否有算法描述：按值查找是指在單鏈表中查找是否有結點值等于結點值等于e的結點，若有的話，則返回首次找到的結點，若有的話，則返回首次找到的其值為的其值為e的結點的存儲位置，否則返回的結點的存儲位置，否則返回NULL。查找過程從單鏈表的頭指針指向的

58、頭結點出發(fā)，查找過程從單鏈表的頭指針指向的頭結點出發(fā)，順著鏈逐個將結點的值和給定值順著鏈逐個將結點的值和給定值e作比較。作比較。58按值查找算法按值查找算法/在帶頭結點的單鏈表在帶頭結點的單鏈表L中查找其結點值等于中查找其結點值等于key的結的結點，若找到則返回該結點的位置點，若找到則返回該結點的位置p，否則返回，否則返回NULL Node *Locate(LinkList L,ElemType key) Node *p; p=L-next; /從表中第一個結點比較從表中第一個結點比較 while (p!=NULL) if (p-data!=key) p=p-next; else break;

59、 /找到結點找到結點key，退出循環(huán)，退出循環(huán) return p;59單鏈表插入操作單鏈表插入操作算法描述算法描述要在帶頭結點的單鏈表要在帶頭結點的單鏈表L中第中第i個數(shù)據(jù)元素個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素e，需要首先在單鏈，需要首先在單鏈表中找到第表中找到第i-1個結點并由指針個結點并由指針pre指示，然指示，然后申請一個新的結點并由指針后申請一個新的結點并由指針s指示，其數(shù)指示，其數(shù)據(jù)域的值為據(jù)域的值為e，并修改第，并修改第i-1個結點的指針使個結點的指針使其指向其指向s，然后使，然后使s結點的指針域指向第結點的指針域指向第i個個結點。結點。60單鏈表插入操作單鏈表插入

60、操作61單鏈表插入操作單鏈表插入操作To insert a node between two nodesnewPtr-next = cur;prev-next = newPtr;62單鏈表插入操作單鏈表插入操作To insert a node at the beginning of a linked listnewPtr-next = head;head = newPtr;63單鏈表插入操作單鏈表插入操作Inserting at the end of a linked list is not a special case if cur is NULLnewPtr-next = cur;prev-next = newPtr;64單鏈表插入操作單鏈表插入