1、目錄摘要3學生成績管理系統4第一章概述41.1 開發前的準備41.2 開發設計的意義41.3 需求分析4第二章學生成績管理系統概要設計52.1 開發方案52.2系統流程圖52.3 系統功能圖6第三章詳細設計83.1 刪除學生信息功能的實現83.2 修改學生信息功能的實現9第四章調試分析114.1系統運行主界面114.2 增加學生信息功能的實現114.3 刪除學生信息功能的實現124.4 查詢學生信息功能的實現134.5 修改學生信息功能的實現134.6 排序功能的實現14第五章程序設計結語155.1 系統存在的問題155.2 系統改進的方向155.3 此次課程設計的體會15猴子選大王16第一章

2、概述161.1 開發的目的161.2 開發設計的意義161.3 需求分析16第二章猴子選大王系統概要設計172.1系統流程圖17第三章詳細設計183.1系統的實現18第四章調試分析204.1系統運行主界面204.2系統運行結果21第五章程序設計結語225.1 此次課程設計的總結22迷宮求解23第一章概述231.1 開發的目的和意義231.2 需求分析23第二章迷宮求解系統概要設計242.1系統設計概要24第三章詳細設計253.1系統的實現25第四章調試分析294.1系統運行界面29第五章程序設計結語305.1 此次課程設計的總結30圖的遍歷及拓撲排序31第一章概述311.1 開發設計的目的和意

3、義311.2 需求分析31第二章圖的遍歷及拓撲排序系統概要設計322.1系統流程圖322.2功能模塊圖33第三章詳細設計343.1 系統功能的實現34第四章調試分析384.1系統運行主界面384.2 系統運行結果38第五章程序設計結語405.1 此次課程設計的總結40參考文獻42摘要隨著社會的發展，人民生活水平的提高，人們對教育的重視程度也隨之增加，越來越多的人走入高等學府，由此，各所學校的學生數量也日益增加。這使得學校對學生的管理難度逐漸增大。而管理好學生成績是維護社會安定、提高教學質量、保證教學進度有條不紊進行的有力保障。由此可見，學生成績管理是一項極其重要的工作；同時，學生成績管理又是一

4、項極其龐大的工作。那么，如何管理學生成績呢？由于計算機技術的迅速發展和普及，如果用計算機來管理學生成績，則會使學生成績的管理工作變得更輕松。介于這種需求，學生成績管理系統便應運而生了。此次課程設計便是運用我們所學的知識試著設計一個學生成績管理系統，使其實現一些簡單的基本過程。經過分析，本系統以VC+6.0為開發工具，主要運用C語言進行編程。本系統實現了增添學生、刪除學生、查找學生、修改學生信息以及排序、保存信息、讀取信息、退出系統等功能。其操作簡單易學、界面清晰明了易于理解；操作人員不需要有很高的專業知識，容易普及推廣；運行比較穩定，比較適合現在大學校園對學生成績的管理，能夠有效提高成績處理的

5、速度和準確度。另外還有猴子選大王系統可以解決日常生活中出現的選舉問題；迷宮求解系統，可以供人們娛樂以及智力開發；圖的遍歷和拓撲排序系統，用來解決排序問題。關鍵詞：成績管理，VC+6.0，C語言，編程學生成績管理系統第一章 概述1.1 開發前的準備在進行程序設計之前要熟練掌握數據結構以及C語言中的相關基礎知識。根據我們日常生活中的經驗，結合自己平時所接觸到的本校學生成績管理系統，做好需求分析，明確程序設計的具體要求。掌握VC+6.0的使用方法，準備計算機、VC+6.0等基本設備。為下一步具體開發設計做好充分的準備。1.2 開發設計的意義學生成績管理系統可以提高學校管理部門工作人員的工作效率，減少

6、不必要的人力、物力和財力的支出；方便學校管理部門的工作人員全面地掌握學生成績情況。使得學生成績實現標準化和規范化的管理。此外，通過對“學生成績管理系統”的學習和動手實踐編寫，可以使我們對數據結構的基礎知識的理解更透徹；促進我們對C語言的理解與使用；提高我們對綜合知識的運用能力，為今后從事項目開發積累經驗。該課程設計還能夠培養我們的實踐動手能力，提高我們的學習興趣，拓展我們的思維，加強我們查閱資料以及解決問題的能力，提高我們將老的思想運用到新事物上的能力。通過對此課題的開發，無論是理論知識還是動手能力，我們都會有不同程度上的提高。1.3 需求分析本次課程設計所編寫的學生成績管理系統，要實現增加學

