數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)必背

第一章：緒論

:數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)是：討論數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及各

種操作的算法設(shè)計(jì)。

:數(shù)據(jù)：是客觀描述事物的數(shù)字、字符以及所有的能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)接

收的各種集合的統(tǒng)稱(chēng)。

數(shù)據(jù)元素：表示一個(gè)事物的一組數(shù)據(jù)稱(chēng)作是一個(gè)數(shù)據(jù)元素，是數(shù)據(jù)的基本單位。

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)元素中有獨(dú)立含義的、不可分割的最小標(biāo)識(shí)單位。

數(shù)據(jù)結(jié)構(gòu)概念包含三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)的操作。

數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系，用一個(gè)數(shù)據(jù)元素的集合定義在此集合上

的若干關(guān)系來(lái)表示，數(shù)據(jù)結(jié)構(gòu)可以分為三種：線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖。

:數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱(chēng)為物理結(jié)構(gòu)。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)基本形式有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

:算法：一個(gè)算法是一個(gè)有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類(lèi)型問(wèn)題

的操作序列。算法規(guī)則需滿(mǎn)足以下五個(gè)特性：

輸入——算法有零個(gè)或者多個(gè)輸入數(shù)據(jù)。

輸出——算法有一個(gè)或者多個(gè)輸出數(shù)據(jù)，與輸入數(shù)據(jù)有某種特定關(guān)系。

有窮性——算法必須在執(zhí)行又窮步之后結(jié)束。

確定性——算法的每一個(gè)步驟必須含義明確，無(wú)二義性。

可行性——算法的每步操作必須是基本的，它們的原則上都能夠精確地進(jìn)行，用筆和

紙做有窮次就可以完成。

有窮性和可行性是算法最重要的兩個(gè)特征。

:算法與數(shù)據(jù)結(jié)構(gòu)：算法建立數(shù)據(jù)結(jié)構(gòu)之上，對(duì)數(shù)據(jù)結(jié)構(gòu)的操作需用算法來(lái)描述。

算法設(shè)計(jì)依賴(lài)數(shù)據(jù)的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴(lài)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)。

:算法的設(shè)計(jì)應(yīng)滿(mǎn)足五個(gè)目標(biāo)：

正確性：算法應(yīng)切當(dāng)?shù)臐M(mǎn)足應(yīng)用問(wèn)題的需求，這是算法設(shè)計(jì)的基本目標(biāo)。

茁壯性：即使輸入數(shù)據(jù)不合適，算法也能做出適當(dāng)?shù)奶幚?，不?huì)導(dǎo)致不可控結(jié)

高時(shí)間效率：算法的執(zhí)行時(shí)間越短，時(shí)間效率越高。果。

高空間效率：算法執(zhí)行時(shí)占用的存儲(chǔ)空間越少，空間效率越高。

可讀性：算法的可讀性有利于人們對(duì)算法的理解。

：度量算法的時(shí)間效率，時(shí)間復(fù)雜度，(課本39頁(yè))。

：遞歸定義：即用一個(gè)概念本身直接或者間接地定義它自己。遞歸定義有兩個(gè)條件：

至少有一條初始定義是非遞歸的，如1!=1.

由已知函數(shù)值逐步遞推計(jì)算出未知函數(shù)值，如用(n-1)!定義n!。

第二章：線性表

線性表：線性表是由n(n>=0)個(gè)類(lèi)型相同的數(shù)據(jù)元素a0,a1,a2,…anT,組成的有限序

列，記作：LinearList=(aO,a1,a2,??,an-1)

其中，元素ai可以是整數(shù)、浮點(diǎn)數(shù)、字符、也可以是對(duì)象。n是線性表的元素個(gè)數(shù)，

成為線性表長(zhǎng)度。若n=0,則LinearList為空表。若n>0,則aO沒(méi)有前驅(qū)元素，an-1

沒(méi)有后繼元素，ai(0<i<n-1)有且僅有一個(gè)直接前驅(qū)元素ai-1和一個(gè)直接后繼元素

ai+1o

線性表的順序存儲(chǔ)是用一組連續(xù)的內(nèi)存單元挨次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存

的物理存儲(chǔ)次序與它們?cè)诰€性表中的邏輯次序相同。

線性表的數(shù)據(jù)元素?cái)?shù)據(jù)同一種數(shù)據(jù)類(lèi)型，設(shè)每一個(gè)元素占用c字節(jié)，aO的存儲(chǔ)地址

