拓撲排序課程設計--拓撲排序算法的研究與實現

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

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

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

文檔簡介

1、　　《數據結構》課程設計報告　　學院計算機與通信工程專業(yè) 網絡工程 　　班級網絡1101班學號 　　學生姓名指導教師 　　課

2、程成績完成日期 2013年7月12日　　課程設計任務書　　拓撲排序算法的研究與實現　　摘要該課程設計研究AOV網。研究圖的存儲結構，研究AOV網（活動在頂點的網，有向網）的存儲結構與輸入算法，并研究拓撲排序算法的實現方法，在此基

3、礎上對該算法進行分析。通過對拓撲排序問題的分析、設計、編碼、測試等工作，掌握針對實際應用問題設計數據結構，結合C語言解決實際應用問題的一般方法和過程，初步掌握利用數據結構解決實際應用問題的一般方法。　　關鍵字 AOV網；拓撲排序；算法設計；C語言；數據結構　　目錄<b

4、>　　摘要3　　1 引言5　　1.1 課程設計的目的5　　1.2 課程設計的內容6　　1.3 課程設計的目標6　　2 設計內容7&

5、lt;/b>　　2.1 問題描述7　　2.2 思路分析7　　2.3 過程演示8　　3 算法分析及詳細實現9　　3.1 算法分析9　　3.2 算法中用到的函數聲明

6、9　　3.3 部分程序編寫9　　4 程序的運行環(huán)境及運行結果11　　4.1 程序運行的環(huán)境11　　4.2 運行結果11　　5 總結14

7、　　5.1 課程設計總結14　　5.2 心得與體會14　　參考文獻15　　附件16　　1 引言　　課程設

8、計是培養(yǎng)學生綜合運用所學知識，發(fā)現，提出，分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對學生實際工作能力的具體訓練和考察過程。　　數據結構是學習計算機相關專業(yè)的非常重要的知識，所謂結構就是組織形式，數據的結構就是數據怎么組織，即怎么描述，怎么在電腦中存儲。不同類型的數據，它們的組織形式（數據結構）是不同的，在程序設計中，除了應精心設計算法外，還應精心組織數據（包括原始數據、中間結果、最終結果

9、），使之形成一定的組織形式（數據結構），以便讓計算機盡可能高效率地處理?！稊祿Y構》是計算機科學與工程的基礎研究之一，掌握該領域的知識對于我們進一步進行高效率的計算機程序開發(fā)非常重要。無論在中國還是在美國，《數據結構》一直是大學的計算機專業(yè)重要的專業(yè)基礎課。　　數據結構的課程設計要求學生熟練掌握數據結構的邏輯特性和物理表示，具有分析問題的能力，可以根據問題選擇合適的數據結構，運用該數據結構結合相

10、應的算法解決實際問題。　　1.1 課程設計的目的　　為了更好的學習數據結構，深刻理解數據結構在解決實際問題中的應用，體會其重要性，熟練掌握線性表、棧和隊列、串、數組、樹、圖等常用的數據結構，熟悉各自的特點和應用場合。　　同時鍛煉自己獨立分析理解問題的能力，學會根據不同的問題選擇合適的數據結構，然后結合適當的算法

11、解決問題。鍛煉自己的設計和編寫程序的技巧，進一步調試和測試自己所寫的程序，使其功能更加完善，養(yǎng)成較好的編寫程序習慣。　　提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力[1]，訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際

12、問題在計算機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能[2]。　　1.2 課程設計的內容　　本次課程設計要求對于給定的AOV網求出它所有拓撲序列。AOV網（是一個有向無環(huán)圖（Directed Acycline Graph，DAG圖）[3]。AOV網中，如果頂點Vi表示的活動在和頂點Vj表示的活動之前進行，則稱Vi是Vj的前驅頂點，Vj是Vi后繼頂點

