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

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

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

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

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

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

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

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

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

9、序遍歷右子樹。中根序的遍歷算法：中根序的遍歷算法： 若二叉樹為空樹，則空操作；否則，（1后序遍歷左子樹；（2后序遍歷右子樹；（3訪問根結(jié)點。后根序的遍歷算法：后根序的遍歷算法：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前綴、后綴表達式 二叉樹的應(yīng)用。二叉樹的應(yīng)用。 中綴表達式轉(zhuǎn)換后綴表達式中綴表達式轉(zhuǎn)換后綴表達式 從左向右掃描表達式、運算數(shù)送到輸出隊列、運從左向右掃描表達式、運算數(shù)送到輸出隊列、運算符進棧、如果運算優(yōu)先級大于棧頂元素直接進算符進棧

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

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

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

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

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

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

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

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

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