版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、<p><b> 車廂調(diào)度問題</b></p><p> 摘要: 實(shí)現(xiàn)棧的基本操作,即實(shí)現(xiàn)類型。程序?qū)5娜魏未嫒?,即更改,讀取和狀態(tài)判別等操作,必須借助于基本操作。在操作過程中的任何狀態(tài)下都有兩種可</p><p> 能的操作:“入”“出”。 每個狀態(tài)下處理問題的方法都是相同的,具有遞歸特性 。</p><p> 關(guān)鍵字:棧
2、 遞歸 打印 </p><p><b> 0.引言</b></p><p> 《數(shù)據(jù)結(jié)構(gòu)》是計算機(jī)科學(xué)與技術(shù)、軟件工程及相關(guān)學(xué)科的專業(yè)基礎(chǔ)課,也是軟件設(shè)計的技術(shù)基礎(chǔ)?!稊?shù)據(jù)結(jié)構(gòu)》課程的教學(xué)要求之一是訓(xùn)練學(xué)生進(jìn)行復(fù)雜的程序設(shè)計的技能和培養(yǎng)良好程序設(shè)計的風(fēng)格,其重要程度決不亞于理論知識的傳授,因此課程設(shè)計環(huán)節(jié)是一個至關(guān)重要的環(huán)節(jié),是訓(xùn)練學(xué)生從事工程科技的基本能力,
3、是培養(yǎng)創(chuàng)新意識和創(chuàng)新能力的極為重要的環(huán)節(jié)?;疽笕缦拢?lt;/p><p> (1) 熟練掌握基本的數(shù)據(jù)結(jié)構(gòu);</p><p> (2) 熟練掌握各種算法;</p><p> (3) 運(yùn)用高級語言編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序。</p><p><b> 1.需求分析</b></p><p>
4、 (1)這個實(shí)驗(yàn)要求我用棧實(shí)現(xiàn)車廂調(diào)度.</p><p> (2)車廂的個數(shù)是由用戶輸入的.</p><p> (3)程序會自動給車廂進(jìn)行從1到 n的編號.</p><p> (4)用戶輸入車廂個數(shù)后,程序打印出所有可能的車廂出站順序.</p><p><b> 2.數(shù)據(jù)結(jié)構(gòu)設(shè)計 </b></p>
5、<p> 在這個程序中存儲結(jié)構(gòu)是棧,對于棧的聲明和定義如下:</p><p> typedef struct SqStack </p><p><b> { </b></p><p> int *top; /*棧頂指針*/ </p><p> int *base; /*在
6、棧構(gòu)造之前和銷毀之后.base的值為NULL*/ </p><p> int stacksize; /*當(dāng)前分配的存儲空間*/ </p><p> }SqStack; /*順序棧的結(jié)構(gòu)體聲明和定義*/</p><p><b> 3.算法設(shè)計</b></p><p> 3.1 對算法的簡單描述</p
7、><p> 這個實(shí)驗(yàn)中, 要求用到棧. 實(shí)現(xiàn)棧的基本操作,即實(shí)現(xiàn)類型。程序?qū)5娜魏未嫒。锤模x取和 狀態(tài)判別等操作)必須借助于基本操作。在操作過程中的任何狀態(tài)下都有兩種可能的操作:“入”“出”。 每個狀態(tài)下處理問題的方法都是相同的,具有遞歸特性 。棧實(shí)現(xiàn)是方便的</p><p> 無論如何調(diào)度,我們的操作都是入棧和出棧,設(shè)定入棧為1,出棧為-1,對n列車 廂有2n次這樣的操作,例
8、如n=4,則有操作1111-1-1-1-1、1-11-11-11-1等.所以還要構(gòu)造一個操作命令隊(duì)列trainlist[]。</p><p> 在算法中還要用到遞歸算法,其本質(zhì)為:</p><p> 一個數(shù)的進(jìn)棧以后 有兩種處理方式: 要么立刻出棧,或者下一個數(shù)的進(jìn)棧。 </p><p> 一個數(shù)的出棧以后 也有兩種處理方式:要么繼續(xù)出棧(棧不
9、為空),或者下一個數(shù)的入棧。</p><p><b> 3.2棧的基本操作</b></p><p> 3.2.1構(gòu)造一個棧</p><p> void InitStack2(SqStack *S,int base_size) </p><p><b> { </b><
10、;/p><p> S->base=(int *)malloc(base_size * sizeof(int)); </p><p> if(!S->base) </p><p><b> { </b></p><p> puts("ERROR!"); <
11、;/p><p> return ; </p><p><b> } </b></p><p> S->top=S->base; </p><p> S->stacksize=base_size; </p><p> } /*構(gòu)造一個空棧*/ </p
12、><p> 3.2.2 插入新的棧頂元素</p><p> void Push2(SqStack *S, int e) </p><p><b> { </b></p><p> *(S->top++)=e; </p><p> } /*插入元素e為新的
13、棧頂元素*/</p><p> 3.2.3 輸出棧頂元素</p><p> void Pop2(SqStack *S) </p><p><b> { </b></p><p> int e; </p><p> if(S->top==S->base)
14、 </p><p><b> { </b></p><p> puts("ERROR"); </p><p> return ; </p><p><b> } </b></p><p> e=*--S->top;
15、 </p><p> printf("%d ",e); </p><p> } /*若棧不空,則刪除s的棧頂元素,用e返回其值*/</p><p> 3.3 輸入車廂數(shù)并給車廂編號</p><p> printf("please input the number of the trains:
16、"); </p><p> scanf("%d",&trainsize); </p><p> if(trainsize<=0 || trainsize>=33) </p><p><b> { </b></p><p> puts(&qu
17、ot;the number is wrong!"); </p><p> return; </p><p><b> } </b></p><p> for(i=0;i < trainsize;i++) </p><p> trainsource[i]=i+1; /*給
18、火車貼上從1到trainsize的編號*/</p><p><b> 4 程序?qū)崿F(xiàn)</b></p><p><b> 4.1 源代碼</b></p><p> #include <stdio.h> </p><p> #include <stdlib.h>
19、 </p><p> typedef struct SqStack </p><p><b> {</b></p><p> int *top; </p><p> int *base; </p><p> int stacksize; </
20、p><p> }SqStack; </p><p> struct SqStack stack; /*定義一個棧變量*/ </p><p> int trainsize; /*車廂個數(shù)*/ </p><p> int trainsource[33]; /*車廂數(shù)組*/ </p><p>
21、 void Show(int list_in[]);/*打印*/ </p><p> void Schedule(int list_in[],int source_num,int list_num); /*對第source_num 號車廂進(jìn)行處理*/ </p><p> void InitStack2(SqStack *S,int
22、 base_size) </p><p><b> { </b></p><p> S->base=(int *)malloc(base_size * sizeof(int)); </p><p> if(!S->base) </p><p><b> {
23、</b></p><p> puts("ERROR!"); </p><p> return ; </p><p><b> } </b></p><p> S->top=S->base; </p><p> S->s
24、tacksize=base_size; </p><p><b> } </b></p><p> void Push2(SqStack *S, int e) </p><p><b> { </b></p><p> *(S->top++)=e;
25、</p><p><b> } </b></p><p> void Pop2(SqStack *S) </p><p><b> { </b></p><p> int e; </p><p> if(S->top==S->
26、base) </p><p><b> { </b></p><p> puts(""); </p><p> return ; </p><p><b> } </b></p><p> e=*--S->top;
27、 </p><p> printf("%d ",e); </p><p><b> } </b></p><p> void TrainSchedule() </p><p><b> { </b></p><p> i
28、nt i; </p><p> int trainlist[66]; </p><p> printf("please input the number of the trains:");</p><p> scanf("%d",&trainsize); </p><p&g
29、t; if(trainsize<=0 || trainsize>=33) </p><p><b> { </b></p><p> puts("WRONG LENGTH!"); </p><p> return; </p><p><b> }
30、 </b></p><p> for(i=0;i < trainsize;i++) </p><p> trainsource[i]=i+1; </p><p> Schedule(trainlist,1,0); </p><p><b> } </b></p&
31、gt;<p> void Schedule(int list_in[],int source_num,int list_num) /*對當(dāng)前第source_num號車廂的處理用到了遞歸*/ </p><p><b> { </b></p><p>
32、 int i; </p><p> int sum=0; </p><p> int judge; </p><p> int trainlist[50]; </p><p> if(source_num > trainsize) </p><p> ret
33、urn; </p><p> for(i=0;i<50;i++) </p><p> trainlist[i]=-1; </p><p> for(i=0;i<=list_num-1; i++)</p><p><b> { </b></p><p> tra
34、inlist[i]=list_in[i]; </p><p> sum=sum+trainlist[i];</p><p><b> } </b></p><p> if(sum != 0) </p><p><b> { </b></p><p&
35、gt; trainlist[list_num]=1; </p><p> Schedule(trainlist,source_num+1,list_num+1);/*對下一車廂進(jìn)行處理*/</p><p> for(i=0,judge=0;i<trainsize*2;i++) </p><p> judge=judge+trainlist[i]
36、; </p><p> if(source_num == trainsize && judge == 0) </p><p> Show(trainlist); /*打印出可能的列車序列*/ </p><p> trainlist[list_num]=-1; </p><p> S
37、chedule(trainlist,source_num,list_num+1); </p><p> for(i=0,judge=0;i<trainsize*2;i++) </p><p> judge=judge+trainlist[i]; </p><p> if(source_num == trainsize &&
38、amp; judge == 0) </p><p> Show(trainlist); /*打印出可能的列車序列*/ </p><p><b> } </b></p><p><b> else </b></p><p><b> { </b&g
39、t;</p><p> trainlist[list_num]=1; </p><p> Schedule(trainlist,source_num+1,list_num+1); </p><p> for(i=0,judge=0;i<trainsize*2;i++) </p><p> judge=judge+tr
40、ainlist[i]; </p><p> if(source_num == trainsize && judge == 0) </p><p> Show(trainlist); </p><p><b> } </b></p><p><b>
41、 } </b></p><p> void Show(int list_in[]) /*輸出可能的車廂序列*/ </p><p><b> { </b></p><p> int i,cur=0; </p><p> int length; </p>&
42、lt;p> SqStack stack; </p><p> InitStack2(&stack,trainsize); </p><p> length=trainsize*2; </p><p> for(i=0;i<length;i++) </p><p><b> { &
43、lt;/b></p><p> if(list_in[i]==1) </p><p> Push2(&stack,trainsource[cur++]); </p><p> else if(list_in[i]==-1) </p><p> Pop2(&stack); </p>
44、<p><b> else </b></p><p> puts("error!"); </p><p><b> } </b></p><p> puts(""); </p><p><b> } <
45、/b></p><p> int main() </p><p><b> { </b></p><p> TrainSchedule(); </p><p> getchar();</p><p> getchar();</p><p>&
46、lt;b> } </b></p><p><b> 4.2 運(yùn)行結(jié)果 </b></p><p><b> 運(yùn)行結(jié)果如下:</b></p><p> 不足之處在于對車廂個數(shù)進(jìn)行了限制,車廂數(shù)越小越穩(wěn)定.還有就是一次只能對一組車廂進(jìn)行調(diào)度.</p><p><b>
47、 5.設(shè)計體會</b></p><p> 在進(jìn)行課程設(shè)計的過程中,先把問題具體化,再進(jìn)行編程.車廂調(diào)度問題是個很老的問題,它的難點(diǎn)在于車廂進(jìn)棧出棧的遞歸算法.經(jīng)過這次課程設(shè)計,我加深了對棧的操作的熟練程度,對遞歸有了更深刻的理解,遞歸算法有點(diǎn)難度.</p><p><b> 6.結(jié)束語</b></p><p> 課程設(shè)計終于完
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---車廂調(diào)度
- 排序算法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書
- 排序算法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書
- 教學(xué)計劃編制問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書--進(jìn)制轉(zhuǎn)換的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書(全國交通咨詢模擬系統(tǒng))
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書(全國交通咨詢模擬系統(tǒng))
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計說明書--貪吃蛇的循環(huán)隊(duì)列實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(迷宮問題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)迷宮問題課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計—迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---迷宮問題
- 課程設(shè)計——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(八皇后問題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮問題課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--二路歸并排序說明書
評論
0/150
提交評論