數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件全套 蔣理 第1-8章 數(shù)據(jù)結(jié)構(gòu)與算法概論-查找

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)計(jì)算機(jī)解決問(wèn)題的步驟非數(shù)值數(shù)學(xué)模型1.1問(wèn)題求解計(jì)算機(jī)求解現(xiàn)實(shí)問(wèn)題計(jì)算機(jī)解決問(wèn)題的步驟一個(gè)長(zhǎng)75cm、寬60cm的長(zhǎng)方形紙板，平均切割成大小相等的正方形紙板，使每個(gè)正方形紙板的面積最大，共可切割成多少個(gè)正方形紙板？人要和計(jì)算機(jī)進(jìn)行有效交流，必須通過(guò)程序計(jì)算機(jī)世界機(jī)器語(yǔ)言現(xiàn)實(shí)世界自然語(yǔ)言程序計(jì)算機(jī)解決問(wèn)題的步驟分析問(wèn)題、設(shè)計(jì)算法、編寫程序、執(zhí)行程序人：分析問(wèn)題、確定解決方案、編寫程序計(jì)算機(jī)：執(zhí)行程序最終獲得問(wèn)題的解數(shù)據(jù)模型數(shù)值問(wèn)題：數(shù)學(xué)方程非數(shù)值問(wèn)題：線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)模型一個(gè)簡(jiǎn)單的圖書信息檢索系統(tǒng)包括一張按索書號(hào)、條碼號(hào)和書名的順序排列的圖書信息表。圖書信息表中的順序關(guān)系可以被抽象成線性結(jié)構(gòu)圖書信息檢索系統(tǒng)——線性數(shù)據(jù)結(jié)構(gòu)書名條碼號(hào)索書號(hào)書架號(hào)什么是算法90073160TP393.92/1811-12-3數(shù)據(jù)庫(kù)原理與應(yīng)用70002001TP391.41/3141-12-1軟件測(cè)試項(xiàng)目實(shí)踐00777680TP311.52/8371-13-2Linux系統(tǒng)編程50010241TP316.76/4541-10-2Python程序設(shè)計(jì)90115601TP311.56/1291-14-1對(duì)弈問(wèn)題——樹(shù)人機(jī)對(duì)弈問(wèn)題是一個(gè)古老的人工智能問(wèn)題，對(duì)弈過(guò)程是在一定規(guī)則約束下的隨機(jī)過(guò)程。其解決問(wèn)題的思路是將對(duì)弈策略事先存入計(jì)算機(jī)，包括對(duì)弈過(guò)程中所有可能出現(xiàn)的情況和相應(yīng)的對(duì)策。城市道路問(wèn)題——圖假設(shè)某人要從地點(diǎn)A騎車到地點(diǎn)G，使用導(dǎo)航系統(tǒng)查詢合適的騎行路線。導(dǎo)航系統(tǒng)為解決這個(gè)問(wèn)題，須建設(shè)地區(qū)交通的數(shù)學(xué)模型，描述各個(gè)地點(diǎn)及其之間的交通情況。對(duì)于這類問(wèn)題，通常采用“圖”來(lái)描述路況——將地點(diǎn)抽象成一個(gè)點(diǎn)，地點(diǎn)之間的路線抽象成一條線，路線的距離用線上的數(shù)字描述。這些點(diǎn)、線就組成了一個(gè)圖。小結(jié)1.1問(wèn)題求解計(jì)算機(jī)解決問(wèn)題的步驟非數(shù)值數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念抽象數(shù)據(jù)類型1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)(data)信息的載體，是對(duì)客觀事物的符號(hào)表示，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。圖像、聲音、視頻等都可通過(guò)編碼由計(jì)算機(jī)處理，因此也屬于數(shù)據(jù)的范疇數(shù)據(jù)元素(dataelement)數(shù)據(jù)的基本單位,也稱為元素、結(jié)點(diǎn)或記錄數(shù)據(jù)項(xiàng)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（字段、域）構(gòu)成數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念數(shù)據(jù)對(duì)象數(shù)據(jù)的子集具有相同性質(zhì)的數(shù)據(jù)元素的集合姓名班級(jí)學(xué)號(hào)小明3020112小紅302027小方3020232姓名課程名成績(jī)小明高數(shù)85小紅高數(shù)90小紅英語(yǔ)88數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素的集合中，元素相互之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)圖狀結(jié)構(gòu)數(shù)據(jù)的物理(存儲(chǔ))結(jié)構(gòu)數(shù)據(jù)在存儲(chǔ)器中位置的關(guān)系數(shù)據(jù)邏輯結(jié)構(gòu)表示： Data_Structures=(D,S)D是數(shù)據(jù)元素的有限集S是數(shù)據(jù)元素關(guān)系的有限集GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理(M)，2個(gè)部門經(jīng)理(D)，每個(gè)部門各有3名職員(E)。人員之間的關(guān)系是：經(jīng)理指導(dǎo)部門經(jīng)理的工作，部門經(jīng)理指導(dǎo)職員的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理，2個(gè)部門經(jīng)理，每個(gè)部門各有3名職員。人員之間的關(guān)系是：按人員年齡從大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理，2個(gè)部門經(jīng)理，每個(gè)部門各有3名職員。人員之間的關(guān)系是：人員之間的友好關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素的存儲(chǔ)用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2‘A’=(101)8=(01000001)2關(guān)系的存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)用元素之間存儲(chǔ)的相對(duì)位置表示關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用存儲(chǔ)元素的引用（指針）表示關(guān)系抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具，其目的是使人們能夠獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來(lái)理解數(shù)據(jù)結(jié)構(gòu)的特性。抽象數(shù)據(jù)類型一般通過(guò)數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系以及基本操作來(lái)定義。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象D：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系R：<數(shù)據(jù)關(guān)系的定義>

基本操作P：<基本操作的定義>}小結(jié)1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)算法及其特性算法設(shè)計(jì)的要求算法描述方法1.3算法概述算法評(píng)價(jià)算法(Algorithm)對(duì)特定問(wèn)題求解步驟的一種描述是指令的有限序列算法的特性有窮性確定性可行性輸入輸出算法及其特性正確性：算法應(yīng)當(dāng)滿足具體問(wèn)題的需求，按算法編碼好的計(jì)算機(jī)程序的執(zhí)行結(jié)果應(yīng)當(dāng)符合預(yù)先設(shè)定的功能和性能要求?？勺x性：一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、易讀易懂?？勺x性好，易于理解。健壯性：指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也被稱為容錯(cuò)性。高效性：一個(gè)算法應(yīng)當(dāng)有效使用存儲(chǔ)空間和有較高的效率。對(duì)于同一個(gè)問(wèn)題，通?？梢杂卸鄠€(gè)解決算法，其中執(zhí)行時(shí)間短、占用存儲(chǔ)空間少的算法即“好的算法”。算法設(shè)計(jì)的要求自然語(yǔ)言算法描述框圖算法描述偽代碼算法描述高級(jí)程序語(yǔ)言編寫的程序或函數(shù)算法描述方法事前估算法（定性分析）：對(duì)算法所消耗資源的一種估算方法算法的策略問(wèn)題的規(guī)模書寫程序的語(yǔ)言編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量機(jī)器執(zhí)行指令的速度事后統(tǒng)計(jì)法（定量分析）：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開(kāi)銷評(píng)價(jià)算法算法評(píng)價(jià)指標(biāo)執(zhí)行程序需要占用多少機(jī)器資源時(shí)間資源算法運(yùn)行時(shí)花費(fèi)的時(shí)間代價(jià)空間資源程序執(zhí)行中占用的內(nèi)存空間代價(jià)時(shí)間復(fù)雜性和空間復(fù)雜性T(n)：2n3+3n2+2n+1算法的時(shí)間復(fù)雜性分析算法中所有語(yǔ)句執(zhí)行時(shí)間之和語(yǔ)句的執(zhí)行時(shí)間：該語(yǔ)句的頻度(語(yǔ)句重復(fù)執(zhí)行的次數(shù))，與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。//求兩個(gè)n階方陣的乘積C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求兩個(gè)n階方陣的乘積C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1//求兩個(gè)n階方陣的乘積C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求兩個(gè)n階方陣的乘積C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1算法的時(shí)間復(fù)雜性分析算法時(shí)間取決于控制結(jié)構(gòu)和原操作的綜合效果f(n)是算法中頻度最大的語(yǔ)句頻度，通常是最深層循環(huán)內(nèi)的原操作執(zhí)行的次數(shù)。隨著n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。算法時(shí)間復(fù)雜度記作：T(n)=O(f(n))O(n)：n3常見(jiàn)函數(shù)比較通常有如下的函數(shù)關(guān)系

