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

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

3、的算法，來解決此問題。.需求分析假設停在鐵路調度站入口處白車廂序列的編號依次為1,2,3,，n,設計一個程序，求出所有可能的長度為n的車廂序列。實現棧的順序存儲結構SqStack之上實現棧的基本操作，即實現棧類型。程序對棧的基本操作必須借助于基本操作進行。測試數據取n=3,4,程序輸出的結果應該在屏幕上顯示出來。.數據結構設計全局變量定義typedefintSElemType;typedefintStatus;intend;/*最后一個車廂的號碼*/longtotal=0;/*總的組合方案數目*/棧的定義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).算法設計用到的進出棧算法基礎知識（1）根據要求，了解可能要用到的算法：進棧（PUSH算法若TO田n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出;不滿則作）；置TOP=TOP+1棧指針加1,指向進棧地址）；S（TOP）=X結束（X為新進棧的元素）；退棧（POP算法若TO

5、PC0,則給出下溢信息，作出錯處理（退棧前先檢查是否已為空棧，空則下溢;不空則作）；X=S（SOP）（退棧后的元素賦給X）;TOP=TOP-1結束（棧指針減1,指向棧頂）。程序分析.棧的數據結構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("請輸入車廂數(2-30)n");scanf("%d”,&end);/*初始化三個棧*/Stack_init(&input);Stack_init(&temp);Stack_init(&output);/*將車廂號碼進棧*/for(i=end;i>=1;i-)Stack_Push(&input,i);search(&input,&temp,&output);printf("thetotal:%ldn",total

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