數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教案

1、實(shí)驗(yàn)教案 實(shí)驗(yàn)一 多項(xiàng)式的加減法難點(diǎn)：1. 多項(xiàng)式的表示2. 如何讀入多項(xiàng)式到適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)中3. 如何顯示多項(xiàng)式重點(diǎn)：編程實(shí)現(xiàn)多項(xiàng)式的加減法詳細(xì)講解如下：1、存儲(chǔ)多項(xiàng)式的數(shù)據(jù)結(jié)構(gòu)本實(shí)驗(yàn)中并沒有規(guī)定多項(xiàng)式該用什么樣的數(shù)據(jù)結(jié)構(gòu)表示。一個(gè)多項(xiàng)式可以使用一個(gè)鏈表表示，也可以用一個(gè)隊(duì)列表示一個(gè)多項(xiàng)式等等，完全可以由大家設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)存放多項(xiàng)式。2、用鏈表表示多項(xiàng)式如果先擇用鏈表表示多項(xiàng)式，需要考慮（1）多項(xiàng)式的讀取用戶輸入多項(xiàng)式是按照降冪或者升冪的方式輸入，還是不按照冪的升高或降低排列，隨意輸入的？如果是隨意輸入，則在進(jìn)行多項(xiàng)式加減法的時(shí)候需要進(jìn)行更多的處理，比如進(jìn)行運(yùn)算前，必須先排序等等處理方法

2、。（2）鏈表的構(gòu)造詳細(xì)情況見發(fā)放的c語(yǔ)言實(shí)驗(yàn)教案中的鏈表一項(xiàng)。3、用隊(duì)列表示多項(xiàng)式如果用隊(duì)列表示多項(xiàng)式，也需要注意，一個(gè)隊(duì)列對(duì)應(yīng)一個(gè)多項(xiàng)式。隊(duì)列中的一項(xiàng)是多項(xiàng)式中的一項(xiàng)，隊(duì)列中的元素也是經(jīng)過降冪或者升冪排練的。如果使用STL中的隊(duì)列也是可以的。實(shí)驗(yàn)教案 實(shí)驗(yàn)二 棧和隊(duì)列的應(yīng)用難點(diǎn)：1. 掌握STL中棧的使用2. 具體編程自己實(shí)現(xiàn)棧和隊(duì)列重點(diǎn)：1. 掌握STL中棧的使用很重要，掌握了STL中棧的使用，就可以舉一反三，掌握STL中隊(duì)列的使用，能為后序的實(shí)驗(yàn)打下基礎(chǔ)。2. 理解棧的基本原理，自己編程實(shí)現(xiàn)棧中的幾個(gè)基本函數(shù)3. 理解隊(duì)列的基本原理詳細(xì)講述見下：1、介紹STL中棧的使用，如下是從幫助文檔

3、中copy的代碼#pragma warning(disable:4786)#include <stack>#include <iostream>using namespace std ;typedef stack<int> STACK_INT;int main() STACK_INT stack1; cout << "stack1.empty() returned " << (stack1.empty()? "true": "false") << endl; /

