拓撲排序課程設(shè)計報告

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

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

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

文檔簡介

1、　　拓撲排序　　一目的　　通過課程設(shè)計，加深對《程序設(shè)計語言》和《軟件技術(shù)基礎(chǔ)》課程所學(xué)知識的理解，熟練掌握和鞏固C語言的基本知識和語法規(guī)范，包括：數(shù)據(jù)類型（整形、實型、字符型、指針、數(shù)組、結(jié)構(gòu)等）；運算類型（算術(shù)運算、邏輯運算、自增自減運算、賦值運算等）

2、；程序結(jié)構(gòu)（順序結(jié)構(gòu)、判斷選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)）；庫函數(shù)應(yīng)用等；復(fù)雜任務(wù)功能分解方法（自頂向下逐步求精、模塊化設(shè)計、信息隱藏等），熟練掌握和鞏固三種基本圖形結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及相關(guān)運算和應(yīng)用。　　學(xué)會編制結(jié)構(gòu)清晰、風(fēng)格良好、數(shù)據(jù)結(jié)構(gòu)適當(dāng)?shù)腃語言程序，從而具備利用計算機編程分析解決綜合性實際問題的初步能力。　　二需求分析<

3、;/b>　　題目描述：判斷一個有向圖是否存在回路，并求出有向無環(huán)圖的拓撲序列。　　1、輸入數(shù)據(jù)　　在工程文件中保存輸入2個字符串?dāng)?shù)TXT文件。第一個為圖按次序排列的所有邊的前頂點，第二個為相對應(yīng)的第二個頂點。

4、　2、輸出數(shù)據(jù)　　圖的定點數(shù)，邊數(shù)，每個頂點的信息及入度，構(gòu)造的鄰接表，圖的拓撲排序。　　3、程序功能　　已將AOV網(wǎng)存入文件中，運行時從文件讀取數(shù)據(jù)；對一個AOV網(wǎng)，應(yīng)判斷其是否是有向無環(huán)圖，若是則輸出其任意一個拓撲排序序列，不是則進行相關(guān)的說明；構(gòu)造圖

5、的鄰接表；輸出所有頂點的入度。　　三概要設(shè)計　　1、全局變量或類型說明　　//********結(jié)構(gòu)體定義***********//　　typedef struct A_Node //定義表結(jié)點結(jié)構(gòu)<p

6、>　　{　　int adjvex; //與vi相鄰接的頂點編號　　struct A_Node *nextarc; //指向下一條弧(邊)的指針　　} A_Node;　　typedef str

7、uct V_Node //定義表頭結(jié)點結(jié)構(gòu)　　{　　int data;　　A_Node *firstarc; //指向第一條?。ㄟ叄┑闹羔?lt;/p>　　} V_Node, AdjList[MAX_NUM];

8、　　typedef struct //定義鄰接表結(jié)構(gòu)　　{　　AdjList vertices; //表頭結(jié)點數(shù)組　　int vex_num, arc_num; //頂點和弧（邊）的個數(shù)　　}

9、 ALGraph;　　typedef struct //構(gòu)件棧　　{　　Elem_T *base;　　Elem_T *top;　　int stacksize;<p

10、>　　} Sq;　　2、模塊功能　　1) void Init(Sq *S); 　　功能：初始化棧。構(gòu)造一個空棧S　　參數(shù)：*S 待初始化的棧　　2)

11、 int Stack(Sq *S)　　功能：判斷空棧　　參數(shù)：S 待判斷的棧　　返回值：棧為空返回 1；棧非空返回 0　　3) Void Int(Sq *S, Elem_T e)<b&g

12、t;　　功能：元素入棧　　參數(shù)：*S 待操作的棧；插入元素e為新的棧頂元素　　4) void Out(Sq *S, Elem_T e);　　功能：元素出棧　　參數(shù)：*S 待操作的棧；若棧不空，則刪除S的棧頂元素，用

13、e返回其值，并返回1；否則返回0　　5) void Creat_Graph(ALGraph *G)　　功能：建立圖。函數(shù)內(nèi)包含了由用戶輸入頂點數(shù)、弧數(shù)、頂點以及弧的操作　　參數(shù)：*G 待操作的圖　　返回值：圖建立成功返回1；圖建立失敗返回0<