c<log2n<n<nlog2n<n2<n3<2n指數(shù)時(shí)間的關(guān)系為

O(2n)<O(n!)<O(nn)算法的時(shí)間復(fù)雜度不僅是問(wèn)題規(guī)模n的函數(shù)，還與所處理的數(shù)據(jù)集有關(guān) (1)1,2,3,4,5,6,7,8,9,10 (2)10,9,8,7,6,5,4,3,2,1全面分析算法，需考慮它在最壞情況下的代價(jià)、最好情況下的代價(jià)和平均情況下的代價(jià)。算法的空間復(fù)雜度算法所需的存儲(chǔ)量輸入數(shù)據(jù)所占空間程序本身所占空間輔助變量所占空間 S(n)=O(g(n))隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)空間的增長(zhǎng)率與g(n)的增長(zhǎng)率相同小結(jié)1.3算法概述算法及其特性算法設(shè)計(jì)的要求算法描述方法算法評(píng)價(jià)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)線性表n(n≥0)個(gè)具有相同特性的數(shù)據(jù)元素的有限序列n表示線性表的長(zhǎng)度，即數(shù)據(jù)元素的個(gè)數(shù)n=0時(shí)表為空表n>0時(shí)記為:（a1，a2，…ai-1，ai，ai+1，…an）基本特征有且只有一個(gè)第一元素，且只有一個(gè)最后元素除第一元素之外，其它元素都有唯一的直接前趨除最后元素之外，其它元素都有唯一的直接后繼2.1線性表的概念aebcd數(shù)據(jù)元素在不同問(wèn)題中的含義各不相同，可以是一個(gè)數(shù)、一個(gè)符號(hào)，一個(gè)記錄，或其它復(fù)雜的信息例中學(xué)生成績(jī)表是一個(gè)線性表數(shù)據(jù)元素是每一個(gè)學(xué)生的信息，包括：學(xué)號(hào)、姓名、成績(jī)共三個(gè)數(shù)據(jù)項(xiàng)線性表舉例學(xué)號(hào)姓名成績(jī)043801陳實(shí)80043802陳信85043803秦儉82043804秦奮90┆┆┆043850鐘毅88數(shù)據(jù)元素基本運(yùn)算初始化線性表查找線性表中第i個(gè)元素查找滿足給定條件的數(shù)據(jù)元素在指定位置插入新的數(shù)據(jù)元素刪除線性表中的第i個(gè)數(shù)據(jù)元素查找表中第i個(gè)元素的前驅(qū)元素查找表中第i個(gè)元素的后繼元素表置空 ……線性表的運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)順序存儲(chǔ)在內(nèi)存中開(kāi)辟連續(xù)的存儲(chǔ)空間，用連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素順序表順序存儲(chǔ)的線性表特點(diǎn)邏輯上相鄰的數(shù)據(jù)元素，其物理位置也相鄰利用物理位置上的關(guān)系，反映元素的邏輯關(guān)系2.2線性表的順序存儲(chǔ)優(yōu)點(diǎn)靜態(tài)操作容易實(shí)現(xiàn)根據(jù)定位公式容易確定表中元素的存儲(chǔ)位置缺點(diǎn)動(dòng)態(tài)操作實(shí)現(xiàn)效率較低插入和刪除結(jié)點(diǎn)困難擴(kuò)展不靈活，容易造成空間浪費(fèi)建表時(shí)，若估計(jì)不到表的最大長(zhǎng)度，就難以確定分配的空間，影響數(shù)據(jù)擴(kuò)展分配的空間過(guò)大，則會(huì)浪費(fèi)預(yù)留空間順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)鏈表以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表用一組在物理位置上任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表的節(jié)點(diǎn)存儲(chǔ)單元可以是相鄰的，也可以是不相鄰的物理位置上的關(guān)系不能反映節(jié)點(diǎn)間的邏輯關(guān)系2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)０００００５陳小潔０００００４張吉祥０００００２林春英０００００１李小林０００００６李清０００００３張桂林１７１５２０４０５４7155440NULL1用任意位置的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素節(jié)點(diǎn)間的邏輯關(guān)系借助節(jié)點(diǎn)中的指針(引用)

實(shí)現(xiàn)每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的地址節(jié)點(diǎn)

數(shù)據(jù)域元素本身信息指針域指示直接后繼的存儲(chǔ)位置鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)

數(shù)據(jù)域指針域鏈表中，每個(gè)節(jié)點(diǎn)只包含一個(gè)指針域節(jié)點(diǎn)描述如下：#SinNode{

數(shù)據(jù)域

data;

指針域

next;}單鏈表每一個(gè)節(jié)點(diǎn)中有兩個(gè)指針域一個(gè)指向直接后繼一個(gè)指向直接前趨節(jié)點(diǎn)描述如下:#DulNode

{

數(shù)據(jù)域data

指針域next，prior}雙向鏈表priordatanext數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)均勻性對(duì)于同一線性表，其各數(shù)據(jù)元素必定具有相同的數(shù)據(jù)類型和長(zhǎng)度。有序性各數(shù)據(jù)元素在線性表中的邏輯位置只取決于它們的序號(hào)，數(shù)據(jù)元素之間的是線性的。線性表的特點(diǎn)順序表優(yōu)點(diǎn)：查找速度快缺點(diǎn)：插入和刪除比較復(fù)雜鏈表優(yōu)點(diǎn)：插入和刪除操作簡(jiǎn)單缺點(diǎn)：查找速度慢順序表與鏈表的比較單向鏈表優(yōu)點(diǎn)：增加或刪除節(jié)點(diǎn)操作簡(jiǎn)單缺點(diǎn)：只能從前向后遍歷，只能找到后繼節(jié)點(diǎn)，無(wú)法找到前驅(qū)節(jié)點(diǎn)，操作不夠靈活雙向鏈表優(yōu)點(diǎn)：可以找到前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，操作靈活缺點(diǎn)：增加或刪除節(jié)點(diǎn)時(shí)需要操作的指針較多，比較復(fù)雜單向鏈表與雙向鏈表的比較數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)一元多項(xiàng)式求和有序單鏈表的合并2.5線性表的應(yīng)用coefexpnext稀疏矩陣的三元組表示法線性表的應(yīng)用稀疏矩陣的十字鏈表表示法線性表的應(yīng)用約瑟夫問(wèn)題線性表的應(yīng)用約瑟夫和一個(gè)朋友及另外39個(gè)人圍成一個(gè)圓圈，從第一個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到3的那個(gè)人退出圈子。然后下一個(gè)人從1開(kāi)始重新報(bào)數(shù)，最后圈子里只剩下兩個(gè)人，就是約瑟夫和他朋友。問(wèn)約瑟夫和朋友站在什么位置？數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)3.1棧棧的定義與基本操作棧的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序棧和鏈棧的比較棧的應(yīng)用案例棧的定義與基本操作棧的定義棧：限定僅在一端進(jìn)行插入和刪除操作的線性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱為棧頂棧底（bottom）：另一端稱為棧底插入位置：1~n+1刪除位置：1~n線性表插入位置：n+1刪除位置：n棧棧底棧頂棧的定義與基本操作棧的操作插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧a插入刪除bc此時(shí)執(zhí)行出棧操作，哪個(gè)元素可以出棧呢？棧的操作特性：后進(jìn)先出（LastInFirstOut，LIFO）空棧：不含任何數(shù)據(jù)元素的棧

如何判空棧

