數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、二叉樹、圖ppt課件

1、常見數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、二叉樹、圖（一）、線性表 線性表是線性表是n個(gè)類型相同的數(shù)據(jù)元素的有限個(gè)類型相同的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是一對一的關(guān)系，即序列，數(shù)據(jù)元素之間是一對一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖直接后繼，如圖2.1所示。例如：英文字所示。例如：英文字母表母表(A,B,Z)就是一個(gè)簡單的線性表，就是一個(gè)簡單的線性表，表中的每一個(gè)英文字母是一個(gè)數(shù)據(jù)元素，表中的每一個(gè)英文字母是一個(gè)數(shù)據(jù)元素，每個(gè)元素之間存在唯一的順序關(guān)系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。（二）、棧 棧是允許在一端進(jìn)行插

2、入和刪除操作的特殊線性表。 允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動； 棧中元素個(gè)數(shù)為零時(shí)稱為空棧。棧結(jié)構(gòu)也稱為后進(jìn)先出表LIFO）。 a1 a2 an棧底棧底棧頂棧頂MAXSIZETOP 隊(duì)列(Queue)的定義 隊(duì)列是限定僅在表的一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。 允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)首(front)。 隊(duì)列的插入操作，稱為入隊(duì)；隊(duì)列的刪除操作，稱為出隊(duì)。當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。 設(shè)隊(duì)列q=(a0，a1，a2，an-1)，則a0稱為隊(duì)頭元素，an-1稱為隊(duì)尾元素。元素按a0，a1，

3、a2， ，an-1的次序入隊(duì)，出隊(duì)也只能按照這個(gè)次序。 隊(duì)列和棧相反，隊(duì)列的操作是按先進(jìn)先出First In First Out的原則進(jìn)行的，又稱為先進(jìn)先出的線性表簡稱FIFO表）。三、隊(duì)列（四）、二叉樹（四）、二叉樹 類型與定義類型與定義 二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EF二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹介紹基本術(shù)語 葉子結(jié)點(diǎn) 結(jié)點(diǎn) 結(jié)點(diǎn)總數(shù) 深度 層abcdef

4、ghij 結(jié)點(diǎn)的層次從根開始定義起，根結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層，依次為第一層，根的孩子為第二層，依次累計(jì)。累計(jì)。 樹中結(jié)點(diǎn)的最大層次稱為樹的深樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。度或高度。 性質(zhì)性質(zhì) 1 ： 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 (i1)用歸納法證明：用歸納法證明： 歸納基：歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)，層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2i-1 = 20 = 1；假設(shè)對所有的 j，1 j i，命題成立;二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第 i 層的結(jié)點(diǎn)數(shù) =

5、2i-2 2 = 2i-1 。 性質(zhì)性質(zhì) 2 ： 深度為深度為 k 的二叉樹上至多含的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)k1）證明：證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 性質(zhì)性質(zhì) 3 ： 對任何一棵二叉樹，若它含有對任何一棵二叉樹，若它含有n0 個(gè)葉子個(gè)葉子結(jié)點(diǎn)、結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系的結(jié)點(diǎn)，則必存在關(guān)系式：式：n0 = n2+1證明：證明：設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù)二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù)二叉樹上分支總數(shù) b = n1 + 2n2而 b = n-1 =

6、n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1兩類特殊的二叉樹：兩類特殊的二叉樹：滿二叉樹：指的是滿二叉樹：指的是深度為深度為k且含有且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹完全二叉樹：樹中所含的中所含的 n 個(gè)結(jié)個(gè)結(jié)點(diǎn)和滿二叉樹中點(diǎn)和滿二叉樹中編號為編號為 1 至至 n 的的結(jié)點(diǎn)一一對應(yīng)。結(jié)點(diǎn)一一對應(yīng)。123456789 10 11 12 13 14 15abcdefghij 性質(zhì)性質(zhì) 4 ： 具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹個(gè)結(jié)點(diǎn)的完全二叉樹的深度為的深度為 log2n +1證明：證明：設(shè)設(shè) 完全二叉樹的深度為完全二叉樹的深度為 k 則根據(jù)第二條性