4、Function 3 cout << "stack1.push(2)" << endl; stack1.push(2); if (!stack1.empty() / Function 3 cout << "stack1.top() returned " << stack1.top() << endl; / Function 1 cout << "stack1.push(5)" << endl; stack1.push(5); if (!stack1.e

5、mpty() / Function 3 cout << "stack1.top() returned " << stack1.top() << endl; / Function 1 cout << "stack1.push(11)" << endl; stack1.push(11); if (!stack1.empty() / Function 3 cout << "stack1.top() returned " << stack1.top() <

6、;< endl; / Function 1 / Modify the top item. Set it to 6. if (!stack1.empty() / Function 3 cout << "stack1.top()=6;" << endl; stack1.top()=6; / Function 1 / Repeat until stack is empty while (!stack1.empty() / Function 3 const int& t=stack1.top(); / Function 2 cout <&

7、lt; "stack1.top() returned " << t << endl; cout << "stack1.pop()" << endl; stack1.pop(); 運(yùn)行結(jié)果：stack1.empty() returned truestack1.push(2)stack1.top() returned 2stack1.push(5)stack1.top() returned 5stack1.push(11)stack1.top() returned 11stack1.top()=6;stack1

8、.top() returned 6stack1.pop()stack1.top() returned 5stack1.pop()stack1.top() returned 2stack1.pop()2、自己編寫的棧注意事項(xiàng)自己編寫的?？梢允褂脭?shù)組實(shí)現(xiàn)也可以使用鏈表實(shí)現(xiàn)，可以用C或者C描述，但是必須具有棧的基本功能，即必須具有棧的一些基本函數(shù)。對(duì)照STL的棧，其基本應(yīng)該具有的函數(shù)是push，pop，top，empty，如果是數(shù)組實(shí)現(xiàn)的棧還需要判斷棧是否滿。3、使用自己編寫的棧實(shí)現(xiàn)序列反轉(zhuǎn)如果要使用自己編寫的棧實(shí)現(xiàn)序列反轉(zhuǎn)，一定要注意，自己寫的函數(shù)可能原型跟STL中的不一樣，因此，需要在主函數(shù)調(diào)用

9、的時(shí)候，根據(jù)函數(shù)的具體寫法具體調(diào)用，不能夠直接復(fù)制原有的使用STL中棧進(jìn)行序列反轉(zhuǎn)的代碼，否則編譯可能不能通過。4、隊(duì)列的實(shí)現(xiàn)和使用這里，自己實(shí)現(xiàn)的隊(duì)列也是可以是通過數(shù)組實(shí)現(xiàn)一個(gè)循環(huán)隊(duì)列或者用鏈表實(shí)現(xiàn)。隊(duì)列實(shí)現(xiàn)好后，自己再寫一個(gè)主函數(shù)進(jìn)行測(cè)試。一般隊(duì)列需要具有的基本函數(shù)，比如出隊(duì)，入隊(duì)，判斷隊(duì)列是否為空，取隊(duì)首元素這些都需要具備。實(shí)驗(yàn)教案 實(shí)驗(yàn)三 迷宮重點(diǎn)：一些數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，如何更好的根據(jù)算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)。難點(diǎn)：1. 根據(jù)算法，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以便于程序的編寫。比如需要理解為什么迷宮用二維數(shù)組表示且該二維數(shù)組的維數(shù)大于實(shí)際的迷宮大小2. 弄清回溯算法求解迷宮路徑的非遞歸方法3. 理解迷宮

10、中行走方向，要求8個(gè)方向。理解棧在求解該迷宮非遞歸算法中的作用，以及需要將什么內(nèi)容放入棧中。具體講解如下：本實(shí)驗(yàn)主要是設(shè)計(jì)走迷宮算法，可以用遞歸和非遞歸兩種方式完成實(shí)驗(yàn)題目中詳細(xì)講述的算法是非遞歸算法，用棧為輔助的數(shù)據(jù)結(jié)構(gòu)。這里可以使用標(biāo)準(zhǔn)模板庫(kù)中的stack1.走迷宮非遞歸算法的設(shè)計(jì)實(shí)現(xiàn)這個(gè)算法在實(shí)驗(yàn)指導(dǎo)書中有詳細(xì)的介紹，下面簡(jiǎn)單總結(jié)一下（1）數(shù)據(jù)結(jié)構(gòu)：² 用二維數(shù)組MAZEm+2n+2表示迷宮的結(jié)構(gòu)，數(shù)組中的值為1表示是墻，為0表示可以走通。（用MAZEm+2n+2而不用MAZEmn的原因在于想表示和編寫代碼的時(shí)候簡(jiǎn)單些，而且讓迷宮周圍都是墻，防止錯(cuò)誤的走出去）² 用二

11、維數(shù)組MARKm+2n+2表示迷宮是否被走過，主要是為了回溯時(shí)已經(jīng)證明走不通的路線就不要再去走了。（用MARKm+2n+2而不用MARKmn的原因在于想表示和編寫代碼的時(shí)候簡(jiǎn)單些）² 二維數(shù)據(jù)MOVE82是為了更方便的移動(dòng)到下一步，改變坐標(biāo)。這個(gè)二維數(shù)組是為了更好的轉(zhuǎn)換坐標(biāo)（八個(gè)方向，從0到7），而且也能避免重復(fù)走路² 用棧保存走過的路徑（2）輸出：² 迷宮布局，用0表示可以走通的地方，用1表示墻² 如果能走通，則輸出路徑和路徑的長(zhǎng)度；若不能走通，則輸出提示不能走通² 帶有路徑的迷宮布局注意：雖然總的算法思想在實(shí)驗(yàn)指導(dǎo)書中有介紹，而且相當(dāng)詳細(xì)，

12、但是需要仔細(xì)讀懂的，因?yàn)橛⑽陌嫖臋n中的代碼是偽代碼，要自己寫成用c+的語(yǔ)言實(shí)現(xiàn)。比如對(duì)于C+語(yǔ)言的數(shù)組下標(biāo)是從0開始的。 2.走迷宮遞歸算法的設(shè)計(jì)實(shí)現(xiàn)(選作)下面給出一個(gè)迷宮遞歸算法的實(shí)現(xiàn)bool Maze:solve(int i, int j)/*Post: attempt to find a path through the maze from coordinate (i,j)*/bool finish = false;mazeij = 'X'if (i = rowsize && j = colsize)return true; / because we&#

13、39;re doneif (!finish && mazei+1j = '0')finish = solve(i+1, j);if (!finish && mazeij+1 = '0')finish = solve(i, j+1);if (!finish && mazei-1j = '0')finish = solve(i-1, j);if (!finish && mazeij-1 = '0')finish = solve(i, j-1);if (!finish) /

14、無(wú)法走通，那么修改原來設(shè)置的X符號(hào)，但是不設(shè)置為0，因?yàn)檫@個(gè)點(diǎn)現(xiàn)在已經(jīng)走過mazeij = '+'return finish;在上面的算法中，迷宮的表示還是用字符1表示墻，字符0表示可以走通，用字符X表示路徑。至于字符，僅僅是為了表示這條路已經(jīng)走過。應(yīng)該注意到在實(shí)驗(yàn)題目文檔中的迷宮是有八個(gè)方向可以行走的，而上面的遞歸算法中僅僅有四個(gè)方向是可以行走的，需要改動(dòng)。還有，其直接把路徑放到迷宮結(jié)構(gòu)數(shù)組中了，而且還多出并不需要出現(xiàn)的字符。請(qǐng)改動(dòng)上面的算法，滿足實(shí)驗(yàn)題目文檔的需要，也就是說，滿足八方向行走的要求，輸出的迷宮路徑圖中，也僅僅有三種字符（1：墻；0：可行走；X：走通的路徑）。提

15、示：可以參照上面的非遞歸算法中的數(shù)據(jù)結(jié)構(gòu)，專門用MARKm+2n+2表示這個(gè)路是否已經(jīng)走過了實(shí)驗(yàn)教案 實(shí)驗(yàn)四 樹的構(gòu)造和遍歷重點(diǎn)：理解按層次構(gòu)造樹的算法難點(diǎn)：1. 理解構(gòu)造二叉樹具有多種方式2. 理解隊(duì)列在按層次構(gòu)造樹中起到的作用3. 理解為什么隊(duì)列中需要放置樹節(jié)點(diǎn)的指針，而不直接是樹節(jié)點(diǎn)詳細(xì)講解如下：這個(gè)實(shí)驗(yàn)中要求用類模板來實(shí)現(xiàn)樹的類。需要對(duì)類模板有些了解。注意，在編寫代碼的時(shí)候，要將所有模板信息放在一個(gè)頭文件中，并在要使用這些模板的文件中包含該頭文件(如果分別用.h和.cpp實(shí)現(xiàn)，那就必須在使用該類的地方同時(shí)包含該.h和.cpp文件)。因?yàn)槟０宀皇呛瘮?shù)，模板必須與特定的模板實(shí)例化請(qǐng)求一起使

