Chapter2_線性表

1、第第2章章 線性表線性表王建芳王建芳計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院河南理工大學(xué)河南理工大學(xué) WIN-TC是一個是一個TC2 WINDOWS平臺開發(fā)工具。平臺開發(fā)工具。該軟件使用該軟件使用TC2為內(nèi)核，提供為內(nèi)核，提供WINDOWS平臺的平臺的開發(fā)界面，因此也就支持開發(fā)界面，因此也就支持WINDOWS平臺下的功平臺下的功能，例如剪切、復(fù)制、粘貼和查找替換等。而且能，例如剪切、復(fù)制、粘貼和查找替換等。而且在功能上也有它的獨(dú)特特色例如語法加亮、在功能上也有它的獨(dú)特特色例如語法加亮、C內(nèi)內(nèi)嵌匯編、自定義擴(kuò)展庫的支持等。并提供一組相嵌匯編、自定義擴(kuò)展庫的支持等。并提供一組相關(guān)輔助工具令你在編程

2、過程中更加方便。關(guān)輔助工具令你在編程過程中更加方便。 wintc不能編不能編windows應(yīng)用程序，它只能編控制應(yīng)用程序，它只能編控制臺應(yīng)用程序。臺應(yīng)用程序。2 眾所周知眾所周知TC是是DOS下的下的Text界面，所以界面，所以WIN-TC 和和 TC 屬于是同一個編譯器不同界面而已。屬于是同一個編譯器不同界面而已。 而而VC是微軟公司提供的功能強(qiáng)大的是微軟公司提供的功能強(qiáng)大的Window平臺平臺開發(fā)工具，支持開發(fā)工具，支持C,C+等語言，可以開發(fā)等語言，可以開發(fā)DOS和和Window平臺的程序。而平臺的程序。而TC只能開發(fā)只能開發(fā)DOS平臺下平臺下的程序，現(xiàn)多用來教學(xué)。的程序，現(xiàn)多用來教學(xué)。

3、3 DEV CPP DEV C+是一個是一個C+編譯器編譯器,遵循的是遵循的是GCC標(biāo)準(zhǔn)的編譯器?，F(xiàn)在的標(biāo)準(zhǔn)的編譯器?，F(xiàn)在的DEV C+支持最新支持最新的的C+和和C語言標(biāo)準(zhǔn)。語言標(biāo)準(zhǔn)。 而而turbo C2.0是是DOS時代的遺物了。很老了，一些新標(biāo)準(zhǔn)時代的遺物了。很老了，一些新標(biāo)準(zhǔn)并不支持，并不支持， 4 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表?xiàng)ｊ?duì)列隊(duì)列樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的

4、三個方面數(shù)據(jù)結(jié)構(gòu)的三個方面： 1 問題提出問題提出 一條記錄有學(xué)號和成績兩個數(shù)據(jù)項(xiàng)，依一條記錄有學(xué)號和成績兩個數(shù)據(jù)項(xiàng)，依次輸入數(shù)據(jù)建立一個有序表（按成績由次輸入數(shù)據(jù)建立一個有序表（按成績由大到小）。其中輸入的數(shù)據(jù)如下（學(xué)號大到小）。其中輸入的數(shù)據(jù)如下（學(xué)號，成績）：，成績）：(1,70),(2,85),(3,75), (1,70),(2,85),(3,75), (4,90),(5,60),(6,80),(7,76),(8,50)(4,90),(5,60),(6,80),(7,76),(8,50)等等。等等。 2 問題分析問題分析 可用結(jié)構(gòu)體數(shù)組來存儲記錄?？捎媒Y(jié)構(gòu)體數(shù)組來存儲記錄。 但數(shù)組一般

