數(shù)據(jù)結(jié)構(gòu)知識點-3

第一課緒論

覆蓋的知識點最小集：我們的地址是，重慶市九龍坡區(qū)白市驛鎮(zhèn)金橋2號重慶市農(nóng)業(yè)學校

1.數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)的概念

2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的概念

3.算法設計時的注意事項

4.時間復雜度的概念及度量方法

5.空間復雜度的概念及度量方法

知識點細化：

1-001數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學

科。數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的操作三部分組成。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素

的集合，是數(shù)據(jù)的子集。數(shù)據(jù)是所有需輸入計算機并為程序所處理的對象的總稱。

1-002數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，對后面的名詞要能區(qū)分哪些是屬于邏輯結(jié)構(gòu)哪些屬于物理結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素間的邏輯關系，分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)，或分為

線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)元素及其間邏輯關系在計算機中的表示，也稱存儲結(jié)構(gòu)。其中數(shù)據(jù)元素間

關系的表示有順序映象(順序存儲結(jié)構(gòu))和非順序映象(鏈式存儲結(jié)構(gòu))兩種方式，前者以存儲地址上的

聯(lián)系來體現(xiàn)數(shù)據(jù)元素之間的邏輯關系，后者則通過指針的指向來體現(xiàn)數(shù)據(jù)元素之間的邏輯關系。

1-003算法設計時的注意事項

算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法的特性：有窮性、確定性、可行性、

零或多個輸入、一或多個輸出。算法設計的要求：正確性、可讀性、健壯性、高效性。

1-004時間復雜度的概念及度量方法

算法的時間復雜度是算法執(zhí)行效率的量度，記作：T(n)=O(f(n)),其中n為問題的規(guī)模。

衡量算法效率時，通常在算法中選擇一種不可再分解的基本操作(該操作的重復執(zhí)行次數(shù)應與算法的

執(zhí)行時間成正比)，若該操作的執(zhí)行次數(shù)為f(n),則記該算法的時間復雜度為O(f(n))。

若基本操作的執(zhí)行次數(shù)與輸入數(shù)據(jù)有關，則可求算法的平均時間復雜度或最壞時間復雜度。一般，當

所有可能的輸入數(shù)據(jù)集及其出現(xiàn)概率均可知時，可求算法的平均時間復雜度，否則求最壞情況下的時間復

雜度。

1-005空間復雜度的概念及度量方法

算法的空間復雜度是算法執(zhí)行時所需存儲空間的量度，記作：S(n)=O(f(n)),其中n為問題的規(guī)模。

分析算法空間復雜度時，一般只考慮執(zhí)行算法所需輔助空間，但若輸入數(shù)據(jù)所占空間與算法本身有關,

則也應計算在內(nèi)。若執(zhí)行算法所需輔助空間與輸入數(shù)據(jù)有關，則可求最壞情況下的空間復雜度。

第二課線性表

覆蓋的知識點最小集：

1.線性表的定義和基本操作

2.線性表的實現(xiàn)

(1)順序存儲

⑵鏈式存儲

(3)線性表的應用

知識點細化：

2-010線性表基本概念

線性表是n個數(shù)據(jù)元素構(gòu)成的有限序列。表長指線性表中數(shù)據(jù)元素的個數(shù)，表長20。空表指表長為

0的線性表。若線性表非空，則表中第一個元素沒有直接前趨，有且僅有一個直接后繼；表中最后一個元

素沒有直接后繼，有且僅有一個直接前趨；其余每個數(shù)據(jù)元素有且僅有一個直接前趨，有且僅有一個直接

后繼。

2-011線性表的基本操作

(1)取元素

GetElem(L,i,&e)

初始條件：線性表L已存在，iWiWListLength(L)

操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值

(2)插入

Li>tInsert(&L,i,e)

初始條件：線性表L已存在，1WiWListLength(L)+l

操作結(jié)果：在L中第i個位置之前插入數(shù)據(jù)元素e,L的長度加1

(3)刪除

LiitDelete(&L,i,&e)

初始條件：線性表L已存在且非空，iWiWLislLength(L)

操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1

2-012線性表的順序存儲方式

用一組地址連續(xù)的存儲單元依次存儲線性表中數(shù)據(jù)元素，以數(shù)據(jù)元素物理地址上的相鄰關系表示其邏

輯上的先后關系。以順序存儲方式保存的線性表也稱順序表。

在順序表中訪問結(jié)點時，由丁第一個元素就存儲在相對地址為i-1的位置上(隨機存取)，算法時間復:

雜度為。⑴。

設順序表長為n,則在第i(lWiWn+1)個元素前插入時，需移動n-i+1個元素。設在各位置上插入元

素的概率相等，則需移動元素的平均個數(shù)為n/2,算法時間復雜度為O(n)。

設順序表長為n,則刪除第i(iWiWn)個數(shù)據(jù)元素時，需移動n-i個元素。設刪除任一元素的概率相

等，則需移動元素的平均個數(shù)為：(n-l)/2,算法時間復雜度為O(n)。

2-013以靜態(tài)分配方法實現(xiàn)順序表

由于線性表的長度是可變的，采用靜態(tài)分配，則需定義最大可能長度，并需設變量記錄線性表長。

#defineMAXSIZE1000〃最大可能長度