16、用。若將模板成員函數(shù)放置在一個(gè)獨(dú)立的實(shí)現(xiàn)文件中將無(wú)法運(yùn)行。本實(shí)驗(yàn)有三個(gè)主要任務(wù)（1）按層次構(gòu)造二叉樹（要求必須按照實(shí)驗(yàn)指導(dǎo)書文檔中的要求按層次構(gòu)造一棵二叉樹，但是實(shí)驗(yàn)指導(dǎo)書中沒有描述具體的算法，這里等下會(huì)簡(jiǎn)單講述具體的算法）（2）二叉樹中按高度插入節(jié)點(diǎn)（3）遍歷二叉樹（前根序、中根序和后根序，寫出遞歸算法即可）詳細(xì)介紹如下：二叉樹的構(gòu)建（1）總述題目要求在構(gòu)造樹的時(shí)候，依層次（從根開始）輸入樹中每個(gè)結(jié)點(diǎn)，然后用這些結(jié)點(diǎn)構(gòu)造樹。經(jīng)過分析可以看到，當(dāng)一個(gè)結(jié)點(diǎn)被插入樹中后，它還是需要保留指向它的指針的，因?yàn)椋竺孑斎氲男蛄兄幸苍S還有它的孩子，因此需要記錄它的位置為將來把它的孩子也插入樹中做準(zhǔn)備。這樣