5、固定長度，分配多大空間才合適？但數(shù)組一般固定長度，分配多大空間才合適？ 如何實(shí)現(xiàn)每輸入一條記錄都保持有序？如何實(shí)現(xiàn)每輸入一條記錄都保持有序？ 如果需要增加其它功能，如刪除、修改、查詢、如果需要增加其它功能，如刪除、修改、查詢、排序，如何實(shí)現(xiàn)？排序，如何實(shí)現(xiàn)？ 如果數(shù)組長度不固定，如何動態(tài)分配數(shù)組空間？如果數(shù)組長度不固定，如何動態(tài)分配數(shù)組空間？ 如果記錄還有姓名、課程等數(shù)據(jù)項(xiàng)，應(yīng)如何修改如果記錄還有姓名、課程等數(shù)據(jù)項(xiàng)，應(yīng)如何修改程序？程序？ 8第第2章章 線性表線性表2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性

6、表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 2.4 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加 92.1 線性表的類型定義線性表的類型定義 線性結(jié)構(gòu)：第線性結(jié)構(gòu)：第2章至第章至第4章將討論章將討論“線性表線性表”、“棧?！?、“隊(duì)列隊(duì)列”、“串串” 線性結(jié)構(gòu)特點(diǎn)：有線性結(jié)構(gòu)特點(diǎn)：有“頭頭”元素元素有有“尾尾”元素元素，中，中間的元素有間的元素有“前驅(qū)前驅(qū)”元素元素和和“后繼后繼”元素元素 線性表是一個數(shù)據(jù)元素的線性表是一個數(shù)據(jù)元素的有序（次序）集有序（次序）集(1)集合中必存在唯一的一個集合中必存在唯一的一個“第一元素第一元素”；(2)集合中必存在唯一的一個集合中必存在唯一的一個 “最后元素最后元素” ；(3)除最后

7、元素在外，均有除最后元素在外，均有 唯一的后繼唯一的后繼；(4)除第一元素之外，均有除第一元素之外，均有 唯一的前驅(qū)唯一的前驅(qū)。 102.1 線性表的類型定義線性表的類型定義抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型線性表線性表的定義如下：的定義如下：ADT List 數(shù)據(jù)對象：數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 稱稱 n 為線性表的為線性表的表長表長; 稱稱 n=0 時的線性表為時的線性表為空表空表。 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱稱 i 為為 a

8、i 在線性表中的在線性表中的位序位序。 112.1 線性表的類型定義線性表的類型定義 基本操作：基本操作： 結(jié)構(gòu)初始化操作（結(jié)構(gòu)初始化操作（添加添加） 結(jié)構(gòu)銷毀操作（結(jié)構(gòu)銷毀操作（刪除刪除） 引用型操作（引用型操作（查詢查詢） 加工型操作（加工型操作（修改修改）ADT List 122.1 線性表的類型定義線性表的類型定義 結(jié)構(gòu)初始化操作（結(jié)構(gòu)初始化操作（添加添加）InitList( &L ) 操作結(jié)果：操作結(jié)果：構(gòu)造一個空的線性表構(gòu)造一個空的線性表L。 結(jié)構(gòu)銷毀操作（結(jié)構(gòu)銷毀操作（刪除刪除）DestroyList( &L ) 初始條件：初始條件：線性表線性表 L 已存在。已存在。 操作結(jié)果：

9、操作結(jié)果：銷毀線性表銷毀線性表 L。 132.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e )GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( ) 142.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）ListEmpty( L )（線性表判空）（線性表判空）初始條件：初始條件：線性

10、表線性表L已存在。已存在。操作結(jié)果：操作結(jié)果：若若L為空表，則返回為空表，則返回TRUE， 否則返回否則返回FALSE。 152.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）ListLength( L ) （求線性表的長度）（求線性表的長度）初始條件：初始條件：線性表線性表L已存在。已存在。操作結(jié)果：操作結(jié)果：返回返回L中元素個數(shù)。中元素個數(shù)。 162.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢） PriorElem( L, cur_e, &pre_e )（求數(shù)據(jù)元素的前驅(qū)）（求數(shù)據(jù)元素的前驅(qū)）初始條件：初始條件：線性表線性表L已存在。已

