第2章 數(shù)據(jù)結構

1、? 算法算法? 數(shù)據(jù)結構概述數(shù)據(jù)結構概述? 線性結構線性結構? 棧和隊列棧和隊列? 樹樹? 圖圖第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構 數(shù)據(jù)結構是討論非數(shù)值類問題的對象描述、信息組織方法及其相應的操作。 第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構電子計算機的主要用途：電子計算機的主要用途： 早期：早期： 主要用于數(shù)值計算。主要用于數(shù)值計算。 后來：后來： 處理逐漸擴大到非數(shù)值計算領域處理逐漸擴大到非數(shù)值計算領域（能處理多種復雜的具有一定結構關系的數(shù)據(jù)）（能處理多種復雜的具有一定結構關系的數(shù)據(jù)）數(shù)學模型數(shù)學模型選擇計算機語言選擇計算機語言編出程序編出程序測試測試最終解答最終解答數(shù)據(jù)元素之間的相互關系一般無法用數(shù)學方程加

2、以描述數(shù)據(jù)元素之間的相互關系一般無法用數(shù)學方程加以描述數(shù)據(jù)結構的數(shù)據(jù)結構的研究內(nèi)容算法算法數(shù)據(jù)結構概述數(shù)據(jù)結構概述線性結構線性結構棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構1. 算法的特征算法: 對問題求解的描述，具有以下五個重要的特征： 1）有窮性：一個算法必須保證執(zhí)行有限步之后結束。 2）確切性：算法的每一步驟必須有確切的定義。 3）輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況。 4）輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法沒有實際意義。 5）可行性：比如，永動機則不可行。一、算法2、算法的描述: 1）流程圖 2）偽代碼類似

3、程序設計語言 3、算法的基本結構 算法代碼化的過程:1）順序結構 2）分支結構 3）循環(huán)結構一、算法 算法的時間復雜度是指（ ）。A. 執(zhí)行算法程序所需要的時間B. 算法程序的長度C. 算法執(zhí)行過程中所需要的基本運算次數(shù)D. 算法程序中的指令條數(shù)一、算法 算法的空間復雜度是指（ ）。A. 算法程序的長度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間D. 算法執(zhí)行過程中的所需要的存儲空間一、算法4、算法效率衡量方法與準則 :時間復雜度：Windows程序設計中，指執(zhí)行時間的長短。空間復雜度：指存儲空間的大小。 一、算法5、算法與數(shù)據(jù)結構的關系:計算機科學家沃斯（計算機科學家沃斯（N.Wi

4、rth）提出的）提出的:“算法算法+數(shù)據(jù)結構數(shù)據(jù)結構=程序程序” 一、算法 計算機內(nèi)的數(shù)值運算依靠方程式，而計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算則要依靠數(shù)據(jù)結構。 同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結構來表示，同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結構來表示，運算效率可能有明顯的差異。運算效率可能有明顯的差異。算法算法數(shù)據(jù)結構概述數(shù)據(jù)結構概述線性結構線性結構棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構 特性相同的數(shù)據(jù)元素構成的集合中，如果在數(shù)據(jù)元素之間存在一種或多種特定的關系，則稱之為數(shù)據(jù)結構 。 Data_Structure =（D，R） 其中，其中，D是數(shù)據(jù)元素的有限集，是數(shù)據(jù)元素的

5、有限集，R是是D上關系的有上關系的有限集。限集。二、數(shù)據(jù)結構概述例1 線性數(shù)據(jù)結構 =（D，R） D = 1，2，3，4，5，6，7，8，9，10 R = ，二、數(shù)據(jù)結構概述例2 圖形數(shù)據(jù)結構 =（D，R）D = 1，2，3，4，5，6，7，8，9R = ，二、數(shù)據(jù)結構概述 例3 樹形結構 =（D，R）D = a，b，c，d，e，f，g，h，i，j，k，lR = ，二、數(shù)據(jù)結構概述四類基本的數(shù)據(jù)結構 集合結構。各元素間沒有直接的關聯(lián)。 線性結構。該結構的數(shù)據(jù)元素之間存在著一對一的關系。 樹型結構。該結構的數(shù)據(jù)元素之間存在著一對多的關系。 圖形結構。該結構的數(shù)據(jù)元素之間存在著多對多的關系，也稱作

