1、目錄摘要3學(xué)生成績(jī)管理系統(tǒng)4第一章概述41.1 開(kāi)發(fā)前的準(zhǔn)備41.2 開(kāi)發(fā)設(shè)計(jì)的意義41.3 需求分析4第二章學(xué)生成績(jī)管理系統(tǒng)概要設(shè)計(jì)52.1 開(kāi)發(fā)方案52.2系統(tǒng)流程圖52.3 系統(tǒng)功能圖6第三章詳細(xì)設(shè)計(jì)83.1 刪除學(xué)生信息功能的實(shí)現(xiàn)83.2 修改學(xué)生信息功能的實(shí)現(xiàn)9第四章調(diào)試分析114.1系統(tǒng)運(yùn)行主界面114.2 增加學(xué)生信息功能的實(shí)現(xiàn)114.3 刪除學(xué)生信息功能的實(shí)現(xiàn)124.4 查詢學(xué)生信息功能的實(shí)現(xiàn)134.5 修改學(xué)生信息功能的實(shí)現(xiàn)134.6 排序功能的實(shí)現(xiàn)14第五章程序設(shè)計(jì)結(jié)語(yǔ)155.1 系統(tǒng)存在的問(wèn)題155.2 系統(tǒng)改進(jìn)的方向155.3 此次課程設(shè)計(jì)的體會(huì)15猴子選大王16第一章

2、概述161.1 開(kāi)發(fā)的目的161.2 開(kāi)發(fā)設(shè)計(jì)的意義161.3 需求分析16第二章猴子選大王系統(tǒng)概要設(shè)計(jì)172.1系統(tǒng)流程圖17第三章詳細(xì)設(shè)計(jì)183.1系統(tǒng)的實(shí)現(xiàn)18第四章調(diào)試分析204.1系統(tǒng)運(yùn)行主界面204.2系統(tǒng)運(yùn)行結(jié)果21第五章程序設(shè)計(jì)結(jié)語(yǔ)225.1 此次課程設(shè)計(jì)的總結(jié)22迷宮求解23第一章概述231.1 開(kāi)發(fā)的目的和意義231.2 需求分析23第二章迷宮求解系統(tǒng)概要設(shè)計(jì)242.1系統(tǒng)設(shè)計(jì)概要24第三章詳細(xì)設(shè)計(jì)253.1系統(tǒng)的實(shí)現(xiàn)25第四章調(diào)試分析294.1系統(tǒng)運(yùn)行界面29第五章程序設(shè)計(jì)結(jié)語(yǔ)305.1 此次課程設(shè)計(jì)的總結(jié)30圖的遍歷及拓?fù)渑判?1第一章概述311.1 開(kāi)發(fā)設(shè)計(jì)的目的和意

3、義311.2 需求分析31第二章圖的遍歷及拓?fù)渑判蛳到y(tǒng)概要設(shè)計(jì)322.1系統(tǒng)流程圖322.2功能模塊圖33第三章詳細(xì)設(shè)計(jì)343.1 系統(tǒng)功能的實(shí)現(xiàn)34第四章調(diào)試分析384.1系統(tǒng)運(yùn)行主界面384.2 系統(tǒng)運(yùn)行結(jié)果38第五章程序設(shè)計(jì)結(jié)語(yǔ)405.1 此次課程設(shè)計(jì)的總結(jié)40參考文獻(xiàn)42摘要隨著社會(huì)的發(fā)展，人民生活水平的提高，人們對(duì)教育的重視程度也隨之增加，越來(lái)越多的人走入高等學(xué)府，由此，各所學(xué)校的學(xué)生數(shù)量也日益增加。這使得學(xué)校對(duì)學(xué)生的管理難度逐漸增大。而管理好學(xué)生成績(jī)是維護(hù)社會(huì)安定、提高教學(xué)質(zhì)量、保證教學(xué)進(jìn)度有條不紊進(jìn)行的有力保障。由此可見(jiàn)，學(xué)生成績(jī)管理是一項(xiàng)極其重要的工作；同時(shí)，學(xué)生成績(jī)管理又是一

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

