數(shù)據(jù)結(jié)構(gòu)期末總結(jié)

2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)—鏈表鏈?zhǔn)酱鎯?chǔ)不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，僅通過(guò)指針來(lái)映射數(shù)據(jù)元素之間的邏輯關(guān)系。存儲(chǔ)結(jié)點(diǎn)包含數(shù)據(jù)域：所有存元素本身的信息；指針域：元素之間邏輯關(guān)系的信息；包含有后繼結(jié)點(diǎn)的地址信息。循環(huán)隊(duì)列：將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接。如何解決假溢出？01234入隊(duì)出隊(duì)a3a4fronta5rearreara6隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（順序隊(duì)列）不存在物理的循環(huán)結(jié)構(gòu)，但可用軟件方法實(shí)現(xiàn)。求模：（4＋1）mod5＝0如何實(shí)現(xiàn)循環(huán)隊(duì)列？01234入隊(duì)出隊(duì)a3a4frontreara6隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（順序隊(duì)列）a5append

job1append

job2append

job3Popjob1append

job4append

job5Popjob2append

job6append

job7append

job8【0】【1】【2】【3】【4】【5】rearfront空隊(duì)：front=rearjob11rear2job23job3rear45job4front6job5rear7front8job69job710job8rear隊(duì)滿：front=rear3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)---幾個(gè)問(wèn)題1、當(dāng)rear指向數(shù)組的最大下標(biāo)的時(shí)候，如何向下標(biāo)為0的位置改變？2、隊(duì)空和隊(duì)滿的條件都是front=rear,如何區(qū)分？3、如何表示出隊(duì)和入隊(duì)操作？【0】【1】【2】【3】【4】【5】CDEfrontrearBMaxSize=6chardata[MaxSize];rear=5rear=?data[rear]=‘F’;rear=(rear+1)%MaxSize3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)---問(wèn)題一

循環(huán)隊(duì)列首尾相連,這可以利用除法取余的運(yùn)算(％)來(lái)實(shí)現(xiàn):

隊(duì)首指針進(jìn)1:front=(front+1)％MaxSize

隊(duì)尾指針進(jìn)1:rear=(rear+1)％MaxSize

循環(huán)隊(duì)列的隊(duì)頭指針和隊(duì)尾指針初始化時(shí)都置0:front=rear=0。在入隊(duì)元素和出隊(duì)元素時(shí),指針都按順時(shí)針?lè)较蜻M(jìn)1。隊(duì)空和隊(duì)滿的條件都是front=rear,如何區(qū)分？

rear

0

1

2

3

4

front

(a)空隊(duì)

rear

0

1

2

3

4

front

(e)出隊(duì)多

次,

隊(duì)空

front==rear

rear

0

1

2

3

4

front

(e),隊(duì)滿

ABCDEfront==rear3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)---問(wèn)題二循環(huán)隊(duì)的入隊(duì)和出隊(duì)操作示意圖

rear

0

43

2

1

front

(a)空隊(duì)

(b)a,b,c入隊(duì)

0

4

3

2

1

front

c

b

ar0

4

3

2

1d

c

b

afront

(c)d入隊(duì),隊(duì)滿

reara隊(duì)滿：(rear+1)%MaxSize==front

怎樣區(qū)分隊(duì)空與隊(duì)滿之間的差別呢?在入隊(duì)時(shí)少用一個(gè)數(shù)據(jù)元素空間,以隊(duì)尾指針加1等于隊(duì)首指針判斷隊(duì)滿,即隊(duì)滿條件為:

(q->rear+1)%MaxSize==q->front隊(duì)空條件仍為:

q->rear==q->front假設(shè)以數(shù)組sq[0..7]存放循環(huán)隊(duì)列元素，變量f指向隊(duì)頭元素的前一個(gè)位置，變量r指向隊(duì)尾元素，如果用A和D分別表示入隊(duì)和出隊(duì)操作，請(qǐng)回答如下問(wèn)題：執(zhí)行操作訓(xùn)練A4D2A6時(shí)的狀態(tài).（A3表示三次入隊(duì)操作，D1表示一次出隊(duì)操作）A4r=4,f=0D2f=2,r=4A6溢出1.1通俗定義樹形表示法樹的括號(hào)表達(dá)式a(b(e,f,g),c(h),d(i,j))會(huì)根據(jù)括號(hào)表達(dá)式畫出樹形圖7.1.3樹的基本術(shù)語(yǔ)

1.樹的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素和指向其子樹的所有分支。

2.結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn),又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。4.樹的度：樹中所有結(jié)點(diǎn)的度的最大值max(D(I))。含義：樹中最大分支數(shù)為樹的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

樹形表示法

樹的度：3結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC樹的基本術(shù)語(yǔ) 5.7.2.1二叉樹概念二叉樹也稱為二次樹或二分樹，它是結(jié)點(diǎn)數(shù)為0或當(dāng)節(jié)點(diǎn)數(shù)不為0時(shí)每個(gè)結(jié)點(diǎn)最多只有左右兩棵子樹的樹。特點(diǎn)是：（1）每個(gè)結(jié)點(diǎn)最多只有兩棵樹，既不存在度大于2的結(jié)點(diǎn)。（2）子樹有左右之分，不能顛倒。思考：二叉樹和度為2的樹一樣嗎有什么區(qū)別？度為2的樹中至少有一個(gè)節(jié)點(diǎn)的度為2，而二叉樹沒(méi)有此要求。結(jié)點(diǎn)孩子的有序性：度為2的樹不區(qū)分左右樹，二叉樹嚴(yán)格區(qū)分。二叉樹的特點(diǎn)：⑴每個(gè)結(jié)點(diǎn)最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

7.2.1二叉樹的邏輯結(jié)構(gòu)注意：二叉樹和樹是兩種樹結(jié)構(gòu)。ABCDEFGABAB二叉樹的基本形態(tài)Ф空二叉樹只有一個(gè)根結(jié)點(diǎn)左子樹根結(jié)點(diǎn)只有左子樹右子樹根結(jié)點(diǎn)只有右子樹左子樹右子樹根結(jié)點(diǎn)同時(shí)有左右子樹二叉樹的邏輯結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。特殊的二叉樹斜樹1.所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；2.所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。

二叉樹的邏輯結(jié)構(gòu)---斜樹的特點(diǎn)：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。CDEFGHIJKLMNO1112131415特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---滿二叉樹?不是滿二叉樹，雖然所有分支結(jié)點(diǎn)都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---完全二叉樹對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點(diǎn)CDEFGHIJ特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---7.2.2二叉樹性質(zhì)（5個(gè)）

性質(zhì)1非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。

性質(zhì)2高度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)(h≥1)。證明：深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是二叉樹中每層結(jié)點(diǎn)的最大數(shù)之和，即=20+21+22+……+2h-1=2h-1(等比級(jí)數(shù)求和)

性質(zhì)3非空二叉樹上葉結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)加1。有如下關(guān)系：n0=n2+1

證明：設(shè)二叉樹上葉結(jié)點(diǎn)數(shù)為n0,單分支結(jié)點(diǎn)數(shù)為n1,雙分支結(jié)點(diǎn)數(shù)為n2,則總結(jié)點(diǎn)數(shù)n=n0+n1+n2。在一棵二叉樹中,度為i(i=0,1,2)的結(jié)點(diǎn)，有i個(gè)孩子。孩子數(shù)=n1+2n2。由于二叉樹中除根結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)都是另一個(gè)結(jié)點(diǎn)的孩子,因此二叉樹中有：孩子數(shù)=總結(jié)點(diǎn)數(shù)-1=n-1。由上述三個(gè)等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉樹

在一棵二叉樹中,如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn),并且葉結(jié)點(diǎn)都集中在二叉樹的最下一層,這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫?duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹根為1開(kāi)始,按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。每一層上結(jié)點(diǎn)樹都達(dá)到最大度為1的結(jié)點(diǎn)n1=0完全二叉樹:若二叉樹中度小于2的結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上,則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉樹中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿二叉樹相同。

性質(zhì)4具有n個(gè)(n＞0)結(jié)點(diǎn)的完全二叉樹的高（深）度為log2n+1。證明：設(shè)深度為H余下的性質(zhì)是針對(duì)完全二叉樹的：證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。

對(duì)不等式取對(duì)數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開(kāi)始按層序編號(hào)，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為

i/2；結(jié)點(diǎn)i的左孩子為2i；結(jié)點(diǎn)i的右孩子為2i＋1。

在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì)

思考題：二叉樹和樹的區(qū)別有哪些？7.8哈夫曼樹與哈夫曼編碼

哈夫曼(Huffman)樹，又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹。概念：兩結(jié)點(diǎn)間的路徑：從一結(jié)點(diǎn)到另一結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)序列。路徑長(zhǎng)度：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間路徑上的分支數(shù)。樹的路徑長(zhǎng)度：樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為。4123567結(jié)點(diǎn)1到5之間的路徑：（1）（2）（5）結(jié)點(diǎn)1到5之間的路徑長(zhǎng)度：2樹的路徑長(zhǎng)度：1+1+2+2+2+2=10定理：對(duì)于具有n個(gè)葉子節(jié)點(diǎn)的哈夫曼樹，共有2n-1個(gè)節(jié)點(diǎn)。樹的帶權(quán)路徑長(zhǎng)度WPL：設(shè)樹中有M個(gè)葉結(jié)點(diǎn)，每個(gè)葉結(jié)點(diǎn)帶一個(gè)權(quán)值WK，樹根到每一個(gè)葉結(jié)點(diǎn)K的路徑長(zhǎng)度為L(zhǎng)K則WPL=。哈夫曼樹：WPL最小的樹稱為最優(yōu)二叉樹，又稱哈夫曼樹7A5B4C2DWPL=7*2+5*2+4*2+2*2=36相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。

二叉樹的帶權(quán)路徑長(zhǎng)度：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。記為：WPL=7.8哈夫曼樹及哈夫曼編碼?=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長(zhǎng)度哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹。例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為{2，3，4，7}，可以構(gòu)造出形狀不同的多個(gè)二叉樹。

7.8哈夫曼樹及哈夫曼編碼WPL=32WPL=41WPL=30234723477423哈夫曼樹的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).

7.8哈夫曼樹及哈夫曼編碼2347WPL=32WPL=41WPL=3023477423哈夫曼樹的構(gòu)造過(guò)程

abcd2347(a)c4d7ab5(b)d7cab9(c)dcab16(d)哈夫曼算法基本思想：⑴初始化：由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷

重復(fù)⑵、⑶兩步，當(dāng)集合F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。

7.8哈夫曼樹及哈夫曼編碼W＝{2，3，4，5}

哈夫曼樹的構(gòu)造過(guò)程7.8哈夫曼樹及哈夫曼編碼重復(fù)第2步54325549重復(fù)第3步554932哈夫曼樹的構(gòu)造過(guò)程

例1：W={5,29,7,8,14,23,3,11}7.8哈夫曼樹及哈夫曼編碼前綴編碼：一組編碼中任一編碼都不是其它任何一個(gè)編碼的前綴。前綴編碼保證了在解碼時(shí)不會(huì)有多種可能。P196例7.15：一組字符{A,B,C,D,E,F,G,H}出現(xiàn)的頻率分別是{7,19,2,6,32,3,21}，設(shè)計(jì)最經(jīng)濟(jì)的編碼方案。答案參考教材哈夫曼樹應(yīng)用——哈夫曼編碼8.1圖的基本概念8.1.1圖的定義（多對(duì)多）

圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點(diǎn)的有限集合V(G),E是連接V中兩個(gè)不同頂點(diǎn)的邊的有限集合,記為E(G)。

1

3

0

2

4

(a)

8.1.2圖的基本概念和術(shù)語(yǔ)基本術(shù)語(yǔ)頂點(diǎn)：圖中數(shù)據(jù)元素?。ㄟ叄河邢驁D：由頂點(diǎn)和弧構(gòu)成的圖（圖a）無(wú)向圖：由頂點(diǎn)和邊構(gòu)成的圖（圖b）無(wú)向完全圖：無(wú)向圖有n(n-1)/2條邊(圖8.2a)有向完全圖:有向圖有n(n-1)個(gè)弧(圖8.2b)權(quán)：與圖的邊或弧相關(guān)的數(shù)值叫做權(quán)網(wǎng)：帶權(quán)的圖稱為網(wǎng)12453573841628.1.2圖的基本術(shù)語(yǔ)1.頂點(diǎn)的度、入度和出度在無(wú)向圖中,頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中,以頂點(diǎn)vi為終點(diǎn)的弧的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的弧的數(shù)目,稱為該頂點(diǎn)的出度。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。

圖的存儲(chǔ)方法很多，但是目標(biāo)是相同的。即不僅要存儲(chǔ)圖中各個(gè)頂點(diǎn)的數(shù)據(jù)信息，還要存儲(chǔ)頂點(diǎn)與頂點(diǎn)之間的關(guān)系（邊或弧）。兩種存儲(chǔ)方法：鄰接矩陣（數(shù)組存儲(chǔ)）鄰接表8.2圖的存儲(chǔ)結(jié)構(gòu)

8.2圖的存儲(chǔ)結(jié)構(gòu)

8.2.1鄰接矩陣存儲(chǔ)方法（教材P207) 鄰接矩陣是一個(gè)（n×n）階方陣，n為圖的頂點(diǎn)數(shù)，它的每一行分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)，它的每一列也分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)。我們規(guī)定矩陣的元素為：

無(wú)向圖的鄰接矩陣

DCBAAúúúú?ùêêêê?é=0111101111011110A

B

C

D

有向圖的鄰接矩陣8.2.2鄰接表存儲(chǔ)方法

圖的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法。在鄰接表中,對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表,對(duì)于無(wú)向圖鏈表中每個(gè)結(jié)點(diǎn)表示與該頂點(diǎn)相鄰接的一個(gè)頂點(diǎn)；對(duì)于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。

無(wú)向圖的鄰接表VA

B

C

D∧

A

B

D

∧

A

C

D

∧

A

B

C

∧

VBVCVD有向圖的鄰接表

AVBVCV

C

∧

B

C∧

B∧

8.3圖的遍歷8.3.1圖的遍歷的概念從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余結(jié)點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程稱為圖的遍歷圖的遍歷有兩種：深度優(yōu)先搜索廣度優(yōu)先搜索。深度優(yōu)先搜索過(guò)程：從圖中某個(gè)初始頂點(diǎn)v出發(fā)，首先訪問(wèn)初始頂點(diǎn)v，然后選擇一個(gè)與頂點(diǎn)v相鄰且沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)w為初始頂點(diǎn)，再?gòu)膚出發(fā)進(jìn)行深度優(yōu)先遍歷，直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問(wèn)過(guò)為止。遞歸調(diào)用

圖的深度優(yōu)先遍歷例子深度優(yōu)先遍歷序列：12485367深度優(yōu)先遍歷序列：12485367訪問(wèn)結(jié)點(diǎn)1訪問(wèn)結(jié)點(diǎn)2訪問(wèn)結(jié)點(diǎn)4訪問(wèn)結(jié)點(diǎn)8訪問(wèn)結(jié)點(diǎn)5訪問(wèn)結(jié)點(diǎn)3訪問(wèn)結(jié)點(diǎn)6訪問(wèn)結(jié)點(diǎn)7

