汽車(chē)課件第十四講

第十四講算法基礎(chǔ)和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)主要教學(xué)內(nèi)容算法基礎(chǔ)1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2小結(jié)3學(xué)習(xí)目標(biāo)1

了解算法的基本概念；掌握算法的三種基本結(jié)構(gòu)；了解常見(jiàn)算法。2

掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、物理存儲(chǔ)結(jié)構(gòu)的基本概念。3

掌握線性列表、堆棧、隊(duì)列的基本操作；掌握樹(shù)和二叉樹(shù)的概念；掌握二叉樹(shù)的特點(diǎn)、性質(zhì)和遍歷方案。重點(diǎn)與難點(diǎn)

算法的概念、特征與設(shè)計(jì)原則，算法的描述與常用算法的實(shí)現(xiàn)思想為本講的重點(diǎn)；數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)為本講的難點(diǎn)。1.算法基礎(chǔ)算法是指解決問(wèn)題的方法和步驟，是對(duì)解決某一問(wèn)題方案的準(zhǔn)確描述。算法Algorithm如：求圓的面積問(wèn)題（s=πr2）

，把這個(gè)問(wèn)題交給計(jì)算機(jī)來(lái)處理，過(guò)程為先輸入圓的半徑，然后按面積計(jì)算公式計(jì)算，最后輸出計(jì)算結(jié)果。描述如下：1.輸入圓的半徑2.計(jì)算圓的面積；s=πr2；3.輸出圓的面積s；上述這種解決問(wèn)題的方法就是一個(gè)算法。算法的特征有窮性有輸入有輸出確定性可行性算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。算法中的所有運(yùn)算都是基本的，都可以通過(guò)基本運(yùn)算有限次實(shí)現(xiàn)之。算法的每一種運(yùn)算有確定的意義，執(zhí)行何種動(dòng)作無(wú)二義性，目的明確。1.1算法的概念算法設(shè)計(jì)的原則正確性高效率與低存儲(chǔ)量需求可讀性健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理。程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。1.1算法的概念時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。

空間復(fù)雜度是指算法需要消耗的空間資源。算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，記作：T(n)=O(f(n))

（a）x:=x+1（b）fori:=1tondox:=x+1（c）forj:=1tondofork:=1tondox:=x+1基本操作:加法操作時(shí)間復(fù)雜度:（a）O(1)（b）O(n)（c）O(n2)算法的復(fù)雜度1.1算法的概念⑴一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f(n)，因此，算法的時(shí)間復(fù)雜度記為T(mén)(n)=O(f(n))。隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率成正比，所以f(n)越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。⑵在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找出T(n)的同數(shù)量級(jí)（它的同數(shù)量級(jí)有1，Log2n，n，nLog2n，n2，n3，2n，n?。页龊?，f(n)=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n)=O(f(n))。注意：隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。算法的復(fù)雜度1.1算法的概念算法的復(fù)雜度例：算法：

for（i=1;i<=n;++i）