typedefstruct(

ElemTypeelem[MAXSIZE];〃保存數(shù)據(jù)元素

intlen;〃線性表長度

JSqList;〃順序表類型名(靜態(tài)線性表就是用數(shù)組來存儲的那種形式)

2-014以一次性動態(tài)分配方法實現(xiàn)順序表

采用一次性的動態(tài)分配方法時，需定義最大可能長度，并需設變量記錄線性表長。

#defineMAXSIZE1000〃最大可能長度

typedcfstruct{

ElemType*elem;//保存首地址

intlen;〃線性表長度

ISqList;〃順序表類型名（動態(tài)的就是需要用指針來實現(xiàn)的）

2-015以帶增量的動態(tài)分配方法實現(xiàn)順序表

采用帶增量的動態(tài)分配方法時，需定義初始分配量和增量，并需分別設變量以記錄線性表長及當前分

配總量。

#defineLISTJNIT_SIZE100//初始分配量，以數(shù)據(jù)元素個數(shù)為單位

#defineLISTINCREMENT10〃增量

typedefstruct）

ElemType*elem;//保存首地址

intlen;〃線性表長度

intlistsize;〃當前分配量，以數(shù)據(jù)元素個數(shù)為單位

JSqList;〃順序表類型名

在該結(jié)構(gòu)上實現(xiàn)三個基本操作。

2?016線性表的鏈式存儲方式

用一組任意的（可連續(xù)可不連續(xù)）存儲單元存儲線性表中數(shù)據(jù)元素，用指針來表示數(shù)據(jù)元素間的邏輯

關系。根據(jù)所用指針的類型、個數(shù)、方法等的不同，又可分為：、循環(huán)鏈表、雙向線性鏈表（單鏈表）鏈

表、雙向循環(huán)鏈表、靜態(tài)鏈表等。

2?017線性鏈表（單鏈表）及其特點

每個結(jié)點由兩個域組成，其中數(shù)據(jù)域用以保存數(shù)據(jù)元素的值，指針域用以保存其直接后繼結(jié)點的絕對

地址。表中最后一個結(jié)點的指針域值為空指針NULL。在首元結(jié)點前還可附設頭結(jié)點，以方便運算的實現(xiàn)

（無論表空與否，頭指針值不變；插入時不必特別判斷是否在第一個元素之前插入：刪除時不必特別判斷

是否刪除第一個元素）。頭結(jié)點的數(shù)據(jù)域一般不使用。頭結(jié)點（若表中不含頭結(jié)點則為首元結(jié)點）的地址

保存在頭指針中。

typedefstructLNode!

ElemTypedata;〃數(shù)據(jù)域

slruclLNodc*ncxl;〃指針域

）LNode,*LinkList;

在該結(jié)構(gòu)上實現(xiàn)三個基本操作。

在單鏈表中訪問結(jié)點時，必須從頭指針開始順序查找該結(jié)點，指針的移動是其中的基本操作，查找第

i個結(jié)點時需移動i-1次。設查找任一元素的概率相等，則需移動指針的平均次數(shù)為（n-l）/2,算法時間復雜

度為0（n）。

在單鏈表中插入結(jié)點時，時間主要用于查找插入位置，即查找第i-1個結(jié)點上。算法的時間復雜度為

O（n）o

在單鏈表中刪除結(jié)點時，時間主要用于查找待刪結(jié)點。算法的時間復雜度為O（n）。

2.018循環(huán)鏈表及其特點

循環(huán)鏈表的結(jié)點結(jié)構(gòu)同單鏈表，但表中最后一個結(jié)點的指針域保存頭結(jié)點（若表中不含頭結(jié)點則為首

元結(jié)點）的絕對地址。在循環(huán)鏈表中，從任一結(jié)點出發(fā)均可訪問到表中其余結(jié)點。

循環(huán)鏈表上基本操作的實現(xiàn)與單鏈表基本相同，主要區(qū)別在于算法中的循環(huán)條件。

2.019雙向鏈表及其特點

2-024線性表的應用

基于線性表的各種存儲方式實現(xiàn)指定的操作，尤其是各種鏈表（帶頭結(jié)點、不帶頭結(jié)點）（僅設頭指

針、僅設尾指針、分設頭尾指針）上插入（當前結(jié)點之前，當前結(jié)點之后，頭結(jié)點之后，尾結(jié)點之后，其

它位置），刪除（當前結(jié)點、前趨結(jié)點、后繼結(jié)點、首元結(jié)點、具它結(jié)點），分解（一表到多表），歸并（多

表合一表），查找（順序表上的順序和折半查找，鏈表上的順序查找）、排序（各種排序方法的實現(xiàn)）等。

第三課棧、隊列和數(shù)組

覆蓋的知識點最小集：

1.棧和隊列的基本概念

2.棧和隊列的順序存儲結(jié)構(gòu)

3.棧和隊列的鏈式存儲結(jié)構(gòu)

4.棧和隊列的應用

5.特殊矩陣的壓縮存儲

知識點細化：

3-001棧的基本概念

棧是限定僅在表尾端進行插入、刪除的線性表；表尾端稱棧頂，而稱棧頂元素；表頭端稱棧底，ai稱

棧底元素。棧的長度即棧中元素個數(shù)。長度為0的棧稱空棧。向棧中插入元素稱入棧，從棧中刪除元素稱

出棧,棧的修改是按后進先出的原則進行的。

3-002棧的順序存儲方式

與線性表的順序存儲方式類似：三種分配方法；線性表長度分量一棧頂指針分量（指向棧頂元素的下

一個位置）。以順序存儲方式保存的棧稱順序棧。

設采用靜態(tài)分配。實現(xiàn)入棧和出棧操作。

#defineMAXSIZE1000〃棧的最人容量

typedefstruct（

ElemTypeelem[MAXSIZE];〃保存數(shù)據(jù)元素，以低地址為棧底

inttop;〃棧頂指針

JSqStack;

3?003棧的鏈式存儲方式

與單鏈表類似：帶/不帶頭結(jié)點；插入、刪除操作點（即棧頂端）放在靠近頭指針的一端。以鏈式存儲

方式保存的棧稱鏈棧。

實現(xiàn)入棧和出棧操作

typedefstructSNode（

ElemTypedata;

structSNodc*next;

}SNode,*LinkStack;

3-101隊列的基本概念

隊列是限定僅在表尾端進行插入，而在表頭端進行刪除的線性表。表頭端稱隊頭，a1稱隊頭元素；表

尾端稱隊尾，“稱隊尾元素。隊列的長度即隊列中元素個數(shù)。長度為。的隊列稱空隊。向隊列中插入元素

稱入隊，從隊列中刪除元素稱出隊。隊列的修改是按先進先出的原則進行的。

雙端隊列是限定僅在表的兩端進行插入刪除操作的線性表（如果規(guī)定從哪端入的只能從哪端出，則退

化為兩個棧底相鄰的棧）。輸入受限的雙端隊列是插入操作僅在一端進行而刪除操作可在兩端進行的線性

表。輸出受限的雙端隊列是刪除操作僅在--端進行而插入操作可在兩端進行的線性表。

3-102隊列的順序存儲方式

線性表的順序存儲方式f去除線性表長度分量，添加指向隊頭元素所在位置的隊頭指針以及指向隊尾

元素的下一個位置的隊尾指針一產(chǎn)生假溢出問題f三個解決方案：（1）每刪一個元素，其余元素向前移；（2）

發(fā)生假溢出時才移動剩余元素；（3）采用循環(huán)隊列，不移動元素，但不能采用帶增量的動態(tài)分配，且需解決

隊空、隊滿判定條件相同的問題，解決方法可為：①添加長度分量（添加標志分量）②浪費一個元素的存

儲空間。

循環(huán)隊列另一設計方案：以數(shù)組存儲元素，以隊尾指針指示隊尾元素所在位置，并記錄隊列長度。

循環(huán)隊列只能采用靜態(tài)分配或一次性動態(tài)分配，不能采用帶增量的動態(tài)分配，因而隊列最大長度應能

預估。

3-103循環(huán)隊列的入隊和出隊

設采用一次性動態(tài)分配，設置隊頭隊尾指針，以浪費一個元素存儲空間的方式解決隊空、隊滿判定條

件相同的問題。

實現(xiàn)入隊、出隊和求隊列長度操作。

#defineMAXSIZE1000

typedefstruct{

ElemType*base;

intfront;

intrear;

JCirQueue;

3-104隊列的鏈式存儲方式

與單鏈表類似：帶/不帶頭結(jié)點；刪除操作點（即隊頭端）放在靠近頭指針的一端，另設尾指針，指向

隊尾元素結(jié)點，以方便插入操作的執(zhí)行。以鏈式存儲方式保存的隊列稱鏈隊列。

鏈隊列在執(zhí)行出隊操作時要考慮空隊列和隊列中只有一個結(jié)點這兩種特殊情況。

3405鏈隊列的入隊和出隊

實現(xiàn)入隊和出隊操作。

typedefstructQNode{

ElemTypedata;

structQNode*next;

}QNode;

typedefstruct（

QNode*front;

QNode*rear;

JLinkQueue;

3-106棧和隊列的應用

棧在表達式求值、括號匹配、進制轉(zhuǎn)換、遞歸問題等中都有應用。隊列在共享打印機緩沖池、消息隊

列、二叉樹的層序遍歷、圖的廣度優(yōu)先遍歷等中都有應用。

3-107從遞歸到非遞歸

一個函數(shù)直接或間接調(diào)用自己即為遞歸。

函數(shù)遞歸是因為：（1）有很多數(shù)學函數(shù)是遞歸定義的；（2）有些數(shù)據(jù)結(jié)構(gòu)本身就有遞歸性（廣義表、樹、

二叉樹），其上操作常用遞歸描述；（3）有些問題本身雖無明顯遞歸結(jié)構(gòu)，但用遞歸求解較簡單（漢諾塔）。

遞歸算法可轉(zhuǎn)換為用棧來實現(xiàn)的半遞歸算法。

3-201對稱陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)卻，ijG[l,n]/[0,n-l],則稱A為n階對稱陣。

壓縮存儲時用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存對稱陣上或下三角（含對角線）中的

數(shù)據(jù)元素，共n（n+l）/2個。

對矩陣進行壓縮存儲是為了節(jié)省空間，仍屬隨機存取，但計算地址的運算會復雜。

3-202上三角陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)C,7￡[1,亞[0.1]且間，C為常量，則稱A為n階上三角陣。上三角陣中下三

角部分元素（不含對角線）的值為常量。

壓縮存儲時用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存上三角（含對角線）中的數(shù)據(jù)元素，

再加一個下三角常量，共n（n+l）/2+l個。

3-203下二角陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)C,且i<j,C為常量，則稱A為n階下三角陣。下三角陣中上三