7、質(zhì)得 2k-1 n 2k 即 k-1 log2 n k 由于由于 k 只能是整數(shù)，因此，只能是整數(shù)，因此， k =log2n + 1滿二叉樹的葉節(jié)點(diǎn)為N，則它的節(jié)點(diǎn)總數(shù)（ ） A、N B、2N C、2N-1 D、2N+1 E、2N-1 高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（ ）。 A. 10 B. 11 C. 12 D. 13 二叉樹的遍歷二叉樹的遍歷 順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。一、

8、問題的提出一、問題的提出“訪問的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 對對“二叉樹二叉樹而言，可以而言，可以有三條搜索路徑：有三條搜索路徑： 1先上后下的按層次遍歷； 2先左子樹后右子樹的遍歷； 3先右子樹后左子樹的遍歷。二、先左后右的遍歷算法二、先左后右的遍歷算法先根序的遍歷算法先根序的遍歷算法中根序的遍歷算法中根序的遍歷算法后根序的遍歷算法后根序的遍歷算法根根左子樹右子樹根根根根根根根根根根 若二叉樹為空樹，則空操作；否則，（1訪問根結(jié)點(diǎn)；（2先序遍歷左子樹；（3先序遍歷右子樹。先根序的遍歷算法：先根序的遍歷算法： 若二叉樹為空樹，則空操作；否則，（1中序遍歷左子樹；（2訪問根結(jié)點(diǎn)；（3中

9、序遍歷右子樹。中根序的遍歷算法：中根序的遍歷算法： 若二叉樹為空樹，則空操作；否則，（1后序遍歷左子樹；（2后序遍歷右子樹；（3訪問根結(jié)點(diǎn)。后根序的遍歷算法：后根序的遍歷算法：ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A前綴、后綴表達(dá)式 二叉樹的應(yīng)用。二叉樹的應(yīng)用。 中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式 從左向右掃描表達(dá)式、運(yùn)算數(shù)送到輸出隊(duì)列、運(yùn)從左向右掃描表達(dá)式、運(yùn)算數(shù)送到輸出隊(duì)列、運(yùn)算符進(jìn)棧、如果運(yùn)算優(yōu)先級大于棧頂元素直接進(jìn)算符進(jìn)棧

10、、如果運(yùn)算優(yōu)先級大于棧頂元素直接進(jìn)棧，如果運(yùn)算優(yōu)先級小于或等于棧頂元素，則先棧，如果運(yùn)算優(yōu)先級小于或等于棧頂元素，則先彈出棧頂元素，再進(jìn)棧、左括號直接進(jìn)棧、右括彈出棧頂元素，再進(jìn)棧、左括號直接進(jìn)棧、右括號則依次彈出棧中的元素，直到遇到第一個(gè)左括號則依次彈出棧中的元素，直到遇到第一個(gè)左括號為止。號為止。 有些題目要求寫出前綴、中綴和后綴表達(dá)式，做有些題目要求寫出前綴、中綴和后綴表達(dá)式，做這類題目時(shí)，可以先通過優(yōu)先級畫出一棵二叉樹這類題目時(shí)，可以先通過優(yōu)先級畫出一棵二叉樹再分別利用先根、中根和后根遍歷寫出對應(yīng)的序再分別利用先根、中根和后根遍歷寫出對應(yīng)的序列，就是它們的前綴、中綴和后綴表達(dá)式。列，就

11、是它們的前綴、中綴和后綴表達(dá)式。 表達(dá)式a*(b+c)-d的后綴表達(dá)式是： A)abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為 。 一棵二叉樹的中序遍歷序列為：DGBAECHF，后序遍歷序列為：GDBEHFCA，則前序列遍歷序列是 _。數(shù)據(jù)結(jié)構(gòu)之圖 什么是圖什么是圖 什么是計(jì)算機(jī)中所說的圖?請先看下面的“柯尼斯堡橋問題”。傳說在東普魯士境內(nèi)，有一座柯尼斯堡城，希雷格爾河流經(jīng)這個(gè)城市的克奈霍福島后，就將這個(gè)城市一分為二，形成如圖11左的A、B、C、D 4個(gè)

