车厢调度.cpp

利用栈的方式完成车厢调度,数据结构的实习题目,已完成基本内容.

#include <iostream.h>
#include <stdlib.h>
typedef int SElemType;
typedef int Status; 

int n;//最后一个车厢的号码
long total=0;//总的组合方案数目 
 
typedef struct stacklist
{//顺序栈定义
     SElemType *base;
     SElemType *top;
     int stacksize;
}SqStack; 

void InitStack(SqStack *s)
{//构造一个空栈S
     s->base=(SElemType *)malloc(n*sizeof(int));
     if(!s->base) exit(0);
     s->top=s->base;
     s->stacksize=n;
} 

void Push(SqStack *s,SElemType e)
{//插入元素e为新的栈顶元素
  *(s->top)++=e;
} 

SElemType Pop(SqStack *s)
{//若栈不空,则删除S的栈顶元素,否则返回0
  if(s->top==s->base)
  return 0;
  return *(--(s->top));
} 

Status Empty(SqStack *s)
{//若栈为空栈,则返回1,否则返回0
  if(s->top==s->base)
  return 1;
  return 0;
} 

Status Full(SqStack *s)
{//若栈满,则返回1,否则返回0
  if(s->top-s->base==n)
  return 1;
  return 0;
}

void Printreverse(SqStack s)
{//输出所有的车厢序列
  int *po;
  po=s.base;     
  cout<<"n"<<"["<<total<<"]:";
  for(;po!=s.top;) 
  cout<<*po++<<" ";
  cout<<endl;
} 

void search(SqStack *input,SqStack *temp,SqStack *output)
{//两次递归调用
 if(!Empty(input))
{
  Push(temp,Pop(input));
  search(input,temp,output);
  Push(input,Pop(temp));
}

 if(!Empty(temp))
{
  Push(output,Pop(temp));
  search(input,temp,output);
  Push(temp,Pop(output));
}

 if(Full(output))
{
  total++;
  Printreverse(*output);
}
}

void main()
{
  SqStack input,temp,output;
  int i;
   cout<<"             * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
   cout<<"             *  					   *"<<endl;
   cout<<"             * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
   cout<<"-------------------------------车厢调度---------------------------------"<<endl;
   cout<<endl;
   cout<<"请输入最后一列车厢的序列号:";
  cin>>n;
 
  {//初始化三个栈
  InitStack(&input);
  InitStack(&temp);
  InitStack(&output);
  }

  for(i=n;i>=1;i--)
  Push(&input,i);//将车厢号码进栈
  search(&input,&temp,&output);
  cout<<"所有可能由此输出的车厢序列总数为:"<<total<<endl;
}