數(shù)據(jù)結(jié)構(gòu)及算法的設(shè)計與實現(xiàn)

1、沈陽工程學(xué)院課程設(shè)計設(shè)計題目:數(shù)據(jù)結(jié)構(gòu)及算法的設(shè)計與實現(xiàn)系 別 信息系學(xué)生姓名指導(dǎo)教師班級學(xué)號職稱起止日期：2009年12月28日起-至2010年1月8日止沈陽工程學(xué)院計算機組成原理課程設(shè)計成績評定表系（部）： 信息工程系 班級： 學(xué)生姓名： 指導(dǎo)教師評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分調(diào)研 論證能獨立查閱文獻，收集資料；能制定課程設(shè)計 方案和日程安排。0。15432工作能力 態(tài)度工作態(tài)度認真，遵守紀(jì)律，出勤情況是否良好， 能夠獨立完成設(shè)計工作，0。25432工作量按期圓滿完成規(guī)定的設(shè)計任務(wù)，工作量飽滿，難度適宜。0.25432說明書的質(zhì)量說明書立論正確，論述充分，結(jié)論嚴(yán)謹合理，文字通順，技

2、術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊全， 圖表完備，書寫工整規(guī)范。0。55432指導(dǎo)教師評審成績 （加權(quán)分合計乘以8）分加權(quán)分合計指導(dǎo)教師簽名：年 月日評閱教師評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分查閱 文獻查閱文獻有一定廣泛性；有綜合歸納資料的能 力0。25432工作量工作量飽滿，難度適中0.55432說明書的質(zhì)量說明書立論正確，論述充分，結(jié)論嚴(yán)謹合理，文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊全， 圖表完備，書寫工整規(guī)范。0.35432評閱教師評審成績 （加權(quán)分合計乘以4）分加權(quán)分合計評閱教師簽名：年 月日答辯小組評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分學(xué)生匯報匯報準(zhǔn)備充分，思路清晰；語言表達準(zhǔn)確，概

3、 念清楚，論點正確，有層次，有重點，基本上 反映了所完成任務(wù)的全部內(nèi)容；時間符合要求。0.55432答辯思路清晰；回答問題有理論依據(jù)，基本概念清 楚；主要問題回答準(zhǔn)確，深入，有說服力。0。55432答辯小組評審成績 （加權(quán)分合計乘以8）分加權(quán)分合計答辯小組教師簽名：年 月日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書設(shè)計目的數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程， 是一門實踐性很強的課程。 課程設(shè)計是 加強學(xué)生實踐能力的一個強有力手段 ,要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編 寫、類C語言的算法轉(zhuǎn)換成C （C+）程序并上機調(diào)試的基本方法，還要求學(xué)生 在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告 .嚴(yán)格實施課程設(shè)計這一環(huán) 節(jié)

4、，對于學(xué)生基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練， 將起到顯 著的促進作用 .二、設(shè)計要求1、課程設(shè)計題目每組三題，每個學(xué)生必須獨立完成 ;2、課程設(shè)計時間為 2 周;3、設(shè)計語言C （ C+）不限；4、課余時間完成源程序和課程設(shè)計報告等文檔書寫工作，上機時間只能做 調(diào)試工作。上機時帶上源程序、數(shù)據(jù)結(jié)構(gòu)教材、 C 語言教材 .5、上機任務(wù)1）選擇合適的數(shù)據(jù)結(jié)構(gòu)，并定義數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體；2）根據(jù)程序所要完成的基本要求，設(shè)計出完整的算法 ；3）設(shè)計出主程序（ main 函數(shù)） ,使其成為完整的程序。6、上機時間：按照實驗室上機時間安排計劃執(zhí)行7、無論在校外、校內(nèi)，都要嚴(yán)格遵守學(xué)校和所在單

5、位的學(xué)習(xí)和勞動紀(jì)律、 規(guī)章制度 ,學(xué)生有事離校必須請假。課程設(shè)計期間，無故缺席按曠課處理 ；缺席時 間達四分之一以上者 ,其成績按不及格處理。三、報告書寫格式1封皮2成績單3任務(wù)書4目錄5正文6參考文獻四、成績評定評定成績根據(jù)課程設(shè)計表現(xiàn)、 成績測驗、 課程設(shè)計報告等進行綜合評定。 評定等級：不及格、及格、中、良好、優(yōu)秀。五、設(shè)計題目設(shè)計題目一 教學(xué)計劃安排檢驗程序（拓撲排序）【問題描述】 針對學(xué)院的計算機系本科課程， 根據(jù)課程之間的依賴關(guān)系， 制定課 程安排計劃 ,并滿足各學(xué)期課程數(shù)大致相同。按照用戶輸入的課程數(shù)，學(xué)期數(shù)， 課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系， 程序執(zhí)行后會給出每

