數(shù)據(jù)結(jié)構課程設計-拓撲排序

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：20 大?。?21.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩19頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結(jié)構課程設計報告　　題目：拓撲排序算法 　　院（系）：理學院　　專業(yè)：信息與計算科學 　　班級： &l

2、t;p>　　學號： 　　姓名： 　　指導教師： 　　2011年12月　　目

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

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

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

6、;　　1 課程設計介紹　　1.1 課程設計內(nèi)容　　編寫算法，建立有向無環(huán)圖，系統(tǒng)主要功能如下：　　能夠求解該有向無環(huán)圖的拓撲排序并輸出出來；　　拓撲排序應能夠處理出現(xiàn)環(huán)的情況。　　頂點信息要有幾種情況可以選擇

7、。　　1.2 課程設計要求　　輸出除拓撲排序數(shù)據(jù)外，還要求輸出鄰接表數(shù)據(jù)；　　參考相應資料，獨立完成課程設計任務；　　交規(guī)范課程設計報告和軟件代碼。　　2 課程設計原理

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

9、和鄰接表。本人在構思時使用鄰接表來建立有向無環(huán)圖，將其存儲起來；　　2. 求解該有向無環(huán)圖的拓撲排序，并將其輸出出來。若通過構造，建立了一個有向無環(huán)圖，那么一定可以求出其拓撲排序，其原理比較簡單。即統(tǒng)計每個節(jié)點的入度，將入度為0的結(jié)點提取出來，然后再統(tǒng)計剩下的結(jié)點的入度，再次將入度為零的結(jié)點提取出來，以此類推，這樣就形成了一個序列，這樣的序列就是該圖的拓撲排序序列；<

10、;p>　　3. 拓撲排序算法應能夠處理出現(xiàn)環(huán)的情況。個人在寫程序時，考慮到構造圖時，會有構造成有向有環(huán)圖的情況，應該在運行程序時，提醒出來，然后重新輸入有向無環(huán)圖，知道輸入正確為止。這樣就有多次構造鄰接表的問題，每一次構造鄰接表時，都應該將原來錯誤的（不是無環(huán)圖的）鄰接表空間釋放掉，否則，會變得混亂；　　4. 輸出除拓撲排序外，還要求輸出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲的，所以很容易將其鄰

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

12、具體分析如下：　　1. 圖像輸入，根據(jù)題目要求，要能夠建立一個有向無環(huán)圖，這就要我們在程序中去建立。考慮到輸入方式要盡量方便全面，采用輸入弧的方式，輸入每條弧的鏈接的兩個結(jié)點，當輸入-1時結(jié)束輸入。這樣再輸入的時候，與相鄰的兩個結(jié)點的鄰接矩陣對應的位置也做相應改變。　　2. 判斷圖是不是有向無環(huán)圖。當圖為有向無環(huán)圖時，則挑選完畢后，隊列應該是滿的，進行后

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

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

15、/p>　　對于圖的存儲，用到鄰接表，是一種鏈式存儲結(jié)構。　　typedef struct Node　　{　　int data;　　struct Node *next;&

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

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

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

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

20、當鄰接矩陣Graph[i][j]有值時，則構造鄰接表　　}　　2. 隊列初始化（入隊操作）及出隊操作　　在本算法中隊列主要用來，構造拓撲排序序列。由于隊列具有先入先出的特點，所以，將每次選擇入度為零的結(jié)點入隊，這樣當結(jié)點都入隊的時候，再依次出隊，這樣，排序序列顯而易見。它將圖

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

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

23、>　　return;　　}　　（2）出隊操作：　　int delqueue(int *queue)//出隊操作　　{</b&g

24、t;　　int e;　　if(rear==front)　　{　　return -2;　　}&

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

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

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

28、拓撲排序，其主要方法是將入度為零的結(jié)點依次輸出出來，知道圖的所有定點全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結(jié)點在其他結(jié)點都選擇出來后，入度都不為零，即無法被輸出出來。那么就可以認為按照拓撲排序的方法輸出結(jié)點后，若不是將節(jié)點全部輸出出來的，則此圖為有環(huán)圖。　　判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現(xiàn)環(huán)的情況，若構造的圖為有環(huán)圖，則折回開始重新輸入圖的數(shù)據(jù)，重新構造圖，直到該圖為無環(huán)

29、圖為止。若圖已經(jīng)是無環(huán)圖，則進行拓撲排序，排序方法前面已經(jīng)講過，在此主要訴說用到的輔助存儲。數(shù)組存儲各結(jié)點的入度，對入度為零的結(jié)點，依次入隊列，調(diào)整數(shù)組，結(jié)點全部入隊列后，然后依次出隊列，拓撲排序完成。　　void TopoSort(int *visited,int *Queue)　　{<

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

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

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

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

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

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

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

37、/b>　　printf("拓撲排序為：\n");　　for(i=0;i<l;i++)　　{printf("%d",ml[i]);　　if(i+1!=l)　　printf(&quo

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

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

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

41、一樣進行“拓撲排序”。　　程序應該條例清晰，結(jié)構明朗，各個函數(shù)代表各個模塊，起到不同的作用，并協(xié)調(diào)運作，形成含有不同功能的程序。開始時因為程序的結(jié)構混亂而導致很難調(diào)試，無法找到錯誤的根源。　　4.2 程序執(zhí)行過程　　對于有向無環(huán)圖，以圖4.2.1為例進行拓撲排序：　　圖4

42、.1 有向無環(huán)圖　　程序運行結(jié)果如圖4.2.2所示：　　圖4.2 有向無環(huán)圖拓撲排序　　對于有向有環(huán)圖，以圖4.2.3為例：　　圖4.3 有向有環(huán)圖　　程序運行結(jié)果如圖4.2.4所示：

43、圖4.4 有向有環(huán)圖程序運行結(jié)果　　參考文獻　　[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構[M].北京：清華大學出版社，2007.　　[2] 張長海，陳娟.C程序設計[M].北京：高等教育出版社，2004. 　　[3] 譚浩強.C程序設計[M]

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

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

46、表示當前點到源點的最短路徑長度　　int visited[maximum];　　int Queue[maximum];　　int l;　　int jj=0;<p&g

47、t;　　typedef struct Node　　{　　int data;　　struct Node *next;　　}GraphNode;　　Graph

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

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

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

51、gt;　　int delqueue(int *queue)//出隊操作　　{　　int e;　　if(rear==front)　　{&

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

53、　return e;　　}　　void CreateAdjacentTable(int v1,int v2)　　{　　GraphNode *newnode;

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

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

56、　　{　　int i;　　rear=-1;　　front=-1;　　int topnum=0;&l

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

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

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

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

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

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

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

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

65、n+1;　　}　　if(n==l)　　{　　printf("拓撲排序為：\n");<p&

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

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

68、nt Graph[maximum][maximum];　　GraphNode *kk,*dd;　　int source,destination;　　int i,j;　　printf("輸入圖的頂點個數(shù)：");<

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

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

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

72、",&source);　　}　　printf("輸入邊的第二個頂點：");　　scanf("%d",&destination);　　printf("\n&qu

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

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

75、amp;destination);　　}　　Graph[source-1][destination-1]=1;　　printf("輸入邊的第一個頂點：");　　scanf("%d",&s

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構課程設計-拓撲排序

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構課程設計-拓撲排序

文檔簡介

溫馨提示

最新文檔

評論

免費下載