第二章_線性表課1

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第一章第一章 緒緒 論論 第六章第六章 樹與二叉樹樹與二叉樹第二章第二章 線性表線性表 第七章第七章 圖圖第三章第三章 棧和隊(duì)列棧和隊(duì)列 第八章第八章 動(dòng)態(tài)存儲(chǔ)管理動(dòng)態(tài)存儲(chǔ)管理第四章第四章 串串 第九章第九章 查找查找第五章第五章 數(shù)組與廣義表數(shù)組與廣義表 第十章第十章 內(nèi)部排序內(nèi)部排序數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)隊(duì)樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)

2、據(jù)結(jié)構(gòu)的三個(gè)方面數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1 問題提出n一條記錄有學(xué)號(hào)和成績(jī)兩個(gè)數(shù)據(jù)項(xiàng)，依次輸入數(shù)據(jù)建立一個(gè)有序表（按成績(jī)由大到?。?。其中輸入的數(shù)據(jù)如下（學(xué)號(hào)，成績(jī)）：(1,70),(2,85),(3,75), (4,90),(5,60),(6,80),(7,76),(8,50)等等。2 問題分析n可用結(jié)構(gòu)體數(shù)組來存儲(chǔ)記錄。n但數(shù)組一般固定長度，分配多大空間才合適？n如何實(shí)現(xiàn)每輸入一條記錄都保持有序？n如果需要增加其它功能，如刪除、修改、查詢、排序，如何實(shí)現(xiàn)？n如果數(shù)組長度不固定，如何動(dòng)態(tài)分配數(shù)組空間？n如果記錄還有姓名、課程等數(shù)據(jù)項(xiàng)，應(yīng)如何修改程序？5n理解線性表的理解線性表的邏輯

3、結(jié)構(gòu)邏輯結(jié)構(gòu)特性特性n熟練掌握線性表的熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的描述方的描述方法，以及在該存儲(chǔ)結(jié)構(gòu)下的法，以及在該存儲(chǔ)結(jié)構(gòu)下的基本操作基本操作n熟練掌握線性表的熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方的描述方法，靈活使用法，靈活使用單鏈表單鏈表、雙鏈表雙鏈表、循環(huán)鏈表循環(huán)鏈表，學(xué)會(huì)在相應(yīng)存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)其各種學(xué)會(huì)在相應(yīng)存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)其各種基本算基本算法法及相關(guān)的時(shí)間性能分析及相關(guān)的時(shí)間性能分析6第二章第二章 線性表線性表782.1 線性表的類型定義線性表的類型定義92.1 線性表的類型定義線性表的類型定義10（a1, a2, ai-1，ai, ai1 ，, an）線性表的

4、定義：線性表的定義：是是n個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)下標(biāo)，是元是元素的序號(hào)，素的序號(hào)，表示元素在表示元素在表中的位置表中的位置n為元素總個(gè)為元素總個(gè)數(shù)，即表長數(shù)，即表長空表空表線性終點(diǎn)線性終點(diǎn)2.1 線性表的類型定義線性表的類型定義 例例1 例例2. 班級(jí)人數(shù)班級(jí)人數(shù)(33, 32, 35, 30) 例例32.1 線性表的類型定義線性表的類型定義12132.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義142.1 線性表的類型定義線性表的類型定義15

5、ADT List 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=ai |ai ElemSet, i=1, 2, , n, n 0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=| ai-1, ai D, i=1, 2, , n 基本操作：基本操作： InitList(&L) 操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表L DestroyList(&L) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：操作結(jié)果：銷毀線性表銷毀線性表2.1 線性表的類型定義線性表的類型定義16 ClearList(&L) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：操作結(jié)果：將線性表將線性表L重

