車(chē)廂調(diào)度問(wèn)題設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)報(bào)告名稱車(chē)廂調(diào)度問(wèn)題實(shí)驗(yàn)室 完成日期車(chē)廂調(diào)度問(wèn)題實(shí)驗(yàn)報(bào)告一、目的與要求掌握線性結(jié)構(gòu)的邏輯特點(diǎn)及存儲(chǔ)實(shí)現(xiàn)；根據(jù)選題，按規(guī)范化流程完成課程設(shè)計(jì)報(bào)告：（1）.提供需求分析。（15分）（2）.列出概要設(shè)計(jì)。（包括：抽象數(shù)據(jù)類型的描述；程序結(jié)構(gòu)圖或功能模塊圖）（20分）.給出詳細(xì)設(shè)計(jì)。（包括：存儲(chǔ)結(jié)構(gòu)的描述；算法的詳細(xì)設(shè)計(jì)，對(duì)復(fù)雜算法，最 好畫(huà)出其N(xiāo)-S流程圖；函數(shù)的調(diào)用關(guān)系圖）（30分）.進(jìn)行調(diào)試分析（注：調(diào)試時(shí)遇到的問(wèn)題及解決方法，程序的輸出結(jié)果及對(duì)結(jié)果的分 析）。（15分）.整理設(shè)計(jì)總結(jié)。（設(shè)計(jì)心得體會(huì)，以及其他總結(jié)信息等）（10分）.附有程序清單（注：代碼可具有適當(dāng)注

2、釋，用來(lái)說(shuō)明程序的功能、結(jié)構(gòu)）。（10分）二、設(shè)計(jì)步驟需求分析本程序的任務(wù)是:假設(shè)停在鐵路調(diào)度站入口處的車(chē)廂序列的編號(hào)依次為1，2,3, n. 設(shè)計(jì)一個(gè)程序，求出所有可能由此輸入的長(zhǎng)度為N的車(chē)廂序列。若實(shí)現(xiàn)車(chē)廂調(diào)度的基本要求，所以需要建立一個(gè)棧來(lái)實(shí)現(xiàn)。棧的特性是先進(jìn)后出，而 根據(jù)棧的特性，進(jìn)棧與出棧都有兩種可能:一個(gè)數(shù)進(jìn)棧后，要么立即出棧，要么進(jìn)行下一 個(gè)數(shù)的進(jìn)棧；同樣一個(gè)數(shù)出棧后，在棧不為空的情況下要么繼續(xù)出棧，要么進(jìn)行下一個(gè)數(shù) 的進(jìn)棧；輸入一個(gè)車(chē)廂長(zhǎng)度，從而得到由此輸出長(zhǎng)度為n的車(chē)廂序列，并定義一個(gè)一維數(shù) 組來(lái)保存所有的輸出序列。概要設(shè)計(jì)2.1功能模塊設(shè)計(jì)主程序模塊，棧模塊，遞歸模塊，調(diào)度

3、模塊。主程序模塊 第1頁(yè)開(kāi)始結(jié)束判斷棧空 或棧滿棧模塊遞歸模塊調(diào)度模塊2.2所有功能模塊的流程圖定義一個(gè)空棧調(diào)用函數(shù)輸出車(chē)廂總個(gè)數(shù)輸出所有車(chē)廂序列3.詳細(xì)設(shè)計(jì)開(kāi)始結(jié)束判斷?？?或棧滿棧模塊遞歸模塊調(diào)度模塊2.2所有功能模塊的流程圖定義一個(gè)空棧調(diào)用函數(shù)輸出車(chē)廂總個(gè)數(shù)輸出所有車(chē)廂序列3.詳細(xì)設(shè)計(jì)3.1棧類型;typedef struct stacklist(SElemType *base;SElemType *top;int stacksize;SqStack;棧的基本操作設(shè)置如下：void Stack_init(SqStack *s)/初始化，設(shè) s 為空棧void Stack_Push(SqS

4、tack *s,SElemType e)/若分配空間成功，則在s的棧頂插入新的元 素e,并返回TRUE/若棧不變，并返回FALSESElemType Stack_Pop(SqStack *s)Status Stack_Empty(SqStack *s)Status Stack_Full(SqStack *s)void Stack_printreverse(SqStack s)void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)3.2算法的詳細(xì)設(shè)計(jì)定義棧初始化三個(gè)棧 input,temp,outputfo