14、p>　　6) void Find_InDegree(ALGraph G, int indegree[])　　功能：求頂點的入度　　參數(shù)：G 待操作的圖，indegree[]儲存每個頂點的入度的數(shù)組　　7) void TuoPu(ALGraph G);

15、　　功能：實現(xiàn)拓撲排序，并在圖形界面上演示排序過程　　參數(shù)：G 待進行拓撲排序的圖　　錯誤判斷：包含有向圖是否有環(huán)的判斷　　四詳細設(shè)計　　源代碼詳情如下：</p&g

16、t;　　//*****拓撲排序*********//　　//******張雪濤*********//　　//*****2013.12.27******//　　//*****函數(shù)頭文件、宏定義、變量聲明*******//　　#include<ST

17、DIO.H>　　#include<STDLIB.H>　　#define MAX_NUM 15 　　#define STACK_SIZE 100　　#define STACK_MENT 10　　#define

18、OK 1　　#define M 20　　#define ERROR 0　　#define NUM 15　　typedef int Elem_T;　　char number1[NUM];

19、char number2[NUM];　　//********結(jié)構(gòu)體定義***********//　　typedef struct A_Node //定義表結(jié)點結(jié)構(gòu)　　{　　int adjvex; //與vi相鄰接的頂點編號</p

20、>　　struct A_Node *nextarc; //指向下一條弧(邊)的指針　　} A_Node;　　typedef struct V_Node //定義表頭結(jié)點結(jié)構(gòu)　　{<

21、p>　　int data;　　A_Node *firstarc; //指向第一條?。ㄟ叄┑闹羔?lt;/p>　　} V_Node, AdjList[MAX_NUM];　　typedef struct //定義鄰接表結(jié)構(gòu)　　{

22、　　AdjList vertices; //表頭結(jié)點數(shù)組　　int vex_num, arc_num; //頂點和?。ㄟ叄┑膫€數(shù)　　} ALGraph;　　typedef struct //構(gòu)件棧<b&g

23、t;　　{　　Elem_T *base;　　Elem_T *top;　　int stacksize;　　} Sq;　　//********函數(shù)聲明***********//

24、　　void Init(Sq *);　　int Stack(Sq *); 　　void TuoPu(ALGraph);　　int Out(Sq *, Elem_T);　　int Int(Sq *, Elem_T *);</p

25、>　　void Creat_Graph(ALGraph *);　　void Find_InDegree(ALGraph, int *);　　//********主函數(shù)***********//　　int main(void)

26、　　{　　char num='Y';FILE *fp;　　fp=fopen("num1.txt","r"); //打開num1文件　　if(fp!=NULL)

27、;　　{　　for(int i=1;i<=NUM;i++){　　fscanf(fp,"%d",&number1[i]);//將文件的內(nèi)容讀入number1數(shù)組中　　}　　fclos

28、e(fp); //關(guān)閉文件　　}　　fp=fopen("num2.txt","r"); //打開文件num2　　if(fp!=NULL)<

29、p>　　{　　for(int i=1;i<=NUM;i++){　　fscanf(fp,"%d",&number2[i]);//讀取文件的內(nèi)容到number2中　　}<p

30、>　　fclose(fp); //關(guān)閉文件　　}　　while(1)　　{　　printf("

31、\n歡迎您繼續(xù)使用，請選擇 Y or N :"); //判斷是否為Y，若是則繼續(xù)運行，若是N則退出　　scanf("%c",&num);　　if(num=='N')　　exit(0);<p&g

32、t;　　ALGraph G;　　Creat_Graph(&G); //調(diào)用函數(shù)創(chuàng)建有向圖　　TuoPu(G); //進行拓撲排序　　}

33、　　return 0;　　}　　void Init(Sq *S) //初始化棧　　{　　S->base

34、 = (Elem_T *) malloc(STACK_SIZE * sizeof (Elem_T));//構(gòu)建空指針　　if (!S->base) {　　printf("memory allocation failed, goodbye");//判斷是否建立成功　　ex

35、it(1);　　}　　S->top = S->base;　　S->stacksize = STACK_SIZE;　　}

36、;　　int Out(Sq *S, Elem_T *e)//出棧操作　　{　　if (S->top == S->base) {　　return ERROR;　　}

37、　　*e = *--S->top;　　return 0;　　}　　void Int(Sq *S, Elem_T e)//進棧操作　　{

38、;　　if (S->top - S->base >= S->stacksize) {　　S->base = (Elem_T *) realloc(S->base, (S->stacksize + STACK_MENT) * sizeof (Elem_T));　　if (!

39、S->base) {　　printf("memory allocation failed, goodbye");　　exit(1);　　}　　S->top = S-

40、>base + S->stacksize;　　S->stacksize += STACK_MENT;　　}　　*S->top++ = e;　　}&l

