车厢调度问题报告

1、车厢调度问题1.题目分析车厢调度题目，题目的目的是有n辆车依次进入一个车站，把所有可能的出站的序 列输出，题目要求使用栈数据结构完成出站和入站操作。根据栈的数据特性，最先进栈 的最后出栈。而且对问题进行分析可知对栈来说只有出栈和入栈两 种操作，所以问题具 有递归的特性，所以对这个题目的核心解法就是采用递归的操作。问题着眼于进栈的n辆车，当这n辆车完成进栈操作，所有的出栈的可能都 已经出 来了。首先从第一辆进行分析，它只有一种可能：进栈。对于后面的 n-1 辆车，如果栈不为空，则有两种可能，一种是它进栈，另一种是栈中的顶元素出栈。所 以整个过程可以的结果就是一颗二叉树，只要完成对这棵二叉树的遍历

2、，就可以把所有 的结果输出，下面我用n=3来说明这个例子。图一，三辆车依次入栈所有可能的出栈结果有上图可知，只要完成对二叉树的遍历就可以输出所有可能的出栈顺序2.设计过程因为栈的基本操作都需要使用，所以下面先介绍栈的基本操作的设计栈数据结构体：typedef struct(int *stk;int top;int size; stack;置空栈：void initstack(stack *s, int n);入栈:void push(stack* s, int x);出栈:int pop(stack* s);判断是否空：int stackempty(stack* s);出栈，入栈，置空栈，判断

3、栈是否为空都是栈的基本操作，不做介绍介绍主函数:主函数是整个程序的核心部分，它实现了对所有的出栈可能性的探索。是按 它也 照递归的思想编写的。主函数的源代码如下：void main()(int i;int k;stack in put, s, output;in itstack(&in put, N);in itstack(&s, N);initstack(&output, N);printf("请输入车厢数量：n");sea nf(n%d",&k);prin tf(n可能的出站序列为：nn);for(i=k; i>0; i-

4、)push(&in put, i);stackseq (&in put, &s, &output); F面写出的是整个程序的流程图:Main函数流程图siackiisioo;puiMs.popdnput).Stackseq函数流程图3.调试过程和试验结果c： *C: Docuaents and SettingsAd>mistrat or3Q99seKAAGJUsdDebug j. exe请输入车厢数量可能的出站序列为:11223Press23132any key32311 to continue4.结论5程序清单# i nclude <stdio.h

5、># i nclude <stdlib.h># defi ne N 20 typedef structint*stk;inttop;int size; stack;sizeof(int);sizeof(int);VUIU initstack(stack *s, int n)s-> stk =(int*)malloc (s>> size=n)s-> top =0;)void copystack(stack *ss, stack *s)int i;if(ss-> stk) free(ss-> stk);ss-> stk = (int*)m

6、alloc(ss-> size=s-> size) ss->top = s-> top;i=s-> top-1;for(;i>=0;i-)ss-> stki=s-> stki;)void outputstack(stack* s) int i;for(i=0; i <s-> top; i+) printf( "5d”，printf( nnn);int stackempty(stack* s) <return !s-> top;)void push(stack* s, int x) s-> stks->

7、 top+ = x;)int pop(stack* s)return s-> stk-s-> top;)void stackseq(stack *input5 stack *s, stack *output)(/*初始状态：栈input中存放要输入的元素，s, output为分结束状态：input和s均为 空*/ 'stack ii, ss, oo;if(stackempty(input)/*如果数据已经全部输入完毕*/ if(stackempty(s)outputstack(output);/*而且栈中也没有剩余，则输出序列*/else(push(output, pop(

8、s); /* 栈中元素进入输出序列*/ stackseq(input, s, output); /*重新调度7 >else/*还有元素要输入7if(!stackempty(s)/*我们需要保存现有状态7initstack(&ii,1);copystack(&ii,input);initstack(&ss,1);copystack(&ss, s);initstack(&oo, 1); copystack(&oo, output)push(&oo, pop(&ss); stackseq(&ii, &ss, &oo); push(s, pop(input); /* 再输入一个元素 */ stackseq(input, s, output);void main(), h k ntntstack input, s, output; initstack(&input, N); initstack(&s, N); initstack(&output, N);printf("请输入车厢数量：