為L(zhǎng)oc(aO),則ai的存儲(chǔ)地址Loc(ai)為：Loc(ai)=Loc(aO)+i*c

數(shù)組是順序存儲(chǔ)的隨機(jī)存儲(chǔ)結(jié)構(gòu)，它占用一組連續(xù)的存儲(chǔ)單元，通過(guò)下標(biāo)識(shí)別元

素，元素地址是下標(biāo)的線性函數(shù)。

：順序表的插入和刪除操作要挪移數(shù)據(jù)元素。平均挪移次數(shù)是

屬數(shù)據(jù)表長(zhǎng)度的一半。(課本第50頁(yè))

：線性表的鏈?zhǔn)酱鎯?chǔ)是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)

元素在物理位置上不一定相鄰，必須采用附加信息表示數(shù)據(jù)元素之間的順序關(guān)系。

它有兩個(gè)域組成：數(shù)據(jù)域和地址域。通常成為節(jié)點(diǎn)。(課本第55頁(yè)及56頁(yè))

單鏈表(課本56頁(yè))

單鏈表的遍歷:Node<E>p=head;while(p!=nulI){訪問(wèn)p節(jié)點(diǎn)；p=;}

單鏈表的插入和刪除操作非常簡(jiǎn)便，只要改變節(jié)點(diǎn)間的鏈接關(guān)系，不需挪移數(shù)據(jù)元

素。

單鏈表的插入操作：1)：空表插入/頭插入2)中間插入/尾插入

if(head==null)Node<E>q=newNode<E>(x);

{head=newNode<E>(x);=;

}eIse{=q；

Node<E>q=newNode<E>(x);中間插入或者尾插入都不會(huì)改變單表

=head;的頭指針head。

head=q;

單鏈表的刪除操作:

頭刪除：head=;

中間/尾刪除：if!=nulI){=

循環(huán)單鏈表：如果單鏈表最后一個(gè)節(jié)點(diǎn)的next鏈保存單鏈表的頭指針head值，則該

單鏈表成為環(huán)形結(jié)構(gòu)，稱(chēng)為循環(huán)單鏈表。(課本67)

若rear是單鏈表的尾指針，則執(zhí)行(=head;)語(yǔ)句，使單鏈表成為一條循環(huán)單鏈表。

當(dāng)=卜62￡|時(shí)，循環(huán)單鏈表為空。

:雙鏈表結(jié)構(gòu)：雙鏈表的每一個(gè)結(jié)點(diǎn)有兩個(gè)鏈域，分別指向它的前驅(qū)和后繼結(jié)點(diǎn)，

當(dāng)=皿11時(shí)，雙鏈表為空。

設(shè)P指向雙鏈表中非兩端的某個(gè)結(jié)點(diǎn)，則成立下列關(guān)系：P=o

雙鏈表的插入和刪除：1)插入2)刪除

q=newDLinkNode(x)；=;

=;=p;if=nulI){

=q；=q；.prev=;}

循環(huán)雙鏈表：當(dāng)=*62~且=卜62￡1時(shí)，循環(huán)雙鏈表為空。

第三章：棧和隊(duì)列

棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進(jìn)行。允許

操作的一端稱(chēng)為棧頂，不允許操作的一端稱(chēng)為棧底。棧有順序棧和鏈?zhǔn)綏！?/p>

棧中插入元素的操作稱(chēng)為入棧，刪除元素的操作稱(chēng)為出棧。沒(méi)有元素的中稱(chēng)為空棧。

棧的進(jìn)出棧順序：后進(jìn)先出，先進(jìn)后出。(及75頁(yè)的思量題)。

:隊(duì)列：隊(duì)列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進(jìn)行。

向隊(duì)列中插入元素的過(guò)程稱(chēng)為入隊(duì)，刪除元素的過(guò)程稱(chēng)為出對(duì)，允許入隊(duì)的一端稱(chēng)為

隊(duì)尾，允許出隊(duì)的一端稱(chēng)為對(duì)頭。沒(méi)有元素的隊(duì)列稱(chēng)為空隊(duì)列。隊(duì)列是先進(jìn)先出。

第四章：串

：串是一種特殊的線性表，其特殊性在于線性表中的每一個(gè)元素是一個(gè)字符。一個(gè)串

記

為：s="s0s1s2…sn-1”其中n>=0,s是串名，一對(duì)雙引號(hào)括起來(lái)的字符序列

