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

1、常見數(shù)據(jù)結(jié)構(gòu),線性表、棧、隊列、二叉樹、圖,（一）、線性表,線性表是n個類型相同的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是一對一的關(guān)系，即每個數(shù)據(jù)元素最多有一個直接前驅(qū)和一個直接后繼，如圖2.1所示。例如：英文字母表(A,B,Z)就是一個簡單的線性表，表中的每一個英文字母是一個數(shù)據(jù)元素，,每個元素之間存在唯一的順序關(guān)系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。,（二）、棧,棧是允許在一端進(jìn)行插入和刪除操作的特殊線性表。 允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動； 棧中元素個數(shù)為零時稱為空棧。棧結(jié)構(gòu)也稱為后進(jìn)先出表（LIFO）

2、。,隊列(Queue)的定義 隊列是限定僅在表的一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。 允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊首(front)。 隊列的插入操作，稱為入隊；隊列的刪除操作，稱為出隊。當(dāng)隊列中沒有元素時稱為空隊列。 設(shè)隊列q=(a0，a1，a2，an-1)，則a0稱為隊頭元素，an-1稱為隊尾元素。元素按a0，a1，a2， ，an-1的次序入隊，出隊也只能按照這個次序。 隊列和棧相反，隊列的操作是按先進(jìn)先出（First In First Out）的原則進(jìn)行的，又稱為先進(jìn)先出的線性表（簡稱FIFO表）。,三、隊列,（四）、二叉樹 類型與定義,二叉樹或為空樹；

3、或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。,根結(jié)點,左子樹,右子樹,E,F,二叉樹的五種基本形態(tài)：,N,空樹,只含根結(jié)點,N,N,N,L,R,R,右子樹為空樹,L,左子樹為空樹,左右子樹均不為空樹,介紹基本術(shù)語,葉子結(jié)點 結(jié)點 結(jié)點總數(shù) 深度 層,結(jié)點的層次從根開始定義起，根為第一層，根的孩子為第二層，依次累計。 樹中結(jié)點的最大層次稱為樹的深度或高度。,性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i-1 個結(jié)點。 (i1),用歸納法證明： 歸納基： 歸納假設(shè)： 歸納證明：,i = 1 層時，只有一個根結(jié)點， 2i-1 = 20 = 1；,假設(shè)對所有的 j，1 j i

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

5、兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。,完全二叉樹：樹中所含的 n 個結(jié)點和滿二叉樹中編號為 1 至 n 的結(jié)點一一對應(yīng)。,性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的深度為 log2n +1,證明：,設(shè) 完全二叉樹的深度為 k,則根據(jù)第二條性質(zhì)得 2k-1 n 2k,即 k-1 log2 n k,因為 k 只能是整數(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的滿二叉樹。在這里，樹高等于

6、葉結(jié)點的最大深度，根結(jié)點的深度為0，如果某個均衡的二叉樹共有2381個結(jié)點，則該樹的樹高為（ ）。 A. 10 B. 11 C. 12 D. 13,二叉樹的遍歷,順著某一條搜索路徑巡訪二叉樹 中的結(jié)點，使得每個結(jié)點均被訪問一 次，而且僅被訪問一次。,一、問題的提出,“訪問”的含義可以很廣，如：輸出結(jié) 點的信息等。,對“二叉樹”而言，可以有三條搜索路徑：,1先上后下的按層次遍歷； 2先左（子樹）后右（子樹）的遍歷； 3先右（子樹）后左（子樹）的遍歷。,二、先左后右的遍歷算法,先（根）序的遍歷算法,中（根）序的遍歷算法,后（根）序的遍歷算法,根,左 子樹,右 子樹,根,根,根,根,根,若二叉樹為空

7、樹，則空操作；否則， （1）訪問根結(jié)點； （2）先序遍歷左子樹； （3）先序遍歷右子樹。,先（根）序的遍歷算法：,若二叉樹為空樹，則空操作；否則， （1）中序遍歷左子樹； （2）訪問根結(jié)點； （3）中序遍歷右子樹。,中（根）序的遍歷算法：,若二叉樹為空樹，則空操作；否則， （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結(jié)點。,后（根）序的遍歷算法：,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,前綴、后綴表達(dá)式,二叉樹的應(yīng)用。 中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式 從左向右掃描表達(dá)式、運

8、算數(shù)送到輸出隊列、運算符進(jìn)棧、如果運算優(yōu)先級大于棧頂元素直接進(jìn)棧，如果運算優(yōu)先級小于或等于棧頂元素，則先彈出棧頂元素，再進(jìn)棧、左括號直接進(jìn)棧、右括號則依次彈出棧中的元素，直到遇到第一個左括號為止。 有些題目要求寫出前綴、中綴和后綴表達(dá)式，做這類題目時，可以先通過優(yōu)先級畫出一棵二叉樹再分別利用先根、中根和后根遍歷寫出對應(yīng)的序列，就是它們的前綴、中綴和后綴表達(dá)式。,表達(dá)式a*(b+c)-d的后綴表達(dá)式是： A)abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為

9、。 一棵二叉樹的中序遍歷序列為：DGBAECHF，后序遍歷序列為：GDBEHFCA，則前序列遍歷序列是 _。,數(shù)據(jù)結(jié)構(gòu)之圖,什么是圖,什么是計算機(jī)中所說的圖?請先看下面的“柯尼斯堡橋問題”。傳說在東普魯士境內(nèi)，有一座柯尼斯堡城，希雷格爾河流經(jīng)這個城市的克奈霍福島后，就將這個城市一分為二，形成如圖11（左）的A、B、C、D 4個地區(qū)。人們建造了7座橋?qū)⑦@4個地區(qū)連起來。在游覽中有人提出，是否可以從A地出發(fā)，各座橋恰好通過一次，最后又回到原來出發(fā)地呢?,這個問題在18世紀(jì)被數(shù)學(xué)家歐拉解決了。他把這個問題轉(zhuǎn)化為圖11右邊所示的圖。圖上用A、B、C、D4個頂點分別表示4個地區(qū)，用兩點間的線段表示連接各

