車廂調(diào)度問題課程設(shè)計(jì)

1、課程設(shè)計(jì)(論文)任務(wù)書 軟 件 學(xué) 院 學(xué) 院 軟 件+會(huì)計(jì) 專 業(yè) 20122 班一、課程設(shè)計(jì)(論文)題目 車廂調(diào)度問題 二、課程設(shè)計(jì)(論文)工作自 2013 年 12 月 30 日起至 2014 年 1 月 5 日止 三、課程設(shè)計(jì)(論文) 地點(diǎn): 創(chuàng)新大樓軟件實(shí)訓(xùn)中心機(jī)房 四、課程設(shè)計(jì)(論文)內(nèi)容要求：1本課程設(shè)計(jì)的目的訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)，編寫程序求解指定問題；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力，鞏固、深化學(xué)生的理論知識(shí)，提升編程水平。2課程

2、設(shè)計(jì)的任務(wù)及要求1）基本要求：要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編寫上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的報(bào)告；在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率；程序設(shè)計(jì)語言推薦使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋；每位同學(xué)需提交可獨(dú)立運(yùn)行的程序和規(guī)范的課程設(shè)計(jì)報(bào)告。2）課程設(shè)計(jì)論文編寫要求理論設(shè)計(jì)部分以課程設(shè)計(jì)論文的形式提交，格式必須按照課程設(shè)計(jì)論文標(biāo)準(zhǔn)格式進(jìn)行書寫和裝訂；課程設(shè)計(jì)報(bào)告（論文）包括中文目錄、設(shè)計(jì)任務(wù)、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼實(shí)現(xiàn)、調(diào)試分析、課設(shè)總結(jié)、謝辭、參考文獻(xiàn)、附錄等；設(shè)計(jì)部分應(yīng)包

3、含系統(tǒng)功能模塊圖，調(diào)試分析應(yīng)包括運(yùn)行截圖等。3）課程設(shè)計(jì)評(píng)分標(biāo)準(zhǔn)： 學(xué)習(xí)態(tài)度：10分；系統(tǒng)設(shè)計(jì)：20分；編程調(diào)試：20分；回答問題：20分；論文撰寫：30分。第 1 頁4）參考文獻(xiàn)：嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)M. 清華大學(xué)出版社. 2010.3 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版)M. 清華大學(xué)出版社. 1999.2何欽銘,馮燕等. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M. 浙江大學(xué)出版社. 2007.85）課程設(shè)計(jì)進(jìn)度安排準(zhǔn)備階段（4學(xué)時(shí)）：選擇設(shè)計(jì)題目、了解設(shè)計(jì)目的要求、查閱相關(guān)資料；程序模塊設(shè)計(jì)分析階段（4學(xué)時(shí)）：程序概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)；代碼編寫調(diào)試階段（8學(xué)時(shí)）：程序模塊代碼編寫、調(diào)試、

4、測(cè)試；撰寫論文階段（4學(xué)時(shí)）：總結(jié)課程設(shè)計(jì)任務(wù)和設(shè)計(jì)內(nèi)容，撰寫課程設(shè)計(jì)論文。 學(xué)生簽名： 2013 年 12 月 29 日6） 課程設(shè)計(jì)題目具體要求：車廂調(diào)度問題問題描述：假設(shè)停在鐵路調(diào)度站(如教科書中圖3.1(b)所示)入口處的車廂系列的編號(hào)依次為1，2，3，n。設(shè)計(jì)一個(gè)程序,求出所有可能由此輸出的長度為n 的車廂系列?；疽螅涸O(shè)計(jì)一個(gè)程序，求出由一個(gè)編號(hào)依次為1，2，、，n的車廂序列可能產(chǎn)生的所有出棧系列。利用雙向棧存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)調(diào)度站和輸出序列這兩個(gè)棧的空間共享。 對(duì)于每個(gè)輸出序列演示出所有操作序列的變化過程 課程設(shè)計(jì)(論文)評(píng)審意見（1）學(xué)習(xí)態(tài)度（10分）：優(yōu)（）、良（）、中（）、一般

5、（）、差（）； （2）系統(tǒng)設(shè)計(jì)（20分）：優(yōu)（ ）、良（）、中（）、一般（）、差（）； （3）編程調(diào)試（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）回答問題（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性及考勤是否降等級(jí)：是（）、否（）評(píng)閱人： 王英華 職稱： 講師 2014 年 1 月 8 日 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目： 車廂調(diào)度問題 學(xué)院： 軟件學(xué)院 班級(jí)： 12軟件+會(huì)計(jì)2班 學(xué)生： 韓嵩 目錄正文一、設(shè)計(jì)任務(wù).1二、需求分析.11、抽象數(shù)據(jù)類型.12、存儲(chǔ)結(jié)構(gòu)定義.23、基本操作.3三

6、、系統(tǒng)設(shè)計(jì)1、問題分解.32、模塊結(jié)構(gòu).43、解題思路.4四、編碼實(shí)現(xiàn).4五、調(diào)試分析.71、實(shí)驗(yàn)數(shù)據(jù).72、實(shí)驗(yàn)結(jié)果.7六、課設(shè)總結(jié).91、數(shù)據(jù)結(jié)構(gòu)使用小結(jié).92、需完善之處.9課程設(shè)計(jì)體會(huì)、參考文獻(xiàn).10正 文1、 設(shè)計(jì)任務(wù)車廂調(diào)度問題問題描述：假設(shè)停在鐵路調(diào)度站(如教科書中圖3.1(b)所示)入口處的車廂系列的編號(hào)依次為1，2，3，n。設(shè)計(jì)一個(gè)程序,求出所有可能由此輸出的長度為n 的車廂系列?；疽螅涸O(shè)計(jì)一個(gè)程序，求出由一個(gè)編號(hào)依次為1，2，、，n的車廂序列可能產(chǎn)生的所有出棧系列。利用雙向棧存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)調(diào)度站和輸出序列這兩個(gè)棧的空間共享。 對(duì)于每個(gè)輸出序列演示出所有操作序列的變化過程