{

for(j=1;j<=n;++j)

{

c[i][j]=0;//該步驟屬于基本操作執(zhí)行次數(shù)：n2次

for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j];//該步驟屬于基本操作執(zhí)行次數(shù)：n3次

}

}時(shí)間復(fù)雜度是多少？1.2算法的三種基本結(jié)構(gòu)分支結(jié)構(gòu)包括簡(jiǎn)單分支與選擇分支結(jié)構(gòu)。選擇分支結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行。順序結(jié)構(gòu)是指按程序語(yǔ)句行的編寫(xiě)順序，逐條執(zhí)行。循環(huán)結(jié)構(gòu)是指按照一定的條件反復(fù)執(zhí)行某一或某些處理步驟的結(jié)構(gòu)。有兩種循環(huán)語(yǔ)句：一種是先判斷條件再執(zhí)行循環(huán)體的結(jié)構(gòu)稱為當(dāng)型循環(huán)結(jié)構(gòu)；另一種是先執(zhí)行循環(huán)體后判斷條件的結(jié)構(gòu)稱為直到型循環(huán)結(jié)構(gòu)。順序分支循環(huán)圓角矩形用于算法的起止平行四邊形用于描述算法的輸入與輸出矩形用于算法數(shù)據(jù)的處理棱形框用于算法的判斷有向箭頭用于算法的流程指標(biāo)連接點(diǎn)用于標(biāo)識(shí)流程圖兩個(gè)部分的連接位置1.2算法的三種基本結(jié)構(gòu)輸入/輸出框處理框條件框起止框1.2算法的三種基本結(jié)構(gòu)圖1算法c=a+b的流程圖輸入a、b的值開(kāi)始c=a+b結(jié)束輸出c的值順序1.2算法的三種基本結(jié)構(gòu)圖2簡(jiǎn)單分支圖3選擇分支條件語(yǔ)句組1否是條件語(yǔ)句組1是否語(yǔ)句組2分支圖4把兩個(gè)數(shù)由大到小輸出的算法描述輸出a、b是否a>b嗎？輸入a、b的值開(kāi)始結(jié)束輸出b、a例：計(jì)算機(jī)基礎(chǔ)科學(xué)系1.2算法的三種基本結(jié)構(gòu)是條件循環(huán)體否圖5當(dāng)型循環(huán)是否i<=99S=0i=1S=S+ii=i+2輸出S開(kāi)始結(jié)束圖6計(jì)算1+3+5+7+...+99的當(dāng)型循環(huán)循環(huán)例：計(jì)算機(jī)基礎(chǔ)科學(xué)系1.2算法的三種基本結(jié)構(gòu)圖7直到型循環(huán)否條件循環(huán)體是否是i>99？S=0i=1S=S+ii=i+2開(kāi)始結(jié)束輸出S圖8計(jì)算1+3+5+7+...+99的直到型循環(huán)循環(huán)例：1.3常見(jiàn)算法介紹i=1，a(1)=23，a(4)=8<23，j=4；a(1)與a(4)交換。i=2，a(2)=78，a(3)=45<78，j=3；a(4)=23<45，k=4；a(2)與a(4)交換。i=4，a(4)=78,a(5)=45<78，j=5；a(4)與a(5)交換。i=5，a(5)=78,a(6)=56<78，j=6；a(3)與a(5)交換。i=3，a(3)=45,a(5)=32<45，j=5；a(3)與a(5)交換。⑴選擇排序1.排序算法1.3常見(jiàn)算法介紹

第一步：從最后一個(gè)數(shù)開(kāi)始與前面的數(shù)比較56>32,32>8,位置不變；8<45,兩者交換位置；8<78，交換位置，8<23，交換位置。得出最小值為8。其它同理。⑵冒泡排序1.3常見(jiàn)算法介紹（3）插入排序插入排序是最常用的排序技術(shù)之一，經(jīng)常在撲克牌游戲中使用。游戲人員將每張拿到的牌插入到手中合適的位置，以便手中的牌以一定的順序排列。1.3常見(jiàn)算法介紹2.查找算法⑴順序查找1.3常見(jiàn)算法介紹⑵折半查找1.3常見(jiàn)算法介紹3.遞歸算法2.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)