13、。拓撲排序就是將有向無環(huán)圖中的各個頂點排成一個序列，使得所有的前去后繼關系都得到滿足。對于相互之間沒有次序關系的頂點，在拓撲排序的序列中可以處在任意的位置。因此，拓撲排序的結果往往是不唯一的。本次課程設計的主要任務就是將給定的一個AOV網輸出所有的該種序列[4]。　　1.3 課程設計的目標　　通過對拓撲排序問題的分析、設計、編碼、測試等工作，掌握針對實

14、際應用問題設計數據結構，結合C語言解決實際應用問題的一般方法和過程，初步掌握利用數據結構解決實際應用問題的一般方法。　　2 設計內容　　2.1 問題描述　　在AOV網中為了更好地完成工程，必須滿足活動之間先后關系，需要將各活動排一個先后

15、次序即為拓撲排序。拓撲排序可以應用于教學計劃的安排，根據課程之間的依賴關系，制定課程安排計劃。按照用戶輸入的課程數，課程間的先后關系數目以及課程間兩兩間的先后關系，程序執(zhí)行后會給出符合拓撲排序的課程安排計劃。　　2.2 思路分析　　一種拓撲序列的生成一般有一下步驟：　?。?

16、）、從有向無環(huán)圖中選擇一個沒有前驅結點的頂點并加入到結點的序列中；　　（2）、從有向無環(huán)圖中刪除該頂點以及該頂點為尾的所有的??；　　（3）、重復（1）（2）的步驟。　　在整個拓撲排序的過程中需要頻繁的檢查頂點的前驅以及作刪除頂點和弧的操作，在這里我們用兩個全局變量rudu[max_vertex_num]和visi

17、ted[max_vertex_num]來分別實現這兩個操作，如果rudu[i]為零則表示無前驅結點，如果visited[i]為零則表示沒有被訪問過。如果每刪除一個結點就檢查，那樣的話時間復雜度將很大（等于遍歷所有的頂點一遍），因此設計一個堆棧，把檢測到的入度為零的結點入棧。每次刪除頂點只要從棧中取出一個結點即可。　　但是如果需要實現一個AOV網所有拓撲序列的生成則不止如此。在每找到一個符合要求的

18、結點后入棧，從而實現一種拓撲排序。在一趟拓撲排序結束后，應該進行恢復刪除的結點和刪除的弧，并標記已經有過的序列，在恢復某幾個個結點后進行下一次的拓撲排序。　　2.3 過程演示　　該部分給出了算法執(zhí)行的流程，如圖2-1所示。　　圖 2-1 算法流程圖&

19、lt;p>　　3 算法分析及詳細實現　　3.1 算法分析　　首先建立空棧，并從第一個頂點開始進行拓撲排序。將該結點初始化為被訪問過，并將圖類的結點指針指向該編號的結點的表頭數組firstarc域，把該頂點入棧后，將所有的以它為起點的弧都刪掉，即將弧的終點的入度都減一。接著判斷棧里面的數據個數是否和圖頂點的個數

20、一樣，如果一樣，則說明已經有一次拓撲排序完成，若不一樣，則往下進行遞歸，再將符合條件的頂點入棧，直到一次拓撲排序完成的條件成立。最后將頂點出棧，恢復所有結點的入度，并準備下一趟拓撲排序。　　3.2 算法中用到的函數聲明　　在該程序中用到了很多函數，具體聲明如表3-1所示。　　表3-1 算法中用到的函數聲明<

21、;/p>　　3.3 部分程序編寫　　實現該算法的具體編碼如下：　　void topusort(Stack *L,ALGraph *G,int i){//拓撲排序　　ListNode *P;　　int j,k;Soutput(L);</p

22、>　　Sinsert(L,i); //把頂點Vi加入到棧中　　P=G->head[i].firstarc;　　visited[i]=1; //把排序過的點標記　　while(P){　　j=P->number;&l

23、t;/p>　　rudu[j]--; //把以Vi為頭的終止結點入度減1　　P=P->next;　　}　　if(L->top+1==G->vexnum){//判斷棧中一種拓撲排序完成　　S

24、output(L);　　printf("\n");　　flag++;　　}　　for(k=0;k<G->vexnum;k++)//調用部分&