5、速度和準(zhǔn)確度。另外還有猴子選大王系統(tǒng)可以解決日常生活中出現(xiàn)的選舉問(wèn)題；迷宮求解系統(tǒng)，可以供人們娛樂(lè)以及智力開(kāi)發(fā)；圖的遍歷和拓?fù)渑判蛳到y(tǒng)，用來(lái)解決排序問(wèn)題。關(guān)鍵詞：成績(jī)管理，VC+6.0，C語(yǔ)言，編程學(xué)生成績(jī)管理系統(tǒng)第一章 概述1.1 開(kāi)發(fā)前的準(zhǔn)備在進(jìn)行程序設(shè)計(jì)之前要熟練掌握數(shù)據(jù)結(jié)構(gòu)以及C語(yǔ)言中的相關(guān)基礎(chǔ)知識(shí)。根據(jù)我們?nèi)粘Ｉ钪械慕?jīng)驗(yàn)，結(jié)合自己平時(shí)所接觸到的本校學(xué)生成績(jī)管理系統(tǒng)，做好需求分析，明確程序設(shè)計(jì)的具體要求。掌握VC+6.0的使用方法，準(zhǔn)備計(jì)算機(jī)、VC+6.0等基本設(shè)備。為下一步具體開(kāi)發(fā)設(shè)計(jì)做好充分的準(zhǔn)備。1.2 開(kāi)發(fā)設(shè)計(jì)的意義學(xué)生成績(jī)管理系統(tǒng)可以提高學(xué)校管理部門工作人員的工作效率，減少

6、不必要的人力、物力和財(cái)力的支出；方便學(xué)校管理部門的工作人員全面地掌握學(xué)生成績(jī)情況。使得學(xué)生成績(jī)實(shí)現(xiàn)標(biāo)準(zhǔn)化和規(guī)范化的管理。此外，通過(guò)對(duì)“學(xué)生成績(jī)管理系統(tǒng)”的學(xué)習(xí)和動(dòng)手實(shí)踐編寫(xiě)，可以使我們對(duì)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)的理解更透徹；促進(jìn)我們對(duì)C語(yǔ)言的理解與使用；提高我們對(duì)綜合知識(shí)的運(yùn)用能力，為今后從事項(xiàng)目開(kāi)發(fā)積累經(jīng)驗(yàn)。該課程設(shè)計(jì)還能夠培養(yǎng)我們的實(shí)踐動(dòng)手能力，提高我們的學(xué)習(xí)興趣，拓展我們的思維，加強(qiáng)我們查閱資料以及解決問(wèn)題的能力，提高我們將老的思想運(yùn)用到新事物上的能力。通過(guò)對(duì)此課題的開(kāi)發(fā)，無(wú)論是理論知識(shí)還是動(dòng)手能力，我們都會(huì)有不同程度上的提高。1.3 需求分析本次課程設(shè)計(jì)所編寫(xiě)的學(xué)生成績(jī)管理系統(tǒng)，要實(shí)現(xiàn)增加學(xué)

7、生信息、刪除學(xué)生信息、查詢學(xué)生信息、修改學(xué)生信息以及排序、保存信息、讀取信息、退出系統(tǒng)等功能。第二章 學(xué)生成績(jī)管理系統(tǒng)概要設(shè)計(jì)2.1 開(kāi)發(fā)方案在主函數(shù)中根據(jù)用戶的選擇運(yùn)用switch結(jié)構(gòu)來(lái)分別調(diào)用不同的自定義函數(shù)，從而實(shí)現(xiàn)特定的功能，電話薄中聯(lián)系人的姓名和號(hào)碼等信息則存放在結(jié)構(gòu)體變量中，通過(guò)指針聯(lián)系起來(lái)，形成鏈表結(jié)構(gòu)。各自定義函數(shù)與主函數(shù)之間也通過(guò)頭指針進(jìn)行連接。當(dāng)然，還要通過(guò)文件對(duì)學(xué)生成績(jī)管理系統(tǒng)的數(shù)據(jù)進(jìn)行保存。先寫(xiě)主函數(shù)，然后再依次編寫(xiě)各自定義函數(shù)，最后進(jìn)行程序測(cè)試，寫(xiě)報(bào)告總結(jié)。2.2系統(tǒng)流程圖n根據(jù)輸入值調(diào)用各功能模塊函數(shù)開(kāi)始顯示系統(tǒng)主界面各功能選項(xiàng)結(jié)束此學(xué)生成績(jī)管理系統(tǒng)的總體設(shè)計(jì)思想流

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

