數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書--- 車廂調(diào)度問題

1、<p><b>　　車廂調(diào)度問題</b></p><p>　　摘要: 實(shí)現(xiàn)棧的基本操作,即實(shí)現(xiàn)類型。程序?qū)５娜魏未嫒?，即更改，讀取和狀態(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ì)算機(jī)科學(xué)與技術(shù)、軟件工程及相關(guān)學(xué)科的專業(yè)基礎(chǔ)課，也是軟件設(shè)計(jì)的技術(shù)基礎(chǔ)。《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)要求之一是訓(xùn)練學(xué)生進(jìn)行復(fù)雜的程序設(shè)計(jì)的技能和培養(yǎng)良好程序設(shè)計(jì)的風(fēng)格，其重要程度決不亞于理論知識的傳授，因此課程設(shè)計(jì)環(huán)節(jié)是一個至關(guān)重要的環(huán)節(jié)，是訓(xùn)練學(xué)生從事工程科技的基本能力，

3、是培養(yǎng)創(chuàng)新意識和創(chuàng)新能力的極為重要的環(huán)節(jié)。基本要求如下：</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è)計(jì) </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è)計(jì)</b></p><p>　　3.1 對算法的簡單描述</p

7、><p>　　這個實(shí)驗(yàn)中, 要求用到棧. 實(shí)現(xiàn)棧的基本操作,即實(shí)現(xiàn)類型。程序?qū)５娜魏未嫒。锤?，讀取和 狀態(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è)計(jì)體會</b></p><p>　　在進(jìn)行課程設(shè)計(jì)的過程中,先把問題具體化,再進(jìn)行編程.車廂調(diào)度問題是個很老的問題,它的難點(diǎn)在于車廂進(jìn)棧出棧的遞歸算法.經(jīng)過這次課程設(shè)計(jì),我加深了對棧的操作的熟練程度,對遞歸有了更深刻的理解,遞歸算法有點(diǎn)難度.</p><p><b>　　6.結(jié)束語</b></p><p>　　課程設(shè)計(jì)終于完