上傳人：奔***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：常**（實(shí)名認(rèn)證）

IP屬地：河北

IP屬地：河北 更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：20 大?。?21.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

1、<p>　　數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告</p><p>　　題目： 拓?fù)渑判蛩惴?</p><p><b>　　院（系）：理學(xué)院</b></p><p>　　專 業(yè)：信息與計(jì)算科學(xué) </p><p><b>　　班 級(jí)： </b></p>&l

2、t;p><b>　　學(xué) 號(hào)： </b></p><p><b>　　姓 名： </b></p><p><b>　　指導(dǎo)教師： </b></p><p><b>　　2011年12月</b></p><p><b>　　目

3、 錄</b></p><p>　　1 課程設(shè)計(jì)介紹1</p><p>　　1.1 課程設(shè)計(jì)內(nèi)容1</p><p>　　1.2 課程設(shè)計(jì)要求1</p><p>　　2 課程設(shè)計(jì)原理2</p><p>　　2.1 課設(shè)題目粗略分析2</p><p>　　2.2 原理圖介紹

4、3</p><p>　　2.2.1 功能模塊圖3</p><p>　　2.2.2 流程圖分析3</p><p>　　3 數(shù)據(jù)結(jié)構(gòu)分析5</p><p>　　3.1 存儲(chǔ)結(jié)構(gòu)5</p><p>　　3.2 算法描述5</p><p>　　4 調(diào)試與分析9</p>&l

5、t;p>　　4.1 調(diào)試過程9</p><p>　　4.2 程序執(zhí)行過程9</p><p><b>　　參考文獻(xiàn)11</b></p><p><b>　　總結(jié)12</b></p><p>　　附 錄（關(guān)鍵部分程序清單）13</p><p><b>

6、;　　1 課程設(shè)計(jì)介紹</b></p><p>　　1.1 課程設(shè)計(jì)內(nèi)容</p><p>　　編寫算法，建立有向無(wú)環(huán)圖，系統(tǒng)主要功能如下：</p><p>　　能夠求解該有向無(wú)環(huán)圖的拓?fù)渑判虿⑤敵龀鰜恚?lt;/p><p>　　拓?fù)渑判驊?yīng)能夠處理出現(xiàn)環(huán)的情況。</p><p>　　頂點(diǎn)信息要有幾種情況可以選擇

7、。</p><p>　　1.2 課程設(shè)計(jì)要求</p><p>　　輸出除拓?fù)渑判驍?shù)據(jù)外，還要求輸出鄰接表數(shù)據(jù)；</p><p>　　參考相應(yīng)資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)；</p><p>　　交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。</p><p><b>　　2 課程設(shè)計(jì)原理</b></p>

8、<p>　　2.1 課設(shè)題目粗略分析</p><p>　　本課設(shè)題目要求編寫算法能夠建立有向無(wú)環(huán)圖，有向無(wú)環(huán)圖，顧名思義，即一個(gè)無(wú)環(huán)的有向圖，是一類較有向圖更一般的特殊有向圖。</p><p>　　其功能要求及個(gè)人在寫程序時(shí)對(duì)該功能的實(shí)現(xiàn)作如下分析：</p><p>　　1. 將圖以合適的方式存儲(chǔ)起來。圖有多種存儲(chǔ)方式，其中最常用的存儲(chǔ)方式有圖的鄰接矩陣

9、和鄰接表。本人在構(gòu)思時(shí)使用鄰接表來建立有向無(wú)環(huán)圖，將其存儲(chǔ)起來；</p><p>　　2. 求解該有向無(wú)環(huán)圖的拓?fù)渑判?，并將其輸出出來。若通過構(gòu)造，建立了一個(gè)有向無(wú)環(huán)圖，那么一定可以求出其拓?fù)渑判颍湓肀容^簡(jiǎn)單。即統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，將入度為0的結(jié)點(diǎn)提取出來，然后再統(tǒng)計(jì)剩下的結(jié)點(diǎn)的入度，再次將入度為零的結(jié)點(diǎn)提取出來，以此類推，這樣就形成了一個(gè)序列，這樣的序列就是該圖的拓?fù)渑判蛐蛄校?lt;/p><