9、按姓名查詢和退出功能，其功能圖如圖2-3所示。排序模塊中實(shí)現(xiàn)按學(xué)號(hào)排序、按數(shù)據(jù)結(jié)構(gòu)成績(jī)排序、按語(yǔ)文成績(jī)排序、按英語(yǔ)成績(jī)排序、按總分排序和返回功能，其功能模塊圖如圖2-4所示。學(xué)生成績(jī)管理系統(tǒng)退出讀取保存排序修改學(xué)生查詢學(xué)生刪除學(xué)生增加學(xué)生圖2-2 學(xué)生成績(jī)管理系統(tǒng)功能模塊圖查詢學(xué)生信息按學(xué)號(hào)查詢按姓名查詢返回圖2-3 查詢學(xué)生信息功能圖排序按總分排序按英語(yǔ)成績(jī)排序返回按語(yǔ)文成績(jī)排序按數(shù)據(jù)結(jié)構(gòu)成績(jī)排序按學(xué)號(hào)排序圖2-4 排序模塊功能圖第三章 詳細(xì)設(shè)計(jì)3.1 刪除學(xué)生信息功能的實(shí)現(xiàn)（4）刪除學(xué)生信息調(diào)用函數(shù)void Sub3Menu( )，調(diào)用該函數(shù)時(shí)先輸出一個(gè)子菜單，若用戶選擇刪除，則要求用戶輸

10、入要?jiǎng)h除的學(xué)生的學(xué)號(hào)，并顯示該學(xué)生的所有信息，刪除數(shù)據(jù)后對(duì)未刪除的數(shù)據(jù)進(jìn)行一些調(diào)整。其功能實(shí)現(xiàn)流程圖如圖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+; 結(jié)束是否刪除開(kāi)始輸入要?jiǎng)h除的學(xué)生學(xué)號(hào)查找到相應(yīng)的學(xué)生信息 否 是將對(duì)應(yīng)學(xué)生的信息刪除圖3-1刪除學(xué)生信息功能的實(shí)現(xiàn)流程圖3.2 修改學(xué)生信息功能的實(shí)現(xiàn)修改學(xué)生信息功能調(diào)用函數(shù)void Sub2Menu( )，調(diào)用該函數(shù)時(shí)先輸出一個(gè)子菜單，要求用戶選擇，若用戶選擇修改，則要求用戶輸入要修改的學(xué)生的學(xué)號(hào)，并顯示該學(xué)生的所有信息；，等用戶修改后，顯示出該學(xué)生新的信息。程序代碼如下：oid xiugai() if(fp=fopen("s_score.txt","rb+&q

12、uot;)=NULL|(fp1=fopen("temp.txt","wb+")=NULL) /*檢查是否出錯(cuò)*/ 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個(gè)字節(jié)處*/fseek(fp1,0L,0); while(fread(&data,sizeof(data),1,fp1)=1) fwrite(&data,siz

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

16、的“刪除成功”提示，刪除學(xué)生信息的運(yùn)行界面如圖4-3所示。圖4-3刪除學(xué)生信息的運(yùn)行界面4.4 查詢學(xué)生信息功能的實(shí)現(xiàn)在查詢學(xué)生信息功能中，系統(tǒng)為用戶提供了兩種查詢方式，分別為按學(xué)號(hào)查詢和按姓名查詢。查詢學(xué)生信息的運(yùn)行界面如圖4-4所示。圖4-4查詢學(xué)生信息的運(yùn)行界面4.5 修改學(xué)生信息功能的實(shí)現(xiàn)用戶輸入要修改的學(xué)生的學(xué)號(hào)，然后輸入修改后的學(xué)生的成績(jī)，點(diǎn)擊回車鍵后，則會(huì)提示“修改成功”，其運(yùn)行界面如圖4-5所示。圖4-5 修改學(xué)生信息功能的運(yùn)行界面4.6排序功能的實(shí)現(xiàn)在排序功能中，系統(tǒng)為用戶提供了5種排序方式，分別為按學(xué)號(hào)排序、按數(shù)據(jù)結(jié)構(gòu)成績(jī)排序、按語(yǔ)文成績(jī)排序、按英語(yǔ)成績(jī)排序和按總分排序。其

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

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

19、過(guò)此次編程我也發(fā)現(xiàn)了自己在學(xué)習(xí)中的錯(cuò)誤和不足，復(fù)習(xí)了以前學(xué)過(guò)的知識(shí)。同時(shí)也學(xué)到了一些沒(méi)學(xué)過(guò)的知識(shí)，讓我從中收益非淺，也為期末考試準(zhǔn)備了一下！更重要的是培養(yǎng)了獨(dú)立思考問(wèn)題和解決問(wèn)題的能力，熟悉了一些基本操作和解決問(wèn)題的方法。猴子選大王第一章 概述1.1 開(kāi)發(fā)的目的猴子選大王的問(wèn)題，在現(xiàn)實(shí)社會(huì)中頻頻出現(xiàn)，此次系統(tǒng)開(kāi)發(fā)的目的就是為了解決生活中出現(xiàn)的猴子選大王的問(wèn)題。有時(shí)候，很多選舉需要隨機(jī)性，如何能夠?qū)崿F(xiàn)公平公正的選舉？這就需要借助一個(gè)好的猴子選大王系統(tǒng)來(lái)實(shí)現(xiàn)。由此，猴子選大王系統(tǒng)就應(yīng)運(yùn)而生了。1.2 開(kāi)發(fā)設(shè)計(jì)的意義現(xiàn)實(shí)社會(huì)中，需要選舉的地方很多，然而選舉中的人為操作使得選舉失去了應(yīng)有的意義。猴子選

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

21、從第幾個(gè)猴子開(kāi)始淘汰，按回車鍵執(zhí)行程序，然后得到猴子的大王是第幾號(hào)。開(kāi)始輸入猴子的總數(shù)輸入從第幾個(gè)猴子開(kāi)始得到猴子大王結(jié)束 圖2-1 系統(tǒng)簡(jiǎn)單流程圖第三章 詳細(xì)設(shè)計(jì)3.1系統(tǒng)的實(shí)現(xiàn)由于此系統(tǒng)數(shù)據(jù)元素不可須知，同時(shí)對(duì)于報(bào)完一次之后對(duì)于下一次的報(bào)數(shù)，由于已經(jīng)排除了一部分猴子，猴子的順序被打亂，所以需要使用鏈表。鏈表是動(dòng)態(tài)的，可以在需要的時(shí)候增長(zhǎng)和減少其長(zhǎng)度，而靜態(tài)數(shù)據(jù)結(jié)構(gòu)數(shù)組是在編譯時(shí)分派內(nèi)存的，其大小是不可改變的，而且會(huì)出現(xiàn)內(nèi)存浪費(fèi)的情況。我認(rèn)為單循環(huán)鏈表能很好的解決這個(gè)問(wèn)題，在建立單循環(huán)鏈表時(shí)，因?yàn)殒湵淼拇笮∮奢斎霙Q定，因?yàn)榕c匹配的節(jié)點(diǎn)數(shù)也是變化的，所以要進(jìn)行動(dòng)態(tài)內(nèi)存分配。假設(shè)猴子的個(gè)數(shù)是N，

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