25、lt;p>　　if((visited[k]==0)&&(rudu[k]==0))// 如果Vk在此輪中未被訪問過且入度為0　　topusort(L,G,k);　　visited[i]=0; //使Vi恢復為未訪問　　P=G->head[i].firstarc;

26、　　while(P)　　{　　j=P->number;　　rudu[j]++; //使Vj的入度恢復，加1　　P=P->next;<

27、p>　　}　　Sdelete(L);　　}　　4 程序的運行環(huán)境及運行結果　　4.1 程序運行的環(huán)境　　一個程序需要一個良好的環(huán)境才能運行，該課

28、程設計中的程序運行的硬件、軟件環(huán)境如下。　?。?）硬件環(huán)境　　1）學生用微機　　2）局域網　?。?）軟件環(huán)境</p

29、>　　1）Windows 8 旗艦版系統(tǒng)　　2）VS2010　　4.2 運行結果　　程序的運行結果將從三個方面予以介紹。　?。?）圖的輸入</

30、b>　　輸入圖，結果如圖4-1所示。在這里首先輸入頂點數和邊數，然后輸入沒條邊的起點終點編號和權值。　　圖 4-1 圖的輸入　　（2）圖鄰接表的輸出　　輸出圖的鄰接矩陣。輸入圖過后按回車鍵顯示圖的鄰接表，如圖4-2所示。

31、圖 4-2 圖鄰接表的輸出　?。?）拓撲序列的輸出　　在顯示完拓撲序列后按回車輸出該圖的所有拓撲排序序列，如圖4-3所示。　　圖 4-3 拓撲序列的輸出　　5 總結　　5.1 課程設計總結&

32、lt;/p>　　課程設計可以檢驗學生對知識的掌握程度。同時更反映了一個學生對課程設計的態(tài)度，對待任何事都要認真，可以不會，可以做的不是最好的，但是一定要盡自己最大的努力去完成一件哪怕再小的事。在這次課程設計中學到了很多新的知識，同時也鞏固了之前學過知識。對靜態(tài)鏈表有了更深的理解，對哈夫曼樹及哈夫曼編碼更是印象深刻。雖然，最后根據要求完成了任務，但期間還是出現了種種的問題，比如在編寫完函數時，運行結果總是不對，

33、調試了好多遍，也沒有發(fā)現錯誤，沒有想到是選擇函數除了差錯，一個簡單的函數，怎么也沒有想到會是這里出了錯，是因為我給s1，s2變量賦初值時出了錯誤。同時，為了更好的完成任務還查閱了好多資料，不懂的就到處搜索，去圖書館借相應的書籍來看，鍛煉了自己查閱資料的能力。　　5.2 心得與體會　　我覺得本此課程設計最大的收獲就是學會按部就班的完成任務。首先想好用什么

34、數據結構，主要的思想要明確的認定。然后選一個簡單的例子，按照你選定的思想，一步一步的走程序，才能更早的發(fā)現程序還存在那些沒有考慮到的缺陷。特別忌諱的是到寫程序的時候，對主要思想和數據結構還不是很確定。最后在調試程序的階段，這次我開始用設置斷點的方法，一步一步看是否達到你要的理想結果，從而來找出程序中出錯的地方。還有，一種方法也是用一個輸出語句，分別放在程序的不同位置，通過輸出結果，也可以快速判斷出程序不能運行的是那一個語句了。從而方便你

35、修改，快速得到正確的結果。還有，這次調試的過程中，我表現的比以前要更有耐心，這也是一個很好的收獲。　　還有一個更重要的體會就是，遇到不會的地方，我開始習慣到圖書館或是網上去找資料。這是一個很好的學習過程，它不僅僅是可以解決這個問題，關鍵是你會從找資料學習的過程中，會學好很多很多意想不到的知識?？赡軙饶闶诸^上要學習的知識多得多。　　參考