10、;p>　　3. 拓?fù)渑判蛩惴☉?yīng)能夠處理出現(xiàn)環(huán)的情況。個(gè)人在寫程序時(shí)，考慮到構(gòu)造圖時(shí)，會(huì)有構(gòu)造成有向有環(huán)圖的情況，應(yīng)該在運(yùn)行程序時(shí)，提醒出來，然后重新輸入有向無(wú)環(huán)圖，知道輸入正確為止。這樣就有多次構(gòu)造鄰接表的問題，每一次構(gòu)造鄰接表時(shí)，都應(yīng)該將原來錯(cuò)誤的（不是無(wú)環(huán)圖的）鄰接表空間釋放掉，否則，會(huì)變得混亂；</p><p>　　4. 輸出除拓?fù)渑判蛲猓€要求輸出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲(chǔ)的，所以很容易將其鄰

11、接表輸出出來。</p><p><b>　　2.2 原理圖介紹</b></p><p>　　2.2.1 功能模塊圖</p><p>　　圖2.1 功能模塊圖</p><p>　　2.2.2 流程圖分析</p><p>　　根據(jù)程序的總的步驟，擬將整個(gè)流程分為三個(gè)模塊。三個(gè)模塊既相互獨(dú)立又相互聯(lián)系。

12、具體分析如下：</p><p>　　1. 圖像輸入，根據(jù)題目要求，要能夠建立一個(gè)有向無(wú)環(huán)圖，這就要我們?cè)诔绦蛑腥ソ??？紤]到輸入方式要盡量方便全面，采用輸入弧的方式，輸入每條弧的鏈接的兩個(gè)結(jié)點(diǎn)，當(dāng)輸入-1時(shí)結(jié)束輸入。這樣再輸入的時(shí)候，與相鄰的兩個(gè)結(jié)點(diǎn)的鄰接矩陣對(duì)應(yīng)的位置也做相應(yīng)改變。</p><p>　　2. 判斷圖是不是有向無(wú)環(huán)圖。當(dāng)圖為有向無(wú)環(huán)圖時(shí)，則挑選完畢后，隊(duì)列應(yīng)該是滿的，進(jìn)行后

13、續(xù)步驟。對(duì)于結(jié)點(diǎn)入隊(duì)列的順序，需要借助于數(shù)組。選取入度為零的結(jié)點(diǎn)，入隊(duì)列，調(diào)整數(shù)組，循環(huán)進(jìn)行。若隊(duì)列不滿，則輸入的圖不符合要求，應(yīng)該重新輸入。在程序中應(yīng)做適當(dāng)提醒，然后自動(dòng)轉(zhuǎn)模塊1.，進(jìn)行圖的重新編輯。</p><p>　　3. 拓?fù)渑判颉４藭r(shí)，所輸入的弧應(yīng)該是有向無(wú)環(huán)圖了，下面進(jìn)行拓?fù)渑判?。在判斷它是否為無(wú)環(huán)圖的過程中已經(jīng)形成了一個(gè)滿隊(duì)列。接下來所要做的事情就是循環(huán)出隊(duì)列，按照隊(duì)列固有的順序進(jìn)行輸出即可，排序完

14、成。</p><p>　　圖2.2 程序流程圖</p><p><b>　　3 數(shù)據(jù)結(jié)構(gòu)分析</b></p><p><b>　　3.1 存儲(chǔ)結(jié)構(gòu)</b></p><p>　　一個(gè)無(wú)環(huán)的有向圖叫做有向無(wú)環(huán)圖，簡(jiǎn)稱DAG圖。本算法首先要建立一個(gè)有向五環(huán)圖，即通過輸入各邊的數(shù)據(jù)，搭建圖的結(jié)構(gòu)。<

15、/p><p>　　對(duì)于圖的存儲(chǔ)，用到鄰接表，是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。</p><p>　　typedef struct Node</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct Node *next;&

16、lt;/p><p>　　}GraphNode;</p><p>　　GraphNode vexs[maximum];</p><p>　　對(duì)于用來排序的隊(duì)列，則用到了順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列，用數(shù)組表示。</p><p>　　int Queue[maximum];</p><p><b>　　3.2 算法描述</

17、b></p><p>　　1. 鄰接表的構(gòu)造：</p><p>　　本算法借用圖的鄰接矩陣構(gòu)造鄰接表，其形式如下：</p><p>　　int Graph[maximum][maximum];</p><p>　　對(duì)于相鄰的結(jié)點(diǎn)和，Graph[i][j]=1，若不相鄰，則Graph[i][j]=0；對(duì)于鄰接表的存儲(chǔ)結(jié)構(gòu)，上面已作說明，定