initStack()：初始化操作。設(shè)置一個(gè)空棧isEmpty()：判?？蘸瘮?shù)。若為空，則返回true，否則返回false。getTop()：讀棧頂元函數(shù)。若棧不空，函數(shù)值為棧頂元素，否則為空元素NULLpush(x)：進(jìn)棧操作。將元素x插入棧中，使x成為棧的棧頂元素pop()：出棧函數(shù)。若棧不空，函數(shù)值為棧頂元素，且從棧中刪除當(dāng)前棧頂元素，否則函數(shù)值為空元素NULLclearStack()：棧置空操作。不論棧是否為空棧，置為空棧棧的定義與基本操作棧的基本操作棧的定義與基本操作棧的抽象數(shù)據(jù)類型定義ADTStackDataModelOperationendADT棧中元素具有相同類型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系initStack：棧的初始化clearStack：清空棧內(nèi)元素push：入棧pop：出棧getTop：取棧頂元素isEmpty：判空利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素a1a2……an順序棧Sai……0n棧底棧頂top棧的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序棧用數(shù)組的一端作為棧底設(shè)變量top存儲(chǔ)棧頂元素所在的下標(biāo)組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂FtopdatanextEDANULL棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)鏈棧順序棧和鏈棧的比較順序棧和鏈棧的基本算法的時(shí)間復(fù)雜度均為O(1)空間復(fù)雜度比較Java中，初始時(shí)順序棧需要確定棧的長(zhǎng)度，所以存在存儲(chǔ)元素個(gè)數(shù)的限制和浪費(fèi)存儲(chǔ)空間的問(wèn)題。鏈棧沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用存儲(chǔ)空間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要指針域，從而存在結(jié)構(gòu)性開(kāi)銷。把所有的余數(shù)按出現(xiàn)的逆序排列起來(lái)（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)棧的應(yīng)用351784210110001余數(shù)結(jié)果：100011表達(dá)式求值棧的應(yīng)用對(duì)算術(shù)表達(dá)式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號(hào)內(nèi)，后括號(hào)外的四則運(yùn)算法則，其計(jì)算順序應(yīng)為：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“運(yùn)算符優(yōu)先數(shù)法”對(duì)每種運(yùn)算符賦于一個(gè)優(yōu)先數(shù)，如：運(yùn)算符：*/+-#優(yōu)先數(shù)：22110其中

#是表達(dá)式結(jié)束符表達(dá)式求值時(shí)，設(shè)立兩個(gè)棧運(yùn)算符棧(OPTR)操作數(shù)棧(OPND)分別存放表達(dá)式中的運(yùn)算符和操作數(shù)

步驟OPTR棧OPND棧輸入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14 # 6# RETURN(TOP(OPND))表達(dá)式求值棧的應(yīng)用小結(jié)3.1棧棧的定義與基本操作棧的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序棧和鏈棧的比較棧的應(yīng)用案例數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)3.2隊(duì)列隊(duì)列的定義與基本操作隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)循環(huán)隊(duì)列與鏈隊(duì)列的比較隊(duì)列的應(yīng)用案例隊(duì)列的定義隊(duì)列的定義與基本操作只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表（a1,a2,…,an-1,an）a1

a2

…

an棧a1

a2

…

an隊(duì)列隊(duì)頭隊(duì)尾隊(duì)尾：允許插入的一端，相應(yīng)地，位于隊(duì)尾的元素稱為隊(duì)尾元素隊(duì)頭：允許刪除的一端，相應(yīng)地，位于隊(duì)頭的元素稱為隊(duì)頭元素隊(duì)列的操作隊(duì)列的定義與基本操作隊(duì)列的操作特性：先進(jìn)先出（FirstInFirstOut，F(xiàn)IFO）a插入：入隊(duì)、進(jìn)隊(duì)入隊(duì)bc例：有三個(gè)元素按a、b、c的次序依次入隊(duì)，且每個(gè)元素只允許進(jìn)一次隊(duì)，則出隊(duì)序列是什么？答：出隊(duì)序列只有一種情況：abc出隊(duì)刪除：出隊(duì)空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列

任何時(shí)候執(zhí)行出隊(duì)操作，一定是哪個(gè)元素呢？隊(duì)列的基本操作隊(duì)列的定義與基本操作initQueue()：初始化。設(shè)置一個(gè)空隊(duì)列qisEmpty()：判斷隊(duì)列是否為空。若隊(duì)列q為空，函數(shù)值為true，否則為false

size()：求隊(duì)列長(zhǎng)度。函數(shù)值為隊(duì)列q中當(dāng)前所含元素的個(gè)數(shù)getHead()：讀隊(duì)頭元素。若隊(duì)列q不為空，函數(shù)值為隊(duì)頭元素，否則為空元素enQueue(x)：入隊(duì)。將元素x插入隊(duì)列q的尾部，使x成為新的隊(duì)尾元素delQueue()：出隊(duì)。若隊(duì)列q不為空，函數(shù)值為隊(duì)頭元素，且從隊(duì)列q中刪除當(dāng)前隊(duì)頭元素，否則函數(shù)值為空元素順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)尾：設(shè)變量rear存儲(chǔ)隊(duì)尾元素所在的下標(biāo)隊(duì)頭：用數(shù)組的一端作為隊(duì)頭，從下標(biāo)0處開(kāi)始存放01234a1a2a3a4rear例：a1a2a3a4

依次入隊(duì)順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)例：a1

出隊(duì)01234a1a2a3a4rear01234a2a3a4rear隊(duì)頭元素出隊(duì)后，后面的元素都需要前移，時(shí)間性能較差如何改進(jìn)出隊(duì)操作的時(shí)間性能？01234a2a3a4rear設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)位置變量約定：隊(duì)頭front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾rear指向隊(duì)尾元素fronta1入隊(duì)、出隊(duì)時(shí)間性能均是O(1)順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)隊(duì)列的移動(dòng)有什么特點(diǎn)？01234a2a3a4front整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng)單向移動(dòng)性隊(duì)列的單向移動(dòng)性會(huì)產(chǎn)生什么問(wèn)題？a5假溢出：數(shù)組空間發(fā)生上溢，但數(shù)組的低端還有空閑空間rear循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)如何解決假溢出呢？01234a3a4rearfront如何使數(shù)組下標(biāo)循環(huán)呢？a5a6循環(huán)隊(duì)列：隊(duì)列采用順序存儲(chǔ)，并且數(shù)組是頭尾相接的循環(huán)結(jié)構(gòu)循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)01234a3rearfront如何判斷循環(huán)隊(duì)列的隊(duì)空？隊(duì)空的判定條件：front==rear循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)a6a2a4a5rearfront如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)空的判定條件：front==rear隊(duì)滿的判定條件：front==rearx01234循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)如何確定不同的隊(duì)空、隊(duì)滿的判定條件？隊(duì)空的判定條件：front==rear隊(duì)滿的判定條件：front==rear數(shù)組中有一個(gè)空閑單元01234a6a2a4a5rearfront01234a1a2a4a5rearfront(rear+1)%QUEUE_SIZE=front鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)是單鏈表，同時(shí)帶有頭指針和尾指針頭指針指向隊(duì)頭結(jié)點(diǎn)尾指針指向隊(duì)尾結(jié)點(diǎn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)頭結(jié)點(diǎn)^…...head隊(duì)頭隊(duì)尾tail設(shè)隊(duì)首、隊(duì)尾指針head和tail,head指向隊(duì)頭，tail指向隊(duì)尾循環(huán)隊(duì)列與鏈隊(duì)列的比較循環(huán)隊(duì)列和鏈隊(duì)列基本算法的時(shí)間復(fù)雜度均為O(1)空間復(fù)雜度比較初始時(shí)循環(huán)隊(duì)列必須確定一個(gè)固定的長(zhǎng)度，所以存在存儲(chǔ)元素個(gè)數(shù)的限制和浪費(fèi)存儲(chǔ)空間的問(wèn)題。鏈隊(duì)列沒(méi)有溢出問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用存儲(chǔ)空間時(shí)才會(huì)出現(xiàn)溢出，但是每個(gè)元素都需要指針域，存在結(jié)構(gòu)性開(kāi)銷。隊(duì)列的應(yīng)用案例舞伴配對(duì)問(wèn)題在某舞會(huì)上，男士和女士進(jìn)入舞廳時(shí)，各自排成一隊(duì)。舞會(huì)開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭各出一人配成舞伴。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪。在算法中，假設(shè)男士和女士的記錄存放在一個(gè)數(shù)組中，然后依次掃描該數(shù)組的各元素，并根據(jù)性別來(lái)決定是進(jìn)入男隊(duì)還是女隊(duì)。當(dāng)這兩個(gè)隊(duì)列構(gòu)造完成后，依次使兩隊(duì)當(dāng)前的隊(duì)頭元素出隊(duì)來(lái)配成舞伴，直至某隊(duì)列變空為止。此時(shí)，若某隊(duì)仍有等待者，算法輸出此隊(duì)列中等待者的人數(shù)及排在隊(duì)頭的等待者的名字，他（或她）將是下一輪開(kāi)始時(shí)第一個(gè)可獲得舞伴的人。隊(duì)列的應(yīng)用案例時(shí)間片輪轉(zhuǎn)調(diào)度問(wèn)題系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來(lái)停止執(zhí)行該進(jìn)程，并將它送往就緒隊(duì)列的末尾；然后，把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)讓它執(zhí)行一個(gè)時(shí)間片。小結(jié)3.2隊(duì)列隊(duì)列的定義與基本操作隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)循環(huán)隊(duì)列與鏈隊(duì)列的比較隊(duì)列的應(yīng)用案例數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)4.1遞歸定義若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的。遞歸定義遞歸定義構(gòu)成遞歸需具備的條件子問(wèn)題須與原始問(wèn)題為同樣的問(wèn)題，且更為簡(jiǎn)單不能無(wú)限制地調(diào)用本身，須有個(gè)出口，化簡(jiǎn)為非遞歸狀況來(lái)處理小結(jié)4.1遞歸定義數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)4.2遞歸算法設(shè)計(jì)遞歸問(wèn)題，必須符合以下三個(gè)條件可以把一個(gè)問(wèn)題轉(zhuǎn)化為一個(gè)新的問(wèn)題，這個(gè)新的問(wèn)題的解決方法與原問(wèn)題的解法相同，但是所處理的對(duì)象（參數(shù)）有變化通過(guò)對(duì)象（參數(shù)）的變化使問(wèn)題得到簡(jiǎn)化要有明確的結(jié)束遞歸的條件，否則遞歸將會(huì)陷入死循環(huán)遞歸算法設(shè)計(jì)以下三種情況可以使用遞歸解決問(wèn)題定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的遞歸算法設(shè)計(jì)階乘函數(shù)定義是遞歸的遞歸算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)是遞歸的f