角部分元素（不含對角線）的值為常量。

壓縮存儲時用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存下三角（含對角線）中的數(shù)據(jù)元素，

再加一個上三角常量，共n（n+l）/2+l個。

3-204對角陣的定義及壓縮存儲

若n階方陣A中除主對角線及其上下若干條對角線上的元素之外，其余元素均為0,則稱對角陣。

將矩陣中的非零元按某種次序（行優(yōu)先、列優(yōu)先、對角線順序等）存儲于一組地址連續(xù)的存儲單元。

對n階x對角陣A進行壓縮存儲，采用行優(yōu)先/列優(yōu)先/指定的對角線順序-第一元素為aoo/a”，保存在

足夠大的一維數(shù)組e中。若a.保存在e[k]中，要求由ij值求k值。

3-205稀疏陣的定義及壓縮存儲

設在mXn矩陣中，有t個數(shù)據(jù)元素不為零，則通常認為當B=」一<0.05時，稱該矩陣為稀疏矩陣,

mxn

其中6稱稀疏因子。

對稀疏矩陣進行壓縮存儲時，可只保存其中非零元，同時還需指明非零元所處的行列位置及總的行數(shù)、

列數(shù)（可再加非零元個數(shù)），此即稀疏矩陣的三元組表示法。此時不能再隨機存取。

第四課樹與二叉樹

覆蓋的知識點最小集：

I.樹的基本概念

2.二叉樹

(1)二叉樹的定義及具主要特征

(2)二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

(3)二叉樹的遍歷

(4)線索二叉樹的基本概念和構(gòu)造

3.樹、森林

(1)樹的存儲結(jié)構(gòu)

(2)森林與二叉樹的轉(zhuǎn)換

(3)樹和森林的遍歷

4.樹與二叉樹的應用

(1)二叉排序樹

⑵平衡二叉樹

(3)哈夫曼(Huffman)樹和哈夫曼編碼

知識點細化：

4-001樹和結(jié)點

樹是n520)個結(jié)點的有限集。若n=0則為空樹，記為中。若nWO,貝的⑴有且僅有一個根結(jié)點；

⑵若n>l,則其余結(jié)點可分為m(m>0)個互不相交的有限集TI,T2,…,Tm，其中每一集合又是一棵樹，

并稱根的子樹.若將樹中結(jié)點的各子樹看成從左至右是有次序的，即不能互換的，則稱該樹為有序樹，否

則稱無序樹，結(jié)點可分為分支結(jié)點(根結(jié)點+內(nèi)部結(jié)點)和葉子結(jié)點°結(jié)點的度即結(jié)點擁有的子樹數(shù)。樹

的度是樹內(nèi)各結(jié)點的度的最大值。結(jié)點的層次從根開始定義起，根為第一層，根的孩子為第二層，余則類

推。樹的深度(高度)即樹內(nèi)結(jié)點的層次的最大值。

4-002二叉樹

二叉樹是具有如下特點的樹型結(jié)構(gòu)：⑴每個結(jié)點至多只有兩棵子樹；⑵二叉樹的子樹有左右之分。