23、);scanf("%d",&m);printf("n*請(qǐng)輸入從第幾個(gè)猴子開(kāi)始: ");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; /建立一個(gè)不帶頭結(jié)點(diǎn)的單鏈表q->next=head;/這里，將單鏈表組成環(huán)狀，形成循環(huán)單鏈表

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

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

26、輸入從第幾個(gè)猴子開(kāi)始后，按下回車鍵，系統(tǒng)則的到運(yùn)行的結(jié)果，即選擇出猴子的大王。程序運(yùn)行結(jié)果如圖4-2所示。圖4-2系統(tǒng)運(yùn)行結(jié)果圖第五章 程序設(shè)計(jì)結(jié)語(yǔ)5.1 此次課程設(shè)計(jì)的總結(jié)猴子選大王是一個(gè)數(shù)據(jù)結(jié)構(gòu)很古老很經(jīng)典的問(wèn)題，融知識(shí)性和娛樂(lè)性為一體，能讓人產(chǎn)生較大興趣，因此編寫(xiě)程序?qū)崿F(xiàn)之是一件很有意義的事。在課程設(shè)計(jì)中，首先要看清問(wèn)題，將問(wèn)題要求理解透徹，在構(gòu)思要如何實(shí)現(xiàn)，要用到哪些函數(shù)，要用什么算法，在課程構(gòu)思中選算法是一個(gè)很重要的概念，只有確定用這么算法后才能接下來(lái)的工作，將流程圖畫(huà)在紙上，再依次編寫(xiě)代碼，在程序設(shè)計(jì)中，編寫(xiě)代碼只是一個(gè)方面，調(diào)試才是關(guān)鍵。它是一個(gè)相當(dāng)繁瑣的過(guò)程，有許多新的問(wèn)題需要