s0s1s2-sn-1是串值，si(i=0,1,2,…n-1)為特定字符集合中的一個(gè)字符。一個(gè)

串中包含的字符個(gè)數(shù)稱(chēng)為串的長(zhǎng)度。

長(zhǎng)度為0的串稱(chēng)為空串，記作“”，而由一個(gè)或者多個(gè)空格字符構(gòu)成的字符串稱(chēng)為空

格

串。

子串：由串S中任意連續(xù)字符組成的一個(gè)子序列sub稱(chēng)為S的子串，S稱(chēng)為sub的主

串。子串的序號(hào)是指該子串的第一個(gè)字符在主串中的序號(hào)。

串比較：兩個(gè)串可比較是否相等，也可比較大小。兩個(gè)串(子串)相等的充要條件是

兩個(gè)串(子串)的長(zhǎng)度相同，并且各對(duì)應(yīng)位置上的字符也相同。

兩個(gè)串的大小由對(duì)應(yīng)位置的第一個(gè)不同字符的大小決定，字符比較次序是從頭開(kāi)始依

次向后。當(dāng)兩個(gè)串長(zhǎng)度不等而對(duì)應(yīng)位置的字符都相同時(shí)，較長(zhǎng)的串定義為較“大”。

第五章：數(shù)組和廣義表

:數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素具有相同的數(shù)據(jù)類(lèi)型。一維數(shù)組的邏輯結(jié)構(gòu)是線性

表，多維數(shù)組是線性表的擴(kuò)展。

:一維數(shù)組：一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)。一個(gè)一維數(shù)組占用一組連續(xù)的存儲(chǔ)單元。

度數(shù)組第一個(gè)元素aO的存儲(chǔ)地址為L(zhǎng)oc(aO),每一個(gè)元素占用c字節(jié)，則數(shù)組其他

元

素ai的存儲(chǔ)地址Loc(ai)為：Loc(ai)=Loc(aO)+i*c

數(shù)組通過(guò)下標(biāo)識(shí)別元素，元素地址是下標(biāo)的線性函數(shù)。一個(gè)下標(biāo)能夠惟一確定一個(gè)元

素，所劃給的時(shí)間是0(1)。因此數(shù)組是隨機(jī)存取結(jié)構(gòu)，這是數(shù)組最大的優(yōu)點(diǎn)。

：多維數(shù)組的遍歷：有兩種次序：行主序和列主序。

行主序：以行為主序，按行遞增訪問(wèn)數(shù)組元素，訪問(wèn)完第i行的所有元素之后再訪問(wèn)

第i+1行的元素，同一行上按列遞增訪問(wèn)數(shù)組元素。

aOO,aO1,,?,aO(n-1),a10,a11,,■■al(n-1),,■,a(m-1)0,a(nr-1)1,,,,,a(m-1)(n-1)

2)列主序：以列為主序，按列遞增訪問(wèn)數(shù)組元素，訪問(wèn)完第j列的所有元素之后

再訪問(wèn)第j+1列的元素，同一列上按列遞增訪問(wèn)數(shù)組元素。

多維數(shù)組的存儲(chǔ)結(jié)構(gòu)：多維數(shù)組也是由多個(gè)一維數(shù)組組合而成，組合方式有一下兩

種。

靜態(tài)多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)：可按行主序和列主序進(jìn)行順序存儲(chǔ)。

按行主序存儲(chǔ)時(shí)，元素aij的地址為：Loc(aij)=Loc(aOO)+(i*n+j)*c

按列主序存儲(chǔ)時(shí)，Loc(aij)=Loc(aOO)+(j*m+i)*c

動(dòng)態(tài)多維數(shù)組的存儲(chǔ)結(jié)構(gòu)。

二維數(shù)組元素地址就是兩個(gè)下標(biāo)的線性函數(shù)。無(wú)論采用哪種存儲(chǔ)結(jié)構(gòu)，多維數(shù)組都

是基于一維數(shù)組的，因此也只能進(jìn)行賦值、取值兩種存取操作，不能進(jìn)行插入，刪除

操作。

第六章：

樹(shù)是數(shù)據(jù)元素(結(jié)點(diǎn))之間具有層次關(guān)系的非線性結(jié)構(gòu)。在樹(shù)結(jié)構(gòu)中，除根以外的結(jié)

點(diǎn)惟獨(dú)一個(gè)直接前驅(qū)結(jié)點(diǎn)，可以有零至多個(gè)直接后繼結(jié)點(diǎn)。根沒(méi)有前驅(qū)結(jié)點(diǎn)。