11、存在。操作結(jié)果：操作結(jié)果：若若cur_e是是L的元素，但不是第一，的元素，但不是第一，則用則用pre_e 返回它的前驅(qū)，否則操作失敗，返回它的前驅(qū)，否則操作失敗，pre_e無定義。無定義。 172.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）NextElem( L, cur_e, &next_e )（求數(shù)據(jù)元素的后繼）（求數(shù)據(jù)元素的后繼）初始條件：初始條件：線性表線性表L已存在。已存在。操作結(jié)果：操作結(jié)果：若若cur_e是是L的元素，但不是最后一的元素，但不是最后一個，則用個，則用next_e返回它的后繼，否則操作失返回它的后繼，否則操作失敗，敗，next_e無定義

12、。無定義。 182.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）GetElem( L, i, &e ) （求線性表中某個數(shù)據(jù)元素）（求線性表中某個數(shù)據(jù)元素）初始條件：初始條件：線性表線性表L已存在。且已存在。且 1iListLength (L)。操作結(jié)果：操作結(jié)果：用用 e 返回返回L中第中第 i 個元素的值。個元素的值。 192.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）LocateElem( L, e, compare( ) )（定位函數(shù)）（定位函數(shù)）初始條件：初始條件：線性表線性表L已存在，已存在，e為給定值，為給定值， comp

13、are( )是元素判定函數(shù)。是元素判定函數(shù)。操作結(jié)果：操作結(jié)果：返回返回L中第中第1個個與與e滿足關(guān)系滿足關(guān)系compare( )的元素的位序。若這樣的元素不存的元素的位序。若這樣的元素不存在，則返回值為在，則返回值為0。 202.1 線性表的類型定義線性表的類型定義 引用型操作（引用型操作（查詢查詢）ListTraverse(L, visit( )（遍歷線性表）（遍歷線性表）初始條件：初始條件：線性表線性表L已存在，已存在，visit() 為某個訪問為某個訪問函數(shù)。函數(shù)。操作結(jié)果：操作結(jié)果：依次依次對對L的每個元素調(diào)用函數(shù)的每個元素調(diào)用函數(shù)visit( )。一旦一旦visit( )失敗，則操

14、作失敗。失敗，則操作失敗。 212.1 線性表的類型定義線性表的類型定義 加工型操作（加工型操作（修改修改）ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) 222.1 線性表的類型定義線性表的類型定義 加工型操作（加工型操作（修改修改）ClearList( &L )（線性表置空）（線性表置空）初始條件：初始條件：線性表線性表L已存在。已存在。操作結(jié)果：操作結(jié)果：將將L重置為空表。重置為空表。 232.1 線性表的類型定義線性表的類型定義 加工型操作（加工型操作（修改修改）PutElem

15、( &L, i, &e ) （改變數(shù)據(jù)元素的值）（改變數(shù)據(jù)元素的值）初始條件：初始條件：線性表線性表L已存在，且已存在，且 1iListLength (L) 。操作結(jié)果：操作結(jié)果： L中第中第i個元素賦值同個元素賦值同e的值。的值。 242.1 線性表的類型定義線性表的類型定義 加工型操作（加工型操作（修改修改） ListInsert( &L, i, e )（插入數(shù)據(jù)元素）（插入數(shù)據(jù)元素）初始條件：初始條件：線性表線性表L已存在，已存在， 且且 1iListLength (L)+1 。 操作結(jié)果：操作結(jié)果：在在L的第的第i個元素之前個元素之前插入新的元插入新的元素素e，L的長度增的長度增1。

16、252.1 線性表的類型定義線性表的類型定義 加工型操作（加工型操作（修改修改）ListDelete(&L, i, &e)（刪除數(shù)據(jù)元素）（刪除數(shù)據(jù)元素）初始條件：初始條件：線性表線性表L已存在且非空，已存在且非空， 1iLengthList(L) 。操作結(jié)果：操作結(jié)果：刪除刪除L的第的第i個元素，并用個元素，并用e返回其值，返回其值，L的長度減的長度減1。 262.1 線性表的類型定義線性表的類型定義 利用上述定義的利用上述定義的線性表線性表可以實(shí)現(xiàn)其它更復(fù)雜可以實(shí)現(xiàn)其它更復(fù)雜的操作的操作 事物可從簡單演化為復(fù)雜，復(fù)雜中包含簡單。事物可從簡單演化為復(fù)雜，復(fù)雜中包含簡單。例如，生物的多樣性、社