例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設(shè)初始頂點(diǎn)編號(hào)v=2,寫出深度優(yōu)先遍歷序列。

圖的廣度優(yōu)先遍歷例子廣度優(yōu)先遍歷序列：12345678訪問(wèn)結(jié)點(diǎn)1訪問(wèn)結(jié)點(diǎn)2訪問(wèn)結(jié)點(diǎn)3訪問(wèn)結(jié)點(diǎn)4訪問(wèn)結(jié)點(diǎn)5訪問(wèn)結(jié)點(diǎn)6訪問(wèn)結(jié)點(diǎn)7訪問(wèn)結(jié)點(diǎn)8廣度優(yōu)先遍歷過(guò)程：首先訪問(wèn)初始頂點(diǎn)v，接著訪問(wèn)頂點(diǎn)v的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)v1，v2，v3..vt，然后在按照v1，v2，v3..vt的次序訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，以此類推，直到途中所有和初始頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。

一個(gè)有向圖的鄰接表深度優(yōu)先序列：13452廣度優(yōu)先序列：132458.3.3廣度優(yōu)先搜索遍歷

廣度優(yōu)先搜索遍歷的過(guò)程是：首先訪問(wèn)初始點(diǎn)vi,接著訪問(wèn)vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn),依次類推,直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。

1、已知一個(gè)有無(wú)向圖的鄰接矩陣P208圖8.5A1.根據(jù)無(wú)向圖的鄰接矩陣，寫出無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)。圖8.6(a).

根據(jù)無(wú)向圖的深度優(yōu)先遍歷算法，寫出從頂點(diǎn)v0出發(fā)所得到的頂點(diǎn)序列。(3)根據(jù)無(wú)向圖的廣度優(yōu)先遍歷算法，寫出從頂點(diǎn)v0出發(fā)所得到的頂點(diǎn)序列。2、給定某圖求其深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。8.4圖的應(yīng)用----生成樹和最小生成樹最小生成樹的概念可以應(yīng)用到許多實(shí)際問(wèn)題中。例：在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每?jī)蓚€(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最??？

應(yīng)用實(shí)例——計(jì)算機(jī)網(wǎng)絡(luò)傳輸?shù)膯?wèn)題：怎樣找到一種最經(jīng)濟(jì)的方式，從一臺(tái)計(jì)算機(jī)向網(wǎng)上所有其它計(jì)算機(jī)發(fā)送一條消息。8.4圖的應(yīng)用----生成樹和最小生成樹8.4.1生成樹的概念在一個(gè)無(wú)向連通圖G中，含有N個(gè)頂點(diǎn)（1）N個(gè)頂點(diǎn)（2）N-1條邊（3）無(wú)環(huán)路最小生成樹生成樹中，每個(gè)邊都有權(quán)值，權(quán)值總和最小的樹。8.4.2普里姆算法普里姆算法求解最小生成樹的過(guò)程

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

0

2

(b)

1

0

2

5

(c)

1

4

0

2

3

5

(d)

1

4

2

0

2

1

3

5

(e)

1

5

4

2

0

2

1

3

4

5

(f)

1

3

4

2

5

普里姆(prim)算法描述假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空。算法開(kāi)始時(shí)，首先從V中任取一個(gè)頂點(diǎn)（假定為V1），將此頂點(diǎn)并入U(xiǎn)中，此時(shí)最小生成樹頂點(diǎn)集U={V1}；然后從那些其一個(gè)端點(diǎn)已在U中，另一個(gè)端點(diǎn)仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪?，假定該邊為(Vi,Vj),其中Vi∈U，Vj∈V-U,并把該邊(Vi,Vj)和頂點(diǎn)Vj分別并入T的邊集TE和頂點(diǎn)集U；普里姆(prim)算法描述續(xù)如此進(jìn)行下去，每次往生成樹里并入一個(gè)頂點(diǎn)和一條邊，直到n-1次后，把所有n個(gè)頂點(diǎn)都并入生成樹T的頂點(diǎn)集U中，此時(shí)U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。普里姆算法中每次選取的邊兩端，總是一個(gè)已連通頂點(diǎn)（在U集合內(nèi)）和一個(gè)未連通頂點(diǎn)（在U集合外），故這個(gè)邊選取后一定能將未連通頂點(diǎn)連通而又保證不會(huì)形成環(huán)路?？唆斔箍査惴ㄇ蠼庾钚∩蓸涞倪^(guò)程4