樹(shù)是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合(樹(shù)中元素通常稱(chēng)為結(jié)點(diǎn))。N=0的樹(shù)稱(chēng)為空

樹(shù)；nX)大的樹(shù)T；

@有一個(gè)特殊的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，它惟獨(dú)后繼結(jié)點(diǎn)，沒(méi)有前驅(qū)結(jié)點(diǎn)。

@除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m(m>=0)個(gè)互不相交的集合TO,T1,13……..,Tm-1,

其中每一個(gè)集合Ti(0Vi<m)本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)。

樹(shù)是遞歸定義的。結(jié)點(diǎn)是樹(shù)大的基本單位，若干個(gè)結(jié)點(diǎn)組成一棵子樹(shù)，若干棵互不相

交的子樹(shù)組成一棵樹(shù)。樹(shù)的每一個(gè)結(jié)點(diǎn)都是該樹(shù)中某一棵子樹(shù)的根。因此，樹(shù)是由結(jié)

點(diǎn)組成的、結(jié)點(diǎn)之間具有層次關(guān)系大的非線性結(jié)構(gòu)。

結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱(chēng)為其父母結(jié)點(diǎn)，反之，結(jié)點(diǎn)大的后繼結(jié)點(diǎn)稱(chēng)為其孩子結(jié)點(diǎn)。一棵樹(shù)

中，惟獨(dú)根結(jié)點(diǎn)沒(méi)有父母結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個(gè)父母結(jié)點(diǎn)。

擁有同一個(gè)父母結(jié)點(diǎn)的多個(gè)結(jié)點(diǎn)之間稱(chēng)為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的祖先是指從根結(jié)點(diǎn)到其父

母結(jié)點(diǎn)所經(jīng)過(guò)大的所有結(jié)點(diǎn)。結(jié)點(diǎn)的后代是指該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，以及孩子的孩

子等。

結(jié)點(diǎn)的度是結(jié)點(diǎn)所擁有子樹(shù)的棵數(shù)。度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)，又叫終端結(jié)點(diǎn)；樹(shù)

中除葉子結(jié)點(diǎn)之外的其他結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)，又叫非葉子結(jié)點(diǎn)或者非終端結(jié)點(diǎn)。樹(shù)的

度是指樹(shù)中各結(jié)點(diǎn)度的最大值。

結(jié)點(diǎn)的層次屬性反應(yīng)結(jié)點(diǎn)處于樹(shù)中的層次位置。約定根結(jié)點(diǎn)的層次為1,其他結(jié)點(diǎn)的層

次是其父母結(jié)點(diǎn)的層次加1o顯然，兄弟結(jié)點(diǎn)的層次相同。

樹(shù)的高度或者深度是樹(shù)中結(jié)點(diǎn)的最大層次樹(shù)。

設(shè)樹(shù)中x結(jié)點(diǎn)是y結(jié)點(diǎn)的父母結(jié)點(diǎn)，有序?qū)?x,y)稱(chēng)為連接這兩個(gè)結(jié)點(diǎn)的分支，也

稱(chēng)為邊。

設(shè)(X0,X1,….，Xk-1)是由樹(shù)中結(jié)點(diǎn)組成的一個(gè)序列,且(Xi,Xi+1)(0<=i<k-1)

都是樹(shù)中的邊，則該序列稱(chēng)為從X0到Xk-1的一條路徑。路徑長(zhǎng)度為路徑上的邊數(shù)。

在樹(shù)的定義中，結(jié)點(diǎn)的子樹(shù)TO,T1-之間沒(méi)有次序，可以交換位置，稱(chēng)為無(wú)

序樹(shù)，簡(jiǎn)稱(chēng)樹(shù)。如果結(jié)點(diǎn)的子樹(shù)TO,T1……,TnH從左到右是有次序的，不能交換位

置，則稱(chēng)該樹(shù)為有序樹(shù)。

森林是m(m>=0)棵互不相干的樹(shù)的集合。給森林加之一個(gè)根結(jié)點(diǎn)就變成一棵樹(shù)，將樹(shù)

的根節(jié)點(diǎn)刪除就變成森林。

二叉樹(shù)的性質(zhì)1：若根結(jié)點(diǎn)的層次為1,則二叉樹(shù)第i層最多有2的i-1次方

(i>=1)個(gè)結(jié)點(diǎn)。

二叉樹(shù)的性質(zhì)2：在高度為k的二叉樹(shù)中，最多有2的k次方減一個(gè)結(jié)點(diǎn)。