17、會的自然性例如，生物的多樣性、社會的自然性 哲學(xué)意義上哲學(xué)意義上萬物發(fā)展的原動力萬物發(fā)展的原動力：物質(zhì)之間的：物質(zhì)之間的相互作用相互作用 內(nèi)因內(nèi)因(內(nèi)部元素之間的作用內(nèi)部元素之間的作用)通過通過外因外因(外部數(shù)外部數(shù)據(jù)之間的作用據(jù)之間的作用)表現(xiàn)出來表現(xiàn)出來 272.1 線性表的類型定義線性表的類型定義例例 2-1 假設(shè)假設(shè):有兩個集合有兩個集合 A 和和 B 分別用兩個線分別用兩個線性表性表 LA 和和 LB 表示，即：線性表中的數(shù)據(jù)元表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)欲求一個新的集合素即為集合中的成員。現(xiàn)欲求一個新的集合AAB。上述問題可演繹為：上述問題可演繹為：要求對線性表

18、做如下操作：要求對線性表做如下操作： 擴(kuò)大線性表擴(kuò)大線性表 LA，將存在于線性表，將存在于線性表LB 中而中而不存在于線性表不存在于線性表 LA 中的數(shù)據(jù)元素插入到線性中的數(shù)據(jù)元素插入到線性表表 LA 中去。中去。 282.1 線性表的類型定義線性表的類型定義操作步驟：操作步驟：1從線性表從線性表LB中依次察看每個數(shù)據(jù)元素中依次察看每個數(shù)據(jù)元素;GetElem(LB, i, &e)2依值在線性表依值在線性表LA中進(jìn)行查訪中進(jìn)行查訪;LocateElem(LA, e, equal( )3若不存在，則插入之。若不存在，則插入之。ListInsert(&LA, n+1, e) 292.1 線性表的類

19、型定義線性表的類型定義void union(List &La, List Lb) La_len = ListLength(La); / 求線性表的長度求線性表的長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, &e); / 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal( ) ) ListInsert(&La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之 / union 302.

20、1 線性表的類型定義線性表的類型定義例例 2-2 已知一個非純集合已知一個非純集合 B，試構(gòu)造一個純集，試構(gòu)造一個純集合合 A，使，使 A中只包含中只包含 B 中所有值各不相中所有值各不相 同的數(shù)同的數(shù)據(jù)元素。據(jù)元素。仍選用線性表表示集合。仍選用線性表表示集合。 312.1 線性表的類型定義線性表的類型定義集合集合 B集合集合 A從集合從集合 B 取出物件放入集合取出物件放入集合 A要求集合要求集合A中中同樣物件不能有兩件以上同樣物件不能有兩件以上因此，因此，算法的策略應(yīng)該和例算法的策略應(yīng)該和例2-1相同相同 322.1 線性表的類型定義線性表的類型定義void union(List &La,

21、 List Lb) InitList(&La); / 構(gòu)造構(gòu)造(空的空的)線性表線性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, &e); / 取取Lb中第中第 i 個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(&La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之 / union 332.1 線性表的類型定義線性表

22、的類型定義試改變結(jié)構(gòu)，以試改變結(jié)構(gòu)，以有序表有序表表示集合。表示集合。若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即元素在線性表中依值非遞減或非遞增有序排列，即 aiai-1 或或 aiai-1(i = 2,3, n) 則稱該線性表為則稱該線性表為有序表有序表(Ordered List)。 例如：例如： （2，3，3，5，6，6，6，8，12） 對集合對集合 B 而言，值相同的數(shù)據(jù)元素必定相鄰；而言，值相同的數(shù)據(jù)元素必定相鄰； 對集合對集合 A 而言，數(shù)據(jù)元素依值從小至大的順序插入。而言，數(shù)據(jù)元素依值從小

23、至大的順序插入。 數(shù)據(jù)結(jié)構(gòu)改變了，解決問題的策略也相應(yīng)要改變。數(shù)據(jù)結(jié)構(gòu)改變了，解決問題的策略也相應(yīng)要改變。 342.1 線性表的類型定義線性表的類型定義void purge(List &La, List Lb) InitList(&LA); La_len = ListLength(La); / 求線性表的長度求線性表的長度 Lb_len =ListLength(Lb); for (i = 1; i b時，時，c=b 362.1 線性表的類型定義線性表的類型定義void MergeList(List La, List Lb, List &Lc) / 本算法將非遞減的有序表本算法將非遞減的有序表

24、La 和和 Lb 歸并為歸并為 Lc InitList(&Lc); / 構(gòu)造空的線性表構(gòu)造空的線性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) / La 和和 Lb 均非空均非空 while (i=La_len) / 若若 La 不空不空 while (j=Lb_len) / 若若 Lb 不空不空 / merge_list 372.1 線性表的類型定義線性表的類型定義 / La 和和 Lb 均非空均非空 / i = j = 1,

25、 k = 0 GetElem(La, i, &ai); GetElem(Lb, j, &bj); if (ai = bj) / 將將 ai 插入到插入到 Lc 中中 ListInsert(&Lc, +k, ai); +i; else / 將將 bj 插入到插入到 Lc 中中 ListInsert(&Lc, +k, bj); +j; 382.1 線性表的類型定義線性表的類型定義 while (i = La_len) / 當(dāng)當(dāng)La不空時不空時 GetElem(La, i+, &ai); ListInsert(&Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j

26、 = Lb_len) / 當(dāng)當(dāng)Lb不空時不空時 GetElem(Lb, j+, &bj); ListInsert(&Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素 392.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 順序映象順序映象 以以 x 的存儲位置和的存儲位置和 y 的存儲位置之間某種關(guān)的存儲位置之間某種關(guān)系表示邏輯關(guān)系系表示邏輯關(guān)系。 最簡單的一種順序映象方法是：最簡單的一種順序映象方法是： 令令 y 的存儲位置和的存儲位置和 x 的的存儲位置相鄰存儲位置相鄰。 用一組用一組地址連續(xù)地址連續(xù)的存儲單元的存儲單元依次存放依次存放線性表線性表中的數(shù)據(jù)元素中的數(shù)

27、據(jù)元素 402.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 用一組用一組地址連續(xù)地址連續(xù)的存儲單元的存儲單元依次存放依次存放線性表線性表中的數(shù)據(jù)元素中的數(shù)據(jù)元素 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的稱作線性表的基地址基地址 412.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 以以“存儲位置相鄰存儲位置相鄰”表示有序?qū)Ρ硎居行驅(qū)?即：即： LOC(ai) = LOC(ai-1) + C 所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置據(jù)元素的存儲位置 LOC(ai) = LOC(a1) + (i-1)

28、C一個數(shù)據(jù)元素所占存儲量一個數(shù)據(jù)元素所占存儲量基地址基地址 422.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序映像的順序映像的 C 語言描述語言描述#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量線性表存儲空間的分配增量typedef struct ElemType *elem; / 存儲空間基址存儲空間基址 int length; / 當(dāng)前長度當(dāng)前長度 int listsize; / 當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 / (以以sizeof(

29、ElemType)為單位為單位 SqList; / 俗稱俗稱 順序表順序表 432.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 線性表的基本操作在順序表中的實(shí)現(xiàn)線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(&L) / 結(jié)構(gòu)初始化結(jié)構(gòu)初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i, &e) / 刪除元素刪除元素 442.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)Status InitList_Sq( SqList &L ) / 構(gòu)造一個空的線性表構(gòu)造一個空的線性