17、，就需要一個(gè)隊(duì)列來保存這些信息（為什么用隊(duì)列而不是用棧，可以想想）。每次從序列中讀入一個(gè)結(jié)點(diǎn)數(shù)據(jù)的時(shí)候，就從隊(duì)列頭取出一個(gè)指向結(jié)點(diǎn)的指針，讓這個(gè)取出的結(jié)點(diǎn)的左右孩子分別指向新生成的結(jié)點(diǎn)（為此需要再?gòu)男蛄兄凶x入一個(gè)結(jié)點(diǎn)信息），之后刪除隊(duì)列的頭，往隊(duì)列的尾部再壓入指向新生成的兩個(gè)結(jié)點(diǎn)的指針（如果輸入的結(jié)點(diǎn)信息為.，那么就可能只壓入一個(gè)結(jié)點(diǎn)，或者一個(gè)結(jié)點(diǎn)都不壓入）?？偟膩碚f，隊(duì)列中存放的是當(dāng)前的指向樹的葉子結(jié)點(diǎn)的指針。上面是總體的算法思想。在實(shí)現(xiàn)的時(shí)候會(huì)用到的隊(duì)列，這里也不要求大家再去自己實(shí)現(xiàn)一個(gè)有關(guān)隊(duì)列的類，直接用標(biāo)準(zhǔn)模板庫(kù)（STL）中的隊(duì)列就可以了。需要#include <queue>

18、;STL中的queue，里面的一些成員函數(shù)如下（這里僅僅描述也許會(huì)用到的幾個(gè)，具體不明白可以查找?guī)椭臋n）：front：Returns a reference to the first element at the front of the queue.pop：Removes an element from the front of the queuepush：Adds an element to the back of the queueempty：Tests if the queue is empty（2）詳細(xì)算法問題描述：按層次（從上到下，從左到右的順序）輸入樹的結(jié)點(diǎn)，如果該結(jié)點(diǎn)為空，則

19、用一個(gè)特定的值替代（比如0或者.）。例如下面的圖中，輸入為e b f a d . g . . c（當(dāng)然為了方便輸入，也可以用結(jié)束字符串的輸入）要求構(gòu)造一棵如下的二叉樹下面介紹按層次構(gòu)造樹的兩種方法對(duì)于如下的一棵樹輸入：為了構(gòu)造上圖所示的這樣一棵二叉樹，鍵盤上輸入的順序如下：ebfad.g.c#其中可以看到這是根據(jù)層次的一種輸入，先輸入第一層的結(jié)點(diǎn)，然后是第二層的結(jié)點(diǎn)，第三層.直到把所有的帶信息的結(jié)點(diǎn)輸入完。也可以看到，在輸入的序列中，有.號(hào)，這是代表結(jié)點(diǎn)為空。注意在輸入的時(shí)候，為空的結(jié)點(diǎn)也要這樣輸入進(jìn)去。構(gòu)造二叉樹：方法一：用隊(duì)列queue<Binary_node*> A;queu

