數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書

1、武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書車廂調(diào)度問題摘要：實現(xiàn)棧的基本操作，即實現(xiàn)類型。程序?qū)５娜魏未嫒。锤?，讀取和狀態(tài)判別等操作，必須借助于基本操作。在操作過程中的任何狀態(tài)下都有兩種可能的操作：“入”“出”。每個狀態(tài)下處理問題的方法都是相同的，具有遞歸特性。關(guān)鍵字:棧遞歸打印數(shù)據(jù)結(jié)構(gòu)是電腦科學(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é)生從事工程科技的基本能力，是培養(yǎng)創(chuàng)新意識和創(chuàng)新能力的極為重要的環(huán)節(jié)?；疽?/p>

2、求如下：(1)熟練掌握基本的數(shù)據(jù)結(jié)構(gòu)；(2)熟練掌握各種算法；(3)運用高級語言編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序。1 .需求分析(1)這個實驗要求我用棧實現(xiàn)車廂調(diào)度.車廂的個數(shù)是由用戶輸入的.程序會自動給車廂進(jìn)行從1到n的編號.(4)用戶輸入車廂個數(shù)后,程序打印出所有可能的車廂出站順序.2 .數(shù)據(jù)結(jié)構(gòu)設(shè)計在這個程序中存儲結(jié)構(gòu)是棧，對于棧的聲明和定義如下：typedefstructSqStackint*top;/*棧頂指針*/int*base;/*/intstacksize;/*當(dāng)前分配的存儲空間*/SqStack;/*順序棧的結(jié)構(gòu)體聲明和定義*/3 .算法設(shè)計3.1 對算法的簡單描述這個實驗中，要

3、求用到棧.實現(xiàn)棧的基本操作，即實現(xiàn)類型。程序?qū)５娜魏未嫒〖锤?，讀取和狀態(tài)判別等操作必須借助于基本操作。在操作過程中的任何狀態(tài)下都有兩種可能的操作：“入”“出每個狀態(tài)下處理問題的方法都是相同的，具有遞歸特性。棧實現(xiàn)是方便的無論如何調(diào)度，我們的操作都是入棧和出棧，設(shè)定入棧為1,出棧為-1,對n列車廂有2n次這樣的操作，例如n=4,則有操作1111-1-1-1-1、1-11-11-11-1等.所以還要構(gòu)造一個操作命令隊列trainlist口。在算法中還要用到遞歸算法，其本質(zhì)為：一個數(shù)的進(jìn)棧以后有兩種處理方式：要么立刻出棧，或者下一個數(shù)的進(jìn)棧。一個數(shù)的出棧以后也有兩種處理方式：要么繼續(xù)出棧棧不為空

4、，或者下一個數(shù)的入棧。.1構(gòu)造一個棧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;/*構(gòu)造一個空棧*/插入新的棧頂元素voidPush2(SqStack*S,inte)*(S->top+尸e;/*插入元素e為新的棧頂元素*/輸出棧頂元素voidPop2(SqStack*S)inte;

5、if(S->top=S->base)puts("ERROR");return;e=*-S>top；printf("%d",e);/*假設(shè)棧不空，則刪除s的棧頂元素，用e返回其值*/3.3輸入車廂數(shù)弁給車廂編號printf("pleaseinputthenumberofthetrains:");scanf("%d”,&trainsize);if(trainsize<=0|trainsize>=33)puts("thenumberiswrong!");return;for

6、(i=0;i<trainsize;i+)trainsourcei=i+1;/*給火車貼上從1到trainsize的編號*/4程序?qū)崿F(xiàn)4.1源代碼#include<stdio.h>#include<stdlib.h>typedefstructSqStackint*top;int*base;intstacksize;SqStack;structSqStackstack;/*定義一個棧變量*/inttrainsize;/*車廂個數(shù)*/inttrainsource33;/*車廂數(shù)組*/voidShow(intlist_in);/*打印*/voidSchedule(intl

7、ist_in口,intsource_num,intlist_num);/*對第source_num號車廂進(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

8、;if(S->top=S->base)puts("");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<

9、trainsize;i+)trainsourcei=i+1;Schedule(trainlist,1,0);voidSchedule(intlist_in口,intsource_num,intlist_num)/*對當(dāng)前第source_num號車廂的處理用到了遞歸*/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+train

10、listi;if(sum!=0)trainlistlist_num=1;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

11、;i<trainsize*2;i+)judge=judge+trainlisti;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);v

12、oidShow(intlist_in口)/*輸出可能的車廂序列*/inti,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();4.2運行結(jié)果lx受C;Win-TCproiectscNddZ.eKCpleaseInputtheriLimheHafthetFAins：4,運行結(jié)果如下：WC:Win-TCpro)ectscKdd2,eMeS34224331143322 貳laP43T-32 2222 lullinput 22413414434141143422nunkier- ofthe trains：4不足之處在于對車廂個數(shù)進(jìn)行了限制，車廂數(shù)越小越穩(wěn)定.還有就是一次只能對一組車廂進(jìn)行調(diào)度.5 .設(shè)計體會在進(jìn)行課程設(shè)計的過程中，先把問題具體化