41、t;p>　　int Stack(Sq *S)//判斷棧是否為空　　{　　if (S->top == S->base)　　return OK;　　else&

42、lt;p>　　return ERROR;　　}　　void Creat_Graph(ALGraph *G)//構(gòu)建圖　　{　　int m, n, i,j;<p&

43、gt;　　A_Node *p;　　printf("\n***************************************************\n");　　printf("********* 歡迎您使用拓撲排序 ***********\n");<p&

44、gt;　　printf("********* 制作者：張雪濤 ***********\n");　　printf("********* 學(xué)號：10056041 ***********\n");　　printf("********************

45、*******************************\n");　　printf("請輸入頂點數(shù)和邊數(shù):10 15");　　G->vex_num=10 ;//要構(gòu)建的頂點個數(shù)　　G->arc_num=15;//要構(gòu)建的邊數(shù)

46、　　for (i = 1; i <= G->vex_num; i++) {　　G->vertices[i].data = i;//構(gòu)建頂點　　G->vertices[i].firstarc = NULL;　　}

47、　　j=1;　　for (i = 1; i <= G->arc_num; i++) //輸入存在邊的點集合　　{　　if(j>15)<

48、b>　　{ j=1;}　　n=number1[j];//起點數(shù)組　　m=number2[j];//終點數(shù)組　　printf("\n 第");　　printf("%d ",i);&

49、lt;p>　　if(i>=10)　　printf("條邊的兩頂點序號分別為為:");　　else　　printf(" 條邊的兩頂點序號分別為為:");<p&

50、gt;　　printf("%d ",n);//打印構(gòu)建的邊　　printf("%d",m);　　j++;　　//scanf("%d%d", &n, &m);

51、　while (n < 0 || n > G->vex_num || m < 0 || m > G->vex_num) {　　printf("\n 輸入的頂點序號不正確請重新輸入!");　　printf("\n 第");　　pr

52、intf("%d ",i);　　if(i>=10)　　printf("條邊的兩頂點序號分別為為:");　　else　　printf(" 條邊

53、的兩頂點序號分別為為:");　　scanf("%d%d", &n, &m);　　}　　p = (A_Node*) malloc(sizeof (A_Node));//構(gòu)建空鏈表　　if (

54、p == NULL) {　　printf("memory allocation failed,goodbey");　　exit(1);　　}　　p->adjvex = m

55、;//表頭指向終點　　p->nextarc = G->vertices[n].firstarc;　　G->vertices[n].firstarc = p;　　}　　}</

56、p>　　void Find_InDegree(ALGraph G, int indegree[])//找入度為零的節(jié)點　　{　　int i;　　for (i = 1; i <= G.vex_num; i+

57、+) {　　indegree[i] = 0;　　}　　for (i = 1; i <= G.vex_num; i++) {　　while (G.vertices[i].firstarc) {<p&g

58、t;　　indegree[G.vertices[i].firstarc->adjvex]++;　　G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;　　}　　}&

59、lt;/p>　　}　　void TuoPu(ALGraph G) //進行拓撲排序　　{　　int indegree[M];　　int i, k, n;</p&g

60、t;　　int count = 0; //用來統(tǒng)計頂點的個數(shù)　　A_Node *p; //定義一個棧，用來保存入度為0的頂點　　Sq S;　　Find_InDegree(G, indegree);//查找深度

61、Init(&S);//初始化棧　　for (i = 1; i <= G.vex_num; i++) {　　if (!indegree[i])//如果深度為0則入棧　　Int(&S, i);　　}

62、;　　if (count < G.vex_num) {　　printf("\n\n該有向圖有回路!!!\n");　　}　　else{　　printf

63、("\n進行拓撲排序輸出順序為:\n"); //輸出結(jié)果　　while (!Stack(&S)) {　　Out(&S, &n);//出棧　　printf("%4d", G.vertices[n].data);//打印結(jié)果<

64、;p>　　count++;　　for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc) {　　k = p->adjvex;　　if (!(--indegree[k])) //自減若深度為0則入棧&

65、lt;/p>　　Int(&S, k);//入棧　　}　　}　　printf("\n");　　printf("排序成功\n"

66、;);　　}　　}　　五調(diào)試分析　　1、測試數(shù)據(jù)　　圖的