6、網(wǎng)狀結構。二、數(shù)據(jù)結構概述不同聯(lián)系不同聯(lián)系系主任負責系11班級包含學生1N產(chǎn)品組成零件MN一對一聯(lián)系一對多聯(lián)系多對多聯(lián)系（1）Data_Structure=(D,S)，其中，其中， D= 01，02，03，04，05 S= （2） S=(D, R) D= a, b, c, d, e, f R= , , , , 解解: 上述表達式可用圖形表示為：上述表達式可用圖形表示為：aebcfd習題：將下述表達式用圖形的形式表示出來集合結構線性結構（3） Data_Structure=（D，S），其中，），其中， D= 01，02，03，04，05 ，06，07 S=（01，02），（），（01，03），（

7、），（01，04），（），（02，05），（），（02，06），（），（03，07） （4）d1d2d3d4d501020304050607樹形結構圖狀結構邏輯結構可細分為4類：集合結構；線性結構；樹形結構；圖狀結構集合結構；線性結構；樹形結構；圖狀結構一對一關系一對一關系一對多關系一對多關系多對多關系多對多關系非線性非線性結構結構數(shù)據(jù)結構的分類按數(shù)據(jù)結構的性質(zhì)劃分 數(shù)據(jù)的邏輯結構數(shù)據(jù)元素之間的邏輯關系 （設計算法 數(shù)學模型） 數(shù)據(jù)的物理結構數(shù)據(jù)結構在計算機中的映像 （存儲結構，算法的實現(xiàn)）按數(shù)據(jù)結構的操作來劃分 靜態(tài)結構操作后數(shù)據(jù)的結構特征保持不變（如數(shù)組）。 半靜態(tài)結構操作后數(shù)據(jù)的結構特性

8、只允許很小變遷（如棧、隊列）。動態(tài)結構操作后，數(shù)據(jù)的結構特性變化比較靈活，可隨機地重新組織結構（如指針）。二、數(shù)據(jù)結構概述下面敘述正確的是（ ）。 A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結構無關 B. 算法的空間復雜度是指算法程序中指令（或語句）的條數(shù) C. 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止 D. 以上3種描述都不對二、數(shù)據(jù)結構概述按數(shù)據(jù)結構在計算機內(nèi)的存儲方式來劃分 順序存儲結構借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。 鏈式存儲結構借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系 索引存儲結構在存儲結點的同時，還建立附加的索引表，索引表中的每一項稱為索引項，形

9、式為：關鍵字，地址。 散列存儲結構根據(jù)結點的關鍵字直接計算出該結點的存儲地址。說明：四種存儲方法可結合起來對數(shù)據(jù)結構進行存儲映像。二、數(shù)據(jù)結構概述算法算法數(shù)據(jù)結構概述數(shù)據(jù)結構概述線性結構線性結構棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構線性表線性表線性表的定義線性表的定義 線性表線性表是是n(n=0)個數(shù)據(jù)元素的個數(shù)據(jù)元素的有限序列有限序列，表中，表中各個元素具有相同的屬性。各個元素具有相同的屬性。 記做：記做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，其中，ai-1稱為稱為ai 的的直接前趨元素直接前趨元素，ai+1是是ai的的直直接后繼元素接后繼

10、元素 線性表的長度：線性表的長度：表中的元素個數(shù)表中的元素個數(shù) n 三、線性結構 數(shù)據(jù)處理的最小單位是（ ）。 A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 數(shù)據(jù)結構思考：補充補充數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項，是數(shù)據(jù)的最小單位，數(shù)據(jù)項定義的內(nèi)容包括： 名稱、編號（I）、別名、簡述 類型、長度 取值范圍 item數(shù)據(jù)項定義舉例數(shù)據(jù)項定義舉例數(shù)據(jù)項名：年級數(shù)據(jù)項名：年級別名：別名：取值及含義：取值及含義： freshmen，一年級，一年級 sophomore，二年級，二年級 junior，三年級，三年級 senior，四年級，四年級注釋：注釋：F，M，J，S可分別用可分別用1，2，3，4代替代替記錄線性表