6、置為空表重置為空表 ListEmpty(L) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：若操作結(jié)果：若L為為空表空表，則返回，則返回TRUE， 否則返回否則返回FALSE ListLength(L) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：返回操作結(jié)果：返回L中中數(shù)據(jù)元素個(gè)數(shù)數(shù)據(jù)元素個(gè)數(shù) 2.1 線性表的類型定義線性表的類型定義17GetElem( L, i, &e ) 初始條件：線性表初始條件：線性表L已存在，已存在，1iLengthList(L) 操作結(jié)果：操作結(jié)果：用用e返回返回L中第中第i個(gè)元素的值個(gè)元素的值 LocateElem( L, e,

7、 compare( ) ) 初始條件：線性表初始條件：線性表L已存在，已存在，compare( )是元素判定是元素判定 函數(shù)函數(shù) 操作結(jié)果：操作結(jié)果：返回返回L中中第第1個(gè)個(gè)與與e滿足關(guān)系滿足關(guān)系compare( )的的 元素的位序元素的位序。若這樣的元素不存在，則。若這樣的元素不存在，則 返回值為返回值為0 PriorElem( L, cur_e, &pre_e ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：若操作結(jié)果：若cur_e是是L的元素，但不是第一個(gè)，則的元素，但不是第一個(gè)，則 用用pre_e 返回它的前驅(qū)返回它的前驅(qū)，否則操作失敗，否則操作失敗，pre_e無

8、定義無定義2.1 線性表的類型定義線性表的類型定義18NextElem( L, cur_e, &next_e ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：若操作結(jié)果：若cur_e是是L的元素，但不是最后一個(gè)，則的元素，但不是最后一個(gè)，則用用next_e返回它的后繼返回它的后繼，否則操作失敗，否則操作失敗，next_e無定義無定義 ListTraverse(L, visit( ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：依次操作結(jié)果：依次對(duì)對(duì)L的每個(gè)元素調(diào)用函數(shù)的每個(gè)元素調(diào)用函數(shù)visit( )。一。一 旦旦visit( )失敗，則操作失敗失敗，則操作

9、失敗。 PutElem( L, i, &e ) 初始條件：線性表初始條件：線性表L已存在，已存在，1iLengthList(L) 操作結(jié)果：操作結(jié)果：L中第中第i個(gè)元素賦值同個(gè)元素賦值同e的值的值2.1 線性表的類型定義線性表的類型定義192.1 線性表的類型定義線性表的類型定義202.1 線性表的類型定義線性表的類型定義212.1 線性表的類型定義線性表的類型定義222.1 線性表的類型定義線性表的類型定義232.1 線性表的類型定義線性表的類型定義2425 編程序，一定要寫成若干個(gè)函數(shù)編程序，一定要寫成若干個(gè)函數(shù)的組合，一定不要寫成一個(gè)大的函數(shù)。的組合，一定不要寫成一個(gè)大的函數(shù)。把

10、問題切細(xì)，分而治之。把問題切細(xì)，分而治之。2.1 線性表的類型定義線性表的類型定義262.1 線性表的類型定義線性表的類型定義272.1 線性表的類型定義線性表的類型定義282.1 線性表的類型定義線性表的類型定義292.1 線性表的類型定義線性表的類型定義30 下一小節(jié)：下一小節(jié)：2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)32邏輯地址邏輯地址數(shù)據(jù)元素?cái)?shù)據(jù)元素存儲(chǔ)地址存儲(chǔ)地址 數(shù)據(jù)元素?cái)?shù)據(jù)元素0k0Loc(k0)k01k1Loc(k0)+ck1ikiLoc(k0)+i*ckin-1kn-1Loc(k0)+(n-1)*ckn-1 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖33