30、表 L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType) ); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE return OK; / InitList_Sq算法時間復(fù)雜度：算法時間復(fù)雜度：O(1) 452.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)例如：順序表例如：順序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可見，基本操

31、作是：可見，基本操作是：將順序表中的元素逐將順序表中的元素逐個和給定值個和給定值 e 相比較。相比較。 462.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 i = 1; / i 的初值為第的初值為第 1 元素的位序元素的位序 p = L.elem; / p 的初值為第的初

32、值為第 1 元素的存儲位置元素的存儲位置 while (i = L.length & !(*compare)(*p+, e) i +; if (i = L.length) return i; else return 0; / LocateElem_Sq 算法的算法的時間復(fù)雜度時間復(fù)雜度為：為：O( ListLength(L) ) 472.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 線性表操作線性表操作ListInsert(&L, i, e)的實(shí)現(xiàn)的實(shí)現(xiàn) 首先分析首先分析: 插入元素時，線性表的邏輯結(jié)構(gòu)插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？ 482.2 線性表的順序表示和實(shí)

33、現(xiàn)線性表的順序表示和實(shí)現(xiàn) (a1, , ai-1, ai, , an) 改變?yōu)楦淖優(yōu)?(a1, , ai-1, e, ai, , an), a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的長度增加表的長度增加 492.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表在順序表L的第的第 i 個元素之前插入新的元素個元素之前插入新的元素e, / i 的合法范圍為的合法范圍為 1iL.length+1 q = &(L.elemi-1); / q 指示插入位置指示插