11、的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 順序表順序表線性表的線性表的順序存儲表示表示順序表，隨機存取三、線性結構線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) 單鏈表單鏈表線性表的線性表的鏈式存儲表示表示 數(shù)據(jù)域（數(shù)據(jù)域（data）和指針域（指針域（next） 三、線性結構結點：數(shù)據(jù)元素的存儲映象數(shù)據(jù)元素的存儲映象數(shù)據(jù)域數(shù)據(jù)域指針域指針域鏈表：n n個結點鏈接成起來形成一個鏈表，即為線性表的個結點鏈接成起來形成一個鏈表，即為線性表的 鏈式存儲結構。鏈式存儲結構。a1a2ai-1aian指針域為空指針域為空數(shù)據(jù)元素數(shù)據(jù)元素直接后繼位置直接后繼位置頭結點頭結點LL 數(shù)據(jù)結構是討論非數(shù)值類問題的對象描

12、述、信息組織方法及其相應的操作 設有一個電話號碼薄，有N個人的姓名和電話號碼。要求設計一個程序，按人名查找號碼，若不存在則給出不存在的信息。三、線性結構三、線性結構順序表的表示：順序表的表示：順序存儲定義：把邏輯上相鄰的元素存儲在物理 位置上相鄰的存儲單元中。采用順序存儲結構存儲的線性表采用順序存儲結構存儲的線性表簡言之：邏輯相鄰，物理也相鄰順序存儲方法：順序存儲方法：用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次 存放線性表的數(shù)據(jù)元素。存放線性表的數(shù)據(jù)元素。線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)線性表順序存儲結構的特點線性表順序存儲結構的特點1、邏輯上相鄰的物理元素，其物理位

13、置上也相鄰 2、若已知線性表中第1個元素的存儲位置，則線性表中任意一個元素的位置都可由公式計算得出。 即，線性表的順序存儲結構是一種隨機存取的存儲結構。例：例：一個一維數(shù)組一個一維數(shù)組M，下標范圍是，下標范圍是0到到9，每個數(shù)組元素，每個數(shù)組元素用用相鄰的的5個字節(jié)存儲。存儲器按字節(jié)編址，設存儲數(shù)個字節(jié)存儲。存儲器按字節(jié)編址，設存儲數(shù)組元素組元素M0的第一個字節(jié)的地址是的第一個字節(jié)的地址是98，則，則M3的第一個的第一個字節(jié)的地址是字節(jié)的地址是 。113 非數(shù)值計算問題 例1.2 田徑賽的時間安排問題： 設有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）。要求設

14、計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。姓名姓名項目項目1項目項目2項目項目3丁一丁一跳高跳高跳遠跳遠100米米馬二馬二標槍標槍鉛球鉛球張三張三標槍標槍100米米200米米李四李四鉛球鉛球200米米跳高跳高王五王五跳遠跳遠200米米三、線性結構（1）設用如下六個不同的編碼代表不同的項目： 跳高跳高 跳遠跳遠 標槍標槍 鉛球鉛球 100米米 200米米 A B C D E F姓名姓名項目項目1項目項目2項目項目3丁一丁一 A B E馬二馬二 C D 張三張三 C E F李四李四 D F A王五王五 B F （2）用頂點（圓圈）代表比賽項目 不能同時進行比賽的項目之間連上一條邊。不能同時進行

15、比賽的項目之間連上一條邊。比賽比賽時間時間比賽比賽項目項目1A，C2B，D3E4F2、線性表、線性表順序存儲結構的特點順序存儲結構的特點：邏輯相鄰，物理相鄰3、優(yōu)點：、優(yōu)點：可以可以隨機存取表中的任何一個元素表中的任何一個元素4、缺點：、缺點：在插入、刪除時，需要移動大量元素在插入、刪除時，需要移動大量元素1、線性表的定義、線性表的定義 L=（a1，a2，an）其中，其中，n n是線性表的長度。當是線性表的長度。當n n0 0時，時，L L是一個空表是一個空表 小結：ABCD順序存儲結構順序存儲結構ABCD鏈式存儲結構鏈式存儲結構L=（A, B, C, D）用一組任意的存儲單元存儲線性表的元素