6、學(xué)期 應(yīng)學(xué)的課程。（1）輸入的形式和輸入值的范圍：輸入間用空格隔開。要求用戶輸入的課程 數(shù)小于 20，學(xué)期數(shù)小于或是等于 8，課程名的長度小于等于 10 個字符。（2）程序所能達到的功能：按照用戶的輸入，給出每學(xué)期應(yīng)學(xué)的課程。（3）測試數(shù)據(jù)：輸入：學(xué)期數(shù)：5,課程數(shù):12，課程間的先后關(guān)系數(shù)：16, 課程的代表值：v1,v2，v3，v4,v5,v6, v7,v8，v9,v10,v11,v12。課程間兩兩間的 先后關(guān)系： v1 v2,v1 v3, v1 v4， v1 v12， v2 v3， v3 v5， v3 v7， v3 v8， v4 v5, v5 v7,v6 v8,v9 v10, v9 v1

7、1 , v9 v12,v10 v12， v11 v6輸出：第 1 學(xué)期應(yīng)學(xué)的課程： v1 v9 第2學(xué)期應(yīng)學(xué)的課程： v2 v4 v10 v11 第3學(xué)期應(yīng)學(xué)的課程： v3 v6 v12 第4學(xué)期應(yīng)學(xué)的課程： v5 v8 第5學(xué)期應(yīng)學(xué)的課程： v7設(shè)計題目二 停車場問題 【基本要求】停車場是一條可以停放 n 輛車的狹窄通道， 且只有一個大門汽車停放安到達 時間的先后依次由北向南排列（大門在最南端 ,最先到達的第一輛車停在最北端 ） 若停車場已經(jīng)停滿 n 輛車，后來的汽車在便道上等候， 一旦有車開走， 排在便道 上的第一輛車可以開入；當(dāng)停車場的某輛車要離開時 ,停在他后面的車要先后退 為他讓路，

8、等它開出后其他車在按照原次序開入車場 ,每兩停在車場的車要按時 間長短繳費。 要求：以棧模擬停車場 ,以隊列車場外的便道，按照從終端輸入的 數(shù)據(jù)序列進行模擬管理。每一組數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去” 信息、汽車牌照號碼、 以及到達或離去的時刻。 對每一組數(shù)據(jù)進行操作后的信息 為：若是車輛到達， 則輸出汽車在停車場的內(nèi)或便道上的位置： 若是車輛離去則 輸出汽車在停車場內(nèi)的停留時間和應(yīng)繳納的費用 （在便道上的停留時間不收費） 。 棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn) .設(shè)計題目三 編寫一個猜數(shù)字游戲 ,有一定的容錯功能 ,界面友好，功能齊全 。 游戲規(guī)則：a, 個四位數(shù)，各位上的數(shù)字不

9、重復(fù)，從 1到9。b, 按以下提示猜出這個四位數(shù)。c, 每次猜測輸入的數(shù)據(jù)給出類似的提示* A衣B。d, 其中A前的*代表你本次猜對了多少個數(shù)字。e, 其中B前的*代表你本次猜對的數(shù)字并且位置正確的個數(shù)。設(shè)計題目四 設(shè)計實現(xiàn)關(guān)鍵路徑的程序設(shè)計內(nèi)容與步驟選擇合適的數(shù)據(jù)結(jié)構(gòu)結(jié)點結(jié)構(gòu)的設(shè)計算法設(shè)計與分析 程序設(shè)計、實現(xiàn)、調(diào)試課程設(shè)計說明書進度安排設(shè)計工作 4 學(xué)時實現(xiàn)與調(diào)試 12 學(xué)時課程設(shè)計說明書 4 學(xué)時設(shè)計考核要求考勤 20%課程設(shè)計說明書 50 答辯 30%五、參考書目1 佟偉光,楊政 實用數(shù)據(jù)結(jié)構(gòu)（第二版） 科學(xué)出版社2 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社3 李保春編著 , 數(shù)據(jù)結(jié)構(gòu)

