車廂調(diào)度問題

1、目錄1）基本要求：12）課程設(shè)計(jì)論文編寫要求13）課程設(shè)計(jì)評分標(biāo)準(zhǔn)：14）參考文獻(xiàn)：25）課程設(shè)計(jì)進(jìn)度安排26）課程設(shè)計(jì)題目具體要求：21 .需求分析22 .概要設(shè)計(jì)23 .詳細(xì)設(shè)計(jì)3-54 .編碼實(shí)現(xiàn)6-105 .調(diào)試分析10-116 .課設(shè)總結(jié)11-12隼柬央通土號(hào)課程設(shè)計(jì)（論文）任務(wù)書軟件學(xué)院學(xué)院軟件+電氣專業(yè)2010班一、課程設(shè)計(jì)（論文）題目課程設(shè)計(jì)（論文）工作自2011年12月26日起至2011年12月30日止三、課程設(shè)計(jì)（論文）地點(diǎn)：創(chuàng)新大樓機(jī)房四、課程設(shè)計(jì)（論文）內(nèi)容要求：1 .本課程設(shè)計(jì)的目的訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí),編寫程序求解

2、指定問題；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能;提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力，鞏固、深化學(xué)生2 .課程設(shè)計(jì)的任務(wù)及要求1）基本要求：要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編寫上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的報(bào)告；在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率；程序設(shè)計(jì)語言推薦使用C/C+,程序書寫規(guī)范，源程序需加必要的注釋；每位同學(xué)需提交可獨(dú)立運(yùn)行的程序和規(guī)范的課程設(shè)計(jì)報(bào)告。2）課程設(shè)計(jì)論文編寫要求理論設(shè)計(jì)部分以課程設(shè)計(jì)論文的形式提交，格式必須按照課程設(shè)計(jì)論

3、文標(biāo)準(zhǔn)格式進(jìn)行書寫和裝訂；課程設(shè)計(jì)報(bào)告（論文）包括中文目錄、設(shè)計(jì)任務(wù)、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼實(shí)現(xiàn)、調(diào)試分析、課設(shè)總結(jié)、謝辭、參考文獻(xiàn)、附錄等；設(shè)計(jì)部分應(yīng)包含系統(tǒng)功能模塊圖，調(diào)試分析應(yīng)包括運(yùn)行截圖等。3）課程設(shè)計(jì)評分標(biāo)準(zhǔn)：學(xué)習(xí)態(tài)度：10分；編程調(diào)試：20分；回答問題：20論文撰寫：30分。4）參考文獻(xiàn):嚴(yán)蔚敏，吳偉民.數(shù)據(jù)Z勾（C語言版）M.清華大學(xué)出版社.2010.3嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)本題集（C語言版）M.清華大學(xué)出版社.1999.2何欽銘，馮燕等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M.浙江大學(xué)出版社.2007.85）課程設(shè)計(jì)進(jìn)度安排準(zhǔn)備階段（4學(xué)時(shí)）：選擇設(shè)計(jì)題目、了解設(shè)計(jì)目的要求、查閱相關(guān)資

4、料；程序模塊設(shè)計(jì)分析階段（4學(xué)時(shí)）：程序概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)；代碼編寫調(diào)試階段（8學(xué)時(shí)）：程序模塊代碼編寫、調(diào)試、測試；撰寫論文階段（4學(xué)時(shí)）：總結(jié)課程設(shè)計(jì)任務(wù)和設(shè)計(jì)內(nèi)容，撰寫課程設(shè)計(jì)論文。學(xué)生簽名：2011年12月26日6）課程設(shè)計(jì)題目具體要求：1需求分析（1）這個(gè)實(shí)驗(yàn)要求我用棧實(shí)現(xiàn)車廂調(diào)度.車廂的個(gè)數(shù)是由用戶輸入的.程序會(huì)自動(dòng)給車廂進(jìn)行從1到n的編號(hào).（4）用戶輸入車廂個(gè)數(shù)后，程序打印出所有可能的車廂出站順序2概要設(shè)計(jì)（1）菜單顯示voidmessage（）主要功能就是顯示主菜單：1：輸入火車的長度2:輸出所有可能序列3:演示一個(gè)序列變化4:退出本程序(2)調(diào)度過程voidAttemper(

5、intpos,intpath,intcur)入棧時(shí)，輸入一個(gè)數(shù)i,判斷是否小于n(全局變量)，如果小于n,則一個(gè)數(shù)進(jìn)棧后，要么立刻出棧，要么進(jìn)行下一個(gè)數(shù)的進(jìn)棧；同樣，出棧時(shí)，首先判斷棧是否為空，如果不為空，則一個(gè)數(shù)出棧后，要么繼續(xù)出棧(棧不空),要么繼續(xù)下一個(gè)數(shù)的進(jìn)棧。每個(gè)數(shù)根據(jù)以上的兩種出棧入、棧選擇，將產(chǎn)生所有可能的車廂序列，然后在運(yùn)用一個(gè)二維數(shù)組，把每種序列保存在二維數(shù)組里。(2)序列輸出voidPrint()根據(jù)棧的特性輸出所有可能長度為n的車廂序列。(3)變化過程voidDisplayOnly(intk,intOutput,intInput)實(shí)現(xiàn)對于每個(gè)輸出序列印出操作序列或狀態(tài)變化