二叉樹(shù)的性質(zhì)3：設(shè)一棵二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為n0,2度結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。

一棵高度為k的滿(mǎn)二叉樹(shù)是具有2的k次方減一個(gè)結(jié)點(diǎn)的二叉樹(shù)。滿(mǎn)二叉樹(shù)中每一層

的結(jié)點(diǎn)數(shù)目都達(dá)到最大值。對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定根節(jié)點(diǎn)的序號(hào)為0,

從根節(jié)點(diǎn)開(kāi)始，自上而下，每層自左至右編號(hào)。

一棵具有n個(gè)結(jié)點(diǎn)高度為k的二叉樹(shù)，如果他的每一個(gè)節(jié)點(diǎn)都與高度為k的滿(mǎn)二叉樹(shù)

中序號(hào)為0~n-1

的結(jié)點(diǎn)一一對(duì)應(yīng)，則這棵二叉樹(shù)為為徹底二叉樹(shù)。

滿(mǎn)二叉樹(shù)是徹底二叉樹(shù)，而徹底二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。徹底二叉樹(shù)的第廣廣1層

是滿(mǎn)二叉樹(shù)第k層不滿(mǎn)，并且該層所有結(jié)點(diǎn)必須集中在該層左邊的若干位置上。

二叉樹(shù)的性質(zhì)4：一棵具有n個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)，其高度k=log2n的絕對(duì)值+1

二叉樹(shù)的性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)，對(duì)序號(hào)為i的結(jié)點(diǎn)，有

@若i=0,則i為根節(jié)點(diǎn)，無(wú)父母結(jié)點(diǎn)；若i>0,則i的父母結(jié)點(diǎn)的序號(hào)為[(iT)

/2]o

@若21+13,貝I]i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無(wú)左孩子。

蜻2i+2<n,則i的右孩子結(jié)點(diǎn)的序號(hào)為2i+2,否則i無(wú)右孩子。

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷是按照一定規(guī)則和次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，并且每一個(gè)結(jié)點(diǎn)僅被

訪問(wèn)一次。

二叉樹(shù)的三種次序遍歷

1：先根次序；訪問(wèn)根節(jié)點(diǎn)，遍歷左子樹(shù)，遍歷右子樹(shù)。

2：中根次序；遍歷左子樹(shù)，訪問(wèn)右子樹(shù)，遍歷右子樹(shù)。

3：后根次序；遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)根節(jié)點(diǎn)。

先根次序遍歷時(shí)，最先訪問(wèn)根節(jié)點(diǎn)；后根次序遍歷時(shí)，最后訪問(wèn)根節(jié)點(diǎn)；中根次序遍

歷時(shí)，左子樹(shù)上的結(jié)點(diǎn)在根節(jié)點(diǎn)之前訪問(wèn)，右子樹(shù)上的結(jié)點(diǎn)在根節(jié)點(diǎn)之后訪問(wèn)。

二叉樹(shù)的插入和刪除操作P147

二叉樹(shù)的層次遍歷P149

習(xí)題P1676—10,6—19

第七章

圖是由定點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)關(guān)邊系。頂點(diǎn)之間的關(guān)系成為

邊。一個(gè)圖G記為G=(V,E),V是頂點(diǎn)A的有限集合，E是邊的有限集合。即

V={A|A屬于某個(gè)數(shù)據(jù)元素集合}

E={(A,B)|A,B屬于V}或者E={<A,B>|A,B屬于V且Path(A,B)}其中Path(A,B)表

示從頂點(diǎn)A到B的一條單向通路，即Path(A,B)是有方向的。

無(wú)向圖中的邊事沒(méi)有方向，每條邊用兩個(gè)頂點(diǎn)的無(wú)序?qū)Ρ硎尽?/p>

有向圖中的邊是有方向，每條邊用兩個(gè)頂點(diǎn)的有序?qū)Ρ硎尽?/p>

徹底圖指圖的邊數(shù)達(dá)到最大值。n個(gè)頂點(diǎn)的徹底圖記為Kn。無(wú)向徹底圖Kn的邊數(shù)為n*

(n-1)/2,有向徹底圖Kn的邊數(shù)為n*(n-1)o

子圖：設(shè)圖G=(V,E),G'=(V',E'),若V'包含于V且E'包含于E,則稱(chēng)圖G'是G

的子圖。若G'是G的真子圖。