ffff

a0a1a2a3a4鏈表操作遞歸算法設(shè)計(jì)問(wèn)題的解法是遞歸的漢諾塔(TowerofHanoi)問(wèn)題的解法如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上否則，執(zhí)行以下三步用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤子移到B柱上將A柱上最后一個(gè)盤子直接移到C柱上用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤子移到C柱上遞歸算法設(shè)計(jì)遞歸的結(jié)構(gòu)遞歸的結(jié)構(gòu)是由遞歸出口和遞歸體兩部分組成遞歸出口確定遞歸到何時(shí)為止遞歸體確定遞歸的方式遞歸是把一個(gè)不能或不好直接求解的"大問(wèn)題"轉(zhuǎn)化為若干個(gè)"小問(wèn)題"來(lái)解決再把這些"小問(wèn)題"進(jìn)一步分解成更小的"小問(wèn)題"來(lái)解決一直向下分解，直到每一個(gè)"小問(wèn)題"都可以直接解決"直接解決"就是遞歸出口遞歸的執(zhí)行過(guò)程求解n!的過(guò)程遞歸的執(zhí)行過(guò)程主程序

fact(4)參數(shù)4計(jì)算4*fact(3)參數(shù)3計(jì)算3*fact(2)參數(shù)2計(jì)算2*fact(1)參數(shù)1計(jì)算1*fact(0)參數(shù)0直接定值=1

參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值返回1返回1返回2返回6返回

24對(duì)原問(wèn)題f(s)進(jìn)行分析，假設(shè)出合理的"較小問(wèn)題"f(s')；假設(shè)f(s')是可解的，確定f(s)的解，即給出f(s)與f(s')的關(guān)系；確定特定情況，如f(1)或f(0)的解，由此作為遞歸出口。遞歸設(shè)計(jì)步驟小結(jié)4.2遞歸算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)4.3消除遞歸直接轉(zhuǎn)換法間接轉(zhuǎn)換法遞歸的優(yōu)點(diǎn)可解決復(fù)雜問(wèn)題可縮短程序代碼、提高編程效率遞歸的缺點(diǎn)不能提高程序的運(yùn)行效率在遞歸算法調(diào)用的過(guò)程中，系統(tǒng)為每一層的返回點(diǎn)、局部變量等開(kāi)辟了棧來(lái)存儲(chǔ)，遞歸次數(shù)過(guò)多容易造成棧溢出消除遞歸消除遞歸兩種消除遞歸的方法直接轉(zhuǎn)換法：對(duì)于采用尾遞歸和單向遞歸的算法，可用循環(huán)結(jié)構(gòu)的算法來(lái)代替。間接轉(zhuǎn)換法：用棧來(lái)模擬系統(tǒng)運(yùn)行時(shí)的棧，保存有關(guān)的信息，而用非遞歸算法來(lái)模擬遞歸算法。

直接轉(zhuǎn)換法尾遞歸是指在遞歸算法的函數(shù)中，遞歸調(diào)用語(yǔ)句只有一條，而且是處在函數(shù)的最后，如求解階乘的函數(shù)即尾遞歸。尾遞歸可以方便地用循環(huán)結(jié)構(gòu)來(lái)替代間接轉(zhuǎn)換法間接轉(zhuǎn)換法使用棧保存中間結(jié)果，一般根據(jù)遞歸函數(shù)在執(zhí)行過(guò)程中棧的變化得到小結(jié)4.3消除遞歸直接轉(zhuǎn)換法間接轉(zhuǎn)換法數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)4.4回溯法回溯法是從問(wèn)題的某一種可能出發(fā)，搜索從這種情況出發(fā)所能達(dá)到的所有可能。當(dāng)這一條路走到“盡頭”的時(shí)候，再倒回上一節(jié)點(diǎn)，從另一個(gè)可能出發(fā)，繼續(xù)搜索?；厮菔且环N思想，遞歸是一種解決問(wèn)題的方法。回溯可以用遞歸來(lái)實(shí)現(xiàn)，也可以不用遞歸實(shí)現(xiàn)。回溯法迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙。假設(shè)迷宮的每個(gè)岔路口只有東南西北四個(gè)方向或是這四個(gè)方向的子集?；厮莘ㄋ枷耄阂环N不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若某處可以到達(dá)，則到達(dá)新起點(diǎn)；否則試探下一方向。若所有的方向均沒(méi)有通路，則沿原路返回到前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都試探到。結(jié)果是或找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。遞歸實(shí)現(xiàn)：從入口出發(fā)，每到一個(gè)結(jié)點(diǎn)（岔路口），按東南西北的秩序訪問(wèn)相應(yīng)方向的下一個(gè)結(jié)點(diǎn)，如果相應(yīng)方向沒(méi)有可以訪問(wèn)的結(jié)點(diǎn)，則訪問(wèn)下一個(gè)方向。如果四個(gè)方向全被訪問(wèn)完，則返回到前一個(gè)結(jié)點(diǎn)。直到找到出口或回到入口。迷宮問(wèn)題小結(jié)4.4回溯法數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)4.5遞歸的評(píng)價(jià)可解決適應(yīng)遞歸的復(fù)雜問(wèn)題可縮短程序代碼、提高編程效率不能提高程序的運(yùn)行效率遞歸的評(píng)價(jià)遞歸運(yùn)行效率問(wèn)題例：計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義:求解斐波那契數(shù)列的遞歸算法的偽代碼：

fib(n){ if(n==1或n==2){

return1 }else{ returnfib(n-1)+fib(n-2) }}調(diào)用次數(shù)

Num(k)=2*Fib(k+1)-1算法復(fù)雜度為O(2n),