16、邏輯相鄰，物理不一定相鄰ai除表示本身信除表示本身信息之外，還要表息之外，還要表示其直接后繼的示其直接后繼的地址地址線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)例：一個線性表的邏輯結構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結構用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針是指向鏈表中第一頭指針是指向鏈表中第一個結點的指針，因此關鍵是要個結點的指針，因此關鍵是要尋找第一個結點的地址。尋找第一個結點的地址。

17、7ZHAOH31稱：頭指針稱：頭指針H的值是的值是31答：X= Y= Z= , 首址= 末址= 。例：現(xiàn)有一個有5個元素的線性表 L=23，17，47，05， 31，若它以鏈式結構存儲在下列100119號地址空間中，每個結點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)）組成，如下圖所示。問：其中指針X，Y，Z的值分別為多少？該線性表的首結點起始地址為多少？末結點的起始地址為多少？100100119119104104108108116116112112116NULL(0)100108112 線性表中結點間的關系是 的。一對一 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為： A

18、. 存儲結構 B. 邏輯結構 C. 順序存儲結構 D. 鏈式存儲結構【答案】C 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。 A. 110 B. 108 C. 100 D. 120【答案】B三、線性結構 線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址: A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以【答案】D三、線性結構已知：已知：線性表線性表A A和和B B，分別由，分別由單鏈表單鏈表LaLa和和LbLb存儲，其中數(shù)據(jù)存儲，其中數(shù)據(jù) 元素按值元素按值非遞減有序排列非遞減有序排列（即已經(jīng)有序）；

19、（即已經(jīng)有序）；例：例：兩個鏈表的歸并兩個鏈表的歸并重點是鏈表重點是鏈表要求：要求：將將A A和和B B歸并為一個新的線性表歸并為一個新的線性表C C , C , C的數(shù)據(jù)元素仍按的數(shù)據(jù)元素仍按 值非遞減排列。設線性表值非遞減排列。設線性表C C由單鏈表由單鏈表 Lc Lc 存儲。存儲。假設：假設：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）預測：預測：合并后的合并后的C C = =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）線性表的鏈式表示和實現(xiàn)（應用舉例）鏈表示意圖：合并

20、算法設計：算法設計：算法主要包括算法主要包括搜索、比較、插入搜索、比較、插入三個操作：三個操作：搜索：搜索：需要設立需要設立三個指針三個指針來指向來指向La 、Lb和和Lc c鏈表；鏈表；比較：比較：比較比較La a和和Lb b表中結點數(shù)據(jù)的大?。槐碇薪Y點數(shù)據(jù)的大??；插入：插入：將將La a和和Lb b表表中數(shù)據(jù)中數(shù)據(jù)較小的結點插入新鏈表較小的結點插入新鏈表Lc c 。3 5 8 11 LaLb2 6 8 11 9 Lc 2 3 5 6 8 8 9 11 11線性表的鏈式表示和實現(xiàn)PcPa、Pb用于搜索用于搜索La和和Lb，Pc指向新鏈表指向新鏈表Lc的當前結點。的當前結點。鏈表鏈表Lc存儲在

21、新開辟的空間中存儲在新開辟的空間中，歸并過程示意如下：，歸并過程示意如下：Lb2 6 8 119 3 5 8 11 LaLc 2 3 5 Pa6 Pb8 PcPbPcPaPaPcPcPbPcPaPb線性表的鏈式表示和實現(xiàn)線性表線性表順序存儲順序存儲特征：特征：邏輯相鄰，物理也相鄰；邏輯相鄰，物理也相鄰；優(yōu)點：優(yōu)點：隨機存取結構隨機存取結構缺點：缺點：插入、刪除需要移動大量元素插入、刪除需要移動大量元素改進方案：改進方案：鏈式存儲結構鏈式存儲結構邏輯結構：邏輯結構：“一對一一對一” 或或 “1:11:1”存儲結構：存儲結構：順序存儲、鏈式存儲順序存儲、鏈式存儲運運 算：算：插入、刪除插入、刪除小