18、義一個(gè)GraphNode類型的數(shù)組變量vexs[maximum]和一個(gè)GraphNode類型的指針變量*newnode。若兩個(gè)結(jié)點(diǎn)和相鄰（由指向，Graph[i][j]=1），則在vexs[maximum]第行添加以為值的newnode數(shù)據(jù)，即vexs[i-1]->next=*newnode。其中newnode->data=j，newnode->next=NULL。直到遍歷完整個(gè)鄰接矩陣，鄰接表隨即建立完成。簡(jiǎn)單算法說

19、明如下：</p><p>　　for(i=0;i<l;i++)</p><p>　　for(j=0;j<l;j++)</p><p><b>　　{</b></p><p>　　if(Graph[i][j])</p><p>　　CreateAdjacentTable(i,j); //

20、當(dāng)鄰接矩陣Graph[i][j]有值時(shí)，則構(gòu)造鄰接表</p><p><b>　　}</b></p><p>　　2. 隊(duì)列初始化（入隊(duì)操作）及出隊(duì)操作</p><p>　　在本算法中隊(duì)列主要用來，構(gòu)造拓?fù)渑判蛐蛄?。由于?duì)列具有先入先出的特點(diǎn)，所以，將每次選擇入度為零的結(jié)點(diǎn)入隊(duì)，這樣當(dāng)結(jié)點(diǎn)都入隊(duì)的時(shí)候，再依次出隊(duì)，這樣，排序序列顯而易見。它將圖

21、這樣的非線性結(jié)構(gòu)轉(zhuǎn)化為隊(duì)列這樣的線性結(jié)構(gòu)。</p><p>　?。?） 隊(duì)列初始化：</p><p>　　void addqueue(int *queue,int x)//入隊(duì)操作</p><p><b>　　{</b></p><p>　　if(rear==l-1)</p><p><b&

22、gt;　　{</b></p><p>　　printf("隊(duì)列已滿\n"); return;</p><p><b>　　}</b></p><p><b>　　rear++;</b></p><p>　　queue[rear]=x;</p><p

23、><b>　　return;</b></p><p><b>　　}</b></p><p><b>　?。?） 出隊(duì)操作：</b></p><p>　　int delqueue(int *queue)//出隊(duì)操作</p><p><b>　　{</b&g

24、t;</p><p><b>　　int e;</b></p><p>　　if(rear==front)</p><p><b>　　{</b></p><p>　　return -2;</p><p><b>　　}</b></p>&

25、lt;p><b>　　front++;</b></p><p>　　e=queue[front];</p><p>　　queue[front]=0;</p><p><b>　　return e;</b></p><p><b>　　}</b></p>&

26、lt;p><b>　　3. 拓?fù)渑判?lt;/b></p><p>　　本程序的拓?fù)渑判?，必須在圖的鄰接表已知的情況下。它還有另外一個(gè)功能：判斷一個(gè)圖是不是無(wú)環(huán)圖。確切的說，不能單純的叫拓?fù)渑判?，但考慮它主要的作用，在不引起誤解的情況下就叫拓?fù)渑判蛩惴ā?lt;/p><p>　　判斷一個(gè)圖是否為有向無(wú)環(huán)圖并進(jìn)行拓?fù)渑判?，判定方法有很多種，檢查一個(gè)有向圖是否存在環(huán)要比無(wú)向圖

27、復(fù)雜。對(duì)于無(wú)向圖來說，若深度優(yōu)先遍歷過程中遇到回邊（即指向已訪問過的頂點(diǎn)的邊），則必存在環(huán)；而對(duì)于有向圖來說，這條回邊有可能指向深度優(yōu)先森林中另一棵生成樹上頂點(diǎn)的弧。但是，如果從有向圖上某個(gè)頂點(diǎn)出發(fā)的遍歷，在結(jié)束之前出現(xiàn)一條從頂點(diǎn)到頂點(diǎn)的回邊，由于在生成樹上是的子孫，則有向圖中必定存在包含頂點(diǎn)和的環(huán)。</p><p>　　另一種判斷是否有環(huán)的方法則顯得簡(jiǎn)單的多，尤其是對(duì)于本題目來說，由于本題要求是對(duì)有向無(wú)環(huán)圖進(jìn)行