27、被解決，但同時(shí)它也是一個(gè)比較重要的過(guò)程，因?yàn)樵诔绦蛘{(diào)試過(guò)程中，你會(huì)學(xué)到很多新的東西，從而增加你編程的經(jīng)驗(yàn)。 在設(shè)計(jì)一元多項(xiàng)式算法時(shí)，出現(xiàn)了一些問(wèn)題，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒(méi)能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。實(shí)現(xiàn)加法時(shí)該鏈表并沒(méi)有向通常那樣通過(guò)建立第三個(gè)鏈表來(lái)存放運(yùn)算結(jié)果，而是再度利用了鏈表之一來(lái)進(jìn)行節(jié)點(diǎn)的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個(gè)節(jié)點(diǎn)的排序函數(shù)，通過(guò)對(duì)鏈表排序后再進(jìn)行之后加減運(yùn)算。迷宮求解第一章 概述1.1 開(kāi)發(fā)的目的和意義迷宮問(wèn)題要求尋找一條從入口到出口的路徑。即從入口出發(fā)，順

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

29、退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中要應(yīng)用“棧”的思想假設(shè)“當(dāng)前位置”指的是“在搜索過(guò)程中的某一時(shí)刻所在圖中某個(gè)方塊位置”，以0和1所組成的迷宮形式輸出，標(biāo)記所走過(guò)的路徑結(jié)束程序；當(dāng)迷宮無(wú)路徑時(shí)，提示輸入錯(cuò)誤結(jié)束程序 。第二章 迷宮求解系統(tǒng)概要設(shè)計(jì)2.1系統(tǒng)設(shè)計(jì)概要從入口出發(fā)，按某一方向向前探索，若能走通并且未走過(guò)，即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一個(gè)方向；若所有的方向均沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到找到一條通路，或無(wú)路可走又返回入口點(diǎn)。在求解過(guò)程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無(wú)路）時(shí)，能正確

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

31、變mazeij的值，迷宮棧的實(shí)現(xiàn)直接置-1，算法結(jié)束前恢復(fù)原迷宮；而迷宮遞歸是將當(dāng)前值置為已走的步驟，這樣輸出時(shí)對(duì)走過(guò)的路更顯而易見(jiàn)。棧的函數(shù)設(shè)計(jì)：棧的初始化函數(shù) Init_SeqStack()判棧空 Empty_SeqStack()入棧函數(shù) Push_SeqStack()出棧函數(shù) Pop_SeqStack()取棧頂函數(shù) GetTop_SeqStack()銷毀棧 Destroy_SeqStack()第三章 詳細(xì)設(shè)計(jì)3.1系統(tǒng)的實(shí)現(xiàn)在上述表示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)（x，y），與其相鄰的4個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定

32、為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針?lè)较蜻M(jìn)行。為了簡(jiǎn)化問(wèn)題，方便求出新點(diǎn)的坐標(biāo)，將從正東開(kāi)始沿順時(shí)針進(jìn)行的4個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move4中，在move數(shù)組中，每個(gè)元素有兩個(gè)域組成，x為橫坐標(biāo)增量，y為縱坐標(biāo)增量。這樣對(duì)move設(shè)計(jì)會(huì)很方便地求出從某點(diǎn)（x，y）按某一方向v(0<=v<=3)到達(dá)的新點(diǎn)（i，j）的坐標(biāo)：i=x+movev.x;j=y+movev.y;當(dāng)?shù)竭_(dá)了某點(diǎn)而無(wú)路可走時(shí)需返回前一點(diǎn)，再?gòu)那耙稽c(diǎn)開(kāi)始向下一個(gè)方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向。棧中元素是一個(gè)由行、列、方向組成。具體結(jié)構(gòu)定義如