1

0

2

1

3

4

5

(a)

1

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

0

2

1

3

4

5

(d)

1

4

2

(e)

0

2

1

3

4

5

1

3

4

2

5

2

2

3

3

0

0

3

5

4

1

0

03

3

1

1

0

0

3

3

1

1

0

0

0

0

1

1

1

1

1

1

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

8.4.3克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來(lái)構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T=(U,TE)是G的最小生成樹,則構(gòu)造最小生成樹的步驟如下：

(1)置U的初值等于V(即包含有G中的全部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。

(2)將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止。已知某帶權(quán)無(wú)向圖，用普里姆算法求其最小生成樹，寫出算法過(guò)程。粘圖？？

AOE網(wǎng)絡(luò)AOE網(wǎng)絡(luò)有向圖邊表示活動(dòng)(ActivityOnEdge)的網(wǎng)絡(luò)，簡(jiǎn)稱為AOE網(wǎng)絡(luò)頂點(diǎn)表示事件，弧表示事件完成的過(guò)程也就是活動(dòng)，弧上的權(quán)值表示完成該項(xiàng)活動(dòng)需要的時(shí)間。源點(diǎn)：入度為0，表示工程的開(kāi)始匯點(diǎn)：出度為0，表示工程的結(jié)束事件V:表示以它為弧頭的所有活動(dòng)已經(jīng)結(jié)束，也表示以它為弧尾的活動(dòng)可以開(kāi)始了。求關(guān)鍵路徑首先分別求出活動(dòng)的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間，然后利用兩者之差是否為0來(lái)確定關(guān)鍵活動(dòng)，因?yàn)榛顒?dòng)的最早發(fā)生時(shí)間與最晚發(fā)生時(shí)間為0就意味著該活動(dòng)的時(shí)間余量，時(shí)間余量為0的活動(dòng)為關(guān)鍵活動(dòng)。

例如,下圖表示某工程的AOE網(wǎng)。共有9個(gè)事件和11項(xiàng)活動(dòng)。其中A表示開(kāi)始事件,I表示結(jié)束事件。根據(jù)三元組畫出AOE網(wǎng)（1，2，3）a1（1，3，2）a2（2，4，2）a3（3，4，4）a5粘圖9.2順序查找structRecord{intkey;……};Recordr[n];

無(wú)監(jiān)視哨的順序查找:

intSeqSearch(Recordr[],intn,intk)

{

inti=0;

while(i<n&&r[i].key!=k)i++;

if(i<n)returni;

elsereturn-1;

}

順序查找的平均查找長(zhǎng)度為：順序查找的特點(diǎn)：算法簡(jiǎn)單，但查找效率低。9.3二分查找

二分查找又稱為折半查找。

二分查找要求順序表是有序的。二分查找的基本思想是：首先將待查的K值與有序表R[0]到R[n-1]的中間位置mid上的結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等，則查找完成；否則，若

R[mid].key>K，則說(shuō)明待查找的結(jié)點(diǎn)只可能在左子表R[0]到R[mid-1]中，只需在左子表中繼續(xù)查找；否則在右子表R[mid+1]到R[n-1]中繼續(xù)查找。這樣，經(jīng)過(guò)一次關(guān)鍵字的比較就縮小了一半的查找區(qū)間。如此進(jìn)行下去，直到找到為止（當(dāng)然也存在最后找不到的可能）。例:[0513192137566475808892][0513192137]566475808892051319[2137]566475808892查找K=21的過(guò)程（查找成功）[0513192137566475808892]051319213756[6475808892]051319213756647580[8892]查找K=85的過(guò)程（查找失?。?51319213756647580[8892]9.4Hash查找1.基本概念

