數據結構與算法講解-資料下載頁

　　

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