10、習(xí)題與解析 ,清華大學(xué)出版 2001 年第一版4 徐孝凱編著,數(shù)據(jù)結(jié)構(gòu)課程實驗 ,清華大學(xué)出版 2002 年第一版5 張乃笑編著,數(shù)據(jù)結(jié)構(gòu)與算法 ,電子工業(yè)出版社 2004 年 10月6 王衛(wèi)東編著 , 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)課 ,西安電子科技大學(xué)出版社 2001 年7 陳文博 朱青著,數(shù)據(jù)結(jié)構(gòu)與算法 ,機械工業(yè)出版社 1996 年8 趙文靜等編, 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo) ,西安交通大學(xué)出版社 1999 年摘要“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。它的教學(xué)要求是：學(xué)會分析研究計 算機加工的數(shù)據(jù)結(jié)構(gòu)的特征， 以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、 存儲 結(jié)構(gòu)及其相應(yīng)的算法 , 并初步掌握算法的時間分析和空間分析的技術(shù)

11、 . 另一方面， 本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程， 要求學(xué)生編寫的程序結(jié)構(gòu)清楚 和正確易讀，符合軟件工程的規(guī)范。在學(xué)習(xí)中，先要學(xué)習(xí)程序設(shè)計課程的目的掌握設(shè)計程序的思路 , 學(xué)習(xí)會用計 算機語言編寫程序，以實現(xiàn)所需要處理的任務(wù)。要正確處理算法與語法的關(guān)系， 算法是程序的核心、是靈魂，語法是外殼、是工具。不應(yīng)把學(xué)習(xí)重。點放在語法 規(guī)則上，語法是重要的，不掌握語法規(guī)則就無法編寫出正確的程序 . 一定要把重 點放在解題的思路上， 通過思考，和大量的閱讀 ,來構(gòu)造一個完整的程序 . 請記住： 重要的是學(xué)會編程 , 而不是背語法。程序設(shè)計是為了鍛煉我們的實際動手能力， 在一定程度上， 又增加了

12、我們的 各方面的知識， 特別是一些聯(lián)系實際的課程設(shè)計， 它的完成需要自己平時積累的 大量知識、 并且需要勤于思考的能力和無限的激情。 本次課設(shè)主要是學(xué)習(xí)程序設(shè) 計的方法 , 進行程序設(shè)計的基本訓(xùn)練，大多數(shù)的學(xué)生應(yīng)該把精力放在最基本，最 常用的內(nèi)容上 , 學(xué)好基本功。最后, 感謝老師在我們程序設(shè)計的過程中辛勤的指導(dǎo)和不倦的教誨。關(guān)鍵詞 ：線性表, 棧和隊列，二叉樹，圖，查找，排序數(shù)據(jù)結(jié)構(gòu)及算法課程設(shè)計成績評定.。. 。分2代結(jié)程分分1519 21分分代結(jié)游目錄課程設(shè)計任務(wù)書 .n摘要 。 。.v1.停車場問題 21.1 問 題 析.。21.2數(shù)據(jù)結(jié)構(gòu)與算法分析 . 1 。 3 。 核 心碼 。

13、41 。 4 運 行果 112 。 關(guān) 鍵 路 徑 的序 。 .。 .。 .142.1 問 題析。 .。.142.2 數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 析.。 。.142.3核心代碼 2.4運行結(jié)果 3。教學(xué)計劃安排檢驗程序 （拓撲排序 ）3.1 問 題析.。. 213 。 2 數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 析 。 .213。3核心碼 223。4運行果 .。 274. 猜 數(shù) 字戲.。 294。1 問題分析 .,294 。 2 數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 析.。 294.3 核 心 碼。 .。294 。 4 運 行 果33結(jié)論 致分代結(jié)。 .35.。 .36謝1 停車場問題1。1 問題分析停車場是一條

14、可以停放 n 輛車的狹窄通道，且只有一個大門汽車停放安到達 時間的先后依次由北向南排列 （大門在最南端， 最先到達的第一輛車停在最北端 ） 若停車場已經(jīng)停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道 上的第一輛車可以開入； 當(dāng)停車場的某輛車要離開時， 停在他后面的車要先后退 為他讓路， 等它開出后其他車在按照原次序開入車場， 每兩停在車場的車要按時 間長短繳費。 要求：以棧模擬停車場，以隊列車場外的便道 ,按照從終端輸入的 數(shù)據(jù)序列進行模擬管理。每一組數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達"或“離去 "信息、汽車牌照號碼、以及到達或離去的時刻 .對每一組數(shù)據(jù)進行操作后的