20、e<Binary_node*> B;假如我們把讀入的數(shù)據(jù)放到一個(gè)隊(duì)列中A，用于方便我們的后續(xù)處理，那么，在讀入后，這個(gè)隊(duì)列中的數(shù)據(jù)為ebfad.g.c，其中e為隊(duì)列頭存放的元素值（即該指針?biāo)赶虻墓?jié)點(diǎn)空間數(shù)據(jù)域中的值為e），而點(diǎn)代表空指針NULL把數(shù)據(jù)讀入隊(duì)列A中的方法如下，要用循環(huán)來讀入所有數(shù)據(jù)：Binary_node* tempNode=new Binary_node();cin>>tempNode->data;tempNode->left=NULL;tempNode->right=NULL;A.push(tempNode);為了按層次的構(gòu)造二叉樹

21、，我們還要使用一個(gè)隊(duì)列B，這個(gè)隊(duì)列中保存的是指向要有兒子結(jié)點(diǎn)的父親結(jié)點(diǎn)的指針。下面是這兩個(gè)隊(duì)列的變化和樹的構(gòu)造變化情況：（1）第一步很特殊，首先是樹根Binary_node* pNode=A.front();A.pop();B.push(pNode);A：bfad.g.cB：e樹：（2）后面的每一步都是從A中取出兩個(gè)隊(duì)首，放入B隊(duì)列尾部（如果為NULL則不放）。從B中取出隊(duì)首，隊(duì)列A中取出的元素正好是B中取出元素的小孩子Binary_node* pfather= B.front();B.pop();Binary_node* pLchild= A.front();/先出來的是左孩子A.pop()

22、;Binary_node* pRchild= A.front();A.pop();pfather->left=pLchild;pfather->right=pRchild;/先放入左孩子if(pLchild!=NULL)B.push(pLchild);if(pRchild!=NULL)B.push(pRchild);A：ad.g.cB：bf樹：（3）A：.g.cB：fad樹：（4）A：.cB：adg樹：（5）A：cB：dg樹：（6）A：空（當(dāng)隊(duì)列A為空的時(shí)候整個(gè)算法結(jié)束，樹構(gòu)造成功）B：g樹：方法二：用數(shù)組給樹的結(jié)點(diǎn)按層次從上到下，從左到右編號(hào)（編號(hào)從1開始，空節(jié)點(diǎn)也要編號(hào)），利用

23、父親跟小孩的編號(hào)的關(guān)系來編寫代碼。即節(jié)點(diǎn)的編號(hào)除以2，得到的商代表這該節(jié)點(diǎn)父親節(jié)點(diǎn)的編號(hào)，得到的余數(shù)為0，則表示該節(jié)點(diǎn)為父親的左孩子，若得到的余數(shù)為1，則表示該節(jié)點(diǎn)為父親的右孩子。實(shí)現(xiàn)方法可以為，（1）為每個(gè)節(jié)點(diǎn)分配空間；（2）定義一個(gè)一維數(shù)組，該數(shù)組中存放的元素為指向節(jié)點(diǎn)的指針，將每個(gè)分配好空間的節(jié)點(diǎn)的指針放入該一維數(shù)組中（3）逐一訪問節(jié)點(diǎn)，確定節(jié)點(diǎn)的父子關(guān)系。當(dāng)除了根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)的父親都確定后，這顆二叉樹就構(gòu)造好了。兩種方法分析：用隊(duì)列的方法，實(shí)現(xiàn)有點(diǎn)難度，但是靈活。數(shù)組的方法，實(shí)現(xiàn)比較簡(jiǎn)單，但是有局限性。實(shí)驗(yàn)教案 實(shí)驗(yàn)五 排序重點(diǎn)：至少掌握一種排序算法。難點(diǎn)：1、隨機(jī)生成要排序的數(shù)據(jù)