34、入位置 for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移 *q = e; / 插入插入e +L.length; / 表長增表長增1 return OK; / ListInsert_Sq 算法算法時間復(fù)雜度時間復(fù)雜度為為: O( ListLength(L) ) 502.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)11) 1(niiisinpE11) 1(11niisinnE 若假定在線性表中任何一個位置上進(jìn)行若假定在線性表中任何一個位置上進(jìn)行插入的概插入的概率率都是都是相等相等的，

35、則的，則移動元素的期望值移動元素的期望值為為：2n 假設(shè)在第假設(shè)在第 i 個元素之前插入的概率為個元素之前插入的概率為 ， 則在長度為則在長度為n 的線性表中的線性表中插入一個元素所需插入一個元素所需移動元素次數(shù)的期望值移動元素次數(shù)的期望值為：為：ip 512.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配當(dāng)前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.

36、listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗存儲分配失敗 L.elem = newbase; / 新基址新基址 L.listsize += LISTINCREMENT; / 增加存儲容量增加存儲容量 522.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)21 18 30 75 42 56 8721 18 30 75例如：例如：ListInsert_Sq(&L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置

37、指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p 532.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) 線性表操作線性表操作ListDelete(&L, i, &e)的實(shí)現(xiàn)的實(shí)現(xiàn) 首先分析首先分析: 刪除元素時，線性表的邏輯結(jié)構(gòu)刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)發(fā)生什么變化生什么變化？ 542.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn) (a1, , ai-1, ai, ai+1, , an) 改變?yōu)楦淖優(yōu)?(a1, , ai-1, ai+1, , an)ai+1an, 表的長度減少表的長度減少a1 a2 ai-1

38、ai ai+1 ana1 a2 ai-1 552.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)Status ListDelete_Sq(SqList &L, int i, ElemType &e) 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; / 被刪除元素

39、之后的元素左移被刪除元素之后的元素左移 -L.length; / 表長減表長減1 return OK; / ListDelete_Sq 算法算法時間復(fù)雜度時間復(fù)雜度為為: O( ListLength(L) 562.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)考慮移動元素的平均情況考慮移動元素的平均情況:假設(shè)刪除第假設(shè)刪除第 i 個元素的概率為個元素的概率為 , 則在長度為則在長度為n 的線性表中的線性表中刪除一個元素刪除一個元素所需所需移動元移動元素次數(shù)的期望值素次數(shù)的期望值為：為：iqniidlinqE1)(nidlinnE1)(121n若假定在線性表中任何一個位置上進(jìn)行刪除的若假定在線

40、性表中任何一個位置上進(jìn)行刪除的概率概率都是都是相等相等的，則的，則移動元素的期望值移動元素的期望值為：為： 572.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; / p指向第一個結(jié)點(diǎn)，指向第一個結(jié)點(diǎn)，j為計數(shù)器為計數(shù)器 while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p 指向第指向第 i 個元素，或個元素，或 p 為空為空 if

41、 ( !p | ji ) return ERROR; / 第第 i 個元素不存在個元素不存在 e = p-data; / 取得第取得第 i 個元素個元素 return OK; / GetElem_L 算法算法時間復(fù)雜度時間復(fù)雜度為為: O(ListLength(L) 662.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)ai-1 線性表的操作線性表的操作 ListInsert_L(&L, i, e) 在單鏈表中的實(shí)現(xiàn)在單鏈表中的實(shí)現(xiàn)： 有序?qū)τ行驅(qū)?a 改變?yōu)楦淖優(yōu)?a , e 和和e, a eaiai-1 672.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 可見，在鏈表中插入結(jié)點(diǎn)只需

