第3章_數(shù)據(jù)結(jié)構(gòu)

1、地圖數(shù)據(jù)庫原理與技術(shù),2,第三章,數(shù) 據(jù) 結(jié) 構(gòu),3,什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)是在整個計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu) 。數(shù)據(jù)結(jié)構(gòu)分為：邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系；物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計算機內(nèi)部的存儲安排。,4,什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，

2、它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu) 線性(線性表，棧，隊列，向量， 字符串，多維數(shù)組，廣義表)，樹，圖，文件,數(shù)據(jù)結(jié)構(gòu)主要研究什么？,5,什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)的物理存儲結(jié)構(gòu)順序方法、索引方法、散列方法對數(shù)據(jù)的操作（或算法） 通常，算法的設(shè)計取決于

3、數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。,6,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),計算機的應(yīng)用的飛速發(fā)展，計算機的應(yīng)用已經(jīng)不在局限于科學(xué)計算，大量非數(shù)值計算的應(yīng)用需要處理各種具有一定結(jié)構(gòu)的數(shù)據(jù)，為此需分析待處理對象的特征以及各處理對象之間的關(guān)系。因此： 數(shù)據(jù)結(jié)構(gòu)也可以認(rèn)為是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 同時數(shù)據(jù)結(jié)構(gòu)也是計算機各有關(guān)專業(yè)核

4、心基礎(chǔ)課程,7,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),它研究了計算機需要處理的數(shù)據(jù)對象和對象之間的關(guān)系。它刻畫了應(yīng)用中涉及到的數(shù)據(jù)的邏輯組織。它描述了數(shù)據(jù)在計算機中如何存儲、傳送、轉(zhuǎn)換。,8,主要內(nèi)容：,串表隊列圖,數(shù)組棧樹,9,§3.1 串,一、應(yīng)用領(lǐng)域二、定義三、存儲結(jié)構(gòu)四、運算,10,§3.1 串,一、應(yīng)用領(lǐng)域非數(shù)值處理對象，由按一定順序排列的各種字符組成在程序中可以作為常量和變量，通過變量名可以調(diào)用

5、信息檢索系統(tǒng)、文字編輯系統(tǒng)、問答系統(tǒng)、自然語言翻譯系統(tǒng)、詞法分析系統(tǒng)、音樂分析程序等,11,§3.1 串,二、定義由零個或多個字符組成的有限序列,記作：S = ‘a(chǎn)1 a2 … an’子串有兩個字串S1 = ‘a(chǎn)1 a2 … an’， S2 = ‘b1b2 … bm’，如果存在整數(shù)i，使得bj = ai+j j = 1, 2, …, m則稱S2是S1的子串,串名,串值,12,

6、7;3.1 串,三、存儲結(jié)構(gòu)順序存放特點查詢快更新慢,按字節(jié)編址,按字編址無壓縮,按字編址壓縮存放,節(jié)省存儲空間，單字節(jié)操作不方便,更新需移動多個存儲單元,13,§3.1 串,鏈?zhǔn)酱娣旁诿恳蛔址箝_辟一定大小的存儲空間，用來存放下一字符串所在存儲位置的起始地址，這塊附加的存儲空間稱為指針域特點不必把一組字符串存放在連續(xù)的存儲單元中刪除或插入字符串時，僅需改變相關(guān)指針查找速度慢,,,,,,指針,14,&

7、#167;3.1 串,,,,,,,,刪除操作,插入操作,,15,§3.1 串,四、運算給一個字符串變量名賦值S ? ‘a(chǎn)bc’S ? S1比較兩字符串是否相等strcmp(S1, S2) 從一個字符串的指定位置截取一定長度的子串substr(S1,i, j)將兩字符串合并形成一個新的字符串S1 // S2 = a1 a2 … anb1b2 … bm,16,§3.2 數(shù)組,一、定義二、表示三、存儲

8、方式,17,§3.2 數(shù)組,一、定義一組具有相同屬性的數(shù)據(jù)元素（數(shù)據(jù)類型、數(shù)據(jù)長度相同）按一定方式進行排列，使得其中每一數(shù)據(jù)元素都能由一個整數(shù)序列唯一確定它的位置，這樣的數(shù)據(jù)結(jié)構(gòu)稱為數(shù)組。,18,§3.2 數(shù)組,二、表示,name(1)=“張三”name(2)=“李四”name(3)=“王五”name(4)=“馬六”,一維數(shù)組,二維數(shù)組,19,§3.2 數(shù)組,三、存儲方式用一組連續(xù)的存儲單元來存放

