數(shù)據(jù)結(jié)構(gòu)：第2章線性表A

1、1課堂練習(xí)：課堂練習(xí)：1. 1. 分析以下程序段的時(shí)間復(fù)雜度。分析以下程序段的時(shí)間復(fù)雜度。i=1; while(i=n) i=i*3; 2將下列函數(shù)，按它們?cè)趯⑾铝泻瘮?shù)，按它們?cè)趎時(shí)的無(wú)窮大階數(shù)，從小到大排序。時(shí)的無(wú)窮大階數(shù)，從小到大排序。n, n-n3+0.7n5, nlogn, 2n/2, n3, 100logn, n1/2+logn, n!答：答：100logn, n1/2+logn, n, nlogn, n3, n-n3+0.7n5, 2n/2, n!答：答：O(log3n)2 習(xí)題集習(xí)題集1.6 1.7 1.8 1.10 1.17 1.20習(xí)題集習(xí)題集 2.8 2.10 2.21 2

2、.22 2.34 2.35助教助教蔡科超蔡科超4302066563第第1章回顧章回顧數(shù)據(jù)結(jié)構(gòu)課程數(shù)據(jù)結(jié)構(gòu)課程 數(shù)據(jù)結(jié)構(gòu)算法程序，涉及數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)算法程序，涉及數(shù)學(xué)、計(jì)算機(jī)硬件和軟件。計(jì)算機(jī)硬件和軟件。數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，可用可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。數(shù)據(jù)結(jié)構(gòu)內(nèi)容數(shù)據(jù)結(jié)構(gòu)內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算運(yùn)算(計(jì)算機(jī)處理非數(shù)值對(duì)象計(jì)算機(jī)處理非數(shù)值對(duì)象) 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)工具數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)工具抽象數(shù)據(jù)類(lèi)型和偽碼

3、抽象數(shù)據(jù)類(lèi)型和偽碼（類(lèi)（類(lèi)C）算法效率指標(biāo)算法效率指標(biāo)時(shí)間效率和空間效率時(shí)間效率和空間效率 4第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊(duì)列棧和隊(duì)列 第第4章章 串串第第5章章 數(shù)組和廣義表數(shù)組和廣義表第第6 6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 第第7章章 圖圖第第9章章 查找查找第第10章章 排序排序目目 錄錄什么是什么是線性結(jié)構(gòu)？線性結(jié)構(gòu)？6線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。

4、接后繼。 可表示為：（可表示為：（a a1 1 , a, a2 2 , , , a, an n） 簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 的。的。特點(diǎn)特點(diǎn) 只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；特點(diǎn)特點(diǎn) 除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。直接后繼。線性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是等，其中最典型、最常用的是-一對(duì)一一對(duì)一 (1:1)78（a1, a2, ai-1，ai, ai1 ，, an）2.1 線

5、性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱(chēng)為時(shí)稱(chēng)為數(shù)據(jù)元素?cái)?shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號(hào)，表示元素序號(hào)，表示元素在表中的位置在表中的位置n為元素總為元素總個(gè)數(shù)，即表個(gè)數(shù)，即表長(zhǎng)。長(zhǎng)。空表空表線性終點(diǎn)線性終點(diǎn)9 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)U200913798章達(dá)航章達(dá)航男男19通信工程通信工程200901班班U200913818張巖張巖男男19通信工程通信工程200902班班U200913955周凱周凱男男19通信工程通信工程

6、200903班班U200913887吳益陽(yáng)吳益陽(yáng)男男1919通信工程通信工程200904班班： ： ：例例2 分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：分析：數(shù)據(jù)元素都是同類(lèi)型（數(shù)據(jù)元素都是同類(lèi)型（記錄記錄），元素間關(guān)系是線性的。），元素間關(guān)系是線性的。分析：分析： 數(shù)據(jù)元素都是同類(lèi)型（數(shù)據(jù)元素都是同類(lèi)型（字母字母），）， 元素間關(guān)系是線性的。元素間關(guān)系是線性的。例例1 分析分析26 個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。10“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包