33、下：#include <stdio.h> #include <stdlib.h> #define MaxSize 100 #define StackIncrement 10 struct Seat /定義坐標(biāo)結(jié)構(gòu)體 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) /構(gòu)建一個(gè)棧 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) /判斷當(dāng)前位置是否通 return Maps.xs.y; bool FootPrint(Seat s) / 在此位置留下標(biāo)記，表示已經(jīng)經(jīng)過(guò) is_throughs.xs.y=true; return true; Seat NextPos(Seat s,int i) / 將當(dāng)前位置指向邏輯上的下個(gè)位置，指向的方向由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); /創(chuàng)建棧并且初始化 Seat curpos; curpos.x=start.x; curpos.y=start.y; /設(shè)定當(dāng)前位置為入口地址 int curstep=1; / 探索第一步 do if(Pass(curpos)&&!is_throughcurpos.xcurpos.y) /當(dāng)前位置通且沒(méi)有來(lái)過(guò) Fo

39、otPrint(curpos); / 留下痕跡 SElemType e; / 構(gòu)建入棧信息 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) / 到達(dá)終點(diǎn) return true; curpos=NextPos(curpos,1); / 探索下一步 curstep+; else / 當(dāng)前位置不通，將前面一個(gè)位置取出，改由其他方向在判斷 SElemType e; if(!StackEmpty(S) P

40、op(S,e); while(e.di=4&&!StackEmpty(S) FootPrint(e.seat); Pop(S,e); / 如果這個(gè)位置的其他四個(gè)方向都不滿足，表示這個(gè)位置不可取，取出棧并且留下標(biāo)識(shí) if(e.di<4) / 如果其他方向還沒(méi)有探索完，繼續(xù)探索下一個(gè)方向 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; 第四章 調(diào)試分析4.1系統(tǒng)運(yùn)行界面系統(tǒng)運(yùn)行后，其運(yùn)行界面如圖4-1所示。圖4-1迷宮求解系統(tǒng)運(yùn)行圖第五章 程序設(shè)計(jì)結(jié)語(yǔ)5.1 此次課程設(shè)計(jì)的總結(jié)本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。 首先由用戶輸入一組二維數(shù)組來(lái)組成迷宮，確認(rèn)后程序自動(dòng)運(yùn)行，當(dāng)迷宮有完整路徑可以通過(guò)時(shí)，通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，讓我學(xué)到了好多東西。在實(shí)際操作過(guò)程中犯了一些錯(cuò)誤卻讓我有了意外的收獲，所學(xué)數(shù)據(jù)結(jié)構(gòu)理論知識(shí)得到了鞏固。通過(guò)實(shí)際操作，學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)程序編程的基本步驟、基本方法，開(kāi)發(fā)了自己的邏輯思維

43、能力，培養(yǎng)了分析問(wèn)題、解決問(wèn)題的能力。現(xiàn)在終于挨到了寫(xiě)收獲與體會(huì)的時(shí)候了，的確令人興奮，看看自己的勞動(dòng)成果，好開(kāi)心。上網(wǎng)查資料、去圖書(shū)館查，查相關(guān)的函數(shù)，經(jīng)過(guò)兩三天的努力，我把框架弄出來(lái)了，可是還有計(jì)算難題擺在我的面前，真的是個(gè)難題，自從把框架弄好了以后就沒(méi)有進(jìn)展了，眼看一個(gè)星期快過(guò)去了，我那個(gè)急啊，可是急也沒(méi)有用。我堅(jiān)持，終于工夫不負(fù)有心人，我參照類似程序，改改和添添，終于大功告成，我們歡呼我們?nèi)杠S，終于相信我們自己是足夠的偉大。圖的遍歷及拓?fù)渑判虻谝徽?概述1.1 開(kāi)發(fā)設(shè)計(jì)的目的和意義本課設(shè)題目要求編寫(xiě)算法能夠建立有向無(wú)環(huán)圖，有向無(wú)環(huán)圖，能夠求解該有向無(wú)環(huán)圖的拓?fù)渑判虿⑤敵鰜?lái)，輸出除拓?fù)渑?/p>