36、文獻　　[1]嚴蔚敏，吳偉民.數據結構(C語言版)[M].北京:清華大學出版社,2012.5[2]李春葆，尹為民.數據結構教程上機指導[M].北京:清華大學出版社,2008[3]Andrew Binstock，John Rex.程序員實用算法(第二版)[M].北京:機械工業(yè)出版社,2009.06[4]Thomas H.Cormen, Charles E.Leiserso

37、n,Ronald L.Riverst, Clfford Stein.Introduction to Alogrithms Second Edition[M].US:Machine Press,2012　　附件　　程序清單　　#includ

38、e"stdio.h"　　#include"malloc.h"　　#include"stdlib.h"　　#define max_vertex_num 100 //頂點的最大個數　　typedef struct n

39、ode{ //鄰接表中的結點類型　　int number; //結點編號　　struct node *next; //指向下一個結點　　int info; //與

40、表頭結點邊的信息　　}ListNode;　　typedef struct{ //定義表頭結點數組　　int number; //頂點信息　　ListNode *firstarc; //指向第一個鄰接點<

41、/p>　　}AdjList; //表頭結點類型　　typedef struct{ //鄰接表類型　　AdjList head[max_vertex_num]; //鄰接表的組<

42、p>　　int vexnum; //頂點個數表頭數　　intedgnum; //邊的個數　　}ALGraph;　　typedef struct{

43、int data[max_vertex_num];//堆棧數組　　int top;//棧頂標志　　}Stack; //順序表類型　　int rudu[max_vertex_num];//定義一個存儲每個頂點入度的全局數組　　int visited[max_vert

44、ex_num];//定義全局數組標志拓撲排序過程中是否訪問過　　int flag=0;//接受拓撲排序的次數，若為0，則該圖不是AOV網　　ALGraph *create_AdjListGraph(){　　ALGraph *T; ListNode *p; //定義指向結點的指針<p&

45、gt;　　int i,j; //輸入邊是的起點和終點　　T=(ALGraph *)malloc(sizeof(ALGraph));//定義圖　　printf("1、請輸入頂點數:");　　scanf("%d",&T-&g

46、t;vexnum); //輸入頂點個數　　for(i=0;i<T->vexnum;i++){ //初始化表頭結點數組　　T->head[i].number=i; //初始化結點編號　　rudu[i]=0; //將每個節(jié)點

47、的荼毒初始化為　　visited[i]=0;　　T->head[i].firstarc=NULL; //將表頭結點數組的每個結點的指針域置空　　}　　printf("2、請輸入邊數:");</p&g

48、t;　　scanf("%d",&T->edgnum); //輸入邊的個數　　printf("3、按起點終點權值的順序一次輸入邊的序列:\n");　　for(i=0;i<T->edgnum;i++){　　prin

49、tf("請輸入第 %d 條邊:",i+1);　　p=(ListNode *)malloc(sizeof(ListNode));　　scanf("%d",&j); //輸入這條邊起始節(jié)點的編號　　scanf("%d",&a

50、mp;p->number); //輸入這條邊的終點的編號　　scanf("%d",&p->info); //輸入這條邊的權值　　printf("\n");　　rudu[p->number]++; //將插入邊

51、中結點的入度加1　　p->next=T->head[j].firstarc;　　T->head[j].firstarc=p; //將該結點插入到單鏈表中創(chuàng)建一條邊　　}　　return T

52、;　　}　　void print(ALGraph *T){//輸出圖的鄰接表　　ListNode *p;　　int i;　　print

53、f("表頭數組(該結點的入度) 與之有邊的節(jié)點（該弧的權值）\n");　　for(i=0;i<T->vexnum;i++){　　printf("V%d（%d） ",T->head[i].number,rudu[i]);　　p=T->

54、;head[i].firstarc;　　while(p){　　printf("---------------->V%d(%d)",p->number,p->info);　　p=p->next;

55、;　　}　　printf("\n");　　}　　}　　Stack *Setnull(){//置棧空

56、;　　Stack *L;　　L=(Stack *)malloc(sizeof(Stack));　　L->top=-1;　　return(L);　　}