9、數(shù)組元素的值 一維數(shù)組對于一個有n個元素組成的一維數(shù)組 a1, a2, … , an 設(shè)每一個元素占用1個存儲單元，若第一個數(shù)據(jù)元素存放的地址是addr(a(1))，則第i個數(shù)據(jù)元素的存放地址為addr(a(i)) = addr(a(1)) + (i – 1),20,§3.2 數(shù)組,二維數(shù)組對于一個m列n行的二維數(shù)組,按行存儲,按列存儲,按行存儲addr(a(i, j)) = addr(a(

10、1, 1))+ (i –1)?m + j -1,按列存儲addr(a(i, j)) = addr(a(1, 1))+ (j –1)?n + i -1,21,§3.3 表,一、定義二、運算三、存儲方式,22,數(shù)據(jù)項,§3.3 表,一、定義表是一組有序的數(shù)據(jù)元素每一數(shù)據(jù)元素包含一個或多個數(shù)據(jù)項每一數(shù)據(jù)元素與唯一的關(guān)鍵字相關(guān)聯(lián),行：數(shù)據(jù)元素,,關(guān)鍵字,,23,§3.3 表,二、運算求出一個表所含數(shù)據(jù)

11、元素個數(shù)對于給定關(guān)鍵字，查找表中相應(yīng)數(shù)據(jù)元素在表中指定位置上插入一個數(shù)據(jù)元素刪除表中指定位置上的數(shù)據(jù)元素按某種要求對表中數(shù)據(jù)元素重新排序,24,§3.3 表,三、存儲方式順序存放把表中元素依次存放在一組連續(xù)的單元內(nèi)訪問方便快捷，更新操作復(fù)雜設(shè)表的基地址為addr(a1)，假定每個數(shù)據(jù)元素占用k 個存儲單元，則的存儲單元的首地址為addr[ai] = addr(a1) + (i - 1) ? k,25,

12、7;3.3 表,鏈?zhǔn)酱娣疟淼拿恳挥涗浽鲈O(shè)一個指針，指明后繼元素的存儲單元的首地址特點無須連續(xù)和順序排放更新簡單增加空間開銷檢索必須從鏈頭開始，效率低,26,§3.4 棧,一、定義二、特性三、存儲四、操作,27,§3.4 棧,一、定義棧是一種操作受限的線性表對于棧的插入和刪除操作都限制在表的末端進行將表的末端稱為棧頂，起始位置稱為棧底二、特性每次刪除的總是最后插入的表目，而最先插入的表目則放

13、在棧的底部，要到最后才能刪除，因此棧是“后進先出表”或下推表食堂里的一疊盤子算術(shù)表達式、遞歸,28,§3.4 棧,三、存儲用向量（由相同數(shù)據(jù)類型組成的線性序列）表示棧，并用指針指示棧頂?shù)奈恢?棧底,棧頂,棧頂指示器?i,29,§3.4 棧,四、操作push(ST, X)：往棧ST中壓入一個值為X的表目pop(ST)：從棧ST中彈出一個表目top(ST, X)：把棧頂表目的值讀到變量X中，棧保持不變sem

14、pty(ST)：判斷棧是否為空?？臻g大小是預(yù)先設(shè)定的，稱為棧容量，如果棧已存滿，再進行push操作，則棧將上溢出(overflow)；如果棧里已沒有表目，再進行pop操作，則棧將下溢出(underflow),30,§3.5 隊列,一、定義二、存儲三、操作,31,§3.5 隊列,一、定義隊列是一種操作受限的線性表對于隊列的插入在表的一端進行，刪除操作在表的另一端進行進行刪除的一端稱為隊列的頭，進行插入的一端

15、稱為隊列的尾新來的成員總是加入到隊尾，每次離開的總是隊頭上的元素(先進先出),32,§3.5 隊列,二、存儲用順序表實現(xiàn)，分配一塊連續(xù)存儲區(qū)域存放隊列中的元素，用兩個指針分別指向隊列的頭尾當(dāng)隊列首尾指針相連時，發(fā)生隊列溢出,頭指針,尾指針,頭指針,尾指針,假溢出,33,§3.5 隊列,三、操作enq(QU, X)：往隊列QU中插入一個值為X的表目deq(QU)：從隊列QU中刪除一個表目front(QU,

16、X)：把隊列QU頭部表目的值讀到變量X中qempty(QU)：判斷隊列是否為空,頭指針,尾指針,頭指針,尾指針,插入aj+1,刪除ai,34,§3.6 樹,一、定義二、樹的遍歷三、存儲方式,35,§3.6 樹,一、定義樹結(jié)構(gòu)是節(jié)點之間有分支的、層次的關(guān)系的結(jié)構(gòu)樹結(jié)構(gòu)是非線性結(jié)構(gòu)線性：數(shù)據(jù)元素能按一定的順序進行排列，其中除第一和最后一個外，其它元素都有一個唯一的前驅(qū)元素和后繼元素，即元素之間存在著唯一的關(guān)系

17、樹樹是n個節(jié)點的有窮集合K，滿足：①有且僅有一個節(jié)點沒有前驅(qū)，稱為樹的根②除根之外，其他節(jié)點有且僅有一個前驅(qū)③任一節(jié)點都存在一個從根到該節(jié)點的節(jié)點序列,36,,,,,,,,,,§3.6 樹,樹是包含n個節(jié)點的有限集合，滿足① 有且僅有一個節(jié)點沒有前驅(qū)，稱為樹的根② 除根之外的其他節(jié)點被分成m個不相交的集合，而且這些集合的每一個又都是樹樹的一枝所含子節(jié)點的數(shù)目稱為度，各節(jié)點度的最大值稱為樹的度,數(shù)據(jù)結(jié)構(gòu)