15、信息 為：若是車輛到達， 則輸出汽車在停車場的內(nèi)或便道上的位置： 若是車輛離去則 輸出汽車在停車場內(nèi)的停留時間和應(yīng)繳納的費用 （在便道上的停留時間不收費 ）。 棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。1。2 數(shù)據(jù)結(jié)構(gòu)與算法分析 本任務(wù)要求應(yīng)用動態(tài)存儲結(jié)構(gòu) , 并且需要兩個棧和一個隊列，棧用來模擬停 車場，隊列模擬便道。棧的特點是后進先出，隊列的特點是先進先出。本任務(wù)應(yīng)用了 C語言中的類來自定義頭文件，將任務(wù)分成多個的模塊 ，增強 了可讀性和簡單性，同時為日后的編寫 , 調(diào)試, 維護提供了極大地方便。該程序的基本流程圖如圖 1-1 所示。主要流程圖如圖 12 所示圖11基本流程圖圖1-2主流程圖1

16、.3 核心代碼include<stdio 。 h#include stdlib.h>#include string.h define MAX 2/ 車庫容量 為了便于觀察這里把車庫容量設(shè)置為 #define price 0.05 / 每分鐘每輛車的費用typedef struct time int hour;int min;Time;/ 時間結(jié)點typedef struct nodechar num10 ;Time reach；Time leave； CarNode;/車輛信息結(jié)點 typedef struct NODE CarNode *stackMAX+1;int top ；