44、序數(shù)據(jù)外，還要輸出鄰接表數(shù)據(jù)。為了更好地完成工程，必須滿足活動(dòng)之間先后關(guān)系，需要將各活動(dòng)排一個(gè)先后次序即為拓?fù)渑判颉Ｍ負(fù)渑判蚩梢詰?yīng)用于教學(xué)計(jì)劃的安排，根據(jù)課程之間的依賴關(guān)系，制定課程安排計(jì)劃。按照用戶輸入的課程數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會(huì)給出符合拓?fù)渑判虻恼n程安排計(jì)劃。1.2需求分析該系統(tǒng)的功能應(yīng)能夠?qū)崿F(xiàn)圖的遍歷以及拓?fù)渑判颍唧w分析如下：1.將圖以合適的方式存儲(chǔ)起來(lái)。圖有多種存儲(chǔ)方式，其中最常用的存儲(chǔ)方式有圖的鄰接矩陣和鄰接表。本人在構(gòu)思時(shí)使用鄰接表來(lái)建立有向無(wú)環(huán)圖，將其存儲(chǔ)起來(lái)。2.求解該有向無(wú)環(huán)圖的拓?fù)渑判颍⑵漭敵龀鰜?lái)。若通過(guò)構(gòu)造，建立了一個(gè)有向無(wú)

45、環(huán)圖，那么一定可以求出其拓?fù)渑判颍湓肀容^簡(jiǎn)單。即統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，將入度為0的結(jié)點(diǎn)提取出來(lái)，然后再統(tǒng)計(jì)剩下的結(jié)點(diǎn)的入度，再次將入度為零的結(jié)點(diǎn)提取出來(lái)，以此類推，這樣就形成了一個(gè)序列，這樣的序列就是該圖的拓?fù)渑判蛐蛄小?.拓?fù)渑判蛩惴☉?yīng)能夠處理出現(xiàn)環(huán)的情況。個(gè)人在寫(xiě)程序時(shí)，考慮到構(gòu)造圖時(shí)，會(huì)有構(gòu)造成有向有環(huán)圖的情況，應(yīng)該在運(yùn)行程序時(shí)，提醒出來(lái)，然后重新輸入有向無(wú)環(huán)圖，知道輸入正確為止。這樣就有多次構(gòu)造鄰接表的問(wèn)題，每一次構(gòu)造鄰接表時(shí)，都應(yīng)該將原來(lái)錯(cuò)誤的（不是無(wú)環(huán)圖的）鄰接表空間釋放掉，否則，會(huì)變得混亂。4.輸出除拓?fù)渑判蛲猓€要求輸出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲(chǔ)的，所以很容易將其鄰接表

46、輸出來(lái)。第二章 圖的遍歷及拓?fù)渑判蛳到y(tǒng)概要設(shè)計(jì)2.1系統(tǒng)流程圖根據(jù)程序的總的步驟，擬將整個(gè)流程分為三個(gè)模塊。三個(gè)模塊既相互獨(dú)立又相互聯(lián)系。具體分析如下：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)改變。2. 判斷圖是不是有向無(wú)環(huán)圖。當(dāng)圖為有向無(wú)環(huán)圖時(shí)，則挑選完畢后，隊(duì)列應(yīng)該是滿的，進(jìn)行后續(xù)步驟。對(duì)于結(jié)點(diǎn)入隊(duì)列的順序，需要借助于visited數(shù)組。選取入度為零的結(jié)點(diǎn)，入隊(duì)列，調(diào)整visited數(shù)組，循

47、環(huán)進(jìn)行。若隊(duì)列不滿，則輸入的圖不符合要求，應(yīng)該重新輸入。在程序中應(yīng)做適當(dāng)提醒，然后自動(dòng)轉(zhuǎn)模塊1.，進(jìn)行圖的重新編輯。3. 拓?fù)渑判颉４藭r(shí)，所輸入的弧應(yīng)該是有向無(wú)環(huán)圖了，下面進(jìn)行拓?fù)渑判颉Ｔ谂袛嗨欠駷闊o(wú)環(huán)圖的過(guò)程中已經(jīng)形成了一個(gè)滿隊(duì)列。接下來(lái)所要做的事情就是循環(huán)出隊(duì)列，按照隊(duì)列固有的順序進(jìn)行輸出即可，排序完成。系統(tǒng)的流程圖如圖2-1所示。開(kāi)始圖形輸入構(gòu)造鄰接表并輸出 否無(wú)環(huán)圖入度為零入隊(duì)列調(diào)整visited 是滿隊(duì)列 否循環(huán)出隊(duì)列 是結(jié)束圖2-1系統(tǒng)流程圖2.2功能模塊圖系統(tǒng)的功能模塊圖如圖2-2所示.包括圖的遍歷和拓?fù)渑判騼刹糠郑瑘D的遍歷中若是有環(huán)圖則遍歷全部，若是無(wú)環(huán)圖則無(wú)法遍歷；拓?fù)渑判?/p>