42、要修改指針。可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時，若要在第但同時，若要在第 i 個結(jié)點(diǎn)之前插入元素，個結(jié)點(diǎn)之前插入元素，修改的是第修改的是第 i-1 個結(jié)點(diǎn)的指針。個結(jié)點(diǎn)的指針。 因此，在單鏈表中第因此，在單鏈表中第 i 個結(jié)點(diǎn)之前進(jìn)行插入個結(jié)點(diǎn)之前進(jìn)行插入的基本操作為的基本操作為: 找到線性表中第找到線性表中第i-1個結(jié)點(diǎn)，然后修改其指向個結(jié)點(diǎn)，然后修改其指向后繼的指針。后繼的指針。 682.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)Status ListInsert_L(LinkList &L, int i, ElemType e) / L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法

43、為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 / 在鏈表中第在鏈表中第i 個結(jié)點(diǎn)之前插入新的元素個結(jié)點(diǎn)之前插入新的元素 e p = L; j = 0; while (p & j next; +j; / 尋找第尋找第 i-1 個結(jié)點(diǎn)個結(jié)點(diǎn) if (!p | j i-1) return ERROR; / i 大于表長或者小于大于表長或者小于1 / LinstInsert_L 算法的算法的時間復(fù)雜度時間復(fù)雜度為為:O(ListLength(L) 692.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)s = (LinkList) malloc ( sizeof (LNode); / 生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s-d

44、ata = e; s-next = p-next; p-next = s; / 插入插入return OK; eai-1aiai-1sp 702.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的操作線性表的操作ListDelete _L(&L, i, &e)在鏈表在鏈表中的實(shí)現(xiàn)中的實(shí)現(xiàn):有序?qū)τ行驅(qū)?和和 改變?yōu)楦淖優(yōu)?ai-1aiai+1ai-1 712.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)Status ListDelete_L(LinkList &L, int i, ElemType &e) / 刪除以刪除以 L 為頭指針為頭指針(帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn))的單鏈表中第的單鏈表

45、中第 i 個結(jié)點(diǎn)個結(jié)點(diǎn) p = L; j = 0; while (p-next & j next; +j; / 尋找第尋找第 i 個結(jié)點(diǎn)，并令個結(jié)點(diǎn)，并令 p 指向其前趨指向其前趨 if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理刪除位置不合理 q = p-next; p-next = q-next; / 刪除并釋放結(jié)點(diǎn)刪除并釋放結(jié)點(diǎn) e = q-data; free(q); return OK; / ListDelete_L算法的算法的時間復(fù)雜度時間復(fù)雜度為為: O(ListLength(L) 722.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)

46、現(xiàn) 在單鏈表中刪除第在單鏈表中刪除第 i 個結(jié)點(diǎn)的基本操作為個結(jié)點(diǎn)的基本操作為:找到線找到線性表中第性表中第i-1個結(jié)點(diǎn)，修改其指向后繼的指針。個結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq 732.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 如何得到單鏈表如何得到單鏈表? 鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要預(yù)先分配鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要預(yù)先分配空間，因此空間，因此生成鏈表的過程生成鏈表的過程是一個結(jié)點(diǎn)是一個結(jié)點(diǎn)“逐逐個插入個插入” 的過程。的過程。 742.3 線性表的

47、鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)例如：逆位序輸入例如：逆位序輸入 n 個數(shù)據(jù)元素的值，個數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：操作步驟：一、建立一個一、建立一個“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素an， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a1為止。為止。 752.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)void CreateList_L(LinkList &L, int n) / 逆序輸入逆序輸入 n 個數(shù)據(jù)

