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

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

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

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

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

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

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

7、。二、需求分析1. 抽象數(shù)據(jù)類型本設(shè)計中用到的數(shù)據(jù)結(jié)構(gòu)ADT定義如下：ADT Stack 數(shù)據(jù)對象：D=CharSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系：R1=<D,i=2,.,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧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é)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit（）。ADT Stack2. 存儲結(jié)構(gòu)定義數(shù)據(jù)存儲結(jié)構(gòu)的C語言定義如下：typedef int SElemType;typedef int Status;int finish

9、; /最后一個車廂號碼typedef struct SNodeSElemType *base;SElemType *top;int stacksize;SqStack;3. 基本操作數(shù)據(jù)結(jié)構(gòu)的基本操作實現(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è)計1. 問題分解該問題主要應(yīng)實現(xiàn)以下功能：1. 棧的初始化2. 函數(shù)的遞歸調(diào)用3. 進棧出棧3.棧的打印2. 模塊結(jié)構(gòu)系統(tǒng)主要由兩個模塊組成，分別是：1.主程序模塊2.棧模塊 棧 主程序模塊之間的結(jié)構(gòu)如下： 主程序3. 解題思路各模塊的實現(xiàn)步驟為：1. 棧的存儲定義，輸出操作信息，并輸入數(shù)據(jù)2. 初始化三個棧Input,Temp,Output3.for循環(huán)控制輸出語句，車廂號依次進棧4.輸出所有情

11、況四、編碼實現(xiàn)#include <stdio.h> #include<malloc.h>#include<iostream>using namespace std;typedef int SElemType;typedef int Status;int finish; /最后一個車廂號碼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("請輸入車廂長度:n ");printf("*韓嵩制作*n");printf("備注：輸入車廂長度即可得到所有進棧序列n"); scanf("%d",&finish); InitStack(&Input);/初始化 InitStack(&Temp);InitStack(&Output);for(i=finish;i>=1;i-) /進棧 Push(&Input,i);Search(&Input,&Temp,&Output); /輸出所有

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