48、模塊則實(shí)現(xiàn)拓?fù)渑判蚬δ堋Ｏ到y(tǒng)拓?fù)渑判驁D的遍歷有環(huán)圖遍歷全部無(wú)環(huán)圖無(wú)法遍歷入度為零入隊(duì)輸出隊(duì)列圖2-2系統(tǒng)功能圖第三章 詳細(xì)設(shè)計(jì)3.1 系統(tǒng)功能的實(shí)現(xiàn)本程序的拓?fù)渑判颍仨氃趫D的鄰接表已知的情況下。它還有另外一個(gè)功能：判斷一個(gè)圖是不是無(wú)環(huán)圖。確切的說(shuō)，不能單純的叫拓?fù)渑判颍紤]它主要的作用，在不引起誤解的情況下就叫拓?fù)渑判蛩惴āＥ袛嘁粋€(gè)圖是否為有向無(wú)環(huán)圖并進(jìn)行拓?fù)渑判颍卸ǚ椒ㄓ泻芏喾N，檢查一個(gè)有向圖是否存在環(huán)要比無(wú)向圖復(fù)雜。對(duì)于無(wú)向圖來(lái)說(shuō)，若深度優(yōu)先遍歷過(guò)程中遇到回邊（即指向已訪問(wèn)過(guò)的頂點(diǎn)的邊），則必存在環(huán)；而對(duì)于有向圖來(lái)說(shuō)，這條回邊有可能指向深度優(yōu)先森林中另一棵生成樹(shù)上頂點(diǎn)的弧。但是，如果

49、從有向圖上某個(gè)頂點(diǎn)出發(fā)的遍歷，在dfs(v)結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，由于在生成樹(shù)上是的子孫，則有向圖中必定存在包含頂點(diǎn)v和u的環(huán)。另一種判斷是否有環(huán)的方法則顯得簡(jiǎn)單的多，尤其是對(duì)于本題目來(lái)說(shuō)，由于本題要求是對(duì)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判颍渲饕椒ㄊ菍⑷攵葹榱愕慕Y(jié)點(diǎn)依次輸出來(lái)，知道圖的所有定點(diǎn)全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結(jié)點(diǎn)在其他結(jié)點(diǎn)都選擇出來(lái)后，入度都不為零，即無(wú)法被輸出出來(lái)。那么就可以認(rèn)為按照拓?fù)渑判虻姆椒ㄝ敵鼋Y(jié)點(diǎn)后，若不是將節(jié)點(diǎn)全部輸出出來(lái)的，則此圖為有環(huán)圖。判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現(xiàn)環(huán)的情況，若構(gòu)造的圖為有環(huán)圖，則折回開(kāi)始重新輸入圖的數(shù)

50、據(jù)，重新構(gòu)造圖，直到該圖為無(wú)環(huán)圖為止。若圖已經(jīng)是無(wú)環(huán)圖，則進(jìn)行拓?fù)渑判颍判蚍椒ㄇ懊嬉呀?jīng)講過(guò)，在此主要訴說(shuō)用到的輔助存儲(chǔ)。數(shù)組visited存儲(chǔ)各結(jié)點(diǎn)的入度，對(duì)入度為零的結(jié)點(diǎn)，依次入隊(duì)列queue，調(diào)整visited數(shù)組，結(jié)點(diǎn)全部入隊(duì)列后，然后依次出隊(duì)列，拓?fù)渑判蛲瓿伞?shí)現(xiàn)功能的程序代碼如下：#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+) /建立鄰接表頭結(jié)點(diǎn) g.ai.data=0; /入度值為0 g.ai.next=NULL; for(k=1; k<=e;k+) cout<<"請(qǐng)輸入一條弧:" cin>>i>>j ; /輸入一條弧 <i,j> cout<<endl;s=new link; /申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j ;s->next=g.ai.next ;g.ai.next=s ;g.aj.data+; /入度加1void node:topsort (node &g,int n ) /拓?fù)渑判騣nt top=0,m=0;for (int i=1;i<=n;i+) /入度為0的頂點(diǎn)進(jìn)棧if (g.ai.data=0) g.ai