48、元素，建立帶頭結(jié)點(diǎn)的單鏈表個數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一個帶頭結(jié)點(diǎn)的單鏈表先建立一個帶頭結(jié)點(diǎn)的單鏈表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 輸入一個元素值輸入一個元素值 p-next = L-next; L-next = p; / 插入插入 / CreateList_L算法的算法的時間復(fù)雜度時間復(fù)雜度為為: O(Listlength(L) 762.3 線性

49、表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 最后一個結(jié)點(diǎn)的指針域的指針又指回第一個結(jié)的鏈表最后一個結(jié)點(diǎn)的指針域的指針又指回第一個結(jié)的鏈表 a1 a2 . an 循環(huán)鏈表循環(huán)鏈表 和單鏈表的差別僅在于，和單鏈表的差別僅在于，判別判別鏈表中最后一個鏈表中最后一個結(jié)點(diǎn)的結(jié)點(diǎn)的條件條件不再是不再是“后繼是否為空后繼是否為空”，而是，而是“后繼后繼是否為頭結(jié)點(diǎn)是否為頭結(jié)點(diǎn)”。 772.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 雙向鏈表雙向鏈表typedef struct DuLNode ElemType data; / 數(shù)據(jù)域數(shù)據(jù)域 struct DuLNode *prior; / 指向前驅(qū)的指針

50、域指向前驅(qū)的指針域 struct DuLNode *next; / 指向后繼的指針域指向后繼的指針域 DuLNode, *DuLinkList; 782.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 雙向鏈表的操作特點(diǎn)：雙向鏈表的操作特點(diǎn)：“查詢查詢”和單鏈表相同。和單鏈表相同?！安迦氩迦搿?和和“刪除刪除”時需要同時修改兩個方向上的時需要同時修改兩個方向上的指針。指針。 792.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)雙向循環(huán)鏈表雙向循環(huán)鏈表空表空表非空表非空表 a1 a2 . an 802.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)ai-1刪除刪除aiai+1p-next

51、 = p-next-next;p-next-prior = p;pai-1 812.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入 822.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時，存在用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時，存在以下以下問題問題：1.1.單鏈表的表長是一個隱含的值；單鏈表的表長是一個隱含的值；2.2.在單鏈表的最后一個元素之后插入元素時，需遍在單鏈表的最后一個元素之后插入元素時，

52、需遍歷整個鏈表；歷整個鏈表； 在鏈表中，元素的在鏈表中，元素的“位序位序”概念淡化，結(jié)點(diǎn)的概念淡化，結(jié)點(diǎn)的“位置位置”概念加強(qiáng)。概念加強(qiáng)。 改進(jìn)鏈表的設(shè)置：改進(jìn)鏈表的設(shè)置：1.1.增加增加“表長表長”、“表尾指針表尾指針” 和和 “當(dāng)前位置的指針當(dāng)前位置的指針” 三個數(shù)據(jù)域；三個數(shù)據(jù)域；2.2.將基本操作中的將基本操作中的“位序位序 i i ”改變?yōu)楦淖優(yōu)椤爸羔樦羔?p p ”。 832.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 一個帶頭結(jié)點(diǎn)的線性鏈表類型一個帶頭結(jié)點(diǎn)的線性鏈表類型typedef struct LNode / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 ElemType data; struct LNode *next; *Link, *Position;typedef struct / 鏈表類型鏈表類型 Link head, tail; / 分別指向頭結(jié)點(diǎn)和分別指向頭結(jié)點(diǎn)和 / 最后一個結(jié)點(diǎn)的指針最后一個結(jié)點(diǎn)的指針 int len; / 指示鏈表長度指示鏈表長