5、r循環(huán)控制輸出語(yǔ)句，車(chē)廂號(hào)依次進(jìn)棧調(diào)用函數(shù) Stack_Push(&input,i);search(&input,&temp,&output);輸出所有情況基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷(xiāo)毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將棧S清為空棧。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長(zhǎng)度。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回1，否則返回0。GetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若S不空

6、，則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()。核心算法：void search(SqStack *input,SqStack *temp,SqStack *output)(if(!Emptystack(input)/ 一個(gè)數(shù)進(jìn)棧后，有兩種處理方式：要么立刻出棧，要么進(jìn)行下一 個(gè)數(shù)的進(jìn)棧(Push(temp,Po

7、p(input);search(input,temp,output);Push(input,Pop(temp);if(!Emptystack(temp)/ 一個(gè)數(shù)出棧后，有兩種處理方式：要么繼續(xù)出棧，要么繼續(xù)下一個(gè)數(shù)的進(jìn)棧(Push(output,Pop(temp);search(input,temp,output);Push(temp,Pop(output);if(Fullstack(output)/棧滿時(shí)輸出序列產(chǎn)生，輸出(total+;PrintStack(*output);主函數(shù)描述int main()(SqStack input,temp,output;int i;printf(nn

8、tttt 車(chē)廂調(diào)度n);printf(nt請(qǐng)輸入車(chē)廂長(zhǎng)度：)；scanf(%d,&final);printf(nt 車(chē)廂序列為：n);將棧初始化Initstack(&input);Initstack(&temp);Initstack(&output);將車(chē)廂號(hào)碼進(jìn)棧for(i=final;i=1;i-)Push(&input,i);search(&input,&temp,&output);/輸出所有可能出現(xiàn)的情況4.調(diào)試分析五.程序清單#include #include typedef int SElemType;typedef int Status;int final;/最后一個(gè)車(chē)廂的號(hào)碼(

9、車(chē)廂長(zhǎng)度)int total=0;/車(chē)廂序列的總個(gè)數(shù)typedef struct(SElemType *base;/棧底指針SElemType *top;/棧頂指針int stacksize;/ 棧大小SqStack;/順序棧Status Initstack(SqStack *s)(/構(gòu)造一個(gè)空棧s-base=(SElemType *)malloc(final*sizeof(int);if(!s-base) exit(0);s-top=s-base;s-stacksize=final; 若棧為空，存儲(chǔ)分配失敗Status Push(SqStack *s,SElemType e)/插入元素 e

10、為新的棧頂元素(*(s-top)+=e;Status PrintStack(SqStack s)/輸出車(chē)廂序列的總個(gè)數(shù) (int *p;p=s.base;printf(t%ld: ,total);for(;p!二s.top;)printf(d ,*p+);printf(n)； void search(SqStack *input,SqStack *temp,SqStack *output)(if(!Emptystack(input)/ 一個(gè)數(shù)進(jìn)棧后，有兩種處理方式：要么立刻出棧，要么進(jìn)行下一 個(gè)數(shù)的進(jìn)棧(Push(temp,Pop(input);search(input,temp,output

11、);Push(input,Pop(temp);if(!Emptystack(temp)/ 一個(gè)數(shù)出棧后，有兩種處理方式：要么繼續(xù)出棧，要么繼續(xù)下一 個(gè)數(shù)的進(jìn)棧(Push(output,Pop(temp);search(input,temp,output);Push(temp,Pop(output);if(Fullstack(output)/棧滿時(shí)輸出序列產(chǎn)生，輸出(total+;PrintStack(*output);/主函數(shù)int main()(SqStack input,temp,output;int i;printf(nntttt 車(chē)廂調(diào)度n);printf(nt請(qǐng)輸入車(chē)廂長(zhǎng)度：)；scanf(%d