二叉樹有五種基本形態(tài)：⑴空二叉樹⑵只有根結(jié)點⑶根結(jié)點只有左子樹⑷根結(jié)點只有右子樹⑸根結(jié)點

左右子樹都有。

二叉樹和度為2的有序樹的本質(zhì)區(qū)別在于有序樹上結(jié)點若只有一個孩子，則孩子無次序之分。

4-003滿二叉樹和完全二叉樹

滿二叉樹是深度為k且有2k-l個結(jié)點的二叉樹。若含n個結(jié)點的二叉樹中各結(jié)點位置與同深度的滿二

叉樹按層序的前n個結(jié)點位置相對，則稱完全二叉樹,滿二叉樹一定是完全二叉樹，反之未必。若完全二

叉樹上有n個結(jié)點按層序從1開始編號，則第|_〃2」個結(jié)點是最后一個有孩子的結(jié)點；若n是偶數(shù)，則該

完全二叉樹上有一個度為1的結(jié)點，若n是奇數(shù)，則該完全二叉樹上沒有度為1的結(jié)點。

4-004森林

森林為m(m2。)棵互不相交的樹的集合。

4-101二叉樹性質(zhì)一

在二叉樹的第i層上最多有2皿個結(jié)點(i21)。

【證明】

⑴當i=l時，只有一個根結(jié)點。2皿=2°=1,結(jié)論成立。

⑵假設第k層上最多有2kd個結(jié)點

???二叉樹中每個結(jié)點最多有2個孩子

，第k層結(jié)點的孩子總數(shù)最多為2卜|><2=2卜個

??,第k+1層上的結(jié)點均為第k層結(jié)點的孩子

工第k+1層上最多有2k=2（k+.個結(jié)點

⑶由⑴⑵可得結(jié)論成立。

4-102二叉樹性質(zhì)二

深度為k的二叉樹最多有2k.i個結(jié)點。（k-l）

【證明】由二叉樹性質(zhì)1可知在二叉樹的第i層上最多有2評個結(jié)點（i2l）,因此深度為k的二叉樹最多結(jié)

2°（T）=2J。

點數(shù)為：Z2'T=2°+2i+...+2J

1-2

深度為k的m叉樹最多有.（用上-l）/（/w-l）個結(jié)點。

4-103二叉樹性質(zhì)三

對任意二叉樹T,若其葉子結(jié)點數(shù)為no,度為2的結(jié)點數(shù)為m，則n產(chǎn)血+1。

【證明】設二叉樹中度為1的結(jié)點數(shù)為川

???二叉樹中結(jié)點的度只能為0、1、2

結(jié)點總數(shù)n=no+n1+圖;....⑴

又.??含n個結(jié)點的二叉樹必有n-l條分支，這些分支是有孩子的結(jié)點提供的

工分支數(shù)b=n-l=2*n2+l*ni

?二結(jié)點總數(shù)n=2*n2+l*ni+l；..⑵

由⑴和⑵,可得no=n2+l,結(jié)論成立。

4?104二叉樹性質(zhì)四

具有n個結(jié)點的完全二叉樹的深度為［log?〃」+1。

【證明】設完全二叉樹深度為k

??,前k?l層元素個數(shù)為2k

又???第k層元素個數(shù)至少為1,最多為2k.i

???深度為k的完全二叉樹最多2<1個結(jié)點，最少2kd個結(jié)點

（另：深度為k的二叉樹最多2卜-1個結(jié)點，最少k個結(jié)點）

即（211）十1WnWQll）十即2k-YnW2k-lv2k

/.k-Klog2n<k

Iog2n<k<log2n+1

Vk是整數(shù)

.\k=|_log2/zj+l

4-105二叉樹性質(zhì)五

若對一棵含n個結(jié)點的完全二叉樹中的結(jié)點按層序進行編號，則其中編號為i的結(jié)點有:

①若i=l,則結(jié)點i為二叉樹的根，無雙親，若IviWn,則其雙親為結(jié)點匕/2」；

②若2i>n,則結(jié)點i無左孩子，否則其左孩子為結(jié)點2i；

③若2i+l>n,則結(jié)點i無右孩子，否則其右孩子為結(jié)點2i+l°

4-106二叉樹的順序存儲結(jié)構(gòu)

用一段地址連續(xù)的存儲空間，從下標為1的存儲單元開始按層序依次保存完全（滿）二叉樹中的數(shù)據(jù)

元素，以結(jié)點間存儲地址上的聯(lián)系(按層序編號為i的結(jié)點保存在下標為i的存儲單元，其雙親若存在則

保存在下標為i/2的存儲單元，其左孩子若存在則保存在下標為2*i的存儲單元，其右孩子若存在則保存在

下標為2巧+1的存儲單元)，體現(xiàn)結(jié)點間雙親與孩子的關系。

二叉樹順序存儲結(jié)構(gòu)的優(yōu)點包括：(1)便于由一個結(jié)點找其雙親結(jié)點、孩子結(jié)點；(2)存儲密度大。缺點

包括：(1)需預測二叉樹上可能的最多結(jié)點數(shù)。適用：完全二叉樹、滿二叉樹，若用于保存一般二叉樹，則

最壞情況下，深度為k的二叉樹只含k個結(jié)點卻需使用長度為2k-l的一維數(shù)組保存。

4-107二叉樹的二叉鏈表存儲結(jié)構(gòu)

每個結(jié)點含三個域，即數(shù)據(jù)域、指向左孩子的指針域和指向右孩子的指針域。設置頭指針，指向根結(jié)

點。含n個結(jié)點的二叉鏈表中有n+1個空鏈域。

typedefstructBiTreeNode{

TElcmTypcdata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

}BiTreeNode,*BiTree;

4-108二叉樹的三叉鏈表存儲結(jié)構(gòu)

在二叉鏈表的基礎上，每個結(jié)點再增加一個指向雙親的指針域。

typcdcfstructBiTreeNode{

TElemTypedata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

structBiTreeNode"parent;

)BiTreeNode,*BiTree;

4-109二叉樹的中序遍歷

【方法】(D中序遍歷左子樹；⑵訪問根結(jié)點；(初中序遍歷右子樹。

【遞歸算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!IiiOrderTraverse(T->luhild,visit))return0;〃中序遍歷左子樹

if(!visit(T->data))return0;〃訪問根結(jié)點

if(!lnOrdcrTraversc(T->rchild,visit))return0;〃中序遍歷右子樹

}