即指數(shù)量級(jí)

Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)遞歸運(yùn)行效率問(wèn)題小結(jié)4.5遞歸的評(píng)價(jià)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)樹(shù)的定義樹(shù)的相關(guān)概念樹(shù)的表示5.1一般樹(shù)定義樹(shù)是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合當(dāng)n＝0時(shí)稱為空樹(shù)否則，在任一非空樹(shù)中必有一個(gè)稱為根的節(jié)點(diǎn)；當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)特點(diǎn)非空樹(shù)中至少有一個(gè)根節(jié)點(diǎn)樹(shù)中各子樹(shù)是互不相交的集合5.1樹(shù)的概念樹(shù)的結(jié)構(gòu)A只有根節(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)樹(shù)的相關(guān)概念節(jié)點(diǎn)(node)節(jié)點(diǎn)的度(degree)樹(shù)的度葉子節(jié)點(diǎn)(leaf)分支節(jié)點(diǎn)孩子節(jié)點(diǎn)(child)雙親節(jié)點(diǎn)(parents)兄弟節(jié)點(diǎn)(sibling)堂兄弟節(jié)點(diǎn)樹(shù)的層次樹(shù)的深度有序樹(shù)與無(wú)序樹(shù)森林路徑祖先與子孫終端節(jié)點(diǎn)與非終端節(jié)點(diǎn)節(jié)點(diǎn)樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向子樹(shù)的分支節(jié)點(diǎn)的度節(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子度為0的節(jié)點(diǎn)，也叫終端節(jié)點(diǎn)分支節(jié)點(diǎn)度不為0的節(jié)點(diǎn)，也叫非終端節(jié)點(diǎn)內(nèi)部節(jié)點(diǎn)除根節(jié)點(diǎn)之外，分支節(jié)點(diǎn)也稱為內(nèi)部節(jié)點(diǎn)樹(shù)的相關(guān)概念孩子節(jié)點(diǎn)子樹(shù)的根稱為該節(jié)點(diǎn)的孩子雙親孩子節(jié)點(diǎn)的上層節(jié)點(diǎn)叫該節(jié)點(diǎn)的雙親兄弟同一雙親的孩子之間互成為兄弟祖先從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)子孫子樹(shù)中的任一節(jié)點(diǎn)都是該節(jié)點(diǎn)的子孫樹(shù)的相關(guān)概念樹(shù)的度一棵樹(shù)中最大的節(jié)點(diǎn)度數(shù)節(jié)點(diǎn)的層次從根節(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……堂兄弟其雙親在同一層的節(jié)點(diǎn)互稱為堂兄弟深度樹(shù)中節(jié)點(diǎn)的最大層次數(shù)樹(shù)的相關(guān)概念有序樹(shù)樹(shù)中節(jié)點(diǎn)的各子樹(shù)從左至右是有序的最左邊的子樹(shù)的根稱為第一個(gè)孩子最右邊的稱為最后一個(gè)孩子森林m(m

0)棵互不相交的樹(shù)的集合樹(shù)的相關(guān)概念樹(shù)的表示樹(shù)形結(jié)構(gòu)表示法凹入表示法嵌套集合表示法廣義表表示法小結(jié)5.1樹(shù)的概念樹(shù)的定義樹(shù)的相關(guān)概念樹(shù)的表示數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)二叉樹(shù)的遍歷5.2二叉樹(shù)定義二叉樹(shù)是節(jié)點(diǎn)的有限集合或者是空樹(shù)或者由一個(gè)根節(jié)點(diǎn)和兩棵二叉子樹(shù)構(gòu)成左子樹(shù)，右子樹(shù)子樹(shù)不相交特點(diǎn)每個(gè)節(jié)點(diǎn)至多有二棵子樹(shù)不存在度大于2的節(jié)點(diǎn)子樹(shù)有左、右之分，次序不能任意顛倒二叉樹(shù)二叉樹(shù)的五種形態(tài)空二叉樹(shù)右子樹(shù)為空的二叉樹(shù)左子樹(shù)非空的二叉樹(shù)僅有根節(jié)點(diǎn)的二叉樹(shù)左右子樹(shù)均非空的二叉樹(shù)深度為k的滿二叉樹(shù)，有2k-1個(gè)節(jié)點(diǎn)2k-1是深度為K的二叉樹(shù)所具有的最大節(jié)點(diǎn)個(gè)數(shù)滿二叉樹(shù)123114589121367101415特點(diǎn)每層上的節(jié)點(diǎn)數(shù)都達(dá)到最大值只有度為0的節(jié)點(diǎn)和度為2的節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)均有兩棵高度相同的子樹(shù)葉子節(jié)點(diǎn)都在樹(shù)的最下面一層上葉子節(jié)點(diǎn)只出現(xiàn)在最低兩層上對(duì)任意節(jié)點(diǎn)，若其右分支下的子孫最大層次為L(zhǎng)，則其左分支下的子孫的最大層次為L(zhǎng)或L+1除最低層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最低層上只缺少右邊的若干節(jié)點(diǎn)(也可不缺)。完全二叉樹(shù)123114589121367101415滿二叉樹(shù)完全二叉樹(shù)123114589126710性質(zhì)1：在二叉樹(shù)第i層上至多有2i-1

個(gè)節(jié)點(diǎn)(i≥1)證明：當(dāng)i=1時(shí)，只有一個(gè)根節(jié)點(diǎn)。顯然，2i-1

＝20

＝１是對(duì)的假設(shè)對(duì)所有的j(1≤j﹤i)，命題成立即第j層上至多有2j-1

個(gè)節(jié)點(diǎn)那么可以證明j=i時(shí)命題成立歸納假設(shè)：第i-1層上至多有2i-2

個(gè)節(jié)點(diǎn)。由于二叉樹(shù)的每個(gè)節(jié)點(diǎn)的度至多為2，故在第i層上的最大節(jié)點(diǎn)數(shù)為第i-1層上的最大節(jié)點(diǎn)數(shù)的2倍即2*2i-2＝2i-1。二叉樹(shù)的性質(zhì)123114589121367101415性質(zhì)2：深度為k的二叉樹(shù)至多有2k-１個(gè)節(jié)點(diǎn)(k≥1)證明：

由性質(zhì)１可見(jiàn)，深度為k的二叉樹(shù)的最大節(jié)點(diǎn)數(shù)為：二叉樹(shù)的性質(zhì)123114589121367101415性質(zhì)3：對(duì)任意二叉樹(shù)T，如果其終端節(jié)點(diǎn)數(shù)為n0

，度為2的節(jié)點(diǎn)數(shù)為n2,則n0=n2+1。證明：二叉樹(shù)中節(jié)點(diǎn)總數(shù)為：

n=n0+n1+n2 (5-1)二叉樹(shù)的分支數(shù)為：

n1+2*n2 (5-2)因此，節(jié)點(diǎn)總數(shù)為：

n=n1+2*n2+1由(5-1)、(5-2)兩式可得：

n0=n2+1二叉樹(shù)的性質(zhì)1234567性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2

n

+1證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有于是因?yàn)閗是整數(shù),所以二叉樹(shù)的性質(zhì)性質(zhì)5：對(duì)一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的節(jié)點(diǎn)按層序號(hào)編號(hào)(從第1層到

log2n

+1層，每層從左到右)，則對(duì)任一節(jié)點(diǎn)i(1≤i≤n)，有：如果i=1，則節(jié)點(diǎn)i是根節(jié)點(diǎn)，無(wú)雙親，否則，其雙親節(jié)點(diǎn)為：

i/2