11、一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素的第一個(gè)字節(jié)的地址是98，則的第一個(gè)字節(jié)的地址是（ ）例:因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：地址計(jì)算通式為：解：地址計(jì)算通式為：LOC(ai) = LOC(a1) + L *（i-1）35362.2.插入：在線性表的第插入：在線性表的第i i個(gè)位置前個(gè)位置前插入插入一個(gè)元素，一個(gè)元素， 并保持?jǐn)?shù)據(jù)的并保持?jǐn)?shù)據(jù)的大小順序。大小順序。實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 找到需要插入的位置找到需要插入的位置i，將第，將第n至第至第i 位的元素向后位的元素向后移動(dòng)一個(gè)位置；移動(dòng)一個(gè)位

12、置； 將要插入的元素寫到第將要插入的元素寫到第i個(gè)位置；個(gè)位置； 表長加表長加1。注意：注意：事先應(yīng)判斷事先應(yīng)判斷: 插入位置插入位置i 是否合法是否合法?表是否已滿表是否已滿? （a1,a2,ai-1,ai,an）（a1,a2,ai-1,x,ai,an）3839實(shí)現(xiàn)步驟：n將第i +1至第n 位的元素向前移動(dòng)一個(gè)位置；n表長減1。注意：n事先需要判斷，刪除位置i 是否合法?n如果要?jiǎng)h除學(xué)號(hào)為2的學(xué)生記錄，如何進(jìn)行？線性表的其它功能如何實(shí)現(xiàn)才可以方便使用？3 3. .刪除：刪除：刪除刪除線性表的第線性表的第i i個(gè)位置上的元素，使長度為個(gè)位置上的元素，使長度為n n的線的線性表變?yōu)殚L度為性表變

13、為長度為n-1n-1的線性表。的線性表。 （a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an） 41/102時(shí)間效率分析時(shí)間效率分析: 插入算法花費(fèi)的時(shí)間，主要在于循環(huán)中元素的后移。插入算法花費(fèi)的時(shí)間，主要在于循環(huán)中元素的后移。但是，插入的位置是不固定的，當(dāng)插入位置但是，插入的位置是不固定的，當(dāng)插入位置i=1時(shí)，全時(shí)，全部元素都得移動(dòng)，需部元素都得移動(dòng)，需n次移動(dòng)，當(dāng)次移動(dòng)，當(dāng)i=n時(shí)，不需移動(dòng)元時(shí)，不需移動(dòng)元素，故在素，故在i位置插入時(shí)移動(dòng)次數(shù)為位置插入時(shí)移動(dòng)次數(shù)為n-i+1。 刪除算法花費(fèi)的時(shí)間，主要在于循環(huán)中元素的前移刪除算法花費(fèi)的時(shí)間，主要在于循環(huán)中元

14、素的前移.但是，刪除的位置是不固定的，當(dāng)刪除位置但是，刪除的位置是不固定的，當(dāng)刪除位置i=1時(shí)，全時(shí)，全部元素都得移動(dòng)，需部元素都得移動(dòng)，需n-1次移動(dòng)，當(dāng)次移動(dòng)，當(dāng)i=n時(shí)，不需移動(dòng)時(shí)，不需移動(dòng)元素，故在元素，故在i位置刪除時(shí)移動(dòng)次數(shù)為位置刪除時(shí)移動(dòng)次數(shù)為n-i-1.假定在表中任意位置插入、刪除元素都是等概率的，插入概率p(i)=1/(n+1) ，刪除概率q(i)=1/n ，則：插入操作時(shí)間效率（平均移動(dòng)次數(shù)）插入操作時(shí)間效率（平均移動(dòng)次數(shù)） 2) 1(11) 1(1111ninninpEniniiis刪除操作時(shí)間效率（平均移動(dòng)次數(shù)）刪除操作時(shí)間效率（平均移動(dòng)次數(shù)） 21)(1)(11ninninqEniniidl顯然，順序表的顯然，順序表的空間空間復(fù)雜度復(fù)雜度S(n)=O(1)S(n)=O(1)（沒有占用輔助空間）（沒有占用輔助空間）本節(jié)小結(jié)本節(jié)小結(jié)線性表線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；兩個(gè)元素在物理存儲(chǔ)位置上也