28、拓?fù)渑判?，其主要方法是將入度為零的結(jié)點(diǎn)依次輸出出來，知道圖的所有定點(diǎn)全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結(jié)點(diǎn)在其他結(jié)點(diǎn)都選擇出來后，入度都不為零，即無(wú)法被輸出出來。那么就可以認(rèn)為按照拓?fù)渑判虻姆椒ㄝ敵鼋Y(jié)點(diǎn)后，若不是將節(jié)點(diǎn)全部輸出出來的，則此圖為有環(huán)圖。</p><p>　　判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現(xiàn)環(huán)的情況，若構(gòu)造的圖為有環(huán)圖，則折回開始重新輸入圖的數(shù)據(jù)，重新構(gòu)造圖，直到該圖為無(wú)環(huán)

29、圖為止。若圖已經(jīng)是無(wú)環(huán)圖，則進(jìn)行拓?fù)渑判?，排序方法前面已?jīng)講過，在此主要訴說用到的輔助存儲(chǔ)。數(shù)組存儲(chǔ)各結(jié)點(diǎn)的入度，對(duì)入度為零的結(jié)點(diǎn)，依次入隊(duì)列，調(diào)整數(shù)組，結(jié)點(diǎn)全部入隊(duì)列后，然后依次出隊(duì)列，拓?fù)渑判蛲瓿伞?lt;/p><p>　　void TopoSort(int *visited,int *Queue)</p><p><b>　　{</b></p><

30、;p>　　int i; rear=-1; front=-1; int topnum=0,ml[maximum],n=0; GraphNode *p;</p><p>　　for(i=0;i<l;i++)</p><p>　　{p=(&vexs[i])->next;</p><p>　　while(p!=NULL)</p>&l

31、t;p>　　{visited[(p->data)-1]++; p=p->next;}}</p><p>　　while(topnum!=l)</p><p><b>　　{</b></p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b>&

32、lt;/p><p>　　if(visited[i]==0)</p><p><b>　　{</b></p><p>　　addqueue(Queue,i+1); p=(&vexs[i])->next;</p><p>　　while(p!=NULL)</p><p>　　{visited

33、[(p->data)-1]--; p=p->next;}</p><p>　　visited[i]=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　topnum++;</b></p>

34、<p><b>　　}</b></p><p>　　for(i=0;i<l;i++)</p><p>　　ml[i]=delqueue(Queue);</p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p><p

35、>　　if(ml[i]==-2)</p><p><b>　　{</b></p><p>　　printf("您輸入的圖為有環(huán)圖,請(qǐng)重新輸入!!\n");</p><p><b>　　break;</b></p><p><b>　　}</b><

36、/p><p><b>　　else</b></p><p><b>　　n=n+1;</b></p><p><b>　　}</b></p><p><b>　　if(n==l)</b></p><p><b>　　{<

37、/b></p><p>　　printf("拓?fù)渑判驗(yàn)椋篭n");</p><p>　　for(i=0;i<l;i++)</p><p>　　{printf("%d",ml[i]);</p><p>　　if(i+1!=l)</p><p>　　printf(&quo

38、t;->");}</p><p><b>　　jj=1;</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><

39、b>　　4 調(diào)試與分析</b></p><p><b>　　4.1 調(diào)試過程</b></p><p>　　在調(diào)試程序是主要遇到以下幾類問題：</p><p>　　數(shù)組的數(shù)據(jù)容易出現(xiàn)混亂，比如結(jié)點(diǎn)用數(shù)字標(biāo)識(shí)，數(shù)組結(jié)點(diǎn)的位置是從0開始，而標(biāo)識(shí)符往往從1開始，這在程序的開始就應(yīng)該注意到；</p><p>　

40、　各函數(shù)的形參，實(shí)參的區(qū)別，全局變量，局部變量的區(qū)別，特別是在做大型程序的時(shí)候，如果多個(gè)函數(shù)都要用到一個(gè)變量，那么就應(yīng)把該變量定義為全局變量，若錯(cuò)誤的定義為局部變量，很容易出現(xiàn)錯(cuò)誤；</p><p>　　對(duì)于一個(gè)程序，對(duì)于出現(xiàn)不同情況應(yīng)能夠正確處理，比如對(duì)本題而言，是對(duì)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判?。若?jīng)過錯(cuò)誤的構(gòu)造，該圖是有環(huán)圖，則應(yīng)該提示該圖是有環(huán)圖，并自動(dòng)重新輸入該圖，開始的時(shí)候由于缺乏考慮，會(huì)導(dǎo)致有環(huán)圖也像無(wú)環(huán)圖

41、一樣進(jìn)行“拓?fù)渑判颉薄?lt;/p><p>　　程序應(yīng)該條例清晰，結(jié)構(gòu)明朗，各個(gè)函數(shù)代表各個(gè)模塊，起到不同的作用，并協(xié)調(diào)運(yùn)作，形成含有不同功能的程序。開始時(shí)因?yàn)槌绦虻慕Y(jié)構(gòu)混亂而導(dǎo)致很難調(diào)試，無(wú)法找到錯(cuò)誤的根源。</p><p>　　4.2 程序執(zhí)行過程</p><p>　　對(duì)于有向無(wú)環(huán)圖，以圖4.2.1為例進(jìn)行拓?fù)渑判颍?lt;/p><p>　　圖4