18、,線性結(jié)構(gòu),非線性結(jié)構(gòu),數(shù)組,串,表,棧,隊列,樹,圖,根節(jié)點,內(nèi)部節(jié)點,葉節(jié)點,37,§3.6 樹,A,B,C,G,H,F,D,E,J,I,,,,,,,,,,(A(B(D)(E(I)(J))(F))(C(G)(H))),樹形表示,文氏圖表示,嵌套括號表示,38,§3.6 樹,二、樹的遍歷遍歷：將樹節(jié)點放入一個線性序列的過程按深度的方向遍歷先根次序訪問頭一棵樹的根在先根次序下遍歷頭一棵樹樹根的子樹在先根次

19、序下遍歷其他的樹,A,B,C,G,H,F,D,E,,,,,,,,J,I,,,A B D E I J F C G H,39,§3.6 樹,后根次序在后根次序下遍歷頭一棵樹樹根的子樹訪問頭一棵樹的根在后根次序下遍歷其他的樹,40,§3.6 樹,按寬度的方向遍歷首先訪問層數(shù)為0的節(jié)點，然后依次訪問層數(shù)為1的節(jié)點，直到訪問完最下一層的所有節(jié)點,ABCDEFGHIJ,41,§3.6 樹,三、存儲方式一般采用

20、鏈表存儲,指向直接后繼節(jié)點,42,§3.7 圖,一、定義二、存儲,43,§3.7 圖,一、定義有限的節(jié)點集合K，對K中節(jié)點的前驅(qū)和后繼節(jié)點的個數(shù)不加限制，則就是圖結(jié)構(gòu)用G=(V, E)表示一個圖，圖的節(jié)點稱為頂點，V是有窮頂點的集合，節(jié)點的偶對稱為邊，E是邊的集合如果節(jié)點的偶對是無序的，則稱為無向圖；如果節(jié)點的偶對是有序的，則稱為有向圖在無向圖中，若頂點Vi與Vj之間有一條邊(Vi, Vj)，則稱Vi與V

21、j鄰接，稱邊(Vi, Vj)依附于頂點Vi, Vj；依附于頂點邊的個數(shù)稱為度在有向圖中，進入該頂點的有向邊的個數(shù)為入度，由該頂點引出的有向邊的個數(shù)為出度，度=入度+出度,44,§3.7 圖,V={V1,V2,V3,V4}E={(V1,V2), (V2,V3), (V1,V4), (V2,V4) (V3,V4)},V={V1,V2,V3,V4}E={(V1,V2), (V1,V4), (V2,V3), (V3,V2)

22、(V4,V3)},度為3,度為2,出度為1入度為2度為3,45,§3.7 圖,二、存儲相鄰矩陣表示法若G是一個具有n個節(jié)點的有向圖，則G的相鄰矩陣為：,{,46,§3.7 圖,鄰接表表示法節(jié)點表 + 邊表節(jié)點表：數(shù)據(jù)域 + 指針域（指向此節(jié)點的邊表）邊表：每個表目對應(yīng)一條邊，包括與此邊相關(guān)聯(lián)的另一個節(jié)點序號 + 指向下一個表目的指針,,,,,,,,,,,,,,,,,,,,,47,§3.7 圖,

23、,,,,,,,,,,,,,,,,,,,,出邊表,入邊表,48,§3.7 圖,三、圖的遍歷遍歷：從圖中某一點出發(fā)訪問圖中其余頂點，或當(dāng)給定的圖是連通圖，則從圖中任意一點出發(fā)順著某些邊可以訪問到該圖中的所有的頂點，且使每一個頂點僅被訪問一次。深度優(yōu)先搜索：廣度優(yōu)先搜索：,49,§3.7 圖,三、圖的遍歷深度優(yōu)先搜索： 設(shè)從圖Ｇ＝（Ｖ，Ｅ）中某一頂點Ｖ０出發(fā)，在訪問了任意一個和Ｖ０鄰接的頂點Ｗ１后，出發(fā)訪問和

24、Ｗ１鄰接且未被訪問過的任意頂點Ｗ２。然后，從Ｗ２出發(fā)進行如上的訪問。重復(fù)這種訪問，直到一個頂點的所有鄰接點都被訪問過為止，接著退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)，重復(fù)上述搜索過程，直到所有的被訪問過的頂點的鄰接點都已被訪問到為止。,Ｖ１→Ｖ２→Ｖ４→Ｖ８→Ｖ５→Ｖ６→Ｖ３→Ｖ７,50,§3.7 圖,三、圖的遍歷廣度優(yōu)先搜索,從圖Ｇ中某一頂點Ｖ0出發(fā)，首先依次訪問Ｖ0的鄰接的頂點Ｗ１，Ｗ２，… ，Ｗｔ。然后，再順