[教育]算法_抽象數(shù)據(jù)型-資料下載頁
2025-02-18 08:34本頁面
【正文】 (算法 )。 ：就是對用自然語言等描述的算法逐步細(xì)致化、精確化和形式化，這一階段可能包括多步求精。當(dāng)逐步求精到某一步時(shí)，根據(jù)程序中所使用的數(shù)據(jù)形式，定義若干 ADT，并且用 ADT中的操作代替對應(yīng)的非形式語句； ：對每個(gè) ADT，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示數(shù)學(xué)模型，并用相應(yīng)的函數(shù)實(shí)現(xiàn)每個(gè)操作。 例 問題描述： 一個(gè)具有多條通路的交叉路口 ,當(dāng)允許某些通路上 的車輛在交叉路口拐彎時(shí) ,必須對其他一些通路上 的車輛加以限制 ,不允許同時(shí)在交叉路口拐彎 ,以免 發(fā)生碰撞 .所有這些可能的拐彎組成一個(gè)集合 . 有 5條組成的交叉路口 ,其中有 2條路是單行道 ,把從一條路到另一條路的通路稱為拐彎 ,有的拐彎可以同時(shí)通過 ,有些拐彎不能同時(shí)通過 ,共有 13個(gè)拐彎 .要求 : (1)設(shè)置一組交通燈 ,實(shí)現(xiàn)安全管理 (2)使交通燈的數(shù)目最少 . 基本要求：把這個(gè)集合分成盡可能少的組 ,使得每組中所有的拐彎都能同時(shí)進(jìn)行而不發(fā)生碰撞 . 這樣 ,每組對應(yīng)一個(gè)指揮燈 ,因而實(shí)現(xiàn)了用盡可能少的指非燈完成交叉路口的管理 . 模型化： (1)用圖作為交叉路口的數(shù)學(xué)模型 。(2)每個(gè)拐彎對應(yīng)圖中的一個(gè)頂點(diǎn)。(3)若兩個(gè)拐彎不能同時(shí)進(jìn)行 ,則用用一條邊把這兩個(gè)拐彎所對應(yīng)的兩個(gè)結(jié)點(diǎn)連接起來 ,并且說這兩個(gè)頂點(diǎn)是相鄰的。 確定算法： (1)窮舉法 。(2)試探法 (3)貪心法 貪心算法的思想是首先用第一種顏色對 圖中盡可能多的頂點(diǎn)著色 (盡可能多表現(xiàn) 出貪心 )然后用第二種顏色對余下的頂點(diǎn)中 盡可能多的頂點(diǎn)著色如此等等，直至所有 的頂點(diǎn)都著完色。 當(dāng)用一種新顏色對余下的頂點(diǎn)著色時(shí)我們采取下列步驟 : （ 1）選取某個(gè)未著色的頂點(diǎn)，并且用新顏色對它著色。 （ 2）掃描所有未著色的頂點(diǎn)集，對其中的每個(gè)頂點(diǎn)，確定它是否與已著新顏色的任何頂點(diǎn)相鄰。若不相鄰，則用新顏色對它著色。 用 C++語言描述的 貧心 算法如下 : void greedy(GRAPH G, SET newclr) /*類型 GRAPH和 SET有待具體說明 */ /*本程序把 G中可以著同一色的頂點(diǎn)放入 newclr*/ { (1) newclr=F (2) while (G中有未著色的頂點(diǎn) v) (3) if(v不與 newclr中的任何頂點(diǎn)相鄰 ){ (4) 對 v著色； (5) 將 v放入 newclr； } }。 其中， G是被著色的圖， newclr的初值為空，算法執(zhí)行的結(jié)果形成可以著相同顏色的頂點(diǎn)的集合 newclr。只要重復(fù)調(diào)用 greedy算法，直到圖中的所有頂點(diǎn)都被著色為止，即可求出問題的解。 逐步求精：第一步求精： void greedy(GRAPH G, SET newclr) /*類型 GRAPH和 SET有待具體說明 */ { int found。 (1) newclr=F 。 (2) while(G中有未著色的頂點(diǎn) v){ () found=0。/*found的初值為 false*/ () for (newclr中的每一個(gè)頂點(diǎn) w） () if(v與 w相鄰 ) () found=1。 () if(found==0){ /*v與 newclr中的任何頂點(diǎn)都不相鄰 */ (4) 對 v著色； (5) 將 v放入 newclr； } } }。 逐步求精：第二步求精： void greedy(GRAPH G, SET newclr) { int found。 newclr=%。 v=G中第一個(gè)未著色的頂點(diǎn)； while (v!=0){ /*G中還有未著色的頂點(diǎn) v*/ found=0。 w=newclr中的第一個(gè)頂點(diǎn)； while(w!=0){ /*newclr中的頂點(diǎn)還沒取盡 */ if(v與 w相鄰 ) found=1。 w=newclr中的下個(gè)頂點(diǎn)； }。 if(found==0){ 對 v著色；將 v放入 newclr； } v=G中下一個(gè)未著色的頂點(diǎn)； } 。 } 逐步求精：第三步求精： 由上一步求精的結(jié)果可見，算法中大部分操作都?xì)w結(jié)為對圖和集合的操作。設(shè)G和 S分別是抽象數(shù)據(jù)型 GRAPH和 SET的實(shí)例，我們在 G上規(guī)定如下操作： (1)FIRSTG(G)返回 G中的第一個(gè)未加標(biāo)記的（未著色的）元素；若 G中沒有這樣的元素存在，則返回 NULL。 (2)EDGE(v,w,G)若 v和 w在 G中相鄰，則返回 true，否則返回 false。 (3)MARK(v,G)標(biāo)記 G中的元素 v。 (4)ADDG(v,G)將元素 v放入 G中。 (5)NEXTG(G)返回 G中下一個(gè)未標(biāo)記得元素，若 G中沒有這樣的元素存在，則返回 NUL。 在 S上規(guī)定如下操作： (1)MAKENULL(S)將集合 S置空。 (2)FIRSTS(S)返回 S中的第一個(gè)元素；若 S為空集，則返回 NULL。 (3)NEXTS(S)返回 S中的下一個(gè)元素；若 S中沒有下一個(gè)元素，則返回 NULL。 (4)ADDS(v,S)將 v放入 S中。 逐步求精：第三步求精： void greedy(GRAPH G, SET newclr) /*類型 GRAPH和 SET有待說明 */ { int found。 elementtype v,w。/*elementtype可以自定義 */ MAKENULL(newclr)。 v=FIRSTG(G)。 while(v!=NULL){ found=0。 w=FIRSTS(newclr)。 while(w!=NULL){ if(EDGE(v,w,G)) found=1。 w=NEXTS(newclr)。 }。 v=NEXTG(G)。 } }。 ADT的實(shí)現(xiàn)： 按上述函數(shù)，最后一步工作就是給出類型 elementtype的定義和實(shí)現(xiàn)抽象數(shù)據(jù)型 GRAPH及 SET。此后，上述函數(shù)就是可執(zhí)的程序了。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1