如果2i>n，則節(jié)點(diǎn)i無(wú)左孩子(節(jié)點(diǎn)i為葉子節(jié)點(diǎn));否則其左孩子是節(jié)點(diǎn)2i如果2i+1>n，則節(jié)點(diǎn)i無(wú)右孩子;否則其右孩子是節(jié)點(diǎn)2i+1二叉樹(shù)的性質(zhì)123114589126710順序存儲(chǔ)將任意二叉樹(shù)“修補(bǔ)”成完全二叉樹(shù)利用順序表對(duì)數(shù)據(jù)元素進(jìn)行存儲(chǔ)原二叉樹(shù)中空缺的節(jié)點(diǎn)在數(shù)組中相應(yīng)單元置空二叉樹(shù)的存儲(chǔ)123φ5φ7φφ10鏈?zhǔn)酱鎯?chǔ):二叉鏈表節(jié)點(diǎn)包含3個(gè)域：數(shù)據(jù)域和指向左、右子樹(shù)的指針域二叉樹(shù)的存儲(chǔ)LChildDataRChild遍歷（taversal）按一定的規(guī)則和次序走遍二叉樹(shù)的所有節(jié)點(diǎn)使每個(gè)節(jié)點(diǎn)都被訪問(wèn)一次，且只被訪問(wèn)一次訪問(wèn)對(duì)節(jié)點(diǎn)進(jìn)行各種操作遍歷二叉樹(shù)的目的遍歷是對(duì)數(shù)據(jù)進(jìn)行操作的基礎(chǔ)得到二叉樹(shù)中各節(jié)點(diǎn)的一種線性順序使非線性的二叉樹(shù)線性化，簡(jiǎn)化有關(guān)的運(yùn)算和處理二叉樹(shù)的遍歷若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作：訪問(wèn)根節(jié)點(diǎn)；按先序遍歷左子樹(shù)；按先序遍歷右子樹(shù)；返回。先序遍歷先序遍歷序列：ABDECACBDEACBDE若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作：按中序遍歷左子樹(shù)；訪問(wèn)根節(jié)點(diǎn)；按中序遍歷右子樹(shù)；返回。中序遍歷中序遍歷序列：DBEACACBDEACBDE若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作：按后序遍歷左子樹(shù)；按后序遍歷右子樹(shù)；訪問(wèn)根節(jié)點(diǎn)；返回。后序遍歷后序遍歷序列：DEBCAACBDEACBDE二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)二叉樹(shù)的遍歷小結(jié)5.2二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)樹(shù)的存儲(chǔ)樹(shù)與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)的遍歷5.3樹(shù)、森林與二叉樹(shù)樹(shù)的存儲(chǔ)結(jié)構(gòu)特點(diǎn)尋找父結(jié)點(diǎn)只需要O(1)時(shí)間可以從一個(gè)結(jié)點(diǎn)出發(fā)，到其父親，再到其祖父等，從而求出根查詢孩子和兄弟的信息困難雙親表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)155特點(diǎn)孩子結(jié)點(diǎn)的數(shù)據(jù)域存放它們?cè)跀?shù)組中的序號(hào)便于實(shí)現(xiàn)有關(guān)孩子及其子孫的運(yùn)算不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算孩子鏈表表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親孩子鏈表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法樹(shù)與二叉樹(shù)的轉(zhuǎn)換abcdefhgiba^c^d^e^f^^g^h^i^^abcdefghi^^^^^^^^^^二叉樹(shù)與樹(shù)的相互轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^樹(shù)轉(zhuǎn)二叉樹(shù)①加線：在兄弟之間加一連線。②抹線：對(duì)每個(gè)節(jié)點(diǎn)，除了其第一孩子外，去除其與其余孩子之間的關(guān)系。③調(diào)整：將節(jié)點(diǎn)按層次排列，形成二叉樹(shù)。樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空！二叉樹(shù)轉(zhuǎn)樹(shù)①加線：若p節(jié)點(diǎn)是雙親節(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)②抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線③調(diào)整：將節(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)森林轉(zhuǎn)二叉樹(shù)①將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)。②將每棵樹(shù)的根節(jié)點(diǎn)用線相連。③以第一棵樹(shù)根節(jié)點(diǎn)為二叉樹(shù)的根，調(diào)整層次，構(gòu)成二叉樹(shù)形結(jié)構(gòu)。二叉樹(shù)轉(zhuǎn)森林①抹線：將二叉樹(shù)中根節(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)。②還原：將孤立的二叉樹(shù)分別還原成樹(shù)。先序遍歷(與對(duì)應(yīng)的二叉樹(shù)先序遍歷序列一致)若樹(shù)非空，則：訪問(wèn)根結(jié)點(diǎn)依次先序遍歷根的各個(gè)子樹(shù)后序遍歷(與對(duì)應(yīng)的二叉樹(shù)后序遍歷序列一致)若樹(shù)非空，則：依次后序遍歷根的各個(gè)子樹(shù)訪問(wèn)根結(jié)點(diǎn)層次遍歷若樹(shù)非空，訪問(wèn)根結(jié)點(diǎn)。若第1，…i(i≥1)層結(jié)點(diǎn)已被訪問(wèn)，且第i+1層結(jié)點(diǎn)尚未訪問(wèn)，則從左到右依次訪問(wèn)第i+1層。樹(shù)的遍歷樹(shù)的遍歷先序遍歷

A，B，E，F(xiàn)，C，D后序遍歷

E，F(xiàn)，B，C，D，A層次遍歷

A，B，C，D，E，F(xiàn)樹(shù)的存儲(chǔ)樹(shù)與二叉樹(shù)轉(zhuǎn)換森林與二叉樹(shù)轉(zhuǎn)換樹(shù)的遍歷小結(jié)5.3樹(shù)與二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)哈夫曼樹(shù)的相關(guān)概念哈夫曼算法哈夫曼編碼5.4哈夫曼樹(shù)路徑若樹(shù)中存在某個(gè)節(jié)點(diǎn)序列k1,k2,…,kj滿足Ki是ki+1的雙親則該節(jié)點(diǎn)序列是樹(shù)上的一條路徑路徑長(zhǎng)度路徑經(jīng)過(guò)的邊數(shù)，稱為路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度從樹(shù)根到樹(shù)中每一個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度之和哈夫曼樹(shù)的相關(guān)概念節(jié)點(diǎn)的權(quán)給樹(shù)的節(jié)點(diǎn)賦以一定意義的數(shù)值，稱為節(jié)點(diǎn)的權(quán)節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度從樹(shù)根到某節(jié)點(diǎn)的路徑長(zhǎng)度與該節(jié)點(diǎn)的權(quán)的積樹(shù)的帶權(quán)路徑長(zhǎng)度（WPL）

樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和哈夫曼樹(shù)相關(guān)概念2357例：4個(gè)節(jié)點(diǎn)的權(quán)值分別為2，3，5，7。以下是以它們?yōu)槿~子節(jié)點(diǎn)構(gòu)造二叉樹(shù)，計(jì)算各二叉樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。WPL=2*3+3*3+5*2+7*1=32WPL=2*2+3*2+5*2+7*2=34WPL=2*1+3*2+5*3+7*3=44由n個(gè)帶權(quán)葉子節(jié)點(diǎn)構(gòu)成的二叉樹(shù)具有不同形態(tài)其中帶權(quán)路徑長(zhǎng)度（WPL）最小的二叉樹(shù)又叫最優(yōu)二叉樹(shù)，或最佳判定樹(shù)哈夫曼樹(shù)的概念最佳判定樹(shù)以各分?jǐn)?shù)段人數(shù)的比例為權(quán)值構(gòu)造最佳判定樹(shù)使得大部分?jǐn)?shù)據(jù)經(jīng)過(guò)較少次數(shù)的比較得到結(jié)果最佳判定樹(shù)構(gòu)造哈夫曼樹(shù)的方法——哈夫曼算法根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根節(jié)點(diǎn)的二叉樹(shù)，令其權(quán)值為分別wj在森林中選取兩棵根節(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)置新二叉樹(shù)根節(jié)點(diǎn)權(quán)值為其左右子樹(shù)根節(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹(shù)，并將新得到的二叉樹(shù)加入森林中重復(fù)上述步驟，直到只含一棵樹(shù)為止這棵樹(shù)即哈夫曼樹(shù)哈夫曼算法例：已知權(quán)值集合{2，4，6，7，8}，構(gòu)造哈夫曼樹(shù)。哈夫曼編碼電報(bào)通訊中，電文以二進(jìn)制的0,1序列傳送發(fā)送端將電文中的字符轉(zhuǎn)換成0,1的二進(jìn)制序列接收端將收到的0,1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列(譯碼)假定電文是英文，電文字符串由26個(gè)英文字母組成，需要編碼的字符集是{A,B,C,D,…,Z}方法一：等長(zhǎng)的二進(jìn)制編碼方法二：不等長(zhǎng)的二進(jìn)制編碼

A:010B:0101C:01011前綴碼任一字符的編碼，不能是其他字符的前綴哈夫曼編碼假設(shè)字符集D={d1,d2,d3,…,dn}每個(gè)字符di的編碼長(zhǎng)度為li每個(gè)字符di在電文中出現(xiàn)的次數(shù)是ci

則電文的總長(zhǎng)度為:∑ci*li每個(gè)字符di在電文中出現(xiàn)頻度的概率是wi

每個(gè)字符di的編碼長(zhǎng)度為li則電文的平均總長(zhǎng)度為:∑wi*li

哈夫曼編碼尋找最優(yōu)前綴碼的方法用d1,d2,d3,…,dn作為葉子節(jié)點(diǎn)用w1,w2,w3,…,wn作為葉子節(jié)點(diǎn)的權(quán)構(gòu)造最優(yōu)二叉樹(shù)將樹(shù)中每個(gè)節(jié)點(diǎn)的左分支置為0，右分支置為1從根到葉子節(jié)點(diǎn)的一個(gè)標(biāo)號(hào)序列，就是該葉子節(jié)點(diǎn)的編碼例：設(shè)某語(yǔ)言有ABCDEF六種字母，出現(xiàn)的概率分別為0.11，0.12，0.13，0.15，0.22，0.27。A：000B：001C：110D：111E：01F：10小結(jié)5.4哈夫曼樹(shù)哈夫曼樹(shù)的相關(guān)概念哈夫曼算法哈夫曼編碼數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)堆的概念堆的操作堆的算法分析5.5堆堆的概念n個(gè)元素的序列(k1,k2,……kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1可將堆序列看成完全二叉樹(shù)，則堆頂元素（完全二叉樹(shù)的根）必為序列中n個(gè)元素的最小值或最大值大根堆小根堆建堆（大根堆）找到最后一個(gè)分支節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）。對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行向下調(diào)整，即與孩子節(jié)點(diǎn)相比較，把比自己大并且是最大的孩子節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)交換位置，如果發(fā)生交換，到達(dá)新位置的節(jié)點(diǎn)將繼續(xù)向下調(diào)整，直到不發(fā)生交換位置或到達(dá)葉子節(jié)點(diǎn)。從后向前對(duì)所有分支節(jié)點(diǎn)進(jìn)行向下調(diào)整。直到對(duì)根節(jié)點(diǎn)完成向下調(diào)整。堆的操作例：設(shè)節(jié)點(diǎn)分別為3、7、5、13、2、17、11，建立大根堆。添加節(jié)點(diǎn)把這個(gè)節(jié)點(diǎn)加到順序表的末尾從下向上調(diào)整至合適位置刪除節(jié)點(diǎn)把待刪除的節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換位置刪除最后一個(gè)節(jié)點(diǎn)把與刪除節(jié)點(diǎn)交換位置的節(jié)點(diǎn)向下調(diào)整至合適位置堆的操作在堆中，向上調(diào)整和向下調(diào)整的操作次數(shù)不會(huì)大于二叉樹(shù)的層數(shù)，所以單個(gè)節(jié)點(diǎn)的調(diào)整，其算法復(fù)雜度為log2n。建堆時(shí)，需要對(duì)所有分支節(jié)點(diǎn)做向下調(diào)整，在完全二叉樹(shù)中分支節(jié)點(diǎn)的個(gè)數(shù)為n/2，所以建堆的算法復(fù)雜度為O(nlog2n)。增加節(jié)點(diǎn)和刪除節(jié)點(diǎn)時(shí)，只需要對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行向上調(diào)整或向下調(diào)整，所以其算法復(fù)雜度為O(log2n)。堆的算法分析堆的插入和刪除操作只需要進(jìn)行O(log2n)次的交換操作，明顯優(yōu)于順序表的O(n)次操作。相較于鏈表，堆在邏輯上存在一定的順序，并且兼具二叉樹(shù)的特點(diǎn)，可以在算法的優(yōu)化上起到明顯的作用。堆的算法分析小結(jié)5.5堆堆的概念堆的操作堆的算法分析數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)圖的相關(guān)術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)6.1圖的概念圖(Graph)G=(V，E)V是非空有限集合，其元素稱為頂點(diǎn)E是邊的集合,頂點(diǎn)偶對(duì)稱為邊圖的相關(guān)術(shù)語(yǔ)有向圖G1(b)無(wú)向圖G2有向圖G1=(V1，E1)V1={v1，v2，v3，v4}E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}弧有序的頂點(diǎn)偶對(duì)：<x，y>

有向圖G1XY弧尾弧頭無(wú)向圖G2=(V2，E2)V2={v1，v2，v3，v4，v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}邊無(wú)序的頂點(diǎn)偶對(duì)(x，y)(b)無(wú)向圖G2完全圖(completedgraph)無(wú)向圖，邊的取值范圍是0到n(n-1)/2有n(n-1)/2條邊的無(wú)向圖有向圖，邊的取值范圍是0到n(n-1)有n(n-1)條弧的有向圖鄰接點(diǎn)(adjacent)無(wú)向圖G=(V，E)，若邊(v，v’)∈E頂點(diǎn)v和v’互為鄰接點(diǎn)，即v和v’相鄰接邊(v,v’)與頂點(diǎn)v,v’相關(guān)聯(lián)有向圖G=(V,E)，如果邊<v,v’>∈E頂點(diǎn)v鄰接到v’,或v’鄰接于v弧<v,v’>與頂點(diǎn)v,v’相關(guān)聯(lián)無(wú)向圖度與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)有向圖入度出度頂點(diǎn)v的度為：TD(v)=ID(v)+OD(v)有n個(gè)頂點(diǎn)，e條邊或弧的圖，滿足關(guān)系:子圖

假設(shè)有兩個(gè)圖G=(V，E)G'=(V'，E')如果V'包含于V，E'包含于E，則稱G'是G的子圖(b)G2的子圖(a)G1的子圖G1(b)