return1;

)//InOrderTraverse

【非遞歸算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P)(

Push(S,p);

p=p->lchild;

else{

Pop(S,p);

if(!visit(p->data))return0;

p=p->rchild;

)//else

(//while

return1;

}//InOrderTraverse

輔助棧的最大容量等于二叉樹的深度，最壞情況下為n。

二叉樹遍歷算法中的基本操作是訪問結(jié)點，無論按何種次序，對含n個結(jié)點的二叉樹，時間復雜度均

為O(n)。

4410二叉樹的先序遍歷

【方法】⑴訪問根結(jié)點；⑵先序遍歷左子樹；⑶先序遍歷右子樹。

【遞歸算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!visit(T->data))return0;〃訪問根結(jié)點

if(!PreOrderTraverse(T->lchild,visit))return0;〃先序遍歷左子樹

if(!PreOrderTraverse(T->rchild,visit))return0;〃先序遍歷右子樹

)

return1;

}//PreOrderTraverse

【非遞歸算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!SlackEniply(S)){

if(!visit(p->data))return0;

if(p->rchild)Push(S,p->rchild);

p=p->lchild;

)

else{

Pop(S,p);

}//else

}//while

return1;

(//PreOrderTraverse

4-111二叉樹的后序遍歷

【方法】⑴后序遍歷左了樹；⑵后序遍歷右了樹；⑶訪問根結(jié)點。

【遞歸算法】

intPostOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!PostOrderTraverse(T->lchild,visit))return0;〃后序遍歷左子樹

if(!PoslOrderTraverse(T->rchild,visit))return0;〃后序遍歷右子樹

if(!visit(T->data))return0;〃訪問根結(jié)點

)

return1;

}//PostOrderTraverse

【非遞歸算法】

