數(shù)據(jù)結(jié)構(gòu)課件第二章1

1、1第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊(duì)列棧和隊(duì)列 第第4章章 串串第第5章章 數(shù)組和廣義表數(shù)組和廣義表第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖第第9章章 查找查找第第10章章 排序排序目目 錄錄什么是什么是線性結(jié)構(gòu)？線性結(jié)構(gòu)？3線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。接后繼。 可表示為：（可表示為：（a a1 1 , a, a2 2 , , , a, an

2、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è)直接后繼。直接后繼。特點(diǎn)特點(diǎn) ai ai是屬于某個(gè)數(shù)據(jù)對(duì)象同一類型的元素，它是屬于某個(gè)數(shù)據(jù)對(duì)象同一類型的元素，它可以是一個(gè)數(shù)字、一個(gè)字母或一個(gè)記錄。可以是一個(gè)數(shù)字、一個(gè)字母或一個(gè)記錄。線性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是等，其中最典型、最常用的是-一對(duì)一一對(duì)一 (1:1

3、)45（a1, a2, ai-1，ai, ai1 ，, an）2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 用數(shù)據(jù)元素的有限序列表示用數(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è)數(shù)，即表個(gè)數(shù)，即表長(zhǎng)。長(zhǎng)?？毡砜毡砭€性終點(diǎn)線性終點(diǎn)6 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)40306114陳建武陳建武男男 192003級(jí)電信級(jí)電信0301班班40306115趙玉鳳趙玉鳳女女 182003級(jí)電

4、信級(jí)電信0302班班40306116王王 澤澤男男 192003級(jí)電信級(jí)電信0303班班40306117薛薛 荃荃男男 192003級(jí)電信級(jí)電信0304班班40306118王 春男 19192003級(jí)電信級(jí)電信0305班班： ：例例2 分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：分析：數(shù)據(jù)元素都是同類型（數(shù)據(jù)元素都是同類型（記錄記錄），元素間關(guān)系是線性的。），元素間關(guān)系是線性的。分析：分析： 數(shù)據(jù)元素都是同類型（數(shù)據(jù)元素都是同類型（字母字母），）， 元素間關(guān)系是線性的。元素間關(guān)系是線性的。例例1 分析分析26 個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。個(gè)英文字母組成的英文表是什么

5、結(jié)構(gòu)。7“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。都相等。試判斷下列敘述的正誤：試判斷下列敘述的正誤：82.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)算效率分析92.2.1 順序表的表示順序表的表示用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次的存儲(chǔ)單元依次存儲(chǔ)線性表的元素存儲(chǔ)線性表的元素。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理