數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上被廣泛使用的術(shù)語(yǔ)，它被用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排，它是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式。數(shù)據(jù)結(jié)構(gòu)作為一門(mén)學(xué)科，研究的內(nèi)容主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)及對(duì)數(shù)據(jù)的操作（或算法）三個(gè)方面。2.1線性列表線性表是一個(gè)含有n≥0個(gè)結(jié)點(diǎn)（數(shù)據(jù)元素）的有限序列，其中的結(jié)點(diǎn)，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。線性表可分為廣義線性表與限制線性表。廣義線性表：可以在任何位置插入與刪除數(shù)據(jù)；限制線性表：只能在列表兩端增加與刪除數(shù)據(jù)，如堆棧，隊(duì)列2.2堆棧圖10出棧操作棧的操作有很多，基本操作有：入棧，出棧和空三種。圖9入棧操作堆棧是一種執(zhí)行“后進(jìn)先出”算法的數(shù)據(jù)結(jié)構(gòu)。2.3隊(duì)列隊(duì)列只允許在數(shù)據(jù)表的前端進(jìn)行刪除操作，而在數(shù)據(jù)列表的后端進(jìn)行插入操作。圖11

計(jì)算機(jī)隊(duì)列2.3隊(duì)列隊(duì)列的操作也很多，基本操作有：入列、出列和空三種圖12入列操作圖13出列操作2.4樹(shù)樹(shù)的基本概念二叉樹(shù)根結(jié)點(diǎn)父結(jié)點(diǎn)子結(jié)點(diǎn)葉子結(jié)點(diǎn)兄弟結(jié)點(diǎn)的度樹(shù)的高（深）度2.4樹(shù)ABCDEFGHIJKLA:

是根結(jié)點(diǎn),同時(shí)是B、C、D結(jié)點(diǎn)的父結(jié)點(diǎn)或雙親結(jié)點(diǎn)B:

是E、F的父結(jié)點(diǎn)，E、F是B的子結(jié)點(diǎn)或孩子結(jié)點(diǎn)J、K、L、F、G、I：是葉子節(jié)點(diǎn)B的子孫為E、F、J、KB,C,D互為兄弟結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)L的層次：4樹(shù)的高度：42.4樹(shù)樹(shù)的種類(lèi)有很多，如無(wú)序樹(shù)、有序樹(shù)、二叉樹(shù)和完全二叉樹(shù)等。1、二叉樹(shù)的概念二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的有序樹(shù)，這兩個(gè)子樹(shù)分別稱為左子樹(shù)和右子樹(shù)，而每一棵子樹(shù)又是二叉樹(shù)。2、二叉樹(shù)的特點(diǎn)每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)，二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能顛倒二叉樹(shù)的五種基本形態(tài)空二叉樹(shù)僅有根結(jié)點(diǎn)右子樹(shù)為空左子樹(shù)為空左右子樹(shù)均非空2.4樹(shù)3.二叉樹(shù)的性質(zhì)性質(zhì)1：二叉樹(shù)的第i層上至多有2i-1（i

1）個(gè)結(jié)點(diǎn)。證明：根據(jù)二叉樹(shù)的特點(diǎn)，結(jié)論是顯然的。（用歸納法證明）。性質(zhì)2：深度為H的二叉樹(shù)中至多2H-1個(gè)結(jié)點(diǎn)。性質(zhì)3：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小高度H為[log2n]+1。2.4樹(shù)(1)前序遍歷(NLR)(2)中序遍歷(LNR)(3)后序遍歷(LRN)訪問(wèn)根結(jié)點(diǎn)按照前序遍歷順序訪問(wèn)根結(jié)點(diǎn)的左子樹(shù)按照前序遍歷順序訪問(wèn)根結(jié)點(diǎn)的右子樹(shù)按中序遍歷順序訪問(wèn)根結(jié)點(diǎn)的左子樹(shù)訪問(wèn)根結(jié)點(diǎn)按中序遍歷順序訪問(wèn)根結(jié)點(diǎn)的右子樹(shù)按后序遍歷順序訪問(wèn)根結(jié)點(diǎn)的左子樹(shù)按后序遍歷順序訪問(wèn)根結(jié)點(diǎn)的右子樹(shù)訪問(wèn)根結(jié)點(diǎn)（4）二叉樹(shù)的遍歷2.4樹(shù)前序遍歷(根左右)：中序遍歷(左根右)

：后序遍歷(左右根)

：ABCDEFCB