24、，使用rand函數(shù)的之前記得調(diào)用函數(shù)srand2、至少掌握一種排序算法并實(shí)現(xiàn)升序排序和降序排序。3、有能力希望能掌握多種排序算法，并進(jìn)行比較。編寫排序算法時(shí)，經(jīng)常會(huì)出現(xiàn)程序能運(yùn)行，但是運(yùn)行結(jié)果有誤的情況，這就需要掌握程序的單步調(diào)試方法。單步調(diào)試的思維C語(yǔ)言復(fù)習(xí)文件夾中對(duì)于每種程序結(jié)構(gòu)都有介紹。而單步調(diào)試的快捷鍵對(duì)于不同的編譯環(huán)境是不同的，比如VC6與codeblock就有所區(qū)別。另外，編寫排序算法后，還需要多用不同的數(shù)據(jù)運(yùn)行測(cè)試幾次。實(shí)驗(yàn)教案 實(shí)驗(yàn)六 圖重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)Dijkstra求圖的最短路徑算法Prim求圖的最小生成樹算法難點(diǎn)：1. 理解Dijkstra求圖的最短路徑算法2. 理解P

25、rim求圖的最小生成樹算法3. 編程實(shí)現(xiàn)上述兩種算法中，需要用到的輔助數(shù)據(jù)結(jié)構(gòu)，圖是如何表示的，以及最后的結(jié)果存放在哪里詳細(xì)講解如下：圖的存儲(chǔ)：用鄰接矩陣，這樣會(huì)方便不少。鄰接矩陣是一個(gè)二維數(shù)組，數(shù)組中的元素是邊的權(quán)（一些數(shù)值），數(shù)組下標(biāo)號(hào)為結(jié)點(diǎn)的標(biāo)號(hào)。（1）例如二維數(shù)組中的一個(gè)元素M56的值為39，則表示結(jié)點(diǎn)5、6連接，且其上的權(quán)值為39。（2）用鄰接矩陣存儲(chǔ)圖，對(duì)圖的讀寫就簡(jiǎn)單了。因?yàn)猷徑泳仃嚲褪且粋€(gè)二維數(shù)組，因此對(duì)圖的讀寫就是對(duì)二維數(shù)組的操作。只要能弄清楚邊的編號(hào)，就能把圖讀入了。用一對(duì)結(jié)點(diǎn)表示邊（也就是輸入的時(shí)候輸入一對(duì)結(jié)點(diǎn)的編號(hào)）1.Dijkstra生成最短路徑書上給出了完整的求最短

26、路徑的源代碼?？偟膩碚f的不斷添加點(diǎn)的過程，把距離原點(diǎn)路徑最短的點(diǎn)添加（通過做標(biāo)記的方法）并更新沒有做標(biāo)記的圖中點(diǎn)距離原點(diǎn)的距離，直到所有的點(diǎn)都做了標(biāo)記。自己編寫代碼的時(shí)候注意，書上僅僅是給出了最短路徑的源代碼，離一個(gè)完整的程序還有距離，其中要補(bǔ)充圖的讀寫的函數(shù)和定義一些常量。關(guān)鍵是要明白書上代碼的意思。程序輸入輸出示例如下（并不要求一定按照該輸入輸出來實(shí)現(xiàn)）：求最短路徑的Dijkstra算法：求最短路徑就是求圖中的每一個(gè)點(diǎn)到圖中某一個(gè)給定點(diǎn)（這里認(rèn)為是編號(hào)為0的點(diǎn)）的最短距離。具體算法就是初始有一個(gè)舊圖，一個(gè)新圖。開始的時(shí)候舊圖中有所有的結(jié)點(diǎn)，新圖中初始為只有一個(gè)結(jié)點(diǎn)（源點(diǎn)，路徑的源頭）。整個(gè)