42、.1 有向無(wú)環(huán)圖</p><p>　　程序運(yùn)行結(jié)果如圖4.2.2所示：</p><p>　　圖4.2 有向無(wú)環(huán)圖拓?fù)渑判?lt;/p><p>　　對(duì)于有向有環(huán)圖，以圖4.2.3為例：</p><p>　　圖4.3 有向有環(huán)圖</p><p>　　程序運(yùn)行結(jié)果如圖4.2.4所示：</p><p>　　

43、圖4.4 有向有環(huán)圖程序運(yùn)行結(jié)果</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.</p><p>　　[2] 張長(zhǎng)海，陳娟.C程序設(shè)計(jì)[M].北京：高等教育出版社，2004. </p><p>　　[3] 譚浩強(qiáng).C程序設(shè)計(jì)[M]

44、.北京：清華大學(xué)出版社，2005.</p><p><b>　　總結(jié)</b></p><p>　　附 錄（關(guān)鍵部分程序清單）</p><p><b>　　程序代碼</b></p><p>　　#include "stdafx.h"</p><p>　　

45、#include "stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#define maximum 20</p><p>　　int Graph[maximum][maximum];</p><p>　　int dist[maximum]; //

46、 表示當(dāng)前點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度</p><p>　　int visited[maximum];</p><p>　　int Queue[maximum];</p><p><b>　　int l;</b></p><p><b>　　int jj=0;</b></p><p&g

47、t;　　typedef struct Node</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct Node *next;</p><p>　　}GraphNode;</p><p>　　Graph

48、Node vexs[maximum]; //頂點(diǎn)數(shù)組</p><p>　　int rear=-1;</p><p>　　int front=-1;</p><p>　　int queue[maximum];</p><p>　　void addqueue(int *queue,int x)//入隊(duì)操作</p><p>

49、;<b>　　{</b></p><p>　　if(rear==l-1)</p><p><b>　　{</b></p><p>　　printf("隊(duì)列已滿\n");</p><p><b>　　return;</b></p><p&g

50、t;<b>　　}</b></p><p><b>　　rear++;</b></p><p>　　queue[rear]=x;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p&

51、gt;　　int delqueue(int *queue)//出隊(duì)操作</p><p><b>　　{</b></p><p><b>　　int e;</b></p><p>　　if(rear==front)</p><p><b>　　{</b></p>&

52、lt;p>　　return -2;</p><p><b>　　}</b></p><p><b>　　front++;</b></p><p>　　e=queue[front];</p><p>　　queue[front]=0;</p><p><b>　

53、　return e;</b></p><p><b>　　}</b></p><p>　　void CreateAdjacentTable(int v1,int v2)</p><p><b>　　{</b></p><p>　　GraphNode *newnode;</p>

54、<p>　　newnode=(GraphNode *)malloc(sizeof(GraphNode));</p><p>　　newnode->data=v2+1;newnode->next=NULL;</p><p>　　GraphNode *p;</p><p>　　p=&vexs[v1];</p><p&

55、gt;　　while(p->next!=NULL)</p><p>　　p=p->next;</p><p>　　p->next=newnode;</p><p><b>　　}</b></p><p>　　void TopoSort(int *visited,int *Queue)</p>