連通圖：在無(wú)向圖G中，若從頂點(diǎn)VI到Vj有路徑，則稱(chēng)Vi和Vj是聯(lián)通的。若圖G

中任意一對(duì)頂點(diǎn)Vi和Vj(Vi不等于Vj)都是聯(lián)通的，則稱(chēng)G為連通圖。非連通圖的

極大聯(lián)通子圖稱(chēng)為該圖的聯(lián)通分量。

強(qiáng)連通圖：在有向圖中，若在每一對(duì)頂點(diǎn)Vi和Vj(Vi不等于Vj)之間都存在一條從

Vi至UVj的路徑，也存在一條從Vi至ljVj的路徑，也存在一條從Vi至ljVj的路徑，則稱(chēng)

該圖的強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱(chēng)為該圖的強(qiáng)連通圖分量。

圖的遍歷

遍歷圖是指從圖G中任意一個(gè)頂點(diǎn)V出發(fā)，沿著圖中的邊前行，到達(dá)并訪問(wèn)圖中的所

有頂點(diǎn)，且每一個(gè)頂點(diǎn)僅被訪問(wèn)一次。遍歷圖要考慮一下三個(gè)問(wèn)題：

@指定遍歷的第一個(gè)訪問(wèn)頂點(diǎn)

@由于一個(gè)頂點(diǎn)可能與多個(gè)頂點(diǎn)相鄰，因此要在多個(gè)鄰接頂點(diǎn)之間約定一種訪問(wèn)次序。

@由于圖中可能存在回路，在訪問(wèn)某個(gè)頂點(diǎn)之后，可能沿著某條路徑又回到該頂點(diǎn)。

深度優(yōu)先搜索

圖的深度優(yōu)先搜索策略是，訪問(wèn)某個(gè)頂點(diǎn)v,接著尋覓v的另一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)

w訪問(wèn)，如此反復(fù)執(zhí)行，走過(guò)一條較長(zhǎng)路徑到達(dá)最遠(yuǎn)頂點(diǎn)；若頂點(diǎn)v沒(méi)有未被訪問(wèn)的其

他鄰接頂點(diǎn)，則回到前一個(gè)被訪問(wèn)頂點(diǎn)，再尋覓其他訪問(wèn)路徑。

圖的深度優(yōu)先搜索遍歷算法P188

聯(lián)通的無(wú)回路的無(wú)向圖，簡(jiǎn)稱(chēng)樹(shù)。樹(shù)中的懸掛點(diǎn)又成為樹(shù)葉，其他頂點(diǎn)稱(chēng)為分支點(diǎn)。

各連通分量均為樹(shù)的圖稱(chēng)為森林，樹(shù)是森林。

由于樹(shù)中無(wú)回路，因此樹(shù)中必然無(wú)自身環(huán)也無(wú)重邊（否則他有回路）若去掉樹(shù)中的任

意一條邊，則變成森林，成為非聯(lián)通圖；若給樹(shù)加之一條邊，形成圖中的一條回路，

則不是樹(shù)。P191

生成樹(shù)和生成森林：

一個(gè)連通無(wú)向圖的生成樹(shù)是該圖的一個(gè)極小聯(lián)通生成子圖，它包含原圖中所有頂點(diǎn)（n

個(gè)）以及足以構(gòu)成一棵樹(shù)的n-1條邊。

一個(gè)非聯(lián)通的無(wú)向圖，其各連通圖分量的生成圖組成該圖的生成森林。

圖的生成圖或者生成森林不是惟一的，從不同頂點(diǎn)開(kāi)始、采用不同遍歷可以得到不同

的生成樹(shù)或者森林。

在生成樹(shù)中，任何樹(shù)中，任何兩個(gè)頂點(diǎn)之間惟獨(dú)惟一的一條路徑。

第八章

折半查找算法描述P206,P207

二叉排序樹(shù)及其查找：

二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：

@每一個(gè)結(jié)點(diǎn)都有一個(gè)作為查找依據(jù)的關(guān)鍵字，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。

@若一個(gè)結(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于這個(gè)節(jié)點(diǎn)的關(guān)鍵字；

@每一個(gè)結(jié)點(diǎn)的擺布子樹(shù)也分別為二叉排序樹(shù)。

在一棵二叉排序樹(shù)中，查找值為value的結(jié)點(diǎn)，算法描述如下：

@從根結(jié)點(diǎn)開(kāi)始，設(shè)P指向根結(jié)點(diǎn)

Rvalue與p結(jié)