12、地區(qū)。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來。在游覽中有人提出，是否可以從A地出發(fā)，各座橋恰好通過一次，最后又回到原來出發(fā)地呢? 這個(gè)問題在18世紀(jì)被數(shù)學(xué)家歐拉解決了。他把這個(gè)問題轉(zhuǎn)化為圖11右邊所示的圖。圖上用A、B、C、D4個(gè)頂點(diǎn)分別表示4個(gè)地區(qū)，用兩點(diǎn)間的線段表示連接各地的橋。這樣原來的問題就轉(zhuǎn)化為：從A頂點(diǎn)出發(fā)經(jīng)過其中每一條線段一次，而且僅一次，再回到A點(diǎn)的“一筆畫問題。 歐拉對柯尼斯堡問題作出了否定的結(jié)論。因?yàn)閷τ诿恳粋€(gè)頂點(diǎn)，不論如何經(jīng)過，必須有一條進(jìn)路和一條出路，所以對每一個(gè)頂點(diǎn)(除起點(diǎn)和終點(diǎn))來說與它有關(guān)的線段(稱為邊)必須是偶數(shù)條。而圖1-1(右)的頂點(diǎn)有關(guān)的線段都是奇數(shù)條，因此不

13、可能一筆畫出。 歐拉通過對柯尼斯堡橋問題的研究，于1736年發(fā)表了著名的關(guān)于圖論的論文，從而創(chuàng)立了圖論的學(xué)說。圖12一類的問題就是圖論中所指的圖。 又如，有6個(gè)足球隊(duì)之間進(jìn)行循環(huán)賽，他們比賽的場次可以用圖1-3(1)來表示。有3個(gè)人相互寫信，可以用圖13(2)來表示。 從上面兩個(gè)例子可看出，我們這里所說的圖(graph)，與人們通常所熟悉的圖，如圓、四邊形、函數(shù)圖象等是很不相同的。是指某些具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)來表示事物(如地點(diǎn)、隊(duì))，用線段來表示兩事物之間的聯(lián)系，那么一個(gè)圖就是表示事物的點(diǎn)集和表示事物之間聯(lián)系的線段集合所構(gòu)成。其中線段僅表示兩點(diǎn)的關(guān)系，它的長短與曲直是無關(guān)

14、緊要的。例如圖1-4中3個(gè)圖，被認(rèn)為是同一個(gè)圖。圖的基本概念圖的基本概念 定義：圖定義：圖G定義為一個(gè)偶對定義為一個(gè)偶對(V，E)，記作，記作G：(V，E)。其中。其中 1)V是一個(gè)非空有限集合，它的元素稱為頂點(diǎn)；是一個(gè)非空有限集合，它的元素稱為頂點(diǎn)； 2)E也是一個(gè)集合，它的元素稱為邊也是一個(gè)集合，它的元素稱為邊 例如圖例如圖1-4中的圖有中的圖有4個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，4條邊。條邊。 或者定義：圖或者定義：圖GGraph是由頂點(diǎn)的集合是由頂點(diǎn)的集合V和邊的集合和邊的集合E所組成的二元組，記作：所組成的二元組，記作：G =（V，E） 其中其中V是頂點(diǎn)的集合，是頂點(diǎn)的集合，E是邊的集合。是邊的集合。

15、無向圖與有向圖：邊的表示方式是用該邊的兩無向圖與有向圖：邊的表示方式是用該邊的兩個(gè)頂點(diǎn)來表示的，如果邊的表示無方向，那么，個(gè)頂點(diǎn)來表示的，如果邊的表示無方向，那么，對應(yīng)的圖就是無向圖，否則稱為有向圖，如下對應(yīng)的圖就是無向圖，否則稱為有向圖，如下圖所示：圖所示： 在無向圖中，邊的兩個(gè)頂點(diǎn)在邊的表示中可以互換，如邊在無向圖中，邊的兩個(gè)頂點(diǎn)在邊的表示中可以互換，如邊V1,V4與邊與邊V4,V1是等價(jià)的，表示的是同一條邊。（無向圖中邊的表是等價(jià)的，表示的是同一條邊。（無向圖中邊的表示用圓括號）示用圓括號） 在有向圖中，邊的走向不同就認(rèn)為是不同的邊。如在邊的集合在有向圖中，邊的走向不同就認(rèn)為是不同的邊。