6、過程。運(yùn)行程序時(shí)，輸入一個(gè)序列號(hào)，然后按一下回車鍵，就會(huì)顯示與序列號(hào)相對應(yīng)的車廂序列，然后每按一次回車，就有一次變化，直到演化完畢為止。(4)顯示操作序列的狀態(tài)的變化過程voidDisplayOnly(intk,intOutput,intInput)在運(yùn)行程序時(shí)顯示操作序列的狀態(tài)的變化主函數(shù)main()inputNumber()Attemrer()DisplayonlPrintf()變數(shù)化組顯輸不3出Chopathosepsy()exit3詳細(xì)設(shè)計(jì)對算法的簡單描述這個(gè)實(shí)驗(yàn)中，要求用到棧.實(shí)現(xiàn)棧的基本操作，即實(shí)現(xiàn)類型。程序?qū)５娜魏未嫒?即更改，讀取和狀態(tài)判別等操作)必須借助于基本操作。在操作過

7、程中的任何狀態(tài)下都有兩種可能的操作：“入”“出每個(gè)狀態(tài)下處理問題的方法都是相同的，具有遞歸特性。棧實(shí)現(xiàn)是方便的無論如何調(diào)度，我們的操作都是入棧和出棧，設(shè)定入棧為1,出棧為-1,對n列車廂有2n次這樣的操作，例如n=4,則有操作1111-1-1-1-1、1-11-11-11-1等.所以還要構(gòu)造一個(gè)操作命令隊(duì)列trainlist口。在算法中還要用到遞歸算法，其本質(zhì)為：一個(gè)數(shù)的進(jìn)棧以后有兩種處理方式：要么立刻出棧，或者下一個(gè)數(shù)的進(jìn)棧。一個(gè)數(shù)的出棧以后也有兩種處理方式：要么繼續(xù)出棧(棧不為空)，或者下一個(gè)數(shù)的入棧。棧的基本操作構(gòu)造一個(gè)棧voidInitStack2(SqStack*S,intbase_

8、size)(S->base=(int*)malloc(base_size*sizeof(int);if(!S->base)(puts("ERROR!");return;S->top=S->base;S->stacksize=base_size;/*構(gòu)造一個(gè)空棧*/插入新的棧頂元素voidPush2(SqStack*S,inte)(*(S->top+)=e;/*插入元素e為新的棧頂元素*/輸出棧頂元素voidPop2(SqStack*S)(inte;if(S->top=S->base)(puts("ERROR"

9、;);return;e=*-S->top;printf("%d",e);/*若棧不空，則刪除s的棧頂元素，用e返回其值*/輸入車廂數(shù)并給車廂編號(hào)printf("pleaseinputthenumberofthetrains:");scanf("%d”,&trainsize);if(trainsize<=0|trainsize>=33)(puts("thenumberiswrong!");return;for(i=0;i<trainsize;i+)trainsourcei=i+1;/*給火車貼上

10、從1到trainsize的編號(hào)*/4編碼實(shí)現(xiàn)源代碼#include<stdio.h>#include<stdlib.h>typedefstructSqStack(int*top;int*base;intstacksize;SqStack;structSqStackstack;/*定義一個(gè)棧變量*/inttrainsize;/*車廂個(gè)數(shù)*/inttrainsource33;/*車廂數(shù)組*/list_num);voidShow(intlist_in);/*打印*/voidSchedule(intlist_in口,intsource_num,int/*對第source_num

11、號(hào)車廂進(jìn)行處理*/voidInitStack2(SqStack*S,intbase_size)(S->base=(int*)malloc(base_size*sizeof(int);if(!S->base)(puts("ERROR!");return;S->top=S->base;S->stacksize=base_size;)voidPush2(SqStack*S,inte)(*(S->top+)=e;)voidPop2(SqStack*S)(inte;if(S->top=S->base)(puts(""

12、);return;)e=*-S->top;printf("%d",e);)voidTrainSchedule()(inti;inttrainlist66;printf("pleaseinputthenumberofthetrains:");scanf("%d”,&trainsize);if(trainsize<=0|trainsize>=33)(puts("WRONGLENGTH!");return;)for(i=0;i<trainsize;i+)trainsourcei=i+1;Schedu

13、le(trainlist,1,0);)voidSchedule(intlist_in,intsource_num,intlist_num)/*對當(dāng)前第source_num號(hào)車廂的處理用到了遞歸*/inti;intsum=0;intjudge;inttrainlist50;if(source_num>trainsize)return;for(i=0;i<50;i+)trainlisti=-1;for(i=0;i<=list_num-1;i+)trainlisti=list_ini;sum=sum+trainlisti;)if(sum!=0)trainlistlist_num=1

14、;Schedule(trainlist,source_num+1,list_num+1)/*對下一車廂進(jìn)行處理*/for(i=0,judge=0;i<trainsize*2;i+)judge=judge+trainlisti;if(source_num=trainsize&&judge=0)Show(trainlist);/*打印出可能的列車序列*/trainlistlist_num=-1;Schedule(trainlist,source_num,list_num+1);for(i=0,judge=0;i<trainsize*2;i+)judge=judge+tr

15、ainlisti;if(source_num=trainsize&&judge=0)Show(trainlist);/*打印出可能的列車序列*/elsetrainlistlist_num=1;Schedule(trainlist,source_num+1,list_num+1);for(i=0,judge=0;i<trainsize*2;i+)judge=judge+trainlisti;if(source_num=trainsize&&judge=0)Show(trainlist);voidShow(intlist_in)/*輸出可能的車廂序列*/int

16、i,cur=0;intlength;SqStackstack;InitStack2(&stack,trainsize);length=trainsize*2;for(i=0;i<length;i+)if(list_ini=1)Push2(&stack,trainsourcecur+);elseif(list_ini=-1)Pop2(&stack);elseputs("error!");)puts("");)intmain()(TrainSchedule();getchar();getchar();)5調(diào)試分析1 .此車廂調(diào)度

17、的基本要求比較簡單，只要掌握好棧的基本特性和基本操作，一般都能順利完成。2 .此系統(tǒng)需要運(yùn)用遞歸算法，所以還必須對整個(gè)系統(tǒng)有個(gè)清晰的認(rèn)識(shí)和思路，這樣才能更好的掌握運(yùn)行的詳細(xì)過程與結(jié)果。每個(gè)步驟都有兩種可能，那怎樣解決操作問題呢？我決定先以入棧為主，能入先入，操作完畢后恢復(fù)至分步時(shí)的狀態(tài)，再進(jìn)行出棧的操作，這樣兩種可能就都完成了。3 .此系統(tǒng)中還有一個(gè)要求就是顯示出操出作序列的狀態(tài)的變化過程，因此，必須弄清楚棧的基本性質(zhì)，誰先入棧，誰先出棧，每一步的過程必須清晰明了。4 .數(shù)據(jù)存儲(chǔ)是用了一個(gè)數(shù)組，便于存儲(chǔ)。運(yùn)行結(jié)果而C:Win-TCprojjiectscHdd2.eKepleaseinputth

18、enumberoFthetrains=運(yùn)行結(jié)果如下:u：*C:Win-TCprojectscKdd2*eKeP43332222211111eS34224331143322aeinputtheniinhei'ofthetrains：411141143422434不足之處在于對車廂個(gè)數(shù)進(jìn)行了限制，車廂數(shù)越小越穩(wěn)定.還有就是一次只能對一組車廂進(jìn)行調(diào)度.課設(shè)總結(jié)：經(jīng)過三天的課程設(shè)計(jì)課，感觸頗深。這段時(shí)間，自己對于這學(xué)期的數(shù)據(jù)結(jié)構(gòu)理解的更加透徹。以前對于抽象的棧的運(yùn)用不是很明了，現(xiàn)在最起碼已經(jīng)會(huì)編寫一些簡單的源代碼。比如棧的長度，初始化，刪除，入棧和出棧等基本操作與基本特性，通過此次的課程設(shè)計(jì)，從原先的理論運(yùn)用到現(xiàn)實(shí)的實(shí)踐中，加深了對棧的理解?？傮w來說棧