文档介绍:目录
目录 - 1 -
正文 1
一、题目分析 1
二、概要设计 1
三、详细设计 3
四、运行结果 8
五、课程设计体会 9
六、参考文献 9
正文
一、题目分析
课程设计题目
车厢调度:假设停在铁路调度站的车厢序列的编号依次为1,2.,3,…..n。设计一个程序,求出所有可能输出的长度为n的车厢序列。
基本要求
,即实现栈类型。程序对栈的任何存取(即更改,读取和状态判别等操作)必须借助于基本操作进行。
二、概要设计
:
ADT Stack {
数据对象:D={∈CharSet,i=1,2,...,n,,n≥0}
数据关系:R1={<∈D,i=2,...,n}
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
DestroyStack(&S)
初始条件:栈S已存在。
操作结果:销毁栈S。
ClearStack(&S)
初始条件:栈S已存在。
操作结果:将栈S清为空栈。
StackLength(S)
初始条件:栈S已存在。
操作结果:返回栈S的长度。
StackEmpty(S)
初始条件:栈S已存在。
操作结果:若S为空栈,则返回TURE,否则返回FALSE。
GetTop(S,&e)
初始条件:栈S已存在。
操作结果:若S不空,则e返回栈顶元素。
Push(&S,&e)
初始条件:栈S已存在。
操作结果:在s的栈顶插入新的栈顶元素e。
Pop(&S,&e)
初始条件:栈S已存在。
操作结果:删除S的栈顶元素,并以e返回其值。
StackTraverse(S,visit())
初始条件:栈S已存在。
操作结果:从栈底到栈顶依次对S中的每个元素调用函数visit()。
}ADT Stack
1)主程序模块:
Void main()
{
初始化;
For循环
}
2)栈模块——实现栈的抽象数据类型
各模块之间的调用关系如下:
主程序模块
栈模块
三、详细设计
1)栈类型;
typedef struct stacklist
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
栈的基本操作设置如下:
void Stack_init(SqStack *s)//初始化,设s为空栈
void Stack_Push(SqStack *s,SElemType e)//若分配空间成功,则在s的栈顶插入新的元素e,并返回TRUE
//若栈不变,并返回FALSE
SElemType 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)
2)代码
#include <iostream>
using namespace std;
typedef int SElemType;
typedef int Status;
int end;/*最后一个车厢的号码*/
long total=0;/*总的组合方案数目*/
typedef struct stacklist
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void Stack_init(SqStack *s)
{
s->base=(SElemType *)malloc(end*sizeof(int));
if(!s->base) exit(0);
s->top=s->base;
s->stacksize=end;
}
void Stack_Push(SqStack *s,SElemType e)
{
*(s->top)++=e;
}
SElemType Stack_Pop(SqStack *s)
{
if(s->top==s->base)
return 0;
return *(--(s->top));
}
Status Stack_Empty(SqStack *s)
{
if(s->top==s->base)
return 1;
return 0;
}
Status Stack