10、地的橋。這樣原來的問題就轉(zhuǎn)化為：從A頂點出發(fā)經(jīng)過其中每一條線段一次，而且僅一次，再回到A點的“一筆畫”問題。 歐拉對柯尼斯堡問題作出了否定的結(jié)論。因為對于每一個頂點，不論如何經(jīng)過，必須有一條進(jìn)路和一條出路，所以對每一個頂點(除起點和終點)來說與它有關(guān)的線段(稱為邊)必須是偶數(shù)條。而圖1-1(右)的頂點有關(guān)的線段都是奇數(shù)條，因此不可能一筆畫出。,歐拉通過對柯尼斯堡橋問題的研究，于1736年發(fā)表了著名的關(guān)于圖論的論文，從而創(chuàng)立了圖論的學(xué)說。圖12一類的問題就是圖論中所指的圖。,又如，有6個足球隊之間進(jìn)行循環(huán)賽，他們比賽的場次可以用圖1-3(1)來表示。有3個人相互寫信，可以用圖13(2)來表示。,

11、從上面兩個例子可看出，我們這里所說的圖(graph)，與人們通常所熟悉的圖，如圓、四邊形、函數(shù)圖象等是很不相同的。是指某些具體事物和這些事物之間的聯(lián)系。如果我們用點來表示事物(如地點、隊)，用線段來表示兩事物之間的聯(lián)系，那么一個圖就是表示事物的點集和表示事物之間聯(lián)系的線段集合所構(gòu)成。其中線段僅表示兩點的關(guān)系，它的長短與曲直是無關(guān)緊要的。例如圖1-4中3個圖，被認(rèn)為是同一個圖。,圖的基本概念,定義：圖G定義為一個偶對(V，E)，記作G：(V，E)。其中 1)V是一個非空有限集合，它的元素稱為頂點； 2)E也是一個集合，它的元素稱為邊 例如圖1-4中的圖有4個頂點，4條邊。 或者定義：圖G（Gra

12、ph）是由頂點的集合V和邊的集合E所組成的二元組，記作：G =（V，E） 其中V是頂點的集合，E是邊的集合。,無向圖與有向圖：邊的表示方式是用該邊的兩個頂點來表示的，如果邊的表示無方向，那么，對應(yīng)的圖就是無向圖，否則稱為有向圖，如下圖所示：,在無向圖中，邊的兩個頂點在邊的表示中可以互換，如邊（V1,V4）與邊（V4,V1）是等價的，表示的是同一條邊。（無向圖中邊的表示用圓括號） 在有向圖中，邊的走向不同就認(rèn)為是不同的邊。如在邊的集合E=,(見右上圖)中，其中表示該邊是由頂點1出發(fā)，到頂點4結(jié)束，即邊表明了該邊的方向性，且兩個頂點的順序不能顛倒。（有向圖中邊的表示用尖括號）,頂點的度：與頂點關(guān)聯(lián)

13、的邊的數(shù)目，有向圖頂點的度等于該頂點的入度與出度之和。 入度以該頂點為終點的邊的數(shù)目和 出度以該頂點為起點的邊的數(shù)目和 圖的階：圖中頂點的個數(shù)。例如圖13中分別是6和3。 度數(shù)為奇數(shù)的頂點叫做奇點，度數(shù)為偶數(shù)的點叫做偶點。,定理1 圖G中所有頂點的度數(shù)之和等于邊數(shù)的2倍。因為計算頂點的度數(shù)時。每條邊均用到2次。定理2 任意一個圖一定有偶數(shù)個奇點。,連通：如果圖中結(jié)點U，V之間存在一條從U通過若干條邊、點到達(dá)V的通路，稱U、V是連通的。 連通圖：如果一個無向圖中,任一對不同頂點U、V，都有一條（U，V）通路，則稱圖G是連通的。 強(qiáng)連通圖：在有向圖G中，每一對結(jié)點之間都有路徑的圖。 網(wǎng)絡(luò)：帶權(quán)的連

14、通圖。,連通：如果頂點u，v屬于G，u，v之間有一條從u通過若干條邊到達(dá)v的通路，則認(rèn)為頂點u和v是連通的。 連通圖：如果對于圖G中每一對不同頂點u，v都有一條(u，v)通路，則稱G是連通圖。 通路指u-邊1-頂點1-邊2-頂點2-v，點和邊交替相接，且互不相同。,圖的遍歷,1、概念：從圖中某一結(jié)點出發(fā)系統(tǒng)地訪問圖中所有結(jié)點，使每個結(jié)點恰好被訪問一次，這種運算 稱圖的遍歷。為了避免重復(fù)訪問某個結(jié)點，可以設(shè)一個標(biāo)志數(shù)組visitedI，未訪問時值為FALSE，訪問一次后就改為TRUE。 2、分類：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。,深度優(yōu)先遍歷：類似于樹的先序遍歷，從圖中某個結(jié)點V0出發(fā)，訪問此結(jié)點，然后依次訪問從V0的未被訪問的鄰接點出發(fā)進(jìn)行深度優(yōu)先遍歷，直到圖中所有和V0有路徑相通的結(jié)點均被訪問到。若此時圖中尚有結(jié)點未被訪問，則另選圖中一個未被訪問的結(jié)點V1作為起點