7、。二、需求分析1. 抽象數(shù)據(jù)類型本設(shè)計(jì)中用到的數(shù)據(jù)結(jié)構(gòu)ADT定義如下：ADT Stack 數(shù)據(jù)對(duì)象：D=CharSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系：R1=<D,i=2,.,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將棧S清為空棧。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長度。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TURE，否則返回FALS

8、E。GetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若S不空，則e返回棧頂元素。Push（&S，&e）初始條件：棧S已存在。操作結(jié)果：在s的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse（S，visit（）初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit（）。ADT Stack2. 存儲(chǔ)結(jié)構(gòu)定義數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的C語言定義如下：typedef int SElemType;typedef int Status;int finish

9、; /最后一個(gè)車廂號(hào)碼typedef struct SNodeSElemType *base;SElemType *top;int stacksize;SqStack;3. 基本操作數(shù)據(jù)結(jié)構(gòu)的基本操作實(shí)現(xiàn)如下：void InitStack(SqStack *s)/初始化，設(shè)s為空棧void Push(SqStack *s,SElemType e)/若分配空間成功，則在s的棧頂插入新的元素e，并返回TRUE，若棧不變，并返回FALSESElemType Pop(SqStack *s)Status StackEmpty(SqStack *s)Status Full(SqStack *s)void

10、Printreverse(SqStack s)void Search(SqStack *InputPoint,SqStack *TempPoint,SqStack *OutputPoint)三、系統(tǒng)設(shè)計(jì)1. 問題分解該問題主要應(yīng)實(shí)現(xiàn)以下功能：1. 棧的初始化2. 函數(shù)的遞歸調(diào)用3. 進(jìn)棧出棧3.棧的打印2. 模塊結(jié)構(gòu)系統(tǒng)主要由兩個(gè)模塊組成，分別是：1.主程序模塊2.棧模塊 棧 主程序模塊之間的結(jié)構(gòu)如下： 主程序3. 解題思路各模塊的實(shí)現(xiàn)步驟為：1. 棧的存儲(chǔ)定義，輸出操作信息，并輸入數(shù)據(jù)2. 初始化三個(gè)棧Input,Temp,Output3.for循環(huán)控制輸出語句，車廂號(hào)依次進(jìn)棧4.輸出所有情

11、況四、編碼實(shí)現(xiàn)#include <stdio.h> #include<malloc.h>#include<iostream>using namespace std;typedef int SElemType;typedef int Status;int finish; /最后一個(gè)車廂號(hào)碼typedef struct SNodeSElemType *base;SElemType *top;int stacksize;SqStack;void InitStack(SqStack *s)s->base=(SElemType *)malloc(finish*s

12、izeof(int);if(!s->base) exit(0);s->top=s->base;s->stacksize=finish;void Push(SqStack *s,SElemType e) /插入 *(s->top)+=e;SElemType Pop(SqStack *s) /刪除 if(s->top=s->base)return 0;return *(-(s->top);Status StackEmpty(SqStack *s) /判斷 if(s->top=s->base)return 1;return 0;Status

13、 Full(SqStack *s)if(s->top-s->base=finish)return 1;return 0;void Printreverse(SqStack s)int *p;p=s.base;for( ;p!=s.top; ) printf("%d ",*p+);printf("n");void Search(SqStack *InputPoint,SqStack *TempPoint,SqStack *OutputPoint)if(!StackEmpty(InputPoint)Push(TempPoint,Pop(Input

14、Point);Search(InputPoint,TempPoint,OutputPoint);Push(InputPoint,Pop(TempPoint);if(!StackEmpty(TempPoint)Push(OutputPoint,Pop(TempPoint);Search(InputPoint,TempPoint,OutputPoint);Push(TempPoint,Pop(OutputPoint);if(Full(OutputPoint)Printreverse(*OutputPoint);int main()SqStack Input,Temp,Output;int i;pr

15、intf("請(qǐng)輸入車廂長度:n ");printf("*韓嵩制作*n");printf("備注：輸入車廂長度即可得到所有進(jìn)棧序列n"); scanf("%d",&finish); InitStack(&Input);/初始化 InitStack(&Temp);InitStack(&Output);for(i=finish;i>=1;i-) /進(jìn)棧 Push(&Input,i);Search(&Input,&Temp,&Output); /輸出所有

16、可能存在的情況 五、調(diào)試分析1. 實(shí)驗(yàn)數(shù)據(jù) 車廂的長度：3，52. 實(shí)驗(yàn)結(jié)果 六、課設(shè)總結(jié)1. 數(shù)據(jù)結(jié)構(gòu)使用小結(jié)棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。棧具有記憶作用，對(duì)棧的插入與刪除操作中，不需要改變棧底指針。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表。棧可以用來在函數(shù)調(diào)用的時(shí)候存儲(chǔ)斷點(diǎn)，做遞歸時(shí)要用到棧！2. 需完善之處此程序不能讓人清除的觀察到操作的狀態(tài)與變化過程，這點(diǎn)需要改進(jìn)第 10 頁課程設(shè)計(jì)體會(huì)通過此次課