57、　　void Sinsert(Stack *L,int x){//入棧　　L->top=L->top+1;　　L->data[L->top]=x;　　} 　　void Sdelete(Stack *L){//出

58、棧　　L->top=L->top-1;　　}　　void Soutput(Stack *L){//輸出棧中元素 　　int i;　　for

59、(i=0;i<L->top+1;i++)　　printf("V%d ",L->data[i]);　　printf("\n");　　}　　void topusort(Stack

60、*L,ALGraph *G,int i){//拓撲排序　　ListNode *P;　　int j,k;Soutput(L);　　Sinsert(L,i); //把頂點Vi加入到順序表中　　P=G->head[i].firstarc;&

61、lt;p>　　visited[i]=1; //把排序過的點標記　　while(P){　　j=P->number;　　rudu[j]--; //把以Vi為頭的終止結點入度減1　　P=P->next;&

62、lt;b>　　}　　if(L->top+1==G->vexnum){//判斷順序表中一種拓撲排序完成　　Soutput(L);　　printf("\n");　　flag++;&

63、lt;/p>　　}　　for(k=0;k<G->vexnum;k++)//調用部分　　if((visited[k]==0)&&(rudu[k]==0))// 如果Vk在此輪中未被訪問過且入度為0　　topusort(L,

64、G,k);　　visited[i]=0; //使Vi恢復為未訪問　　P=G->head[i].firstarc;　　while(P)　　{　　j=

65、P->number;　　rudu[j]++; //使Vj的入度恢復，加1　　P=P->next;　　}　　Sdelete(L);　　}&

66、lt;/p>　　void caidan(){　　printf(" \t_____________________________________________________________\n\n");　　printf(" \t◇

67、 ◇\n");　　printf(" \t◇ ◇\n");　　printf(" \t◇ **********歡迎使用AOV網拓撲序列顯示程序！**

68、******** ◇\n");　　printf(" \t◇ ◇\n");　　printf(" \t◇

69、 ◇\n");　　printf("\t_____________________________________________________________\n");　　}　　void caidan1(){

70、　　printf("\n\n\n\n\n");　　printf(" \t_____________________________________________________________\n\n");　　printf(" \t◇

71、 ◇\n");　　printf(" \t◇ ◇\n");　　printf(" \t◇ ★★★★ 謝謝使用

72、！ ★★★★ ◇\n");　　printf(" \t◇ ◇\n");　　printf(" \t◇

73、 ◇\n");　　printf(" \t_____________________________________________________________\n");　　}　　void main()&l

74、t;/p>　　{　　int i;ALGraph *G;Stack *L;int n=1;　　L=Setnull();　　while(n==1){//循環(huán)顯示拓撲排序　　system("cls&qu

75、ot;);　　caidan();　　printf("注意：請按下列步驟輸入您的ＡＯＶ網！\n");　　G=create_AdjListGraph();　　system("cls");</p

76、>　　caidan();　　printf("該圖的鄰接表為：\n");　　print(G);　　system("pause");

77、　　system("cls");　　caidan();　　printf("以下是該圖所有的拓撲序列：\n");　　for(i=0;i<G->vexnum;i++)　　if(rudu[

78、i]==0&&visited[i]==0) topusort(L,G,i);　　if(flag>0){　　printf("該AOV圖有%d種拓撲排序.\n",flag);　　flag=0;&

79、lt;b>　　}　　else 　　printf("\n\n\t出錯!\n\n此圖不是AOV網，無拓撲排序序列.\n\n\n");　　system("pause");

80、　　system("cls");　　caidan();　　printf("按1繼續(xù)顯示下一個圖的拓撲序列，按0結束程序！\n");　　scanf("%d",&n);

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

溫馨提示

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

拓撲排序課程設計--拓撲排序算法的研究與實現

文檔簡介

溫馨提示

最新文檔

評論

拓撲排序課程設計--拓撲排序算法的研究與實現

文檔簡介

溫馨提示

最新文檔

評論

免費下載