16、如在邊的集合E=,(見右見右上圖上圖)中，其中中，其中表示該邊是由頂點(diǎn)表示該邊是由頂點(diǎn)1出發(fā)，到頂點(diǎn)出發(fā)，到頂點(diǎn)4結(jié)束，即結(jié)束，即邊邊表明了該邊的方向性，且兩個(gè)頂點(diǎn)的順序不能顛倒。（有表明了該邊的方向性，且兩個(gè)頂點(diǎn)的順序不能顛倒。（有向圖中邊的表示用尖括號）向圖中邊的表示用尖括號） 頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖頂點(diǎn)頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。的度等于該頂點(diǎn)的入度與出度之和。 入度入度以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和 出度出度以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 圖的階：圖中頂點(diǎn)的個(gè)數(shù)。例如圖圖的階：圖中

17、頂點(diǎn)的個(gè)數(shù)。例如圖13中分別是中分別是6和和3。 度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。做偶點(diǎn)。 定理1 圖G中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。因?yàn)橛?jì)算頂點(diǎn)的度數(shù)時(shí)。每條邊均用到2次。定理2 任意一個(gè)圖一定有偶數(shù)個(gè)奇點(diǎn)。連通：如果圖中結(jié)點(diǎn)連通：如果圖中結(jié)點(diǎn)U，V之間存在一條從之間存在一條從U通過若干條邊、點(diǎn)到達(dá)通過若干條邊、點(diǎn)到達(dá)V的通路，稱的通路，稱U、V是連通的。是連通的。連通圖：如果一個(gè)無向圖中連通圖：如果一個(gè)無向圖中,任一對不同頂點(diǎn)任一對不同頂點(diǎn)U、V，都有一條，都有一條U，V通路，則通路，則稱圖稱圖G是連通的。是連通的。強(qiáng)連通圖

18、：在有向圖強(qiáng)連通圖：在有向圖G中，每一對結(jié)點(diǎn)之間都有路徑的圖。中，每一對結(jié)點(diǎn)之間都有路徑的圖。網(wǎng)絡(luò)：帶權(quán)的連通圖。網(wǎng)絡(luò)：帶權(quán)的連通圖。BACDFE 連通：如果頂點(diǎn)連通：如果頂點(diǎn)u，v屬于屬于G，u，v之間有一條從之間有一條從u通過若干條邊到達(dá)通過若干條邊到達(dá)v的通路，則認(rèn)為頂點(diǎn)的通路，則認(rèn)為頂點(diǎn)u和和v是是連通的。連通的。 連通圖：如果對于圖連通圖：如果對于圖G中每一對不同頂點(diǎn)中每一對不同頂點(diǎn)u，v都都有一條有一條(u，v)通路，則稱通路，則稱G是連通圖。是連通圖。 通路指通路指u-邊邊1-頂點(diǎn)頂點(diǎn)1-邊邊2-頂點(diǎn)頂點(diǎn)2-v，點(diǎn)和邊交替相接，且互不相同。，點(diǎn)和邊交替相接，且互不相同。 圖的遍歷 1、概念：從圖中某一結(jié)點(diǎn)出發(fā)系統(tǒng)地訪問圖中所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次，這種運(yùn)算 稱圖的遍歷。為了避免重復(fù)訪問某個(gè)結(jié)點(diǎn)，可以設(shè)一個(gè)標(biāo)志數(shù)組visitedI，未訪問時(shí)值為FALSE，訪問一次后就改為TRUE。 2、分類：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。 深度優(yōu)先遍歷：類似于樹的先序