7、生信息、刪除學生信息、查詢學生信息、修改學生信息以及排序、保存信息、讀取信息、退出系統等功能。第二章 學生成績管理系統概要設計2.1 開發方案在主函數中根據用戶的選擇運用switch結構來分別調用不同的自定義函數，從而實現特定的功能，電話薄中聯系人的姓名和號碼等信息則存放在結構體變量中，通過指針聯系起來，形成鏈表結構。各自定義函數與主函數之間也通過頭指針進行連接。當然，還要通過文件對學生成績管理系統的數據進行保存。先寫主函數，然后再依次編寫各自定義函數，最后進行程序測試，寫報告總結。2.2系統流程圖n根據輸入值調用各功能模塊函數開始顯示系統主界面各功能選項結束此學生成績管理系統的總體設計思想流

8、程圖如圖2-1所示。運行程序，首先出現的是系統的主界面，顯示系統的各項功能，增加學生信息、刪除學生信息、查詢學生信息、修改學生信息以及排序、保存信息、讀取信息、退出。用戶輸入相應的選擇，然后程序進入對應的功能模塊。判斷輸入選擇是否是18？ y圖2-1 系統簡單流程圖2.3 系統功能圖根據要求，此學生成績管理系統應該實現增加學生信息、刪除學生信息、查詢學生信息、修改學生信息以及排序、保存信息、讀取信息、退出系統等功能。此學生成績管理系統包括增加學生信息、刪除學生信息、查詢學生信息、修改學生信息以及排序、保存信息、讀取信息、退出八個模塊。其系統功能圖如圖2-2所示。其中的查詢模塊中實現按學號查詢、

9、按姓名查詢和退出功能，其功能圖如圖2-3所示。排序模塊中實現按學號排序、按數據結構成績排序、按語文成績排序、按英語成績排序、按總分排序和返回功能，其功能模塊圖如圖2-4所示。學生成績管理系統退出讀取保存排序修改學生查詢學生刪除學生增加學生圖2-2 學生成績管理系統功能模塊圖查詢學生信息按學號查詢按姓名查詢返回圖2-3 查詢學生信息功能圖排序按總分排序按英語成績排序返回按語文成績排序按數據結構成績排序按學號排序圖2-4 排序模塊功能圖第三章 詳細設計3.1 刪除學生信息功能的實現（4）刪除學生信息調用函數void Sub3Menu( )，調用該函數時先輸出一個子菜單，若用戶選擇刪除，則要求用戶輸

