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

沈陽工程學院課程設(shè)計設(shè)計題目：數(shù)據(jù)結(jié)構(gòu)及算法的設(shè)計與實現(xiàn)系別信息系班級學生姓名學號指導教師職稱起止日期：2009年12月28日起——至2010年1月8日止

沈陽工程學院計算機組成原理課程設(shè)計成績評定表系（部）：信息工程系班級：學生姓名：指導教師評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分調(diào)研論證能獨立查閱文獻收集資料；能制定課程設(shè)計方案和日程安排。0.15432工作能力態(tài)度工作態(tài)度認真，遵守紀律，出勤情況是否良好，能夠獨立完成設(shè)計工作，0.25432工作量按期圓滿完成規(guī)定的設(shè)計任務(wù)，工作量飽滿，難度適宜。0.25432說明書的質(zhì)量說明書立論正確，論述充分，結(jié)論嚴謹合理，文字通順，技術(shù)用語準確，符號統(tǒng)一，編號齊全，圖表完備，書寫工整規(guī)范。0.55432指導教師評審成績（加權(quán)分合計乘以8）分加權(quán)分合計指導教師簽名：年月曰評閱教師評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分查閱文獻查閱文獻有一定廣泛性；有綜合歸納資料的能力0.25432工作量工作量飽滿，難度適中。0.55432說明書的質(zhì)量說明書立論正確，論述充分，結(jié)論嚴謹合理，文字通順，技術(shù)用語準確，符號統(tǒng)一，編號齊全，圖表完備，書寫工整規(guī)范。0.35432評閱教師評審成績（加權(quán)分合計乘以4）分加權(quán)分合計評閱教師簽名：年月曰答辯小組評審意見評價內(nèi)容具體要求權(quán)重評分加權(quán)分學生匯報匯報準備充分，思路清晰；語言表達準確，概念清楚，論點正確，有層次，有重點，基本上反映了所完成任務(wù)的全部內(nèi)容；時間符合要求。0.55432答辯思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準確，深入，有說服力。0.55432答辯小組評審成績（加權(quán)分合計乘以8）分加權(quán)分合計答辯小組教師簽名：年月曰數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書―、設(shè)計目的數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程，是一門實踐性很強的課程。課程設(shè)計是加強學生實踐能力的一個強有力手段，要求學生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C（C++）程序并上機調(diào)試的基本方法，還要求學生在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告。嚴格實施課程設(shè)計這一環(huán)節(jié)，對于學生基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。二、設(shè)計要求1、課程設(shè)計題目每組三題，每個學生必須獨立完成；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)，都要嚴格遵守學校和所在單位的學習和勞動紀律、規(guī)章制度，學生有事離校必須請假。課程設(shè)計期間，無故缺席按曠課處理；缺席時間達四分之一以上者，其成績按不及格處理。三、報告書寫格式1.封皮成績單任務(wù)書目錄正文參考文獻四、成績評定評定成績根據(jù)課程設(shè)計表現(xiàn)、成績測驗、課程設(shè)計報告等進行綜合評定。評定等級：不及格、及格、中、良好、優(yōu)秀。五、設(shè)計題目設(shè)計題目一教學計劃安排檢驗程序（拓撲排序）【問題描述】針對學院的計算機系本科課程，根據(jù)課程之間的依賴關(guān)系，制定課程安排計劃，并滿足各學期課程數(shù)大致相同。按照用戶輸入的課程數(shù)，學期數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會給出每學期應(yīng)學的課程。（1）輸入的形式和輸入值的范圍：輸入間用空格隔開。要求用戶輸入的課程數(shù)小于20，學期數(shù)小于或是等于8,課程名的長度小于等于10個字符。（2）程序所能達到的功能：按照用戶的輸入，給出每學期應(yīng)學的課程。（3）測試數(shù)據(jù)：輸入：學期數(shù)：5,課程數(shù)：12，課程間的先后關(guān)系數(shù)：16，課程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。課程間兩兩間的先后關(guān)系：v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6輸出：第1學期應(yīng)學的課程：v1v9第2學期應(yīng)學的課程：v2v4v10v11第3學期應(yīng)學的課程：v3v6v12第4學期應(yīng)學的課程：v5v8第5學期應(yīng)學的課程：v7設(shè)計題目二停車場問題【基本要求】停車場是一條可以停放n輛車的狹窄通道，且只有一個大門汽車停放安到達時間的先后依次由北向南排列（大門在最南端，最先到達的第一輛車停在最北端）若停車場已經(jīng)停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道上的第一輛車可以開入；當停車場的某輛車要離開時，停在他后面的車要先后退為他讓路，等它開出后其他車在按照原次序開入車場，每兩停在車場的車要按時間長短繳費。要求：以棧模擬停車場，以隊列車場外的便道，按照從終端輸入的數(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ù)字不重復，從1到9。按以下提示猜出這個四位數(shù)。每次猜測輸入的數(shù)據(jù)給出類似的提示*A*B。其中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學時實現(xiàn)與調(diào)試12學時課程設(shè)計說明書4學時設(shè)計考核要求考勤20%課程設(shè)計說明書50%答辯30%五、參考書目佟偉光，楊政《實用數(shù)據(jù)結(jié)構(gòu)》（第二版）科學出版社嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學出版社李保春編著，《數(shù)據(jù)結(jié)構(gòu)習題與解析》，清華大學出版2001年第一版徐孝凱編著，《數(shù)據(jù)結(jié)構(gòu)課程實驗》，清華大學出版2002年第一版張乃笑編著，《數(shù)據(jù)結(jié)構(gòu)與算法》，電子工業(yè)出版社2004年10月王衛(wèi)東編著，《數(shù)據(jù)結(jié)構(gòu)輔導課》，西安電子科技大學出版社2001年陳文博朱青著，《數(shù)據(jù)結(jié)構(gòu)與算法》，機械工業(yè)出版社1996年趙文靜等編，《數(shù)據(jù)結(jié)構(gòu)輔導》，西安交通大學出版社1999年摘要“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。它的教學要求是：學會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特征，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。另一方面，本課程的學習過程也是復雜程序設(shè)計的訓練過程，要求學生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。在學習中，先要學習程序設(shè)計課程的目的掌握設(shè)計程序的思路，學習會用計算機語言編寫程序，以實現(xiàn)所需要處理的任務(wù)。要正確處理算法與語法的關(guān)系，算法是程序的核心、是靈魂，語法是外殼、是工具。不應(yīng)把學習重.點放在語法規(guī)則上，語法是重要的，不掌握語法規(guī)則就無法編寫出正確的程序。一定要把重點放在解題的思路上，通過思考，和大量的閱讀，來構(gòu)造一個完整的程序。請記?。褐匾氖菍W會編程，而不是背語法。程序設(shè)計是為了鍛煉我們的實際動手能力，在一定程度上，又增加了我們的各方面的知識，特別是一些聯(lián)系實際的課程設(shè)計，它的完成需要自己平時積累的大量知識、并且需要勤于思考的能力和無限的激情。本次課設(shè)主要是學習程序設(shè)計的方法，進行程序設(shè)計的基本訓練，大多數(shù)的學生應(yīng)該把精力放在最基本，最常用的內(nèi)容上，學好基本功。最后，感謝老師在我們程序設(shè)計的過程中辛勤的指導和不倦的教誨。關(guān)鍵詞:線性表，棧和隊列，二叉樹，圖，查找，排序目錄TOC\o"1-5"\h\z數(shù)據(jù)結(jié)構(gòu)及算法課程設(shè)計成績評定表I課程設(shè)計任務(wù)書II\o"CurrentDocument"摘要V\o"CurrentDocument"停車場問題.2\o"CurrentDocument"1.1問題分析2\o"CurrentDocument"1.2數(shù)據(jù)結(jié)構(gòu)與算法分析21.3.核心代碼41.4運行結(jié)果11關(guān)鍵路徑的程序14\o"CurrentDocument"2.1問題分析14\o"CurrentDocument"2.2數(shù)據(jù)結(jié)構(gòu)與算法分析142.3核心代碼152.4運行結(jié)果19\o"CurrentDocument"教學計劃安排檢驗程序（拓撲排序）21\o"CurrentDocument"3.1問題分析21\o"CurrentDocument"3.2數(shù)據(jù)結(jié)構(gòu)與算法分析21\o"CurrentDocument"3.3核心代碼223.4運行結(jié)果27\o"CurrentDocument"猜數(shù)字游戲29\o"CurrentDocument"4.1問題分析.,.294.2數(shù)據(jù)結(jié)構(gòu)與算法分析294.3核心代碼294.4運行結(jié)果33結(jié)論35\o"CurrentDocument"致謝361停車場問題1.1問題分析停車場是一條可以停放n輛車的狹窄通道，且只有一個大門汽車停放安到達時間的先后依次由北向南排列（大門在最南端，最先到達的第一輛車停在最北端）若停車場已經(jīng)停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道上的第一輛車可以開入；當停車場的某輛車要離開時，停在他后面的車要先后退為他讓路，等它開出后其他車在按照原次序開入車場，每兩停在車場的車要按時間長短繳費。要求：以棧模擬停車場，以隊列車場外的便道，按照從終端輸入的數(shù)據(jù)序列進行模擬管理。每一組數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼、以及到達或離去的時刻。對每一組數(shù)據(jù)進行操作后的信息為：若是車輛到達，則輸出汽車在停車場的內(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所示。主要流程圖如圖1-2所示。圖1-1基本流程圖否停入車道圖1-2主流程圖1.3核心代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX2//車庫容量為了便于觀察這里把車庫容量設(shè)置為2#defineprice0.05//每分鐘每輛車的費用typedefstructtime(inthour;intmin;}Time;//時間結(jié)點typedefstructnode(charnum[10];Timereach;Timeleave;}CarNode;//車輛信息結(jié)點typedefstructNODE(CarNode*stack[MAX+1];inttop;}SeqStackCar;//模擬車站typedefstructcar(CarNode*data;structcar*next;}QueueNode;typedefstructNode(QueueNode*front;QueueNode*rear;}LinkQueueCar;//模擬通道///////////////////////////////////////////////////*定義方法*/voidInitStack(SeqStackCar*);//初始化車站intInitQueue(LinkQueueCar*);//初始化便道intArrival(SeqStackCar*,LinkQueueCar*);〃車輛到達voidLeave(SeqStackCar*,SeqStackCar*,LinkQueueCar*);〃車輛離開voidList(SeqStackCar,LinkQueueCar);//顯示存車信息/////////////////////////////////////////////*主函數(shù)*/voidmain(){

SeqStackCarEnter,Temp;LinkQueueCarWait;intch;InitStack(&Enter);//構(gòu)造一個空棧InitStack(&Temp);//InitQueue(&Wait);//構(gòu)造一個空隊歹Uwhile(1)//printf("\n請選擇：1234\n");printf("\n&&&&&&&&&&&&&&&&&&&&&&&&&&1.車輛至U達&&&&&&&&&&&&&&&&&&&&&&&&");printf("\n&&&&&&&&&&&&&&&&&&&&&&&&&&2.車輛離開&&&&&&&&&&&&&&&&&&&&&&&&”);列表顯示退出系統(tǒng)printf("\n&&&&&&&&&&&&&&&&&&&&&&&&&&列表顯示退出系統(tǒng)&&&&&&&&&&&&&&&&&&&&&&&&”);printf("\n&&&&&&&&&&&&&&&&&&&&&&&&&&4.&&&&&&&&&&&&&&&&&&&&&&&&\n");scanf("%d",&ch);if(ch<1&&ch>4)〃當不符合要求時重新進行選擇{break;}else{//否則則進行方法的操作switch(ch){case1:Arrival(&Enter,&Wait);break;//車輛到達的操作case2:Leave(&Enter,&Temp,&Wai);break;//車輛離開的操作case3:List(Enter,Wait);break;//列表顯示的操作case4:exit(0);//退出系統(tǒng)的操作default:break;}}}}///////////////////////////////////////////*車場的初始化棧*/voidInitStack(SeqStackCar*s)//{inti;s->top=0;//棧為空for(i=0;i<=MAX;i++)s->stack[s->top]=NULL;//初值為空}///////////////////////////////////////////////*便道的初始化隊列的鏈式結(jié)構(gòu)*/intInitQueue(LinkQueueCar*Q){Q->front=(QueueNode*)malloc(sizeof(QueueNode));if(Q->front!=NULL){Q->front->next=NULL;//隊列頭結(jié)點為空Q->rear=Q->front;return(1);}else{return(0);}}///////////////////////////////////////////////*離站所進行的操作*/voidPRINT(CarNode*p,introom){intA1,A2,B1,B2;printf("\n請輸入離開的時間：”)；scanf(”%d:%d”,&(p->leave.hour),&(p->leave.min));printf("\n離開車輛的車牌號為：”)；puts(p->num);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+(B2-A2))*price);free(p);}//////////////////////////////////////////////*車輛到達*/intArrival(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("\n車輛在停車場內(nèi)的第％d位置”,Enter->top);printf("\n請輸入到達時間：”)；scanf(”%d:%d”,&(p->reach.hour),&(p->reach.min));Enter->stack[Enter->top]=p;//車輛進棧return(1);}else{printf(-\n該車須在便道等候!”)；t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;//把車輛信息存入隊列的結(jié)點即車輛停在便道t->next=NULL;//t結(jié)點的下一個結(jié)點為空W->front->next=t;//頭指針的下一個為tW->rear=t;//尾指針指向treturn(1);}}//////////////////////////////////////////*出棧*/voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W){inti,room;CarNode*p,*t;QueueNode*q;/*判斷車場內(nèi)是否有車*/if(Enter->top>0){while(1){printf("\n請輸入車在車場的位置：”,Enter->top);scanf("%d”,&room);if(room<1&&room>=Enter->top){break;}while(Enter->top>room){Temp->top++;//top指針加一Temp->stack[Temp->top]=Enter->stack[Enter->top];//^E停車場里的車放入temp中Enter->stack[Enter->top]=NULL;//把停車場里的位置清空Enter->top--;//top指針減一同時}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;//當車出去后原來的車回到停車場Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p,room);//離開停車場的信息if((W->front!=W->rear)&&Enter->top<MAX)〃如果便道上有車，并且停車里有空位{q=W->front->next;//把便道里的車賦給qt=q->data;//車的信息賦給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->stack[Enter->top]=t;//進入停車場printf（"\n便道里沒車\n"）;free（q）;}break;}else{printf（"\n車場里沒車?！保?；}break;}}}//////////////////////////////////////////////////*列表的顯示信息*/voidList1（SeqStackCar*s）{inti;if（s->top>0）{printf（"\n車場”）；printf（"\n位置到達時間車牌號\/）;for（i=1;i<=s->top;i++）{printf（"%d%10d:%d%s\n",i,s->stack[i]->reach.hour,s->stack[i]->reach.min,s->stack[i]->num）;//puts（s->stack[i]->num）;}}elseprintf（"\n車場里沒車”）；}/////////////////////////////////////*便道里的信息*/voidList2（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;}}elseprintf（"\n便道里沒有車。"）;}//////////////////////////////////////////////////////voidList（SeqStackCars,LinkQueueCarw）{intflag,m;flag=1;while（flag）{printf（"\n請選擇123”）;printf（"\n1.車場\n2.便道\n3,返回"）;while（1）{scanf（"%d”,&m）;if（m>=1llm<=3）break;elseprintf（”\n”）;}switch（m）{case1:List1（&s）;break;case2:List2（&w）;break;case3:flag=0;break;default:break;}}}

1.4運行結(jié)果運行程序，打開停車場主菜單，如圖1-3所示。"C:\DocumentsandSettings\e302\^ffi\WANGHAO\main.exe"達開示統(tǒng)到葡顯系車車列退■達開示統(tǒng)到葡顯系車車列退■■■■1234根據(jù)菜單提示，輸入“1”，然后輸入停車車牌“遼A888888”和時間“8:30”，如圖1-4所示。圖1-4輸入停車信息3.程序默認兩個車道，當要求繼續(xù)停車時，就停入便道里，如圖1-5所示。C:\Users\AdminiStrator\Desktop\WANGHAO\main.exe請輸入車牌號：A66666666車輛在停車場內(nèi)的第2位置請JfiiASI達M間：9=40&&&&&&&&&&&&&&&&&&&&&&&&&&請輸入車牌號：A66666666車輛在停車場內(nèi)的第2位置請JfiiASI達M間：9=40&&&&&&&&&&&&&&&&&&&&&&&&&&1.&&&&&&&&&&&&&&&&&&&&&&&&&&2.&&&&&&&&&&&&&&&&&&&&&&&&&&3.&&&&&&&&&&&&&&&&&&&&&&&&&&4.1輛輛表出車車列退忱開示統(tǒng)到離顯系請輸入車牌號：C99999999圖1-5便道停車根據(jù)提示，輸入“3”后，再分別輸入“1”和“2”，輸出車道信息和便道信息，分別如圖1-6和1-7所示。--■1234請選擇1231.車場2.便道退回1車場位置到達時間18:309:40車場位置到達時間18:309:40車牌號A888888計66666666圖1-6車道信息請選擇1231.車場便道退回2等待的車輛的號碼為：C99999999A.ITil2青」A.ITil2青」!.圣場道回

加車屆返圖1-7便道信息返回主菜單后，輸入“2”，然后輸入車離開的位置和時間，便顯示車離開的信息費用以及便道的車進入車道要求輸入信息，如圖1-8所示，完成后便顯示便道車的信息，如圖1-9所示。圖1-8車離開SBC;\User5\Admini5trator\De^ktcip睥&代GHAQXmeinexe高丑蘭鋼散車牌虧片:A888888苴至l|達時間為:8理離開時間為:18:8囪患費用為,28-97L哽道^C9?S9?599號車逮/.卒湯笫2位置匚清輸入現(xiàn)在的時間:18=38譚諂巨沿車件&&&&&&&&&&&&&&&&&&&&&&&&&1-車輛到達2-車輛高無4：凜奈&&&&&&&&&&快&&&&&&&&&&&&&件&&&&&&&&&&&&&&&&&&&&&&&&&1-車輛到達2-車輛高無4：凜奈2關(guān)鍵路徑2.1問題分析關(guān)鍵路徑（CPM）是管理科學中的一個重要方法，廣泛應(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)鍵但是完成整個工程所需的時間取決于從開始點到結(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)時間，表示成e[j]。⑵活動a的最遲開始時間：在不影響整個工程按時完成的前提下，此項活動最遲的必須開始時間，表示成L[i]。只要某活動a有L[i]=e[i]的關(guān)系，就稱a為關(guān)鍵活動。事件j的最遲出現(xiàn)時間：事件j在不延誤整個工程的前提下允許發(fā)生的最遲時間，表示為L[j]。對某條指向頂點V的邊所代表的活動a可得到L[i]=L[j]一（活動a所需時間）。該程序的主要流程圖如圖2-1所示。開始+輸入結(jié)點/數(shù)/輸入活動個數(shù)輸入個相鄰結(jié)點關(guān)系及活動時間查找關(guān)鍵路徑輸出各結(jié)點的開始時間及關(guān)/鍵路徑信息，,????’結(jié)束圖2-1關(guān)鍵路徑主要流程圖2.3核心代碼#include<stdio.h>#include<stdlib.h>#include<iomanip.h>#include<process.h>typedefstructnode{intadjvex;intdut;structnode*next;}edgenode;typedefstruct{intprojectname;intid;edgenode*link;}vexnode;voidCreateGraphic(vexnode*,int,int);intSearchPath(vexnode*,int,int,int&);intmain(){intflag,projectnum,activenum,totaltime=0;printf(-請輸入這個工程的化成圖形的結(jié)點數(shù):”)；scanf("%d”,&projectnum);printf("請輸入這個工程的活動個數(shù):”)；scanf("%d”,&activenum);vexnode*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",totaltime);system("pause");}voidCreateGraphic(vexnode*Graphicmap,intprojectnum,intactivenum)〃倉0建圖的函數(shù){intbegin,end,duttem;edgenode*p;for(inti=0;i<projectnum;i++){Graphicmap[i].projectname=i;Graphicmap[i].id=0;Graphicmap[i].link=NULL;}printf("某項目的開始到結(jié)束在圖中的節(jié)點輸A<vi,vj,dut>\n");printf("如：1,2,3回車表示第1結(jié)點到第2結(jié)點之間的活動用了3個單位時間\n");for(intk=0;k<activenum;k++){scanf("%d,%d,%d”,&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p->adjvex=end-1;p->dut=duttem;Graphicmap[end-1].id++;p->next=Graphicmap[begin-1].link;Graphicmap[begin-1].link=p;}}intSearchPath(vexnode*Graphicmap,intprojectnum,intactivenum,int&totaltime)〃查找關(guān)鍵路徑{inti,j,k,m=0;intfront=-1,rear=-1;int*topologystack=(int*)malloc(projectnum*sizeof(int));//保存拓撲排列int*vl=(int*)malloc(projectnum*sizeof(int));//表示在不推遲整個工程的前提下，Vj允許最遲發(fā)生的時間int*ve=(int*)malloc(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(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link;while(p){k=p->adjvex;Graphicmap[k].id--;if(ve[j]+p->dut>ve[k])ve[k]=ve[j]+p->dut;if(Graphicmap[k].id==0)topologystack[++rear]=k;p=p->next;}}if(m<projectnum){return0;}totaltime=ve[projectnum-1];for(i=0;i<projectnum;i++)vl[i]=totaltime;for(i=projectnum-2;i>=0;i--){j=topologystack[i];p=Graphicmap[j].link;while(p){k=p->adjvex;if((vl[k]-p->dut)<vl[j])vl[j]=vl[k]-p->dut;p=p->next;}}i=0;printf(-起點終點最早開始時間最遲完成時間差值是否為關(guān)鍵活動(*)\n");for(j=0;j<projectnum;j++){p=Graphicmap[j].link;while(p){k=p->adjvex;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("%6d%8d%13d%18d%12d",Graphicmap[j].projectname+1,Graphicmap[k].projectname+1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf("*");printf("\n");p=p->next;}}return1;}2.4運行結(jié)果1.運行該程序，打開如圖2-2所示，并輸入這個工程的化成圖形的結(jié)點數(shù)。圖2-2輸入結(jié)點數(shù)2.根據(jù)上圖提示輸入結(jié)點數(shù)后然后輸入活動個數(shù)，如圖2-3所示。圖2-3輸入結(jié)點數(shù)和活動數(shù)3.根據(jù)圖2-3所示，輸入9個節(jié)點之間的活動關(guān)系和時間，如圖2-4所示。圖2-4輸入結(jié)點的關(guān)系和活動時間4.輸完11個活動后，即顯示該工程關(guān)鍵活動信息，如圖2-5所示。圖2-5關(guān)鍵活動信息3教學計劃安排檢驗程序（拓撲排序）3.1.問題分析針對學院的計算機系本科課程，根據(jù)課程之間的依賴關(guān)系，制定課程安排計劃，并滿足各學期課程數(shù)大致相同。按照用戶輸入的課程數(shù)，學期數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會給出每學期應(yīng)學的課程。（1）輸入的形式和輸入值的范圍：輸入間用空格隔開。要求用戶輸入的課程數(shù)小于20，學期數(shù)小于或是等于8,課程名的長度小于等于10個字符。（2）程序所能達到的功能：按照用戶的輸入，給出每學期應(yīng)學的課程。（3）測試數(shù)據(jù)：輸入：學期數(shù)：5,課程數(shù)：12，課程間的先后關(guān)系數(shù)：16，課程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。課程間兩兩間的先后關(guān)系：v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6輸出：第1學期應(yīng)學的課程：v1v9第2學期應(yīng)學的課程：v2v4v10v11第3學期應(yīng)學的課程：v3v6v12第4學期應(yīng)學的課程：v5v8第5學期應(yīng)學的課程：v73.2數(shù)據(jù)結(jié)構(gòu)與算法分析拓撲排序時有向圖的一種重要運算。在課表排序中，每門課都有多種關(guān)系：先后關(guān)系，即必須在一類門課學完后，才能開始學習另一門課；在一類課之間沒有次序要求，即兩門課可以同時噓唏，互不影響。將AOV網(wǎng)絡(luò)中的各個頂點排列成一個線性有序序列，使得所有要求的前趨、后趨關(guān)系都能得到滿足。在AOV網(wǎng)絡(luò)進行拓撲排序的方法：⑴在網(wǎng)絡(luò)中選擇一個沒有前趨的頂點，并把它輸出；⑵從網(wǎng)絡(luò)中刪去該頂點和從該頂點出發(fā)的所有有向邊；⑶重復執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出。該程序的主要流程圖如圖3-1所示：

圖3-1拓撲排序流程圖3.3核心代碼#include"malloc.h”#include"stdio.h”#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineSTACK_INIT_SIZE100/存儲空間初始分配量#defineSTACKINCREMENT10/存儲空間分配增量#defineMAX_VERTEX_NUM20typedefintStatus;typedefintSElemType;typedefstruct(SElemType*base;/在棧構(gòu)造之前和銷毀之后,base的值為NULLSElemType*top;//棧頂指針intstacksize;〃當前已分配的存儲空間,以元素為單位}SqStack;typedefstructArcNode(intadjvex;//該弧所指向的頂點的位置structArcNode*nextarc;//指向第一條依附該頂點的弧的指針}ArcNode;typedefstructVNode(chardata[10];ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct(AdjListvertices;intvexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù)}ALGraph;intindegree[20]={0};//存儲圖的入度的全局變量數(shù)組StatusInitStack(SqStack&S){〃構(gòu)造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)returnERROR;//內(nèi)存分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(!S.base)returnERROR;//存儲分配失敗*S.top++=e;returnOK;}//PushStatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusStackEmpty(SqStackS){//判斷棧是否為空，為空返回TRUE，否則返回FALSEif(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusCreateDG(ALGraph&G){//建立鄰接表inti,v,w,vex;printf(-請輸入課程數(shù)目(課程數(shù)必須小于20)：”);scanf("%d”,&vex);if(vex>=20){printf("請重新輸入課程數(shù)目(課程數(shù)必須小于20)：”);scanf("%d”,&vex);}G.vexnum=vex;printf(”請輸入課程間的先后關(guān)系數(shù)：”)；scanf("%d”,&Garcnum);printf(”請輸入課程的代表值(課程名的長度小于等于10個字符)：”)；for(i=0;ivGvexnum;i++){printf("\n請輸入第％d門課程名:",i+1);scanf("%s”,&Gvertices[i].data);printf("這門課對應(yīng)的編號是％d”,i+1);G.vertices[i].firstarc=NULL;}〃輸入頂點信息printf(-\n請輸入課程間兩兩間的先后關(guān)系(用對應(yīng)編號表示中間用空格隔開，比如12)：”);for(i=0;ivGarcnum;i++){〃輸入邊的信息scanf("%d%d”,&v,&w);//形式2ArcNode*p=newArcNode;//建立結(jié)點if(!p)returnERROR;p->adjvex=w-1;p->nextarc=G.vertices[v-1].firstarc;//M點v的鏈表G.vertices[v-1].firstarc=p;//添加到最左邊}returnOK;}voidFindInDegree(ALGraphG){//求圖的入度ArcNode*p;for(inti=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){for(intj=0;jvGvexnum;j++)if(p->adjvex==j)indegree[j]++;p=p->nextarc;}}}StatusTopologicalSort(ALGraphG){//拓撲排序//有向圖G采用鄰接表存儲結(jié)構(gòu)SqStackS1,S2;ArcNode*p;inti,count,k;FindInDegree(G);InitStack(S1);InitStack(S2);for(i=0;ivGvexnum;++i)if(!indegree[i])Push(S1,i);//把入度為0的壓入棧S1count=0;〃對輸出頂點計數(shù)while(!StackEmpty(S1)){printf("第％d學期應(yīng)學的課程:",count+1);while(!StackEmpty(S1)){Pop(S1,i);printf("%s”,Gvertices[i].data);//輸出i號頂點Push(S2,i);//把i號頂點壓入棧S2}printf("\n");count++;〃計數(shù)while(!StackEmpty(S2)){Pop(S2,i);for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;〃對i號頂點的每個鄰接點的入度減1if(!(--indegree[k]))//若入度減為0,則入棧Push(S1,k);}}}if(count<G.vexnum)〃該有向圖有回路returnERROR;elsereturnOK;}//TopologicalSortintmain(){ALGraphG;CreateDG(G);TopologicalSort(G);return0;}

3.4運行結(jié)果1.運行程序打開界面如圖3-2所示，并根據(jù)提示，輸入課程數(shù)目。圖3-2圖3-2開始界面2.根據(jù)界面提示，輸入課程見的先后關(guān)系數(shù)及課程代表值，如圖3-3所示。圖3-3輸入課程關(guān)系數(shù)和課程名魅麗視課帕課帕課脂課脂課脂課米塑、圖3-3輸入課程關(guān)系數(shù)和課程名魅麗視課帕課帕課脂課脂課脂課米塑、—Ou-IJIOU-IJIOU-IJION-IJION-IJION-IJ程程程如應(yīng)21'應(yīng)31'應(yīng)41'應(yīng)51'應(yīng)61'課課課第對第對第對第對第對第人入入入課入課入課入課入課入d刖八一刖.d刖-ij--刖『八一刖『八一刖「八一刖「八一刖「八一刖-U#-F#-U#4-#..I4-#..I4-#..I4-#..I4-#..I4-#請請請請這請.這請這請.這請這請回玉日3.根據(jù)界面提示，輸入課程間的先后關(guān)系，如圖3-4所示。圖3-4輸入課程間的先后關(guān)系4.輸入完課程間的先后關(guān)系后，便顯示出5個學期的課程名，如圖3-5所示。圖3-5各個學期的課程4猜數(shù)字游戲4.1問題分析編寫一個猜數(shù)字游戲，有一定的容錯功能，界面友好，功能齊全。游戲規(guī)則：a，一個四位數(shù)，各位上的數(shù)字不重復，從1到9。b，按以下提示猜出這個四位數(shù)。c，每次猜測輸入的數(shù)據(jù)給出類似的提示*A*B。d，其中A前的*代表你本次猜對了多少個數(shù)字。e，其中B前的*代表你本次猜對的數(shù)字并且位置正確的個數(shù)。4.2數(shù)據(jù)結(jié)構(gòu)與算法分析本程序多次利用到了調(diào)用函數(shù)參數(shù)，for循環(huán)等，通過比較輸入的四個數(shù)字和電腦隨機的數(shù)字值大小來判斷猜對的數(shù)字正確與否。4.3核心代碼#include<stdio.h>#include<math.h>#include<stdlib.h>#include<time.h>intRnd（）〃產(chǎn)生十以內(nèi)的隨機整數(shù)。{intRteger;Rteger=rand（）%10;returnRteger;}voidGet_b（intb[]）//得到用戶輸入的四位數(shù)，存儲到數(shù)組b[4]中。{inti,j,m,n=10000;scanf（"%d”,&m）;if（m>9999llm<999）{printf（"輸入錯誤請重新輸入：”）；scanf（"%d”,&m）;}for(i=0;i<=3;i++){b[i]=m/(n/10);m=m-b[i]*(n/10);n=n/10;}for(i=0;i<=3;i++)for(j=0;j<=3;j++)if(b[i]==b[j]&&i!=j){printf("輸入重復請重新輸入");Get_b(b);}}voidIswantplay(char*wantplay)//判斷用戶還想不想玩。{printf("再來一局(y)，我不想玩了(n)");scanf("%c”,wantplay);scanf("%c”,wantplay);printf("==============================\n\n\n”);}voidReset(intA[],intB[],int*score,int*a,int*b)//用來初始化一些變量。{inti=0,t=0,j;(*score)=0;〃得分清零。(*a)=0;(*b)=0;//所猜對的數(shù)字的個數(shù)的計數(shù)器清零for(j=0;j<10;j++)A[j]=j;//初始化數(shù)組，為產(chǎn)生無重復隨機數(shù)做準備。while(i<4){t=Rnd();if(A[t])B[i]=A[t],A[t]=0,i++;}//利用撲克牌中抽牌的思想，來產(chǎn)〃生無重復隨機數(shù)，存儲到B[](在main函數(shù)中為b[])中。printf("輸入一個四位數(shù)開始吧!\n");printf("\n");}voidCheck_ab(inta[],intb[],int*A,int*B)//此函數(shù)用來檢查用戶所輸入的四位數(shù)與系

{〃統(tǒng)產(chǎn)生的四位數(shù)的相同情況。inti,j;for(i=0;i<=3;i++)//用兩個嵌套的for循環(huán)來逐個比較a[]與b[]for（j=0；j<=3;j++）{if（a[i]==b[j]）//如果數(shù)字相同。{if（i==j）（*A）++;if（!（i==j））（*B）{if（a[i]==b[j]）//如果數(shù)字相同。{if（i==j）（*A）++;if（!（i==j））（*B）++;}}}voidWelcome（）//如果位置也相同。//A自加。//如果位置不同。//B自加?！ù蛴〕绦虻拈_始界面。{printf““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個\n"）;printf（"*\n"）;printf（"*\n"）;printf（"*\n"）;printf（"*\n"）;printf=======—===========猜數(shù)字游戲———————programedbywxl（"************************************************************************\n\n\n\n”）;}voidUsage（）〃顯示程序的用法。{printf（"===============用法================================\n"）;printf（-1.計算機隨機產(chǎn)生一個無重復數(shù)字的四位數(shù)由你來猜.\n"）;printf（"2.若所猜的數(shù)位置與數(shù)字均正確，會顯示一個A,若數(shù)字對位置不對，會顯示一個B.\n"）;printf（"==================================================================={switch（n）{case0:printf（"你真是撞大運了!！恭喜!！恭喜!！加十分!\n"）;break;case1:printf（"恭喜你！猜對了！你真是天才！加九分!\n"）;break;case2:printf（"不錯！不錯！猜對了！你真夠聰明！加八分!\n"）;break;case3:printf（"恭喜！猜對了！加七分!\n"）;break;case4:printf（'潴對了！及格.加六分!\n”）;default:printf（"猜對了，但不夠快啊，繼續(xù)努力!\n"）;}printf（"================================\n\n”）;}voidPrintresult（intb[],int*A,int*B）〃顯示每次用戶所猜的結(jié)果，供其思考判斷。{inti;printf（"”）;for（i=0;i<=3;i++）{printf（"%d”,b[i]）;}printf（"”）;for（i=0;i<（*A）;i++）printf（"A"）;for（i=0;i<（*B）;i++）printf（"B"）;printf（"\n"）;}intmain（）{inti=0,a[4],b[4],c[10],A=0,B=0,score=0;charwantplay='y';srand（（unsignedint）time（NULL））;〃初始化隨機數(shù)生成器。Welcome（）;

Usage();while(wantplay=='y'llwantplay=='Y')〃如果還想玩{Reset(c,a,&score,&A,&B);while(A!=4){Get_b(b);Check_ab(a,b,&A,&B);Printresult(b,&A,&B);if(A!=4)A=0,B=0;score++;}Printscore(score/3);Iswantplay(&wantplay);〃初始化變量。//只要還沒猜對，繼續(xù)猜?！ㄝ斎胨碌臄?shù)?！娔X判斷?！ㄝ敵鼋Y(jié)果?！ɡ塾嬘脩艨偣膊碌拇螖?shù)?！ù蛴〉梅帧！ㄟ€要不要玩。1.運行程序，打開主界面，如圖4-1所示。圖4-1主界面〃初始化變量。//只