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

1、地圖數(shù)據(jù)庫(kù)原理與技術(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)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(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ù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。,4,什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，

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

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

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

5、信息檢索系統(tǒng)、文字編輯系統(tǒng)、問答系統(tǒng)、自然語言翻譯系統(tǒng)、詞法分析系統(tǒng)、音樂分析程序等,11,§3.1 串,二、定義由零個(gè)或多個(gè)字符組成的有限序列,記作：S = ‘a(chǎn)1 a2 … an’子串有兩個(gè)字串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 串,三、存儲(chǔ)結(jié)構(gòu)順序存放特點(diǎn)查詢快更新慢,按字節(jié)編址,按字編址無壓縮,按字編址壓縮存放,節(jié)省存儲(chǔ)空間，單字節(jié)操作不方便,更新需移動(dòng)多個(gè)存儲(chǔ)單元,13,§3.1 串,鏈?zhǔn)酱娣旁诿恳蛔址箝_辟一定大小的存儲(chǔ)空間，用來存放下一字符串所在存儲(chǔ)位置的起始地址，這塊附加的存儲(chǔ)空間稱為指針域特點(diǎn)不必把一組字符串存放在連續(xù)的存儲(chǔ)單元中刪除或插入字符串時(shí)，僅需改變相關(guān)指針查找速度慢,,,,,,指針,14,&

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

8、方式,17,§3.2 數(shù)組,一、定義一組具有相同屬性的數(shù)據(jù)元素（數(shù)據(jù)類型、數(shù)據(jù)長(zhǎng)度相同）按一定方式進(jìn)行排列，使得其中每一數(shù)據(jù)元素都能由一個(gè)整數(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ù)組,三、存儲(chǔ)方式用一組連續(xù)的存儲(chǔ)單元來存放

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

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

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

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

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

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

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

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

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

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

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é)點(diǎn)，然后依次訪問層數(shù)為1的節(jié)點(diǎn)，直到訪問完最下一層的所有節(jié)點(diǎn),ABCDEFGHIJ,41,§3.6 樹,三、存儲(chǔ)方式一般采用

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

21、j鄰接，稱邊(Vi, Vj)依附于頂點(diǎn)Vi, Vj；依附于頂點(diǎn)邊的個(gè)數(shù)稱為度在有向圖中，進(jìn)入該頂點(diǎn)的有向邊的個(gè)數(shù)為入度，由該頂點(diǎn)引出的有向邊的個(gè)數(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 圖,二、存儲(chǔ)相鄰矩陣表示法若G是一個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖，則G的相鄰矩陣為：,{,46,§3.7 圖,鄰接表表示法節(jié)點(diǎn)表 + 邊表節(jié)點(diǎn)表：數(shù)據(jù)域 + 指針域（指向此節(jié)點(diǎn)的邊表）邊表：每個(gè)表目對(duì)應(yīng)一條邊，包括與此邊相關(guān)聯(lián)的另一個(gè)節(jié)點(diǎn)序號(hào) + 指向下一個(gè)表目的指針,,,,,,,,,,,,,,,,,,,,,47,§3.7 圖,

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

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