27、算法就是不停的從舊圖中往新圖中添加點(diǎn)，直到所有的點(diǎn)都添加到新圖中為止。要實(shí)現(xiàn)這個(gè)算法，除了用二維數(shù)組保存圖，還需要使用到兩個(gè)輔助的數(shù)組數(shù)組findN：此數(shù)組是用來表示標(biāo)號(hào)對(duì)應(yīng)的結(jié)點(diǎn)是否已經(jīng)被添加到新圖中（因?yàn)橹挥信f圖中的點(diǎn)我們才需要添加到新圖中，并且只有舊圖中點(diǎn)到源點(diǎn)的距離，我們才需要進(jìn)行更新）其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。數(shù)組distanceN：此數(shù)組記錄圖中的點(diǎn)到源點(diǎn)的距離。這個(gè)數(shù)組里面存放的值是不斷進(jìn)行更新的。其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。大的循環(huán)：逐一把舊圖中的所有點(diǎn)添加到新圖中。把找到的結(jié)點(diǎn)添加到新圖中。循環(huán)：遍歷distance數(shù)組，找distance數(shù)組中屬于舊圖中的點(diǎn)，其中distance

28、最小的那個(gè)結(jié)點(diǎn)更新distance數(shù)組，因?yàn)樾绿砑恿艘粋€(gè)點(diǎn)到新圖中，所以可能能找到一條通過這條點(diǎn)的新的路徑，這條路徑可能比原來的路徑更短。2.Prim求最小生成樹程序運(yùn)行如下，但是并不要求按照下圖來進(jìn)行輸入數(shù)據(jù)和結(jié)果的輸出，可以自己根據(jù)情況自行設(shè)計(jì)輸入輸出。求最小生成樹的Prim算法：具體算法就是初始有一個(gè)舊圖，一個(gè)新圖。開始的時(shí)候舊圖中有所有的結(jié)點(diǎn)，新圖中初始為只有一個(gè)結(jié)點(diǎn)（源點(diǎn)，路徑的源頭）。整個(gè)算法就是不停的從舊圖中往新圖中添加點(diǎn)，直到所有的點(diǎn)都添加到新圖中為止。要實(shí)現(xiàn)這個(gè)算法，除了用二維數(shù)組保存圖，還需要使用到三個(gè)輔助的數(shù)組數(shù)組componentN：此數(shù)組是用來表示標(biāo)號(hào)對(duì)應(yīng)的結(jié)點(diǎn)是否已

29、經(jīng)被添加到新圖中（因?yàn)橹挥信f圖中的點(diǎn)我們才需要添加到新圖中，并且只有舊圖中點(diǎn)到新圖中任意點(diǎn)的最短的距離，我們才需要進(jìn)行更新）其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。數(shù)組distanceN：此數(shù)組記錄舊圖中的點(diǎn)到新圖中任意點(diǎn)的最短的距離。這個(gè)數(shù)組里面存放的值是不斷進(jìn)行更新的。其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。neighborN：此數(shù)組記錄點(diǎn)的鄰居是誰(shuí)。其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。具體寫代碼的時(shí)候理解算法，自己寫出來，注意對(duì)這些數(shù)組進(jìn)行初始化。不一定要使用書上的結(jié)構(gòu)，注意對(duì)一些常量的定義。大的循環(huán)：逐一把舊圖中的所有點(diǎn)添加到新圖中。把找到的結(jié)點(diǎn)添加到新圖中。循環(huán)：遍歷distance數(shù)組，找distance數(shù)組中屬于舊圖中的點(diǎn)，其中distance最小的那個(gè)結(jié)點(diǎn)更新distance數(shù)組和neighbor數(shù)組，因?yàn)樾绿砑恿艘粋€(gè)點(diǎn)到新圖中，所以可能這個(gè)新添加的點(diǎn)到舊圖中的點(diǎn)的距離要更短些，有可能成為舊圖中某些點(diǎn)的鄰居。注意事項(xiàng)：雖然截圖給出了結(jié)果，但是在界面顯示上不做太多要求，即只要能將算法實(shí)現(xiàn)就好，讀入數(shù)據(jù)和結(jié)果輸出可以按照自己喜歡或者有能力做到的方式實(shí)現(xiàn)。大家初學(xué)最好關(guān)注算法本身。當(dāng)然，一個(gè)交互性好的互動(dòng)還是比較好