7、含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。試判斷下列敘述的正誤：試判斷下列敘述的正誤：112.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.2.1 順序表的表示順序表的表示2.2.2 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)2.2.3 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析122.2.1 順序表的表示順序表的表示用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次的存儲(chǔ)單元依次存儲(chǔ)線性表的元素存儲(chǔ)線性表的元素。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱(chēng)為線性表的順序表示又稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)順

8、序存儲(chǔ)結(jié)構(gòu)或順序映像?；蝽樞蛴诚?。順序存儲(chǔ)定義：順序存儲(chǔ)定義：順序存儲(chǔ)方法：順序存儲(chǔ)方法：特點(diǎn)：特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰可以利用可以利用數(shù)組數(shù)組VnVn來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn)注意：在注意：在C C語(yǔ)言中數(shù)組的下標(biāo)是從語(yǔ)言中數(shù)組的下標(biāo)是從0 0開(kāi)始，即：開(kāi)始，即： VVn n 的有效范圍是從的有效范圍是從 VV0 0 VVn-1n-1 131. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲(chǔ)器中的位置，則其他元若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組V

9、nVn的的下標(biāo)下標(biāo)）。設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為L(zhǎng)OC(a1)（稱(chēng)為稱(chēng)為首地址首地址），），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為為？ 先畫(huà)圖先畫(huà)圖線性表順序存儲(chǔ)特點(diǎn)：線性表順序存儲(chǔ)特點(diǎn)：14a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(m

10、ax-1)+(max-1)L L線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 LOC ( a ) = LOC( a ) + L 表中任一數(shù)據(jù)表中任一數(shù)據(jù)元素的元素的存放地存放地址址為為:下標(biāo)起下標(biāo)起點(diǎn)是點(diǎn)是1 115設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個(gè)數(shù)，每個(gè)數(shù)組元素用相鄰的組元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素設(shè)存儲(chǔ)數(shù)組元素 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是9898，則，則 的第一個(gè)字節(jié)的地址是多少？的第一個(gè)字節(jié)的地址是多少？答案：答案：113但此題要注意下標(biāo)起點(diǎn)是從但此題要注意下標(biāo)起點(diǎn)是從0 0開(kāi)始

11、：開(kāi)始： LOC( M3 ) = 98 + 5 (3-0) =113或或: : LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址計(jì)算通式為：已知地址計(jì)算通式為：LOC(ai) = LOC(a1) + L *（i-1）例例1 116 char V30;void build() /字母線性表的字母線性表的生成生成，即建表操作，即建表操作 例例2用數(shù)組用數(shù)組V來(lái)存放來(lái)存放26個(gè)英文字母組成的線性表（個(gè)英文字母組成的線性表（a，b，c，z），寫(xiě)出在順序結(jié)構(gòu)上），寫(xiě)出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語(yǔ)言語(yǔ)言程序。程序。省略了省略了includeinclude語(yǔ)句語(yǔ)

12、句 int i; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 17void main(void) /主函數(shù)，字母線性表的主函數(shù)，字母線性表的生成和輸出生成和輸出 n=26; / n n是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V V的實(shí)際下標(biāo)的實(shí)際下標(biāo) build( ); display( );void display( ) /字母線性表的字母線性表的顯示顯示，即讀表操作，即讀表操作 執(zhí)行結(jié)果：執(zhí)行結(jié)果： a b c d e f g h i j k l m n o p q r s t u v w x y z int i; for( i=0

13、; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一個(gè)位置元素后移一個(gè)位置/ / 插入插入x x / / 表長(zhǎng)加表長(zhǎng)加1 1 事先應(yīng)判斷事先應(yīng)判斷: 插入位置插入位置i 是否合法是否合法? 表是否已滿(mǎn)表是否已滿(mǎn)? 應(yīng)當(dāng)符合條件：應(yīng)當(dāng)符合條件： 1in+1 或或 i=1, n+1 將第將第n至第至第i 位的元素向后移動(dòng)一個(gè)位置；位的元素向后移動(dòng)一個(gè)位置； 將要插入的元素寫(xiě)到第將要插入的元素寫(xiě)到第i個(gè)位置；個(gè)位置； 表長(zhǎng)加表長(zhǎng)加1。核核心心語(yǔ)語(yǔ)句句if ( iL.length+1) return ERROR2112345678912132124252830427712

14、3456781213212428304277刪除順序表中某個(gè)指定的元素的示意圖如下：刪除順序表中某個(gè)指定的元素的示意圖如下：刪除線性表的第刪除線性表的第i i個(gè)位置上的元素個(gè)位置上的元素3)3)刪除刪除22實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 將第將第i+1 至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減表長(zhǎng)減1。for ( j=i+1; j=n; j+ )aj-1=aj; n-;/ / 元素前移一個(gè)位置元素前移一個(gè)位置/ / 表長(zhǎng)減表長(zhǎng)減1 1 核心語(yǔ)句：核心語(yǔ)句：順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編，順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編，并務(wù)必上機(jī)驗(yàn)證！并務(wù)必上機(jī)驗(yàn)證！if