G2路徑在無(wú)向圖中,若存在一個(gè)頂點(diǎn)序列 vi,vp1,vp2,…,vpm，vj使得(vi,vp1)、(vp1,vp2),...,(vpm,vj)∈E則稱頂點(diǎn)vi到vj存在一條路徑如果G是有向圖，則路徑也是有向的頂點(diǎn)序列應(yīng)滿足<vi,vp1>,<vp1,vp2>,...,<vpm,vj>∈E路徑的長(zhǎng)度路徑上的邊的或弧的數(shù)目簡(jiǎn)單路徑頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)簡(jiǎn)單回路除了第一頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路權(quán)(weight)在圖的每條邊上加上一個(gè)數(shù)字作權(quán)網(wǎng)(network)帶權(quán)的圖稱為網(wǎng)鄰接矩陣鄰接矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣若G是一個(gè)具有n頂點(diǎn)的圖則G的鄰接矩陣是如下定義的n×n矩陣：圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖的鄰接矩陣不一定對(duì)稱有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和鄰接矩陣的特點(diǎn)網(wǎng)的鄰接矩陣定義：網(wǎng)的鄰接矩陣頂點(diǎn)表頂點(diǎn)表的每個(gè)結(jié)點(diǎn)中指針域指向邊表的第一個(gè)結(jié)點(diǎn)數(shù)據(jù)域存儲(chǔ)頂點(diǎn)的名稱或其它信息頂點(diǎn)表的每個(gè)結(jié)點(diǎn)，相當(dāng)于邊表頭結(jié)點(diǎn)邊表把同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)鏈表中，鏈表的每一個(gè)結(jié)點(diǎn)代表一條邊邊表結(jié)點(diǎn)中保存著與某頂點(diǎn)相關(guān)聯(lián)的另一頂點(diǎn)，和指向下一個(gè)表結(jié)點(diǎn)的指針圖的鄰接表表示法鄰接表邊表結(jié)點(diǎn)vexdatafirstarcadjvexnext頂點(diǎn)表結(jié)點(diǎn)圖的鄰接表表示法圖的鄰接表表示法有向圖的鄰接表鄰接表V1V2V4V5V3V7V6V8在弧結(jié)點(diǎn)中有四個(gè)域：尾域(tailvex)和頭域(headvex)分別指示弧尾和弧頭這兩個(gè)頂點(diǎn)在圖中的編號(hào)。鏈域(hlink)：指向弧頭相同的下一條弧。鏈域(tlink)：指向指向弧尾相同的下一條弧。十字鏈表tailvexheadvexhlinktlink弧頭相同的弧在同一鏈表上，弧尾相同的弧也是在同一鏈表上。它們的頭結(jié)點(diǎn)即為頂點(diǎn)結(jié)點(diǎn)，它由三個(gè)域組成data域存儲(chǔ)和頂點(diǎn)相關(guān)的信息firstin域和firstout域分別指向以該頂點(diǎn)為弧頭或弧尾的第一個(gè)弧結(jié)點(diǎn)。十字鏈表datafirstinfirstout十字鏈表tailvexheadvexhlinktlinkdatafirstinfirstout用一維數(shù)組存儲(chǔ)圖中所有的邊每個(gè)元素用于存儲(chǔ)一條邊的起點(diǎn)、終點(diǎn)和權(quán)(對(duì)于無(wú)向圖，可選定邊的任一端點(diǎn)為起點(diǎn)或終點(diǎn))各邊在數(shù)組中的順序可任意安排，也可根據(jù)具體要求而定邊集數(shù)組只是存儲(chǔ)圖中所有邊的信息，若需要存儲(chǔ)頂點(diǎn)信息，同樣需要一個(gè)具有n個(gè)元素的一維數(shù)組邊集數(shù)組邊集數(shù)組小結(jié)6.1圖的概念圖的相關(guān)術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)深度優(yōu)先遍歷廣度優(yōu)先遍歷6.2圖的遍歷從圖中某頂點(diǎn)出發(fā)，沿一些邊訪問(wèn)圖中頂點(diǎn)，使每個(gè)頂點(diǎn)都被訪問(wèn)到，且僅被訪問(wèn)一次無(wú)重復(fù)，無(wú)遺漏關(guān)鍵點(diǎn)圖中可能存在回路圖的頂點(diǎn)可能與其它頂點(diǎn)相通,在訪問(wèn)完某頂點(diǎn)后,可能沿著某些邊回到曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)為避免重復(fù)訪問(wèn),可設(shè)輔助數(shù)組visited[]將其初始化為0遍歷時(shí),如果某頂點(diǎn)i被訪問(wèn),將visited[i]置為1以此防止頂點(diǎn)i被多次訪問(wèn)圖的遍歷圖的深度優(yōu)先搜（DFS）索類似樹(shù)的深度遍歷設(shè)初始狀態(tài)：圖中所有頂點(diǎn)都沒(méi)被訪問(wèn)過(guò)從圖中某一頂點(diǎn)v0出發(fā)，訪問(wèn)v0，然后訪問(wèn)與v0鄰接,但未被訪問(wèn)過(guò)的任一頂點(diǎn)v1接著訪問(wèn)與v1鄰接，但未被訪問(wèn)過(guò)的任意頂點(diǎn)V2當(dāng)達(dá)到某頂點(diǎn)時(shí)，發(fā)現(xiàn)其所有鄰接頂點(diǎn)均被訪問(wèn)過(guò)，則退回到最近被訪問(wèn)過(guò)的前一頂點(diǎn)若它還有鄰接點(diǎn)未被訪問(wèn)過(guò)，從未被訪問(wèn)過(guò)的頂點(diǎn)中，任取一頂點(diǎn),重復(fù)這一過(guò)程若所有鄰接頂點(diǎn)被訪問(wèn)過(guò)，則再回退如此重復(fù)，直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止深度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷（BFS）類似于樹(shù)的層次遍歷假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都沒(méi)被訪問(wèn)過(guò)從圖中某一頂點(diǎn)v0出發(fā)，訪問(wèn)v0然后訪問(wèn)v0的全部鄰接點(diǎn)v1，v2，...，vt再?gòu)倪@些被訪問(wèn)的頂點(diǎn)出發(fā)，逐次訪問(wèn)它們的鄰接點(diǎn)(已被訪問(wèn)的頂點(diǎn)除外)依此類推，直到所有頂點(diǎn)都被訪問(wèn)為止廣度優(yōu)先遍歷廣度優(yōu)先遍歷小結(jié)6.2圖的遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)拓?fù)渑判騿?wèn)題關(guān)鍵路徑問(wèn)題最短路徑問(wèn)題6.3圖的應(yīng)用最小生成樹(shù)連通無(wú)向圖中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱v和v'是連通的連通圖如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則是連通圖連通分量無(wú)向圖的極大連通子圖連通圖只有一個(gè)連通分量，即其自身非連通的無(wú)向圖有多個(gè)連通分量最小生成樹(shù)15732461573246強(qiáng)連通圖有向圖中，如果每一對(duì)頂點(diǎn)vi,vj∈V(vi!=vj)，從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖稱作強(qiáng)連通分量強(qiáng)連通圖的強(qiáng)連通分量是其自身非強(qiáng)連通的有向圖可能有多個(gè)強(qiáng)連通分量最小生成樹(shù)123245136生成樹(shù)連通最小生成樹(shù)是一個(gè)極小連通子圖它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊最小生成樹(shù)生成樹(shù)一個(gè)圖可以有許多棵不同的生成樹(shù)生成樹(shù)具有以下共同特點(diǎn)：頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通最小生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)最小生成樹(shù)設(shè)G=(V，E)是一個(gè)連通圖則從圖中任一頂點(diǎn)出發(fā)，遍歷圖G時(shí)，得到一個(gè)邊集T(G)，T(G)與圖中所有頂點(diǎn)一起構(gòu)成圖G的極小連通子圖，它是連通圖的一棵生成樹(shù)。由DFS得到的是深度優(yōu)先生成樹(shù)由BFS得到的為廣度優(yōu)先生成樹(shù)連通無(wú)向最小生成樹(shù)V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹(shù)這些連通分量的生成樹(shù)組成非連通圖的生成森林非連通最小生成樹(shù)ABLMCFDEGHKIJABLMCFJDEGHKI最小生成樹(shù)不是唯一的從不同的頂點(diǎn)出發(fā)，能得到不同的生成樹(shù)連通網(wǎng)絡(luò)G=(V,E)各邊帶權(quán)生成樹(shù)各邊帶權(quán)生成樹(shù)的權(quán)生成樹(shù)各邊權(quán)值的和最小生成樹(shù)權(quán)值最小的生成樹(shù)最小生成樹(shù)1654327131791812752410最小生成樹(shù)問(wèn)題提出在n個(gè)城市間建立通信網(wǎng)絡(luò)頂點(diǎn)—表示城市權(quán)—城市間建立通信線路所需花費(fèi)代價(jià)希望找到一條路徑，使建立該通信網(wǎng)所需花費(fèi)的總代價(jià)最小路徑上各邊權(quán)值的和最小問(wèn)題分析n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路如何在可能的線路中選擇n-1條邊，把所有城市連起來(lái)，且總耗費(fèi)(各邊權(quán)值之和)最小找圖中的最小生成樹(shù)貪心（Prim）在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇算法得到的是在某種意義上的局部最優(yōu)解貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但是在求最小生成樹(shù)問(wèn)題上適用貪心算法克魯斯卡爾（Kruskal）算法尋找每一步當(dāng)前情況下的最小路徑不能形成回路無(wú)環(huán)圖（DAG）一個(gè)無(wú)環(huán)（回路）的有向圖叫做有向無(wú)環(huán)圖AOV網(wǎng)頂點(diǎn)表示活動(dòng)的網(wǎng)頂點(diǎn)表示活動(dòng)弧表示活動(dòng)間的先后關(guān)系A(chǔ)OV網(wǎng)中不允許有回路拓?fù)渑判騿?wèn)題拓?fù)渑判騿?wèn)題提出問(wèn)題提出如果現(xiàn)在只有一名工人做整個(gè)工程，每次只能做一項(xiàng)活動(dòng)，他應(yīng)怎樣安排所做事情的前后順序，才能順利完成此項(xiàng)工程。拓?fù)渑判蛲負(fù)渑判虻姆椒◤挠邢驁D中任選一個(gè)入度為0的頂點(diǎn)，并訪問(wèn)對(duì)所有以它為尾的弧，弧頭頂點(diǎn)的入度減1刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已訪問(wèn)，或當(dāng)圖中不存在度為0的頂點(diǎn)為止不存在度為0的頂點(diǎn):存在環(huán)拓?fù)渑判蚺e例V1：材料進(jìn)場(chǎng) V2：閥門試壓 V3：預(yù)埋預(yù)留 V4：設(shè)備安裝V5：管道預(yù)制 V6：支吊架安裝 V7：?jiǎn)螜C(jī)試運(yùn)轉(zhuǎn) V8：管道安裝V9：試壓、閉水 V10：衛(wèi)生器具安裝 V11：油漆防腐V12：沖洗消毒 V13：驗(yàn)收拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蛲負(fù)湫蛄校篤1→V2→V3→V4→V5→V6→V7→V8→V9→V10→V11→V12→V13或：V1→V2→V5→V3→V6→V8→V9→V11→V10→V12→V4→V7→V13AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏年P(guān)鍵路徑問(wèn)題987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4用有向圖表示工程計(jì)劃，頂點(diǎn)表示事件，弧表示活動(dòng)每個(gè)頂點(diǎn)表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始問(wèn)題描述一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件V1表示工程開(kāi)始，V9表示