67、拓撲排序：　　2、存在過的問題以及分析解決　?。?）本課程設(shè)計采用先把主體結(jié)構(gòu)寫好后在網(wǎng)結(jié)構(gòu)中添加具體的分布功能。采用的是主分式的形式以保證一個功能不能實現(xiàn)并不影響其他的功能。　　（2）課程設(shè)計有較好的容錯能力，能夠讓一般用戶也不出錯，能正確的輸入信息和統(tǒng)計，保證了正確性。

68、　?。?）修改的時候采用一邊調(diào)試一邊修改，并不斷嘗試錯誤輸入和驗證。　　六測試結(jié)果　　測試結(jié)果如下圖所示：　　正常使用：　　繼續(xù)選擇是否使用：</

69、b>　　錯誤的輸入如下：　　有回路的操作如下：　　七用戶使用說明　　運行程序前在工程文件中輸入所構(gòu)造圖的邊頂點并保存,運行后會輸出圖的頂點數(shù)，邊數(shù)，

70、頂點信息，圖的所有邊數(shù)，構(gòu)造的連接表，每個頂點的入度和有向無環(huán)圖的拓撲排序及對有環(huán)圖進行說明。再按任意鍵，結(jié)束程序運行，進行對其他圖的拓撲排序。　　八課程設(shè)計總結(jié)　　根據(jù)本課程設(shè)計的實驗，從中學(xué)到了編程其實也是一項很有考驗性的活動，從很大程度上提高了我們對這門課程的了解和學(xué)習(xí)，并學(xué)會從實踐中總結(jié)經(jīng)驗，從實驗中找到

71、方法，通過本次課程設(shè)計加深了對所學(xué)知識的理解。大家都知道，編程是一件很需要耐心的事。因為幾乎每一個程序的編寫，都需要學(xué)習(xí)新的知識才能進行，同時程序調(diào)試過程很枯燥，有時候一點小錯意味著長時間的查錯。如語法錯誤中，“;”丟失、“{”與“}”不匹配等問題最難定位到出錯語句；邏輯錯誤中，作為循環(huán)變量的“i”與“j”相互混淆、對未分配空間的節(jié)點進行操作等，都會使程序運行出錯而難以找到原因。算法設(shè)計、程序調(diào)試的過程中，經(jīng)常遇到看似簡單但又無法解決的

72、問題，這時候很容易灰心喪氣，此時切不可煩躁，一定要冷靜的思考，認真的分析；而解決問題，完成程序后，那種興奮感與成就感也令人振奮。可以說編寫程序既是一件艱苦的工作，又是一件愉快的事情。　　在完成課程設(shè)計的過程中，我加深了對程序結(jié)構(gòu)的了解程度，對各種語句理解也更透徹，學(xué)會了靈活運用。同時體會到了團隊合作的樂趣，一向慣于“獨立思考”的我們學(xué)會了積極地同團隊成員交流，取長補短，共同進步，只有和同學(xué)多交流

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

溫馨提示

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

拓撲排序課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

拓撲排序課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載