車廂調(diào)度問題-課程設(shè)計報告

1、山東交通學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計車廂調(diào)度問題院（系）別信息工程系班級計算133學(xué)號130811341姓名閆琛指導(dǎo)教師王成時間2015-03-092015-03-20課程設(shè)計任務(wù)書題目車廂調(diào)度問題系（部）信息科學(xué)與電氣工程學(xué)院專業(yè)計算機(jī)科學(xué)與技術(shù)班級計算133學(xué)生姓名閆琛學(xué)號1308113412月9日至2月20日共2周指導(dǎo)教師（簽字）系主任（簽字）成績評定表作品成績報告成績口試（答辯）成績總評成績課程設(shè)計概述錯誤！未定義書簽。車廂調(diào)度問題功能概述錯誤！未定義書簽。車廂調(diào)度問題總體設(shè)計錯誤！未定義書簽。全局變量定義錯誤！未定義書簽。棧的定義錯誤！未定義書簽。.算法設(shè)計2用到的進(jìn)出棧算法基礎(chǔ)知識錯誤！未

2、定義書簽。程序分析錯誤！未定義書簽。核心算法4.主程序描述5.程序?qū)崿F(xiàn)5.運行界面5.不足之處7.設(shè)計體會7.結(jié)束語.8.車廂調(diào)度問題摘要：通過輸入車廂系列的編號n,求出所有可能由此輸出的長度為n的車廂系列，用入棧出棧的方法，實現(xiàn)車廂調(diào)度，并演示每一種出棧序列的過程。任務(wù)：假設(shè)停在鐵路調(diào)度站入口處的車廂系列的編號依次為1,2,3,-no設(shè)計一個程序，求出所有可能由此輸出的長度為n的車廂系列。關(guān)鍵字：車廂，調(diào)度，棧，遞歸0.引言隨著人民生活水平的提高，越來越多的人坐火車出去旅游，這也讓火車車廂的量大量增大，也隨之出現(xiàn)了一個問題，即合理的調(diào)度車廂，本課程設(shè)計即利用數(shù)據(jù)結(jié)構(gòu)里的棧的知識，設(shè)計一個合理

3、的算法，來解決此問題。.需求分析假設(shè)停在鐵路調(diào)度站入口處白車廂序列的編號依次為1,2,3,，n,設(shè)計一個程序，求出所有可能的長度為n的車廂序列。實現(xiàn)棧的順序存儲結(jié)構(gòu)SqStack之上實現(xiàn)棧的基本操作，即實現(xiàn)棧類型。程序?qū)５幕静僮鞅仨毥柚诨静僮鬟M(jìn)行。測試數(shù)據(jù)取n=3,4,程序輸出的結(jié)果應(yīng)該在屏幕上顯示出來。.數(shù)據(jù)結(jié)構(gòu)設(shè)計全局變量定義typedefintSElemType;typedefintStatus;intend;/*最后一個車廂的號碼*/longtotal=0;/*總的組合方案數(shù)目*/棧的定義typedefstructstacklistvoidStack_init(SqStack*

4、s)voidStack_Push(SqStack*s,SElemTypee)SElemTypeStack_Pop(SqStack*s)StatusStack_Empty(SqStack*s)StatusStack_Full(SqStack*s)voidStack_printreverse(SqStacks).算法設(shè)計用到的進(jìn)出棧算法基礎(chǔ)知識（1）根據(jù)要求，了解可能要用到的算法：進(jìn)棧（PUSH算法若TO田n時，則給出溢出信息，作出錯處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出;不滿則作）；置TOP=TOP+1棧指針加1,指向進(jìn)棧地址）；S（TOP）=X結(jié)束（X為新進(jìn)棧的元素）；退棧（POP算法若TO

5、PC0,則給出下溢信息，作出錯處理（退棧前先檢查是否已為空棧，空則下溢;不空則作）；X=S（SOP）（退棧后的元素賦給X）;TOP=TOP-1結(jié)束（棧指針減1,指向棧頂）。程序分析.棧的數(shù)據(jù)結(jié)構(gòu)typedefstructstacklistSElemType*base;SElemType*top;intstacksize;SqStack;voidStack_init(SqStack*s)s->base=(SElemType*)malloc(end*sizeof(int);if(!s->base)exit(0);s->top=s->base;s->stacksize=

6、end;voidStack_Push(SqStack*s,SElemTypee)*(s->top)+=e;SElemTypeStack_Pop(SqStack*s)if(s->top=s->base)return0;return*(-(s->top);StatusStack_Empty(SqStack*s)if(s->top=s->base)return1;return0;StatusStack_Full(SqStack*s)if(s->top-s->base=end)return1;return0;)voidStack_printreverse

7、(SqStacks)(int*po;po=s.base;printf("%ld:",total);for(;po!=s.top;)printf("%d",*po+);printf("n");)核心算法voidsearch(SqStack*inputPoint,SqStack*tempPoint,SqStack*outputPoint)(if(!Stack_Empty(inputPoint)(Stack_Push(tempPoint,Stack_Pop(inputPoint);search(inputPoint,tempPoint,ou

8、tputPoint);Stack_Push(inputPoint,Stack_Pop(tempPoint);)if(!Stack_Empty(tempPoint)(Stack_Push(outputPoint,Stack_Pop(tempPoint);search(inputPoint,tempPoint,outputPoint);Stack_Push(tempPoint,Stack_Pop(outputPoint);)if(Stack_Full(outputPoint)(total+;Stack_printreverse(*outputPoint);)主程序描述voidmain()SqSta

9、ckinput,temp,output;inti;printf("請輸入車廂數(shù)(2-30)n");scanf("%d”,&end);/*初始化三個棧*/Stack_init(&input);Stack_init(&temp);Stack_init(&output);/*將車廂號碼進(jìn)棧*/for(i=end;i>=1;i-)Stack_Push(&input,i);search(&input,&temp,&output);printf("thetotal:%ldn",total

10、);getch();).程序?qū)崿F(xiàn)運行界面(1)運行主界面CUsersAdministratorDesktop新建支柱夾Debugv.exe"請輸入車廂數(shù)427/(2)當(dāng)輸入n的值為3時，屏幕顯示I*CiUsersAdministratorDesktDpi新建立bugv.exe"(3)當(dāng)輸入n的值為4時，屏幕顯示不足之處我這個程序主要通過設(shè)置三個棧來實現(xiàn)，核心算法通過兩次遞歸調(diào)用實現(xiàn)?？梢詫崿F(xiàn)任務(wù)書里所要求的功能，但是也存在著不足之處，就是在運行界面，輸出n值，接回車鍵,得到輸出結(jié)果后，要想繼續(xù)輸入另一數(shù)值n,不能返回，只有退出，重新運行，才能輸入得到輸出結(jié)果。.設(shè)計體會看到自己寫的程序成功的運行真是種莫大的欣喜！很多時候，總是感覺學(xué)到的東西不知何用，總想用學(xué)過的語言來寫些程序，卻一直不知道寫些什么。終于，機(jī)會來到了，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，讓我一下子回憶起了以前學(xué)到的很多語言，于是，就有了運用自己所學(xué)的所有語言分別來實現(xiàn)車廂的調(diào)度。通過這個星期的課程設(shè)計，我的收獲還是不少。我的編程水平有了比較大的提高，雖然我做的程序里還有寫問題，做的不夠深入，但獨立完成一個比較大一點的程序的經(jīng)歷也是很寶貴的.結(jié)束語本課程設(shè)計主要是為了實現(xiàn)解決以下問題