17、SeqStackCar;/模擬車站typedef struct carCarNode *data ； struct car *next ； QueueNode;typedef struct NodeQueueNode *front ；QueueNode rear; LinkQueueCar; 模擬通道/車輛離開/* 定義方法 / void InitStack ( SeqStackCar) ;/初始化車站 int InitQueue (LinkQueueCar)； /初始化便道 int Arrival (SeqStackCar*，LinkQueueCar*);/ 車輛到達 void Leave(

18、SeqStackCar,SeqStackCar,LinkQueueCar)； void List (SeqStackCar，LinkQueueCar)； /顯示存車信息 / 主函數(shù) / void main( )SeqStackCar Enter， Temp;LinkQueueCar Wait ；int ch ；InitStack （&Enter ）； /構(gòu)造一個空棧InitStack （ Temp）； /InitQueue （ &Wait）;/ 構(gòu)造一個空隊列while （ 1）/printf （” n 請選擇： 1 2 34n”）；printf （ "n &

19、 & & & & &&& & 1。 車輛到達 & && && & && &&&& & "）;printf （” n& && & && & && &&& & & 2. 車輛離開 && & &&&& & & & & &

20、& " ）；printf（"n &&&&&&&&& &&&&& & && 3. 列表顯示 & & & &&& & && &&&&&&"） ；printf（ "n&&&& & &&& & &&& &am

21、p;&& 4。 退出系統(tǒng) && && && &&& & & n ” ）;scanf（ ” d”,ch） ；if （ch1&&ch 4）/ 當(dāng)不符合要求時重新進行選擇break;else / 否則則進行方法的操作 switch（ch ）case 1: Arrival （ &Enter,&Wait） ； break； /車輛到達的操作 case 2： Leave（&Enter,&Temp,&Wait ）; break； /車輛離開的操作ca

22、se 3: List（Enter,Wait） ; break;/列表顯示的操作case 4: exit （0） ;/退出系統(tǒng)的操作default： break;/ 車場的初始化 棧/void InitStack （ SeqStackCar s）/ int i;s- top=0 ； /棧為空 for(i=0;i =MAX;i+ )s- stacks->top =NULL;/ 初值為空 / 便道的初始化 隊列的鏈?zhǔn)浇Y(jié)構(gòu) */ int InitQueue(LinkQueueCar Q)Q->front= (QueueNode* ) malloc(sizeof ( QueueNode) ;

23、if (Qfront!=NULL )Q front->next=NULL;/ 隊列頭結(jié)點為空Q rear=Q front ；return (1 ); else return (0)； /* 離站所進行的操作 */void PRINT ( CarNode *p,int room ) int A1 ，A2 ，B1，B2; printf (” n 請輸入離開的時間： " )；scanf (” %d： d ”，& (p > leave。hour)，& (p->leave。min)；printf (” n 離開車輛的車牌號為： ”) ;puts(p> n

24、um) ;printf(” n 其到達時間為 :%d:%d" ， p->reach.hour，p> reach。 min) ; printf (”離開時間為： d： d"，p->leave。 hour，p-> leave。 min); A1=p > reach。 hour;A2=p > reach.min ；B1=p > leave.hour;B2=p >leave.min;printf("n 應(yīng)繳費用為： 2。1f 元",(B1 A1 ) *60+ ( B2A2) * price) free( p)；/*

25、 車輛到達 /int Arrival(SeqStackCar *Enter ， LinkQueueCar *W )CarNode p;QueueNode *t ；p= (CarNode ) malloc ( sizeof ( CarNode )； /生成結(jié)點/flushall ()； /清除所有緩沖區(qū)printf ( "n 請輸入車牌號 :”)； scanf( "%s”， &p->num )； /得到車牌號 if (Enter top<MAX )/ 判斷 如果停車場未滿 則進入 Enter->top+ ； /top 指針加一 printf ( &q

26、uot;n 車輛在停車場內(nèi)的第 d 位置” ,Enter-top)； printf (” n 請輸入到達時間： ") ；sea nf (" % d: % d", &( p reach。hour)，& ( p->reach. min); Enter >stack Enter->top =p; 車輛進棧 return (1);elseprintf( ” n 該車須在便道等候！ ”) ; t=(QueueNode) malloc( sizeof( QueueNode) ;t data=p； /把車輛信息存入隊列的結(jié)點即車輛停在便道t&g

27、t;next=NULL ； /t 結(jié)點的下一個結(jié)點為空W->front- next=t； /頭指針的下一個為 t W->rear=t;尾指針指向t return ( 1 ) ;/* 出棧 /void Leave(SeqStackCar Enter，SeqStackCar Temp，LinkQueueCar *W ) int i ，room;CarNode p， t；QueueNode q;/判斷車場內(nèi)是否有車 /if(Enter->top>0 )while(1 )場里的車放temp 中里有printf（ ”n 請輸入車在車場的位置 :" ， Enter->

28、;top ）; scanf（” d"， room） ;if（room 1&&room>=Enter top）break;while（Enter- top room）Temp >top+ ；/top 指針加一Temp>stackTemp>top=Enter-stackEnter >top； /把停車 入Enter >stack Enter >top =NULL ； /把停車場里的位置清空Enter->top-;/top 指針減一同時p=EnterstackEnter top；Enter->stack Enter to

29、p=NULL;Enter-top ；while （ Temp top =1）Enter>top+ ； /當(dāng)車出去后原來的車回到停車場Enter- stackEnter- top=Temp >stack Temp top ；Temp- stackTemp>top=NULL;Temp top- ；PRINT（p ， room）； /離開停車場的信息if（W->front!=W->rear ）& Enter- top<MAX ） /如果便道上有車 ,并且停車 空位q=W->front- next； /把便道里的車賦給 qt=q >data； /

30、車的信息賦給 tEnter->top+;printf （"n便道的 s號車進入車場第 d位置。",t>num , Enter-top）;printf（ "n 請輸入現(xiàn)在的時間： ”）;scanf（"d：%d"，（t- reach。 hour），&（t- reach.min）；W >front > next=q >next;/頭指針指向 q 的下一個if（q=W rear） /如果便道里沒車W >rear=W- front;/ 清空Enter stackEnter->top=t ； /進入停車場

31、printf （"n 便道里沒車 n" ）； free（q）；break;elseprintf （"n 車場里沒車?！保?break;/* 列表的顯示信息 */void List1 （ SeqStackCar *s）int i;if（s >top0）printf （"n 車場 "）；printf （ "n 位置 到達時間 車牌號 n”）； for（i=1;i =stop； i+）printf（ ” d%10d ： d%sn", i, s->stacki >reach.hour ，s stack i - re

32、ach.min,s- stack i- num）；/ puts（s- stacki- num） ;else printf （” n 車場里沒車” ） ；/ 便道里的信息 / void List2 （ LinkQueueCar w）QueueNode *p; p=w front next； if （ w >front!=w rear）printf （” n 等待的車輛的號碼為 :"）； while （p!=NULL ）puts（ p->data->num ） ;printf （ ”n"）； p=p next；else printf（"n 便道里沒有

33、車。 ”）；/void List（SeqStackCar s ， LinkQueueCar w ）int flag ， m;flag=1;while（flag ）printf （ "n 請選擇 1 2 3"）;printf（"n1。車場 n2.便道 n3.返回”）；while（1）scanf（ ” d", m）； if（m>=1|m =3）break；n”） ；switch （m）case 1：List1（&s）；break；case 2：List2（ &w ）； breakcase 3: default ： break；flag=

34、0；break；1.4運行結(jié)果1。運行程序，打開停車場主菜單，如圖1 3所示 I*lt:Documents and Setbingse302-ifiiWAHGHAnmaai.eHe1&&&&&&&&&&&&&&&&&&&&&&&&&& 2.&&&&&&&&&&&&&&&&

35、amp;&&&&&&&&&&3.達幵示統(tǒng)到離顯系出車14退&&浜&&&&&&&&&&跪畏浜&&&&隹 4.達開示統(tǒng) H 軸軸表出 車車蛋回圖1-3主菜單2。根據(jù)菜單提示，輸入“1”然后輸入停車車牌“遼A888888”和時間“ 8:30", 如圖1-4所示。rSB C：Users'Administrstor.DesktopydANGHAOmain.exe嚴(yán)輸入車牌號t A8

36、8S888 岸稱在停車場內(nèi)的弟i僅宜 情輸入到達時何：8 = 38圖1 4輸入停車信息3程序默認兩個車道，當(dāng)要求繼續(xù)停車時，就停入便道里，如圖1 5所示KB C;UsersAdministratorDesktopWANGHAOmain.exe請輸入車牌號：冊師&師局蘭輛在停車場內(nèi)的第2位置諳輸入到達吋間：»=«吐臨&&&&&&&&&&&&&&&&&&&&&&&&2.枝昭翻rS&

37、lt;&壓鳩曲&昭顯辭:辭酬r 4,1諳輸入車牌號：C99999999該車須在彳弼首等候TM開亍統(tǒng) 到離顯系 輛輛表出 車車列退圖1 5便道停車Q | 回12 3 4達開示統(tǒng) 到亠腎顯系 輔軻弄士 車車列返32J11 擡場道回 選主便返 主fl kiLzk_r圖1 6車道信息4.根據(jù)提示，輸入“ 3"后，再分別輸入“1”和“ 2”，輸出車道信息和便道信息，分 別如圖1-6和1-7所示。甫戈捋1 2 31 車場2 便著a .逅回2321 掙場道冋迭車便返« «i 2 3圖1 7便道信息5. 返回主菜單后，輸入“ 2"，然后輸入車離開的位置和

38、時間，便顯示車離開的信息 費用以及便道的車進入車道要求輸入信息，如圖1 8所示，完成后便顯示便道車 的信息，如圖1 9所示.圖1 8車離開圖1 9便道車進入停車場2 關(guān)鍵路徑2。1 問題分析關(guān)鍵路徑（CPM ）是管理科學(xué)中的一個重要方法，廣泛應(yīng)用于大型工程計劃 工作，也稱之為“統(tǒng)籌法” 。關(guān)鍵路徑法采用邊表示活動的網(wǎng)絡(luò)，簡稱為 AOE 網(wǎng)絡(luò)。 AOE 網(wǎng)絡(luò)是一個帶權(quán)的有向無環(huán)路圖，其中，每個頂點代表一個事件， 事件說明某些活動或某些活動的完成，即階段的結(jié)果。通常，利用 AOE 網(wǎng)絡(luò)可 以研究一下兩個問題：完成整個工程至少需要多少時間哪些活動是影響工程進度的關(guān)鍵 但是完成整個工程所需的時間取決于

39、從開始點到結(jié)束點的最長路徑長度， 此 長度最大路徑稱作為關(guān)鍵路徑 .2.2數(shù)據(jù)結(jié)構(gòu)與算法分析首先得構(gòu)造一個圖來存儲整個工程的頂點數(shù)和活動數(shù)。在描述關(guān)鍵路勁的算法時，設(shè)a活動由?。╦，k）表示，要確定如下幾個相關(guān) 的量：事件 V 的最早出現(xiàn)時間和活動的最早開始時間，從源點 v1 到頂點 v 的最 長路徑長度稱作事件 j 的最早出現(xiàn)時間，表示成 ej?；顒觓的最遲開始時間：在不影響整個工程按時完成的前提下， 此項活動 最遲的必須開始時間，表示成 L 門。只要某活動a有Li=ei的關(guān)系，就稱a 為關(guān)鍵活動。事件 j 的最遲出現(xiàn)時間：事件 j 在不延誤整個工程的前提下允許發(fā)生的最遲 時間，表示為L 門

40、。對某條指向頂點V的邊所代表的活動a可得到Li=L j （活動 a 所需時間）。該程序的主要流程圖如圖 2-1 所示.圖2 1關(guān)鍵路徑主要流程圖2。3核心代碼#inelude stdio。h>#include<stdlib。h># in elude ioma nip。 h># in elude process。h>typedef struct nodeint adjvex ；int dut;struct node *n ext; edgenode;typedef structint projectname；int id ； edgenode *link;vexno

41、de;void CreateGraphic （ vexnode ,int ， int ）； int SearchPath（ vexnode， int， int,int& ）；int main （）int flag,projectnum ， activenum,totaltime=0 ； printf （ "請輸入這個工程的化成圖形的結(jié)點數(shù):” ）；scanf（ "%d", projectnum ）；printf（" 請輸入這個工程的活動個數(shù)： "） ； scanf（ " d" ，&activenum ）;ve

42、xnode* Graphicmap= （ vexnode* ） malloc（projectnum*sizeof （ vexnode）； CreateGraphic（Graphicmap,projectnum ， activenum ）;flag=SearchPath（ Graphicmap ， projectnum,activenum ， totaltime） ； if （flag=0 ）printf（"n 本程序所建立的圖有回路不可計算出關(guān)鍵路徑n" ）；elseprintf （ "n 全工程可以完成的最早時間為： d 個單位時間 n" ， tota

43、ltime ）; system（"pause"）；void CreateGraphic （ vexnode Graphicmap,int projectnum,int activenum ） /創(chuàng)建圖的函數(shù) int begin ， end,duttem;edgenode p;for （ int i=0;i projectnum;i+ ）Graphicmap i 。 projectname=i ；Graphicmapi.id =0 ；Graphicmapi 。 link =NULL;printf （”某項目的開始到結(jié)束在圖中的節(jié)點輸入vi，vj，dut n"）;pr

44、intf （”如： 1，2，3 回車表示第 1結(jié)點到第 2結(jié)點之間的活動用了 3個單位時間n"） for(int k=0 ；k activenum;k+ )scanf(” d， d,%d"， begin，&end,&duttem )； p= ( edgenode*) malloc (sizeof(edgenode)； p- adjvex =end 1;p >dut =duttem;Graphicmapend-1 .id +;p->next =Graphicmap begin-1 .link ；Graphicmapbegin 1.link =p ；

45、int SearchPath( vexnode* Graphicmap ， int projectnum,int activenum ， int& totaltime ) /查找關(guān) 鍵路徑int i ，j ，k，m=0；int front=-1,rear=-1;int topologystack=(int*)malloc(projectnum sizeof(int ) ;/保存拓撲排列int* vl= (int* ) malloc(projectnum*sizeof (int) );/表示在不推遲整個工程的前提下， Vj 允許最遲發(fā)生的時間int ve= ( int )malloc (

46、 projectnum sizeof(int )； /表示 Vj 最早發(fā)生時間 int* l= (int*)malloc(activenum*sizeof ( int ) ;/表示活動 Ai 最遲完成開始時間 int* e= ( int ) malloc ( activenum sizeof(int ) );/表示活動最早開始時間 edgenode p;totaltime=0 ；for ( i=0;i<projectnum ；i+ ) ve i=0;for ( i=0 ； i<projectnum;i+ )if (Graphicmapi 。 id=0 )topologystack

47、+rear=i ；m+;while ( front!=rear)front+;j=topologystack front m+;p=Graphicmap j.link ；while （ p）k=p->adjvex ；Graphicmapk.id - ；if（ve j+p >dut vek） ve k=vej +p->dut ；if （ Graphicmapk 。 id =0 ） topologystack +rear=k ； p=p- next ;if（m projectnum ）return 0 ；totaltime=ve projectnum 1;for （ i=0 ；

48、i<projectnum ；i+）vli =totaltime;for （ i=projectnum-2;i =0；i-）j=topologystacki ；p=Graphicmap j.link ;while （ p）k=p->adjvex ;if（ （ vlk -p- dut ）<vlj ）vl j=vl k p >dut ；p=p- next ；i=0；printf （" 起點 終點 最早開始時間 最遲完成時間 差值 否為關(guān)鍵活動 （* ） n"）；for （j=0;j<projectnum ；j+）p=Graphicmapj.link;

49、while (p)k=p- > adjvex ；e : +i =vej:;l i=vlk : p >dut;printf ( "%6d % 8d % 13d%18d%12d”,Gjectname+1,Gject name +1 , ei ,li , l i e i);if (li: =e : i:)printf (”*")；prin tf("n ”);p=p->next ;return 1 ;2.4運行結(jié)果1。運行該程序，打開如圖2-2所示，并輸入這個工程的化成圖形的結(jié)點數(shù)圖22輸入結(jié)點數(shù)2

50、。根據(jù)上圖提示輸入結(jié)點數(shù)后然后輸入活動個數(shù)，如圖2-3所示。圖2 3輸入結(jié)點數(shù)和活動數(shù)3。根據(jù)圖23所示，輸入9個節(jié)點之間的活動關(guān)系和時間，如圖24所示圖2-4輸入結(jié)點的關(guān)系和活動時間4.輸完11個活動后,即顯示該工程關(guān)鍵活動信息，如圖2-5所示圖2-5關(guān)鍵活動信息3 教學(xué)計劃安排檢驗程序(拓撲排序)3.1.問題分析針對學(xué)院的計算機系本科課程， 根據(jù)課程之間的依賴關(guān)系， 制定課程安排計 劃，并滿足各學(xué)期課程數(shù)大致相同。按照用戶輸入的課程數(shù)，學(xué)期數(shù)，課程間的 先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系， 程序執(zhí)行后會給出每學(xué)期應(yīng)學(xué)的課 程。(1) 輸入的形式和輸入值的范圍：輸入間用空格隔開。要求用戶

51、輸入的課程 數(shù)小于 20，學(xué)期數(shù)小于或是等于 8，課程名的長度小于等于 10 個字符.(2) 程序所能達到的功能：按照用戶的輸入，給出每學(xué)期應(yīng)學(xué)的課程。(3) 測試數(shù)據(jù)：輸入：學(xué)期數(shù)：5 ，課程數(shù)：12,課程間的先后關(guān)系數(shù)：16, 課程的代表值：v1 , v2,v3,v4,v5, v6,v7, v8, v9,v10, v11,v12。課程間兩兩間的 先后關(guān)系： v1 v2,v1 v3, v1 v4，v1 v12,v2 v3,v3 v5，v3 v7，v3 v8，v4 v5, v5 v7,v6 v8,v9 v10， v9 v11 ， v9 v12，v10 v12,v11 v6輸出：第 1 學(xué)期應(yīng)學(xué)

52、的課程： v1 v9第 2 學(xué)期應(yīng)學(xué)的課程： v2 v4 v10 v11第 3學(xué)期應(yīng)學(xué)的課程： v3 v6 v12第 4學(xué)期應(yīng)學(xué)的課程： v5 v8第 5學(xué)期應(yīng)學(xué)的課程： v73。2 數(shù)據(jù)結(jié)構(gòu)與算法分析拓撲排序時有向圖的一種重要運算 .在課表排序中，每門課都有多種關(guān)系： 先后關(guān)系，即必須在一類門課學(xué)完后，才能開始學(xué)習(xí)另一門課； 在一類課之間沒有次序要求，即兩門課可以同時噓唏，互不影響 將AOV 網(wǎng)絡(luò)中的各個頂點排列成一個線性有序序列， 使得所有要求的前趨、 后趨關(guān)系都 能得到滿足。在 AOV 網(wǎng)絡(luò)進行拓撲排序的方法：在網(wǎng)絡(luò)中選擇一個沒有前趨的頂點，并把它輸出；從網(wǎng)絡(luò)中刪去該頂點和從該頂點出發(fā)的所有有向邊；重復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出。 該程序的主要流程圖如圖 3-1 所示：圖3 1拓撲排序流程圖3.3核心代碼# include"malloc。h”# include"stdio.h"#defi ne OK 1#defi ne ERROR 0# define TRUE 1# define FALSE 0# define STACK_INIT_SIZE 100