6、上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(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開始，即：開始，即： VnVn的有效范圍是從的有效范圍是從 V0V0Vn-1Vn-1101. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲(chǔ)器中的位

7、置，則其他元若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為L(zhǎng)OC(a1)（稱為稱為首地址首地址），），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對(duì)上述公式的解釋如圖所示對(duì)上述公式的解釋如圖所示線性表順序存儲(chǔ)特點(diǎn)：線性表順序存儲(chǔ)特點(diǎn)：11a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址

8、內(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 +(max-1)+(max-1)L L線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖12設(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é)的地址是，則則 的第一個(gè)字節(jié)的地址是多少？的第一個(gè)字節(jié)的地址是多少？113但此題要注

9、意下標(biāo)起點(diǎn)略有不同：但此題要注意下標(biāo)起點(diǎn)略有不同：LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址計(jì)算通式為：已知地址計(jì)算通式為：LOC(ai) = LOC(a1) + L *（i-1）例例1 113 char V30;void build() /*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心語(yǔ)句：核心語(yǔ)句：例例2用數(shù)組用數(shù)組V來(lái)存放來(lái)存放26個(gè)英文字母組成的線性表（個(gè)英文字母組成的線性表（a，b，c，z），寫出在順序結(jié)構(gòu)上），寫出在順序結(jié)構(gòu)上生成生成和和顯示

10、顯示該表的該表的C語(yǔ)言語(yǔ)言程序。程序。14void 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( ) /*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/ int i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一個(gè)位置元素后移一個(gè)位置/ / 插入插入x x / / 表長(zhǎng)加表長(zhǎng)加1 1 核核心心語(yǔ)語(yǔ)句

11、：句：2)2)插入插入17在線性表的第在線性表的第i i個(gè)位置前插入一個(gè)元素的示意圖如下：個(gè)位置前插入一個(gè)元素的示意圖如下：1213212428304277121321242830427712345678123456789插入插入18實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟：將第將第i+1 至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減表長(zhǎng)減1。注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?應(yīng)當(dāng)有應(yīng)當(dāng)有1in 或或 i=1, n刪除線性表的第刪除線性表的第i i個(gè)位置上的元素個(gè)位置上的元素for ( j=i+1; j=n; j+ )aj-1=aj; n-;/

12、/ 元素前移一個(gè)位置元素前移一個(gè)位置/ / 表長(zhǎng)減表長(zhǎng)減1 1 核心語(yǔ)句：核心語(yǔ)句：3)3)刪除刪除19123456789121321242528304277123456781213212428304277刪除順序表中某個(gè)指定的元素的示意圖如下：刪除順序表中某個(gè)指定的元素的示意圖如下：順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編。順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編。202.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)=

13、O (移動(dòng)移動(dòng)元素次數(shù)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.思考：思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在尾結(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)為

14、為:f(n) = n i + 1時(shí)間效率分析時(shí)間效率分析:21推導(dǎo)：推導(dǎo)：假定在每個(gè)元素位置上插入假定在每個(gè)元素位置上插入x x的可能性都一樣（即的可能性都一樣（即概率概率P P相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1個(gè)元素，后移次數(shù)為個(gè)元素，后移次數(shù)為n-1n-1; ;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1個(gè)元素；個(gè)元素；若在尾結(jié)點(diǎn)若在尾結(jié)點(diǎn)a an n之后插入，則后移之

15、后插入，則后移0 0個(gè)元素；個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì)所有可能的元素移動(dòng)次數(shù)合計(jì)： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/2故插入時(shí)的平均移動(dòng)次數(shù)為：故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插入形式? ?連頭帶尾有連頭帶尾有n+1n+1種種! !22同理可證：同理可證：順序表刪除一元素的時(shí)間效率為順序表刪除一元素的時(shí)間效率為: :T T（n)=(n-1)/2 n)=(n-1)/2 順序表插入、刪除算法的順序表插入、刪除算法的平均平均空間空間復(fù)雜度復(fù)雜度為多少？為多少？插入插入效率：效率

16、：刪除刪除效率：效率：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)23鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)本節(jié)小結(jié)本節(jié)小結(jié)線性表線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素：邏輯關(guān)系上相鄰的兩個(gè)

17、元素在物理存儲(chǔ)位置上也相鄰；在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，方便快捷；可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)：缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。解決問(wèn)題的思路：解決問(wèn)題的思路：改用另一種線性存儲(chǔ)方式：改用另一種線性存儲(chǔ)方式：24課堂討論：課堂討論：順序表的順序表的“宏觀宏觀”算法該如何書寫？算法該如何書寫？采用采用抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型來(lái)表示來(lái)表示順序表的存儲(chǔ)結(jié)構(gòu)是一維數(shù)組，如果插入順序表的存儲(chǔ)結(jié)構(gòu)是一維數(shù)組，如果插入的元素個(gè)數(shù)超過(guò)數(shù)組定義的長(zhǎng)度怎么辦？的元素個(gè)數(shù)超過(guò)數(shù)組定義的長(zhǎng)度怎么辦？采用采用動(dòng)態(tài)分配

18、動(dòng)態(tài)分配的一維數(shù)組的一維數(shù)組25線性表的定義線性表的定義（見(jiàn)教材見(jiàn)教材P19）ADT List 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=ai | aiElemSet, i=1,2,n,n0數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1= | ai 1, ai D, i=2,n基本操作：基本操作：l初始化、撤銷、清空、判空；初始化、撤銷、清空、判空；l求表長(zhǎng)、表頭、表尾、前趨、后繼；求表長(zhǎng)、表頭、表尾、前趨、后繼；l讀元素、查找（含定位）、遍歷；讀元素、查找（含定位）、遍歷；l插入、刪除插入、刪除 ADT List26線性表的基本操作如何表示？線性表的基本操作如何表示？ （見(jiàn)教材（見(jiàn)教材P19）InitList( &L ); /建空

19、表，初始化建空表，初始化DestoryList( &L ); /撤銷表，釋放內(nèi)存撤銷表，釋放內(nèi)存int LengthList( L ); /求表中元素個(gè)數(shù)，即表長(zhǎng)求表中元素個(gè)數(shù)，即表長(zhǎng)POSITION LocateElem (L,ElemType e，compare() );PriorElem( L, cur_e, &pre_e ); /求當(dāng)前元素求當(dāng)前元素e的前驅(qū)的前驅(qū)NextElem( L, cur_e, &next_e ); /求當(dāng)前元素求當(dāng)前元素e的后繼的后繼ListInsertBefore(&L, i, e ); /把把e插入到第插入到第i個(gè)元素之前個(gè)元素之前ListDelete( &L, i,&e ); /刪除第刪除第i個(gè)元素并個(gè)元素并“看看”此元素此元素ListTraverse( L, Visit() ); / “看看”表中全部元素（遍歷）表中全部元素（遍歷）l初始化