10、入要刪除的學生的學號，并顯示該學生的所有信息，刪除數據后對未刪除的數據進行一些調整。其功能實現流程圖如圖3-1所示。代碼如下：void deleterecord(student stu,int i) /*刪除信息*/ int j; while(i>=0) for(j=i;j<numstus;j+) stuj=stuj+1; numstus-; printf("刪除成功!n"); void count(student stud) int i,j; for(i=0;i<numstus;i+) studi.index=1; for(j=0;j<numstu

11、s;j+) if(studj.score>studi.score) studi.index+; 結束是否刪除開始輸入要刪除的學生學號查找到相應的學生信息 否 是將對應學生的信息刪除圖3-1刪除學生信息功能的實現流程圖3.2 修改學生信息功能的實現修改學生信息功能調用函數void Sub2Menu( )，調用該函數時先輸出一個子菜單，要求用戶選擇，若用戶選擇修改，則要求用戶輸入要修改的學生的學號，并顯示該學生的所有信息；，等用戶修改后，顯示出該學生新的信息。程序代碼如下：oid xiugai() if(fp=fopen("s_score.txt","rb+&q

12、uot;)=NULL|(fp1=fopen("temp.txt","wb+")=NULL) /*檢查是否出錯*/ printf("Cannot open this file.n"); exit(0); printf("nPLease shuru xiugai xuehao:"); scanf("%d",&i); getchar(); while(fread(&data,sizeof(data),1,fp)=1) j=atoi(data.xuehao); if(j=i) print

13、f("xuehao:%snmingzi:%snnianling:%sn",data.xuehao,data.mingzi,data.nianling); printf("Please shuru mingzi:"); gets(data.mingzi); printf("Please shuru shuxue score:"); gets(temp);data.score0=atof(temp); printf("Please input yingyu score:"); gets(temp);data.score

14、1=atof(temp); printf("Please input wuli score:"); gets(temp);data.score2=atof(temp); data.score3=data.score0+data.score1+data.score2; fwrite(&data,sizeof(data),1,fp1); fseek(fp,0L,0); /*將位置指針移到離頭文件0個字節處*/fseek(fp1,0L,0); while(fread(&data,sizeof(data),1,fp1)=1) fwrite(&data,siz

15、eof(data),1,fp); fclose(fp); fclose(fp1); 第四章 調試分析4.1系統運行主界面啟動此學生成績管理系統后，首先出現的是主窗口，如圖4-1所示。顯示系統的各項功能，用戶可以根據需要輸入相應的選擇。 圖4-1 主窗口運行界面4.2 增加學生信息功能的實現用戶輸入完學生的相應信息后，點擊回車鍵，則會提示：輸入成功，其運行界面如圖4-2所示。成績錄入后將顯示在主界面上。圖4-2 增加學生信息運行界面4.3 刪除學生信息功能的實現刪除學生信息功能為用戶提供了按學號刪除，輸入要刪除的學號后，會提示用戶是否刪除該學生信息，輸入y，才會刪除學生信息，刪除成功后都會有相應

16、的“刪除成功”提示，刪除學生信息的運行界面如圖4-3所示。圖4-3刪除學生信息的運行界面4.4 查詢學生信息功能的實現在查詢學生信息功能中，系統為用戶提供了兩種查詢方式，分別為按學號查詢和按姓名查詢。查詢學生信息的運行界面如圖4-4所示。圖4-4查詢學生信息的運行界面4.5 修改學生信息功能的實現用戶輸入要修改的學生的學號，然后輸入修改后的學生的成績，點擊回車鍵后，則會提示“修改成功”，其運行界面如圖4-5所示。圖4-5 修改學生信息功能的運行界面4.6排序功能的實現在排序功能中，系統為用戶提供了5種排序方式，分別為按學號排序、按數據結構成績排序、按語文成績排序、按英語成績排序和按總分排序。其

17、運行界面如圖4-6所示。圖4-6排序功能運行的界面第五章 程序設計結語5.1 系統存在的問題由于本人經驗不足，對VC+6.0軟件的使用不精通，對C語言知識的學習不夠透徹，所以，此次課程設計存在較多的不足之處。具體問題如下：（1）學生的個人信息不完善，如：缺少學生的個人課表、所在系、成績、身高、體重、健康情況、祖籍等信息；（2）系統運行后，沒有實現對不同的用戶登錄擁有不同的權限功能。 5.2 系統改進的方向介于上一節所述的種種不足，我認為系統改進的總體方向就是擬補以上的種種不足，然后在此基礎上對系統進行優化。首先，完善學生的個人成績；不同的用戶登錄也要有一定的權限限制；實現對已有學生成績的定位；

18、把尚未完成的功能模塊完成。最后，可以將該學生成績管理系統做成網頁版，供學生、學校管理人員以及訪客以相應的身份登錄該系統進行一系列的操作，進而可以將此系統推向各高等學府，輔助學校管理人員更好的管理在校學生。5.3 此次課程設計的體會此次課程設計主要運用了VC+6.0軟件，編程所運用的語言是C語言。經過一周的編程實習，并在后一段的報告總結，我對數據結構這門科有新的認識，本人實在是獲益不淺！要想編寫一個準確、高效并有使用價值的程序，一定先要對課本知識熟悉，還要掌握必要的上機操作能力，寫程序其實很容易而關鍵在于調試程序。這次設計,讓我重新掌握了數據結構,而且還得到了用數據結構解決實際問題的寶貴經驗。通

19、過此次編程我也發現了自己在學習中的錯誤和不足，復習了以前學過的知識。同時也學到了一些沒學過的知識，讓我從中收益非淺，也為期末考試準備了一下！更重要的是培養了獨立思考問題和解決問題的能力，熟悉了一些基本操作和解決問題的方法。猴子選大王第一章 概述1.1 開發的目的猴子選大王的問題，在現實社會中頻頻出現，此次系統開發的目的就是為了解決生活中出現的猴子選大王的問題。有時候，很多選舉需要隨機性，如何能夠實現公平公正的選舉？這就需要借助一個好的猴子選大王系統來實現。由此，猴子選大王系統就應運而生了。1.2 開發設計的意義現實社會中，需要選舉的地方很多，然而選舉中的人為操作使得選舉失去了應有的意義。猴子選

20、大王系統的開發，可以幫助一些社會群體實現公平選舉，避開暗箱操作。，通過對“猴子選大王”的學習和動手實踐編寫，可以使我們對數據結構的基礎知識的理解更透徹；促進我們對C語言的理解與使用；提高我們對綜合知識的運用能力，為今后從事項目開發積累經驗。1.3 需求分析此猴子選大王系統只需實現對于不同數量的群體按照一定的規則進行逐個淘汰，最終獲得選舉結果，可以將參加選舉者排好隊，能夠從不同的序號開始淘汰，從而達到隨機選舉的目的。第二章 猴子選大王系統概要設計2.1系統流程圖此猴子選大王系統的總體設計思想流程圖如圖2-1所示。運行程序后，首先出現系統的主界面，提示用戶輸入猴子的總數，按回車鍵，然后提示用戶輸入

21、從第幾個猴子開始淘汰，按回車鍵執行程序，然后得到猴子的大王是第幾號。開始輸入猴子的總數輸入從第幾個猴子開始得到猴子大王結束 圖2-1 系統簡單流程圖第三章 詳細設計3.1系統的實現由于此系統數據元素不可須知，同時對于報完一次之后對于下一次的報數，由于已經排除了一部分猴子，猴子的順序被打亂，所以需要使用鏈表。鏈表是動態的，可以在需要的時候增長和減少其長度，而靜態數據結構數組是在編譯時分派內存的，其大小是不可改變的，而且會出現內存浪費的情況。我認為單循環鏈表能很好的解決這個問題，在建立單循環鏈表時，因為鏈表的大小由輸入決定，因為與匹配的節點數也是變化的，所以要進行動態內存分配。假設猴子的個數是N，

22、M是要淘汰的編號，那么建立一個N長的鏈表，鏈表最后一個元素的nextPtr指針指向第一個元素，這樣就形成一個循環鏈表，而鏈表的數據域存儲的就是猴子的編號。程序代碼如下：#include<stdio.h>#include<malloc.h>struct Nodeint data;struct Node *next;/建立一個節點結構體int main()struct Node *head, *s, *q, *t;int n, m, count=0, i;printf("*猴子選大王*n");printf("n*請輸入猴子的總數: "

23、);scanf("%d",&m);printf("n*請輸入從第幾個猴子開始: ");scanf("%d",&n);for(i=0; i<m; i+) s=(struct Node *)malloc(sizeof(struct Node);s->data=i+1;s->next=NULL; if(i=0) head=s; q=head; else q->next=s; q=q->next; /建立一個不帶頭結點的單鏈表q->next=head;/這里，將單鏈表組成環狀，形成循環單鏈表

24、printf("before:");q=head; while(q->next!=head)printf("%d ",q->data); q=q->next; /依次輸出節點的值printf("%d ",q->data);q=head; printf(" "); do count+;/計數器開始計數 if(count=n-1) t=q->next;q->next=t->next;/到n前面那個節點stop，然后刪除第n個節點count=0;/計數器復位printf(&quo

25、t;%d ", t->data);/輸出被淘汰的猴子的號碼 free(t);/釋放內存，防止內存泄露 q=q->next; while(q->next!=q);/這句是關鍵，就是循環到只剩下一個節點了，如果說有難度的話應該是理解的難點了printf("n*猴子的大王是第 %d 號*n",q->data);/輸出king的號碼大王是輸入猴子的數目 輸入數字第四章 調試分析4.1系統運行主界面啟動此猴子選大王系統后，首先出現的是主窗口，如圖4-1所示。提示用戶輸入猴子的總數。圖4-1 主窗口運行界面4.2系統運行結果當用戶輸入相應的猴子總數，并

26、輸入從第幾個猴子開始后，按下回車鍵，系統則的到運行的結果，即選擇出猴子的大王。程序運行結果如圖4-2所示。圖4-2系統運行結果圖第五章 程序設計結語5.1 此次課程設計的總結猴子選大王是一個數據結構很古老很經典的問題，融知識性和娛樂性為一體，能讓人產生較大興趣，因此編寫程序實現之是一件很有意義的事。在課程設計中，首先要看清問題，將問題要求理解透徹，在構思要如何實現，要用到哪些函數，要用什么算法，在課程構思中選算法是一個很重要的概念，只有確定用這么算法后才能接下來的工作，將流程圖畫在紙上，再依次編寫代碼，在程序設計中，編寫代碼只是一個方面，調試才是關鍵。它是一個相當繁瑣的過程，有許多新的問題需要

27、被解決，但同時它也是一個比較重要的過程，因為在程序調試過程中，你會學到很多新的東西，從而增加你編程的經驗。 在設計一元多項式算法時，出現了一些問題，例如在建立鏈表時頭指針的設立導致了之后運用到相關的指針時沒能很好的移動指針出現了數據重復輸出或是輸出系統缺省值，不能實現算法。實現加法時該鏈表并沒有向通常那樣通過建立第三個鏈表來存放運算結果，而是再度利用了鏈表之一來進行節點的比較插入刪除等操作。為了使輸入數據按指數降序排列，可在數據的輸入后先做一個節點的排序函數，通過對鏈表排序后再進行之后加減運算。迷宮求解第一章 概述1.1 開發的目的和意義迷宮問題要求尋找一條從入口到出口的路徑。即從入口出發，順

28、著某一個方向進行探索，若能走通，則繼續往前走；否則沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路，通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求解迷宮通路的算法中要應用“棧”的思想。對于棧的內容在整個學期的學習中我也有了一定的了解。1.2需求分析本課程設計是解決迷宮求解的問題，從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路

29、退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中要應用“棧”的思想假設“當前位置”指的是“在搜索過程中的某一時刻所在圖中某個方塊位置”，以0和1所組成的迷宮形式輸出，標記所走過的路徑結束程序；當迷宮無路徑時，提示輸入錯誤結束程序 。第二章 迷宮求解系統概要設計2.1系統設計概要從入口出發，按某一方向向前探索，若能走通并且未走過，即某處可以到達，則到達新點，否則試探下一個方向；若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續試探，直到找到一條通路，或無路可走又返回入口點。在求解過程中，為了保證在到達某一點后不能向前繼續行走（無路）時，能正確

30、返回前一點以便繼續從下一個方向向前試探，則需要用一個棧（遞歸不需要）保存所能夠到達的每一點的下標及從該點前進的方向。設迷宮為m行n列，利用mazemn來表示一個迷宮，mazeij=0或1；其中：0表示通路，1表示不通，當從某點向下試探時，中間點有四個方向可以試探，而四個角點有兩個方向，其他邊緣點有三個方向，為使問題簡單化，用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為1，這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當前點的試探方向有幾個。迷宮棧的實現函數mazepath()迷宮遞歸的實現函數path()為了防止重復達到某點，以避免發生死循環，每次達到了某點(i,j)后，改

31、變mazeij的值，迷宮棧的實現直接置-1，算法結束前恢復原迷宮；而迷宮遞歸是將當前值置為已走的步驟，這樣輸出時對走過的路更顯而易見。棧的函數設計：棧的初始化函數 Init_SeqStack()判棧空 Empty_SeqStack()入棧函數 Push_SeqStack()出棧函數 Pop_SeqStack()取棧頂函數 GetTop_SeqStack()銷毀棧 Destroy_SeqStack()第三章 詳細設計3.1系統的實現在上述表示迷宮的情況下，每個點有4個方向去試探，如當前點的坐標（x，y），與其相鄰的4個點的坐標都可根據與該點的相鄰方位而得到。因為出口在（m，n），因此試探順序規定

32、為：從當前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便求出新點的坐標，將從正東開始沿順時針進行的4個方向的坐標增量放在一個結構數組move4中，在move數組中，每個元素有兩個域組成，x為橫坐標增量，y為縱坐標增量。這樣對move設計會很方便地求出從某點（x，y）按某一方向v(0<=v<=3)到達的新點（i，j）的坐標：i=x+movev.x;j=y+movev.y;當到達了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續試探。因此，壓入棧中的不僅是順序到達的各點的坐標，而且還要有從前一點到達本點的方向。棧中元素是一個由行、列、方向組成。具體結構定義如

33、下：#include <stdio.h> #include <stdlib.h> #define MaxSize 100 #define StackIncrement 10 struct Seat /定義坐標結構體 int x; int y; ; typedef struct /定義入棧信息元素類型 int ord; Seat seat; int di; SElemType; struct Stack /定義棧元素類型 SElemType *base; SElemType *top; int StackLength; ; Stack S; bool Map1010=0,

34、0,1,1,0,1,1,1,0,1,0, 0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,1,1,1,0, 0,1,1,1,0,1,1,1,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,0,0,1,0,0,1,0, 0,0,1,1,1,1,1,1,1,0,0; bool is_through1010=0; bool InitStack(Stack &S) /構建一個棧 S.base=S.top=(SElemType*)malloc(MaxSize*sizeof(SElemType); if(!S.base) retu

35、rn false; S.StackLength=MaxSize; return true; bool Push(Stack &S,SElemType e) / 將信息e入棧 if(S.top-S.base)/sizeof(SElemType)=S.StackLength) S.base=(SElemType*)realloc(S.base,(S.StackLength+StackIncrement)*sizeof(SElemType); S.top=S.base+S.StackLength; S.StackLength += StackIncrement; S.top->di=e

36、.di; S.top->ord=e.ord; S.top->seat.x=e.seat.x; S.top->seat.y=e.seat.y; S.top+; return true; bool Pop(Stack &S,SElemType &e) /將棧頂元素取出，賦值給e if(S.base=S.top) return false; S.top-; e.di=S.top->di; e.ord=S.top->ord; e.seat.x=S.top->seat.x; e.seat.y=S.top->seat.y; return true;

37、 bool StackEmpty(Stack s) /判斷棧是否為空 return !(s.top-s.base); bool Pass(Seat s) /判斷當前位置是否通 return Maps.xs.y; bool FootPrint(Seat s) / 在此位置留下標記，表示已經經過 is_throughs.xs.y=true; return true; Seat NextPos(Seat s,int i) / 將當前位置指向邏輯上的下個位置，指向的方向由i確定 Seat ss; if(i=1) ss.x=s.x+1; ss.y=s.y; else if(i=2) ss.x=s.x;

38、ss.y=s.y+1; else if(i=3) ss.x=s.x-1; ss.y=s.y; else ss.x=s.x; ss.y=s.y+1; return ss; bool MazePath(Seat start,Seat end) InitStack(S); /創建棧并且初始化 Seat curpos; curpos.x=start.x; curpos.y=start.y; /設定當前位置為入口地址 int curstep=1; / 探索第一步 do if(Pass(curpos)&&!is_throughcurpos.xcurpos.y) /當前位置通且沒有來過 Fo

39、otPrint(curpos); / 留下痕跡 SElemType e; / 構建入棧信息 e.di=1; e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; Push(S,e); / 加入路徑 if(curpos.x=end.x)&&(curpos.y=end.y) / 到達終點 return true; curpos=NextPos(curpos,1); / 探索下一步 curstep+; else / 當前位置不通，將前面一個位置取出，改由其他方向在判斷 SElemType e; if(!StackEmpty(S) P

40、op(S,e); while(e.di=4&&!StackEmpty(S) FootPrint(e.seat); Pop(S,e); / 如果這個位置的其他四個方向都不滿足，表示這個位置不可取，取出棧并且留下標識 if(e.di<4) / 如果其他方向還沒有探索完，繼續探索下一個方向 e.di+; Push(S,e); curpos=NextPos(e.seat,e.di); while(!StackEmpty(S); return false; int main() int i,j; Seat sta,end; sta.x=1; sta.y=1; end.x=8; en

41、d.y=8; MazePath(sta,end); SElemType *b=S.base; printf("迷宮地圖為(1表示通，0表示不通):n"); for(i=0;i<10;i+) for(j=0;j<10;j+) printf("%d ",Mapij); printf("n"); printf("迷宮路徑為:"); while(b!=S.top) printf("(%d,%d) -> ",b->seat.x,b->seat.y); +b; printf(&

42、quot;出口n"); scanf("%d",i);return 0; 第四章 調試分析4.1系統運行界面系統運行后，其運行界面如圖4-1所示。圖4-1迷宮求解系統運行圖第五章 程序設計結語5.1 此次課程設計的總結本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。 首先由用戶輸入一組二維數組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，通過這次數據結構課程設計，讓我學到了好多東西。在實際操作過程中犯了一些錯誤卻讓我有了意外的收獲，所學數據結構理論知識得到了鞏固。通過實際操作，學會數據結構程序編程的基本步驟、基本方法，開發了自己的邏輯思維

43、能力，培養了分析問題、解決問題的能力。現在終于挨到了寫收獲與體會的時候了，的確令人興奮，看看自己的勞動成果，好開心。上網查資料、去圖書館查，查相關的函數，經過兩三天的努力，我把框架弄出來了，可是還有計算難題擺在我的面前，真的是個難題，自從把框架弄好了以后就沒有進展了，眼看一個星期快過去了，我那個急啊，可是急也沒有用。我堅持，終于工夫不負有心人，我參照類似程序，改改和添添，終于大功告成，我們歡呼我們雀躍，終于相信我們自己是足夠的偉大。圖的遍歷及拓撲排序第一章 概述1.1 開發設計的目的和意義本課設題目要求編寫算法能夠建立有向無環圖，有向無環圖，能夠求解該有向無環圖的拓撲排序并輸出來，輸出除拓撲排

44、序數據外，還要輸出鄰接表數據。為了更好地完成工程，必須滿足活動之間先后關系，需要將各活動排一個先后次序即為拓撲排序。拓撲排序可以應用于教學計劃的安排，根據課程之間的依賴關系，制定課程安排計劃。按照用戶輸入的課程數，課程間的先后關系數目以及課程間兩兩間的先后關系，程序執行后會給出符合拓撲排序的課程安排計劃。1.2需求分析該系統的功能應能夠實現圖的遍歷以及拓撲排序，具體分析如下：1.將圖以合適的方式存儲起來。圖有多種存儲方式，其中最常用的存儲方式有圖的鄰接矩陣和鄰接表。本人在構思時使用鄰接表來建立有向無環圖，將其存儲起來。2.求解該有向無環圖的拓撲排序，并將其輸出出來。若通過構造，建立了一個有向無

45、環圖，那么一定可以求出其拓撲排序，其原理比較簡單。即統計每個節點的入度，將入度為0的結點提取出來，然后再統計剩下的結點的入度，再次將入度為零的結點提取出來，以此類推，這樣就形成了一個序列，這樣的序列就是該圖的拓撲排序序列。3.拓撲排序算法應能夠處理出現環的情況。個人在寫程序時，考慮到構造圖時，會有構造成有向有環圖的情況，應該在運行程序時，提醒出來，然后重新輸入有向無環圖，知道輸入正確為止。這樣就有多次構造鄰接表的問題，每一次構造鄰接表時，都應該將原來錯誤的（不是無環圖的）鄰接表空間釋放掉，否則，會變得混亂。4.輸出除拓撲排序外，還要求輸出鄰接表數據。由于圖是用鄰接表存儲的，所以很容易將其鄰接表

46、輸出來。第二章 圖的遍歷及拓撲排序系統概要設計2.1系統流程圖根據程序的總的步驟，擬將整個流程分為三個模塊。三個模塊既相互獨立又相互聯系。具體分析如下：1. 圖像輸入，根據題目要求，要能夠建立一個有向無環圖，這就要我們在程序中去建立。考慮到輸入方式要盡量方便全面，采用輸入弧的方式，輸入每條弧的鏈接的兩個結點，當輸入-1時結束輸入。這樣再輸入的時候，與相鄰的兩個結點的鄰接矩陣對應的位置也做相應改變。2. 判斷圖是不是有向無環圖。當圖為有向無環圖時，則挑選完畢后，隊列應該是滿的，進行后續步驟。對于結點入隊列的順序，需要借助于visited數組。選取入度為零的結點，入隊列，調整visited數組，循

47、環進行。若隊列不滿，則輸入的圖不符合要求，應該重新輸入。在程序中應做適當提醒，然后自動轉模塊1.，進行圖的重新編輯。3. 拓撲排序。此時，所輸入的弧應該是有向無環圖了，下面進行拓撲排序。在判斷它是否為無環圖的過程中已經形成了一個滿隊列。接下來所要做的事情就是循環出隊列，按照隊列固有的順序進行輸出即可，排序完成。系統的流程圖如圖2-1所示。開始圖形輸入構造鄰接表并輸出 否無環圖入度為零入隊列調整visited 是滿隊列 否循環出隊列 是結束圖2-1系統流程圖2.2功能模塊圖系統的功能模塊圖如圖2-2所示.包括圖的遍歷和拓撲排序兩部分，圖的遍歷中若是有環圖則遍歷全部，若是無環圖則無法遍歷；拓撲排序

48、模塊則實現拓撲排序功能。系統拓撲排序圖的遍歷有環圖遍歷全部無環圖無法遍歷入度為零入隊輸出隊列圖2-2系統功能圖第三章 詳細設計3.1 系統功能的實現本程序的拓撲排序，必須在圖的鄰接表已知的情況下。它還有另外一個功能：判斷一個圖是不是無環圖。確切的說，不能單純的叫拓撲排序，但考慮它主要的作用，在不引起誤解的情況下就叫拓撲排序算法。判斷一個圖是否為有向無環圖并進行拓撲排序，判定方法有很多種，檢查一個有向圖是否存在環要比無向圖復雜。對于無向圖來說，若深度優先遍歷過程中遇到回邊（即指向已訪問過的頂點的邊），則必存在環；而對于有向圖來說，這條回邊有可能指向深度優先森林中另一棵生成樹上頂點的弧。但是，如果

49、從有向圖上某個頂點出發的遍歷，在dfs(v)結束之前出現一條從頂點u到頂點v的回邊，由于在生成樹上是的子孫，則有向圖中必定存在包含頂點v和u的環。另一種判斷是否有環的方法則顯得簡單的多，尤其是對于本題目來說，由于本題要求是對有向無環圖進行拓撲排序，其主要方法是將入度為零的結點依次輸出來，知道圖的所有定點全部輸出為止。那么若圖為有環圖，在環上的結點在其他結點都選擇出來后，入度都不為零，即無法被輸出出來。那么就可以認為按照拓撲排序的方法輸出結點后，若不是將節點全部輸出出來的，則此圖為有環圖。判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現環的情況，若構造的圖為有環圖，則折回開始重新輸入圖的數

50、據，重新構造圖，直到該圖為無環圖為止。若圖已經是無環圖，則進行拓撲排序，排序方法前面已經講過，在此主要訴說用到的輔助存儲。數組visited存儲各結點的入度，對入度為零的結點，依次入隊列queue，調整visited數組，結點全部入隊列后，然后依次出隊列，拓撲排序完成。實現功能的程序代碼如下：#include<iostream.h>typedef int elemtype;const MAX=100; bool visitedMAX;class link public:elemtype data; link *next; class node public:link aMAX;vo

51、id creatlink3(node &g ,int n,int e);void bfs2(node g,int i); void dfs1(node g,int i); void topsort (node &g,int n ); ;void node:creatlink3( node &g,int n,int e) /建立帶入度的鄰接表 int i,j,k ; link *s ;for(i=1; i<=n;i+) /建立鄰接表頭結點 g.ai.data=0; /入度值為0 g.ai.next=NULL; for(k=1; k<=e;k+) cout<<"請輸入一條弧:" cin>>i>>j ; /輸入一條弧 <i,j> cout<<endl;s=new link; /申請一個動態存儲單元s->data=j ;s->next=g.ai.next ;g.ai.next=s ;g.aj.data+; /入度加1void node:topsort (node &g,int n ) /拓撲排序int top=0,m=0;for (int i=1;i<=n;i+) /入度為0的頂點進棧if (g.ai.data=0) g.ai