typedefstruct{

BiTreeNodenode;

intflag;//0表示結(jié)點node的右子樹尚未被訪問，I表示結(jié)點node的右子樹已被訪問

(SElemType;

iniPostOrderTraverse(BiTreeT,int(*vi$it)(TElemTypee)){

//若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

temp.node=p;

temp.flag=0;

Push(S,temp);

p=p->lchild;

)

else{

Pop(S,temp);

if(temp.flag){〃出棧結(jié)點的左、右子樹均已被訪問

if(!visit(temp.node->data))return0;

)

else{〃出棧結(jié)點的右子樹尚未被訪問

temp.flag=l;

Push(S,temp);//修改標志位后重新入棧

p=temp.node->rchild;〃處理右子樹

)

}//if

(//while

(//PostOrderTraverse

4-112二叉樹的層序遍歷

【方法】⑴按結(jié)點所在層次，由低層向高層依次遍歷；⑵同層中按自左向右次序遍歷。

【算法】

intLeveIOrderTraverse(BiTreeT.int(*visit)(TEIemTypee)){

〃若遍歷成功則返回1，否則返回0

if(IT)return1;〃空二叉樹

InitQueue(Q);//初始化輔助隊列

if(!visit(T->data))return0;〃訪問根結(jié)點

EnQueue(Q,T);〃指向根結(jié)點的指針入隊

while(!QueueEmpty(Q)){〃若隊列非空

DeQueue(Q,p);〃隊頭指針出隊

if(p->Ichild){〃先訪問p所指結(jié)點的左孩子，再訪問其右孩子

if(!visit(p->lchild->data))return0;

EnQueue(Q,p->lchild);

)//if

if(p->rchild){

if(!visit(p->rchild->data))return0;

EnQucuc(Q,p->rchild);

}//if

(//while

return1;

)//LevelOrderTraverse

4-201線索二叉樹

二叉樹的任何一種遍歷，其實質(zhì)均為對非線性結(jié)構(gòu)的線性化。若將遍歷序列中所體現(xiàn)的結(jié)點間的線性

關系保存在二叉樹的存儲結(jié)構(gòu)中，這樣的二叉樹稱線索二叉樹，存儲結(jié)構(gòu)稱線索鏈表。線索鏈表中指向結(jié)

點的前驅(qū)、后繼的指針稱線索。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。

一棵二叉樹在中序線索化后，其中空的鏈域的個數(shù)是2。一棵左子樹為空的二叉樹在先序線索化后，

其中空的鏈域的個數(shù)是2；一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是lo一

棵右子樹為空的二叉樹在后序線索化后，其中空的鏈域的個數(shù)是2；一棵左右子樹均不空的二叉樹在后序

線索化后，其中空的鏈域的個數(shù)是1。

4-202線索鏈表

【方法一】在二叉鏈表中每個結(jié)點上增加兩個指針域，分別用以指向該結(jié)點在遍歷序列中的直接前驅(qū)

和直接后繼。

【方法二】利用二叉鏈表中的空鏈域保存結(jié)點間的線性關系。規(guī)定：若結(jié)點的Ichild域為空，則在其

中保存指向其直接前驅(qū)的指針；若結(jié)點的「child域為空，則在其中保存指向其宜接后繼的指針；每個結(jié)點

再設兩個標志域Itag和rtag,當指針域指向孩子時標志域取值為0,否則取值為1。

在線索鏈表中還可添加頭結(jié)點：頭結(jié)點的data域不使用，其Ichiki域指向根，llag域為0,rchild域指

向遍歷序列中的尾結(jié)點，rtag域為1。同時，令遍歷序列中首結(jié)點的Ichild域和尾結(jié)點的rchild域均指向頭

結(jié)點。

typedefenum{Link,Thread}PointerTag,//Link值為0,Thread值為1

typedefstructBiThrNode{

TElemTypedata;

structBiThrNode*lchild;

structBiThrNode*rchild;

PointcrTagItag;

PointerTagrtag;

(BiThrNode,*BiThrTree;

4-203中序線索化

【方法】

對二叉鏈表T進行中序線索化，生成二叉中序線索鏈表Thr1。

⑴生成頭結(jié)點，其data域不用，ltag=Link,rtag=Thread；

⑵若二叉樹為空，則頭結(jié)點的Ichild和rchild均指向自己；

⑶若二叉樹非空，則頭結(jié)點的Ichild指向根，rchild需指向遍歷序列中的尾結(jié)點，應在遍歷完成后處理；

⑷對二叉鏈表進行中序遍歷，對于在遍歷過程中遇到的每個結(jié)點：

若Ichild域非空

則令Ilag=Link

否則令lchild=指向其直接前驅(qū)的指針且令Mg=Thread(在遍歷中設指針pre指向剛訪問過的結(jié)點)

若rchild域非空

則令rtag=Link

否則令rchild=指向其直接后繼的指針且令rtag=Thread(此操作需在訪問到下一結(jié)點時處理，即訪問當

前結(jié)點時，處理其直接前驅(qū)的rchild、rtag域)。

【遞歸算法】

voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

〃由二叉鏈表T生成二叉中序線索鏈表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成頭結(jié)點

if(!Thrt)exit(-2);

if(!T){〃二叉樹為空樹

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchild=Thrt;

Thrt->rtag=Thread;

)//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃頭結(jié)點的Ichiki指向二叉鏈表根結(jié)點

pre=Thrt;//pre為指向前驅(qū)的指針，在InThreading中需使用，此處用全局變量實現(xiàn)，也可設置為參數(shù)

InThreading(T);〃調(diào)用中序線索化函數(shù)處理二叉鏈表T

pre->rchild=Thrt;

pre->rtag=Thread;〃中序遍歷完成，pre指向遍歷序列中的尾結(jié)點，該結(jié)點一定無右子樹

Thrt->rchild=pre;

Thrt->rtag=Thread;〃頭結(jié)點的rchild指向遍歷序列中的尾結(jié)點

}//else

}//InOrderThreading

voidInThreading(BiThrTrccp){

if(P){

InThreading(p->lchild);〃左子樹線索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

InThrcading(p->rchild);〃右子樹線索化

)//if

(InThreading

【非遞歸算法】

voidInOrdcrThrcading(BiThiTrcc&Thrt,BiThrTreeT){

〃由二叉鏈表T生成二叉中序線索鏈表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成頭結(jié)點

if(!Thrt)exit(-2);

if(!T)(〃二叉樹為空樹

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchiId=Thrl;

Thrt->rtag=Thread;

(//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃頭結(jié)點的Ichiki指向二叉鏈表根結(jié)點

pre=Thrt;//pre為指向前驅(qū)的指針

InitSlack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

Push(S,p);

p=p->lchild;

)

else{

Pop(S,p);

if(!p->lchild){p->lchild=pre;p->ltag=Thread;(

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

p=p->rchild;

}//e!se

}//while

pre->rchild=Thrt;

pre->rtag=Thread;〃遍歷序列中的尾結(jié)點的rchild域指向頭結(jié)點

Thrt->rchild=pre;

Thrt->rtag=Thread;〃頭結(jié)點的rchild域指向遍歷序列中的尾結(jié)點

}//IriOrderThreading

4-204中序線索二叉樹的遍歷

【方法】

對中序線索二叉樹進行遍歷，可從頭結(jié)點開始，沿前驅(qū)或后繼進行遍歷。

若對中序線索二叉樹從首結(jié)點起沿后繼進行遍歷，則遍歷序列中首結(jié)點是二叉樹中最左下的結(jié)點。若

結(jié)點無右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其右子樹中最左下的結(jié)點。

若對中序線索二叉樹從尾結(jié)點起沿前驅(qū)進行遍歷，則遍歷序列中尾結(jié)點由頭結(jié)點的右指針指向(二叉

樹中最右下的結(jié)點)。若結(jié)點無左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其左子樹中最

右下的結(jié)點。

【算法】

StatusIOT_Thr(BiThrTreeT,Status(*visit)(TElemTypee)){

〃對中序線索鏈表T從首結(jié)點起，沿后繼進行遍歷，遍歷成功則返回1,否則返回0

p=T->lchiid;〃p指向根結(jié)點

while(p!=T){

〃第一次判定時若p等于T,則二叉樹為空，以后判定時若p等于T,則遍歷完成

while（p->ltag==Link）p=p->lchild;

〃找p的最左下孩子，第一次p指向根，所找結(jié)點即遍歷序列首結(jié)點，

//以后p指向剛訪問過的結(jié)點的右孩子，此時剛訪問過的結(jié)點，其rtag應為Link

if（!visit（p->data））return0;

while（p->rtag==Thread&&p->rchild!=T）{

〃若p所指結(jié)點的rchild指向其直接后繼，且該直接后繼不是頭結(jié)點，即p所指結(jié)點不是遍歷序列尾

結(jié)點

p=p->rchild;

if（!visit（p->data））return0;

}//while

}while

}//IOT_Thr

4-205先序線索化及其遍歷

若對先序線索二叉樹從首結(jié)點起沿后繼進行遍歷，則遍歷序列中首結(jié)點是二叉樹的根結(jié)點。若結(jié)點無

右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其左孩子（即左子樹的根結(jié)點），若左孩子不

存在，則為其右孩子。

若對先序線索二叉樹從尾結(jié)點起沿前驅(qū)進行遍歷，則遍歷序列中尾結(jié)點是二叉樹中最右下的結(jié)點。若

結(jié)點無左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其雙親（當該結(jié)點是其雙親的左孩子或

該結(jié)點雖是其雙親的右孩子但其雙親并無左孩子時）或為其雙親的左子樹中最右下的結(jié)點（當該結(jié)點是其

雙親的右孩子且其雙親有左孩子時），若該結(jié)點無雙親（即根結(jié)點）則無直接前驅(qū)。

4-206后序線索化及其遍歷

若對后序線索二叉樹從首結(jié)點起沿后繼進行遍歷，則遍歷序列中首結(jié)點是二叉樹中最左下的結(jié)點。若

結(jié)點無右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其雙親（當該結(jié)點是其雙親的右孩子或

該結(jié)點雖是其雙親的左孩子但其雙親并無右孩子時）或為其雙親的右子樹中第一個被訪問的結(jié)點（所以仍

需棧的支持）（當該結(jié)點是其雙親的左孩子且其雙親有右孩子時）。

若對后序線索二叉樹從尾結(jié)點起沿前驅(qū)進行遍歷，則遍歷序列中尾結(jié)點是二叉樹的根結(jié)點,若結(jié)點無

左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其右子樹的根，若該結(jié)點無右子樹，則其直接

前驅(qū)為其左子樹的根。

4-301哈夫曼二叉樹（最優(yōu)二叉樹）

哈夫曼（二叉）樹是帶權(quán)路徑長度最短的（二叉）樹，又稱最優(yōu)（二叉）樹’樹的帶權(quán)路徑長度指樹

中所有葉子結(jié)點的帶權(quán)路徑長度之和；結(jié)點的帶權(quán)路徑長度指從根到結(jié)點的路徑長度與結(jié)點上權(quán)的乘積；

結(jié)點間的路徑長度指從一個結(jié)點到另一結(jié)點的路徑上的分支數(shù)。

完全二叉樹是路徑長度最短的二叉樹。樹的路徑長度指根到每個結(jié)點的路徑長度之和。

4?302哈夫曼二叉樹（最優(yōu)二叉樹）

由給定的n個權(quán)值構(gòu)造哈夫曼二叉樹的方法（哈夫曼算法）如下：

⑴根據(jù)給定的n個權(quán)值{wi,W2,…,wj構(gòu)成n棵二叉樹的集合F={TI,T2,…,T”,其中每棵二叉樹只含一

個帶權(quán)的根結(jié)點，其左右子樹均空；

⑵在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且置新的二叉樹的根

結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和；

⑶在F中刪除這兩棵二叉樹，同時將新得到的二叉樹加入F；

⑷重復⑵和（3）,直到F只含一棵二叉樹，此即哈夫曼二叉樹。

4-303哈夫曼編碼

【方法】⑴以字符出現(xiàn)頻率為權(quán)值，構(gòu)造哈夫曼二叉樹；⑵約定以左分支表示0,右分支表示1,把從根

到葉子的路徑上所有分支構(gòu)成的01串作為葉子的二進制編碼，即為哈夫曼編碼。

4-401樹的雙親表示法存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元，按一定次序保存樹中數(shù)據(jù)元素，每個結(jié)點中設置指針，指示具雙親位置。

此法易查找結(jié)點的雙親，而找結(jié)點的孩子則需掃描整張表。

#defineMAXSIZE1000

typedefstructPTNode{

ElemTypedata;

intparent;

JPTNode;

typedefstruct{

PTNodenodes[MAXSIZE];

intn;

（ParentTree;

4-402樹的孩子表示法存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元，按一定次序保存樹中數(shù)據(jù)元索，每個結(jié)點中設置指針，指向其孩子鏈表。

此法易查找結(jié)點的孩子，而查找結(jié)點的雙親則需掃描整張表。

#defineMAXSIZE1000

typedefstructChildNode{

intchild;

structChildNode*next;

JChildNodc,*ChildPtr;〃孩子鏈表中的結(jié)點

typedefstruct{

ElemTypedata;

ChildPtrfirstchild;

}CTNode;

typedefstruct{

CTNodenodes[MAXSIZEl;

intii;〃樹中結(jié)點數(shù)

intr;〃根的位置

JChildTrcc;

4-403樹的雙親一孩子表示法存儲結(jié)構(gòu)

雙親表示法與孩子表示法的組合。結(jié)點間邏輯關系的存儲冗余。

4-404樹的孩子.兄弟表示法存儲結(jié)構(gòu)

用二叉鏈表保存與樹對應的二叉樹。

4-405樹與二叉樹的相互轉(zhuǎn)化

樹與二叉樹可相互轉(zhuǎn)化。由樹轉(zhuǎn)化而來的二叉樹中，結(jié)點的左指針指向它在樹中的第一個孩子結(jié)點，

右指針指向它在樹中的右兄弟結(jié)點。

由一棵非空樹轉(zhuǎn)化而得的二叉樹，其根結(jié)點無右子樹（若樹中只有一個結(jié)點，則轉(zhuǎn)化而得的二叉樹也

沒有左了樹）。

若二叉樹的根結(jié)點無右子樹，則可將它轉(zhuǎn)化為樹。

對樹的操作也可轉(zhuǎn)化為對相應二叉樹的操作。樹的先序遍歷相當于對相應二叉樹的先序遍歷。樹的后

序遍歷相當于對相應二叉樹的中序遍歷。

4-406樹的遍歷

⑴先序遍歷：①訪問樹的根結(jié)點；②從左至右，依次先序遍歷根的每棵子樹。

⑵后序遍歷：①從左至右，依次后序遍歷根的每棵子樹；②訪問樹的根結(jié)點。

4-407森林與二叉樹的相互轉(zhuǎn)化

將森林中各棵樹的樹根看作互為兄弟。

若森林中有多棵樹，則轉(zhuǎn)化而得的二叉樹，其根結(jié)點有右子樹。若二叉樹的根結(jié)點有右子樹，則轉(zhuǎn)化

而得的必為森林。

森林的先序遍歷相當于對相應二叉樹的先序遍歷。森林的中（后）序遍歷相當于對相應二叉樹的中序

遍歷。

4-408森林的遍歷

⑴森林的先序遍歷

若森林非空，則：

①訪問森林中第一棵樹的根結(jié)點；

②先序遍歷第一棵樹中根結(jié)點的子樹森林；

③先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

⑵森林的中（后）序遍歷

若森林非空，則：

①中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；

②訪問第一棵樹的根結(jié)點；

③中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

第五課圖

覆蓋的知識點最小集：

I.圖的基本概念

2.圖的存儲及基本操作

(1)鄰接矩陣法

⑵鄰接表法

3.圖的遍歷

(1)深度優(yōu)先搜索

⑵廣度優(yōu)先搜索

4.圖的基本應用

(1)最小(代價)生成樹

(2)最短路徑

(3)拓撲排序

(4)關鍵路徑

知識點細化：

5-001圖

圖G=(V,{VR}),其中V為頂點的非空有限集合，VR為頂點間關系的集合，即圖中邊的集合(注意：

離散數(shù)學中將樹定義為一個連通且無回路的無向圖)。

圖中的邊若為頂點的無序序偶，則稱無向邊(簡稱邊)，若為頂點的有序序偶，則稱有向邊(簡稱弧)。

若圖中的邊均為無向邊，則稱無向圖；含n個頂點n(n-l)/2條邊的無向圖稱無向完全圖;若圖中的邊均為

有向邊，則稱有向圖；含n個結(jié)點n(n-l)條弧的有向圖稱有向完全圖。網(wǎng)是邊/弧上帶權(quán)的圖。權(quán)是與圖

的邊/弧相關的數(shù)。

5-002頂點的度

無向圖中依附于頂點v的邊的數(shù)目，稱頂點v的度，記TD(v).

有向圖中以頂點v為弧頭頂點的弧的數(shù)目稱頂點v的入度，記ID(v)；以頂點v為弧尾頂點的弧的數(shù)

目稱頂點v的出度，記OD(v)；入度與出度之和稱頂點v的度.記TD(v),

若圖G中有n個頂點，e條邊/弧，必有€之

5-003頂點間路徑

無向圖G=(V,{E})中頂點V和頂點W間的路徑為頂點序列Vo,Vl/-,Vn?其中Vo=V為起點，Vn=W為終點，

voJ:VnWV,ei=(Vj.i,Vj)￡E,i=l,,,no

有向圖G=(V,{A})中從頂點V到頂點W的路徑為頂點序列Vo,Vi,…,Vn，其中Vo=V為起點，Vn=W為終點，

V。,…,Vn^V，ai=<Vj.|,Vj>^A,

路徑上邊/弧的數(shù)目稱路徑長度，，沒有重復頂點的路徑稱簡單路徑.，起點與終點相同的路徑稱回路,,

除起點和終點相同外，別無重復頂點的路徑稱簡單回路。

5?004子圖

設圖G=<V,{VR}>,若有圖G=vV：{VR}>,滿足▽包含于V,VR包含于VR,則稱G為G的子圖。

5?005無向圖的連通性

無向圖中，若兩頂點間存在路徑，則稱兩頂點連通。若圖中任意兩頂點都是連通的，則稱該圖為連通

圖，否則稱非連通圖，

無向圖的極大連通了圖稱其連通分量，連通圖只有?個連通分量，就是它本身，非連通圖則有多個連

通分量。

連通圖的極小連通子圖（含原圖中全部頂點）稱其生成樹。若連通圖有n個頂點，則其生成樹有n個

頂點，并有且僅有n-1條邊，但該圖的含n個頂點及n-1條邊的子圖不一定是其生成樹。生成樹上任意兩

頂點間有且僅有一條路徑。

非連通圖的各連通分量的生成樹構(gòu)成該圖的生成森林。

5-006有向圖的連通性

有向圖中，任意一對結(jié)點間，若兩者相互可達，則稱該圖為強連通圖；若至少有一個結(jié)點到另一個結(jié)

點是可達的，則稱該圖為單側(cè)連通圖，若略去弧的方向（即把該圖看作無向圖），該圖為一連通圖，則稱

該圖為弱連通圖，以上三者均不符，則為非連通圖。有向圖若強連通，則必單側(cè)連通；若單側(cè)連通，則必

弱連通；反之不然。

有向圖的極大強連通子圖稱其強連通分量

只有一個頂點的入度為0,其余頂點的入度均為1的有向圖稱有向樹。一個有向圖的生成森林由若干

棵有向樹組成，該森林含有圖中全部頂點以及足以構(gòu)成若干棵不相交的有向樹的弧。

含n個頂點的有向強連通圖至少含n條弧，至多含n（n?l）條弧。

5-101圖的鄰接矩陣存儲結(jié)構(gòu)

設圖G含n個頂點，則G的鄰接矩陣是記錄這些頂點間邏輯關系的n階方陣，不妨記為A=（aRxn，

1<v.,v.>eVRw<V,,V>eVR

則對（有向/無向）圖有：八對（有向/無向）網(wǎng)有：Ujj7

J

[（）<vPvy>^VRoo<>^VR

其中W為權(quán)值。

無向圖（網(wǎng)）的鄰接矩陣是對稱陣；有向圖（網(wǎng)）的鄰接矩陣可以對稱，也可以不對稱（后者更為常見）。

鄰接矩陣存儲結(jié)構(gòu)的空間復雜度為0（1?）。

在鄰接矩陣存儲結(jié)構(gòu)中，添加新頂點V：若頂點數(shù)未滿，貝1J（1）將頂點V保存在vexs[vexnum]中；（2）

必要時將adjmaxlrix[vexnum][O..vexnum]及adjmaxtrix[O..vexnum][vexnum]清為0或8；（3）vexnum力口1。

在鄰接矩陣存儲結(jié)構(gòu)中，設頂點V保存在vexs國中，刪除頂點V（注意：刪除頂點時，依附于該頂點

的邊/弧也一并刪除）：（1）求依附于該頂點的邊數(shù)，依此修改arcnum的值；（2）若V不是頂點向量中最后一

個結(jié)點，即i!=vexnum-l,貝令vexs[i]=vexs[vexnum-l],并令

adjmaxtrix[i][O..vexnum]=adjmaxtrix[vexnum][O..vexnum],令

adjmaxtrix[O..vexnuml[i]=adjmaxtrix[O..vexnum][vexnumb令adjmaxtrix[i][i]=OB￡°°；（3）vexnum減1。

在鄰接矩陣存儲結(jié)構(gòu)中，設頂點V保存在vexs國中，頂點W保存在vexslj]中，添加邊（V,W）/弧

vV,W>（注意：添加邊/弧時，要求相關頂點已存儲）：（1）對于無向圖，則令adjmaxtrix[il[jl=adjmaxtrix[jl[il=l,

并使arcnuni加1；（2）對丁有向圖，令adjiiiaxtrix[i]（j]=l,并使arcnuni加1；（3）對丁網(wǎng),則令相應位置的值

為輸入的權(quán)值，并使arcnum加1。

在鄰接矩陣存儲結(jié)構(gòu)中，設頂點V保存在vexs[i]中，頂點W保存在vexsfj]中，刪除邊（V,W）/弧

<V,W>（注意:刪除邊/弧時，不刪除相關頂點）:⑴對于無向圖，則令adjmaxtrix[i][j]=adjmaxtrix皿"=0,

并使arcnum減1；（2）對于有向圖,令adjmaxtrix[i][j]=O,并使arcnum減1；（3）對于網(wǎng)，則令相應位置的值

為8,并使arcnum減1。

在鄰接矩陣存儲結(jié)構(gòu)中，設頂點V保存在vexs[i]中，頂點W保存在vexs[j]中，判斷邊（V,W）/弧

<V,W>是否存在：（1）對于無向圖，若adjmaxtrix[i][j]=l或adjmaxtrix[j][i]=l,則邊（V,W）存在，時間

復雜度0（1）;（2）對于有向圖，若adjmaxtrix[i皿=1,則?。╒,W）存在，時間復雜度0（1）