56、<p><b>　　{</b></p><p><b>　　int i;</b></p><p><b>　　rear=-1;</b></p><p><b>　　front=-1;</b></p><p>　　int topnum=0;&l

57、t;/p><p>　　int ml[maximum];</p><p><b>　　int n=0;</b></p><p>　　GraphNode *p;</p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p>

58、<p>　　p=(&vexs[i])->next;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　visited[(p->data)-1]++;</p><p>　　p=p->next;</p><p&

59、gt;<b>　　}</b></p><p><b>　　}</b></p><p>　　while(topnum!=l)</p><p><b>　　{</b></p><p>　　for(i=0;i<l;i++)</p><p><b&g

60、t;　　{</b></p><p>　　if(visited[i]==0)</p><p><b>　　{</b></p><p>　　addqueue(Queue,i+1);</p><p>　　p=(&vexs[i])->next;</p><p>　　while(p

61、!=NULL)</p><p><b>　　{</b></p><p>　　visited[(p->data)-1]--;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　visited[i]=-1;</

62、p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　topnum++;</b></p><p><b>　　}</b></p><p>　　for(i=0;i<l;i++)<

63、;/p><p>　　ml[i]=delqueue(Queue);</p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p><p>　　if(ml[i]==-2)</p><p><b>　　{</b></p>&l

64、t;p>　　printf("您輸入的圖為有環(huán)圖,請(qǐng)重新輸入!!\n");</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　n=

65、n+1;</b></p><p><b>　　}</b></p><p><b>　　if(n==l)</b></p><p><b>　　{</b></p><p>　　printf("拓?fù)渑判驗(yàn)椋篭n");</p><p&

66、gt;　　for(i=0;i<l;i++)</p><p>　　{printf("%d",ml[i]);</p><p>　　if(i+1!=l)</p><p>　　printf("->");}</p><p><b>　　jj=1;</b></p>&

67、lt;p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　i

68、nt Graph[maximum][maximum];</p><p>　　GraphNode *kk,*dd;</p><p>　　int source,destination;</p><p><b>　　int i,j;</b></p><p>　　printf("輸入圖的頂點(diǎn)個(gè)數(shù)：");<

69、;/p><p>　　scanf("%d",&l);</p><p>　　while(jj==0)</p><p><b>　　{</b></p><p>　　for(i=0;i<l;i++)</p><p>　　for(j=0;j<l;j++)</p>

70、;<p>　　Graph[i][j]=0;</p><p>　　printf("輸入邊的第一個(gè)頂點(diǎn)：");</p><p>　　scanf("%d",&source);</p><p>　　printf("\n");</p><p>　　while(source

71、!=-1)</p><p><b>　　{</b></p><p>　　if(source>l)</p><p><b>　　{</b></p><p>　　printf("超出范圍請(qǐng)重新輸入：");</p><p>　　scanf("%d

72、",&source);</p><p><b>　　}</b></p><p>　　printf("輸入邊的第二個(gè)頂點(diǎn)：");</p><p>　　scanf("%d",&destination);</p><p>　　printf("\n&qu

73、ot;);</p><p>　　if(destination==source)</p><p><b>　　{</b></p><p>　　printf("出現(xiàn)循環(huán)請(qǐng)重新輸入：");</p><p>　　scanf("%d",&destination);</p>

74、<p><b>　　}</b></p><p>　　if(destination>l)</p><p><b>　　{</b></p><p>　　printf("頂點(diǎn)超出范圍，重新輸入：");</p><p>　　scanf("%d",&

75、amp;destination);</p><p><b>　　}</b></p><p>　　Graph[source-1][destination-1]=1;</p><p>　　printf("輸入邊的第一個(gè)頂點(diǎn)：");</p><p>　　scanf("%d",&s

76、ource);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p><p>　　kk=&vexs[i];

77、</p><p>　　while(kk->next!=NULL)</p><p>　　{ dd=kk->next;</p><p>　　kk->next=dd->next;</p><p><b>　　free(dd);</b></p><p><b>　　}

78、</b></p><p>　　visited[i]=0;</p><p>　　Queue[i]=0;</p><p><b>　　}</b></p><p>　　for(i=0;i<l;i++)</p><p>　　for(j=0;j<l;j++)</p>&

79、lt;p><b>　　{</b></p><p>　　if(Graph[i][j])</p><p>　　CreateAdjacentTable(i,j);</p><p><b>　　}</b></p><p>　　printf("輸出鄰接表：\n");</p>

80、;<p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p><p>　　printf("%d",i+1);</p><p>　　kk=&vexs[i];</p><p>　　while(kk->next!=NULL)</p&g

81、t;<p>　　{ kk=kk->next;</p><p>　　printf("%d",kk->data);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b