22、結：三、線性結構 在線性表的在線性表的第第i i個位置前個位置前插入一個元素的示插入一個元素的示意圖如下：意圖如下：1213212428304277121321242830427712345678123456789插入插入i=5i=5三、線性結構123456789121321242528304277123456781213212428304277i=5刪除順序表中刪除順序表中第第i i個個元素的示意圖如下：元素的示意圖如下：三、線性結構算法算法數(shù)據(jù)結構概述數(shù)據(jù)結構概述線性結構線性結構棧和隊列棧和隊列數(shù)組數(shù)組樹樹圖圖第第2章章 數(shù)據(jù)結構數(shù)據(jù)結構 棧 棧的應用舉例 隊列四、棧和隊列棧的定義 棧（S

23、tack）是限定只能在表的一端進行插入和刪除操作的線性表，又稱限定性線性表結構。2. 棧的結構特點和操作 棧頂（Top）、棧底（Bottom）、先入后出（LIFO） 棧堆棧結構示意圖 棧棧是限定僅在表尾進行插入或刪除操作的線性表。表尾稱為棧頂top；表頭稱為棧底bottom；例：棧S=（a1，a2，an-1 ，an）棧頂棧底入棧：在棧頂插入一個元素的操作；出棧：從棧頂刪除一個元素的操作；基本操作：在棧頂進行插入、刪除、棧的初始化、 判空及取棧頂元素 棧basebase為棧底指針，始終指向棧底，base=NULL表示棧結構不存在；top為棧頂指針，初值指向棧底，top入棧：插入新的棧頂元素，指針

24、top加1-先插入后加1A即top=base，表示?？?。BCD出棧：指針top減1，刪除棧頂元素-先減1后刪除非空棧的棧頂指針top始終指向棧頂元素的下一個位置EFtoptoptop棧滿棧滿top-base=stacksizebasetopABCDEFtoptoptoptoptoptop?？諚？杖霔Ｈ霔USH(s,x):stop+=x;出棧出棧 POP(s,x):x=s-top;例：一個棧的輸入序列為1，2，3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？可以通過窮舉所有可能性來求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、

25、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321；合計有5種可能性。 棧例：設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是： A. a，b，c，d B. c，d，a，b C. b，c，d，a D. a，c，d，b若輸入序列是若輸入序列是 ,PjPkPi (PjPkPi) ，一定不存在這樣的輸出序列一定不存在這樣的輸出序列 ,PiPjPk 即對于輸入序列即對于輸入序列1，2，3，不存在輸出序列，不存在輸出序列3，1，2 棧隊列的定義 隊列（Queue）是限定只能在表的一端進行插入，在表的另一端進行刪除操

26、作的線性表。2. 隊列的結構特點和操作 隊列頭（front）、隊列尾（rear），先入先出（FIFO） 隊列隊列是只允許在表的一端進行插入，另一端進行刪除。隊列是只允許在表的一端進行插入，另一端進行刪除。允許插入的一端稱為隊尾（rear）；允許刪除的一端稱為隊頭（front）；特點：特點：先進先出先進先出/FIFOa1 a2 a3 an隊頭隊尾入隊列出隊列 隊列 串（即字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個字符組成 字符串，由零個或多個字符組成的有限序列。 S“a0a1.an-1”串的長度：n空串：n=0，Null String子串與主串，子串的位置（從0開始）串的比較：最大相等前綴

27、子序列補充串 下列數(shù)據(jù)結構中，按先進后出原則組織數(shù)據(jù)的是（ ）A線性鏈表B棧C循環(huán)鏈表D順序表【答案】B四、棧和隊列 下列關于棧的敘述中正確的是（ ） A在棧中只能插入數(shù)據(jù)B在棧中只能刪除數(shù)據(jù)C棧是先進先出的線性表D棧是先進后出的線性表【答案】D四、棧和隊列 下列關于隊列的敘述中正確的是（ ） A在隊列中只能插入數(shù)據(jù)B在隊列中只能刪除數(shù)據(jù)C隊列是先進先出的線性表D隊列是先進后出的線性表【答案】C四、棧和隊列 下列敘述中，正確的是（ ）A線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的B線性鏈表中的表頭元素一定存儲在其他元素的前面C線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面D線性鏈表中的各