Hash,哈希,也稱為散列.

Hash是一種重要的存儲(chǔ)方法，也是一種常見(jiàn)的查找方法。它的基本思想是：以數(shù)據(jù)元素的關(guān)鍵字K為自變量，通過(guò)一個(gè)確定的函數(shù)關(guān)系，計(jì)算出對(duì)應(yīng)的函數(shù)值f(K)，把這個(gè)值作為數(shù)據(jù)元素的存儲(chǔ)地址。查找時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置?！纠考僭O(shè)一組記錄的關(guān)鍵字分別為{18，27，1，20，22，6，10，13，41，15，25}。選取關(guān)鍵字與記錄位置間的函數(shù)為f(key)=key%11。Hash函數(shù)----關(guān)鍵字與記錄位置間的函數(shù).Hash地址----據(jù)Hash函數(shù)計(jì)算出的存儲(chǔ)位置.Hash表----存儲(chǔ)記錄的查找表,該表中根據(jù)Hash函數(shù)計(jì)算出的存儲(chǔ)位置.基于Hash表的查找稱為Hash查找。在建立Hash表時(shí)，若Hash函數(shù)是一個(gè)一對(duì)一的函數(shù)，則在查找時(shí)，只需根據(jù)散列函數(shù)對(duì)給定值進(jìn)行某種運(yùn)算，即可得到待查數(shù)據(jù)的存儲(chǔ)位置。在一般情況下，Hash表的空間必須比數(shù)據(jù)的集合大，此時(shí)雖然浪費(fèi)了一定的空間，但換取的是查找效率。設(shè)散列表的空間大小為m，填入表中的數(shù)據(jù)個(gè)數(shù)為n，則稱α=n/m為散列表的裝填因子。Hash函數(shù)的選取原則是：運(yùn)算盡可能簡(jiǎn)單；函數(shù)的值域必須在表長(zhǎng)的范圍內(nèi)；盡可能使得關(guān)鍵字不同時(shí)，其散列函數(shù)值亦不相同。若某個(gè)Hash函數(shù)對(duì)于不相等的關(guān)鍵字計(jì)算出了相同的

Hash地址，則稱該現(xiàn)象為hash沖突，發(fā)生沖突的兩個(gè)關(guān)鍵字該Hash函數(shù)的同義詞。在實(shí)際應(yīng)用中，不產(chǎn)生沖突的Hash函數(shù)極少存在。例9.9假設(shè)哈希表長(zhǎng)度m=13，采用除留余數(shù)法加線性探查法建立如下關(guān)鍵字集合的哈希表(16,74,60,43,54,90,46,31,29,88,77)并計(jì)算查找成功和查找不成功時(shí)候的平均查找長(zhǎng)度。提示：n=11(記錄個(gè)數(shù))m=13（表長(zhǎng)）h(key)=key%pp應(yīng)該為小于等于m素?cái)?shù)二叉排序樹特點(diǎn)、判斷什么樣的樹是二叉排序樹，P257二叉排序樹上的重要性質(zhì)。10.7堆排序堆排序是選擇排序的改進(jìn)（1964提出）。在排序過(guò)程中，將r[1]到r[n]看成是一個(gè)完全二叉樹順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小元素。堆的定義：n個(gè)數(shù)據(jù)序列K1,k2,...,Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：

此種情況稱為小頂堆。或者，均大于也可以。此種情況情況稱為大頂堆。從堆的定義可以看出，堆實(shí)質(zhì)上是滿足如下性質(zhì)的二叉樹：樹中任一非葉子結(jié)點(diǎn)的值均小于等于它的孩子結(jié)點(diǎn)的值。