15、( iL.length) return ERROR 注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?應(yīng)當(dāng)符合條件：應(yīng)當(dāng)符合條件：1in 或或 i=1, n232.2.3 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析 算法時(shí)間主要耗費(fèi)在算法時(shí)間主要耗費(fèi)在移動(dòng)元素移動(dòng)元素的操作上，因此的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度）計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度） T(n)= O (移動(dòng)元素次數(shù)移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。思考：思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若

16、插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的種可能）的平均平均移動(dòng)次數(shù)才合理。移動(dòng)次數(shù)才合理。討論討論1：若在長(zhǎng)度為若在長(zhǎng)度為 n 的線性表的第的線性表的第 i 位前位前 插入插入一個(gè)元素，一個(gè)元素，則向后移動(dòng)元素的次數(shù)則向后移動(dòng)元素的次數(shù)f(n)為為:f(n) = n i + 1時(shí)間效率分析時(shí)間效率分析:24推導(dǎo)：推導(dǎo)：假定在每個(gè)元素位置上插入假定在每個(gè)元素位置上插入x x的可能性都一樣（即的可能性都一樣（即概率概率P P

17、相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為n n；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1個(gè)元素，后移次數(shù)為個(gè)元素，后移次數(shù)為n-1n-1; ;若在若在a an-1n-1后面插入，后移次數(shù)為后面插入，后移次數(shù)為1 1；若在尾結(jié)點(diǎn)若在尾結(jié)點(diǎn)a an n之后插入，則后移次數(shù)為之后插入，則后移次數(shù)為0 0；故插入時(shí)的故插入時(shí)的平均平均移動(dòng)次數(shù)為：移動(dòng)次數(shù)為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插

18、入形式? ?連頭帶尾有連頭帶尾有n+1n+1種種! !所有所有可能的元素移動(dòng)次數(shù)合計(jì)可能的元素移動(dòng)次數(shù)合計(jì)： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/225同理可證：同理可證：順序表刪除一元素的時(shí)間效率為順序表刪除一元素的時(shí)間效率為: :T T（n)=(n-1)/2 n)=(n-1)/2 順序表插入、刪除算法的順序表插入、刪除算法的平均平均空間空間復(fù)雜度復(fù)雜度為多少？為多少？插入效率：插入效率：刪除效率：刪除效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材P25算法算法2.5也是對(duì)執(zhí)行效率的推導(dǎo)：也是對(duì)執(zhí)行效率的推導(dǎo)：因?yàn)闆](méi)有占用輔助空間！因?yàn)闆](méi)有占用輔助空間！含義：對(duì)于順序表，插入、刪除操含義：對(duì)于順序表，插入、刪除操作平均需要移動(dòng)一半元素作平均需要移動(dòng)一半元素( n / 2 )O(1)O(1)即插入、刪除算法的平均即插入、刪除算法的平均時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n)26例例1(1(華為招聘試題華為招聘試題) )：試用試用C C或類(lèi)或類(lèi)C C語(yǔ)言編寫(xiě)一語(yǔ)言編寫(xiě)一高效高效算法，將一順序存儲(chǔ)的線性表（設(shè)元素均為整型算法，將一順序存儲(chǔ)的線性表（設(shè)元素均為整型量）中所