车厢调度.txt

：假设停在铁路调度站入口处的车厢序列的编号一次为1

#include<iostream.h>
#include<stdio.h>
int n;
int path[45];   //定义全局变量

struct pathss{
int paths[45][45];
int number;
}AllPath;      //定义一个二维数组来保存所有的输出序列

struct SNode{
int data[45];
int top;
}S;   //栈的顺序存储结构的定义

void InitStack()   //栈的初始化
{
S.top=-1;
}

void Push(int q) //进栈
{
S.data[++S.top]=q;
}

int Pop()     //出栈
{
int temp;
temp=S.data[S.top--];
return temp;
}

int StackEmpty() //判断栈是否为空
{
if(S.top==-1)
   return 1;
else
   return 0;
}

void Attemper(int pos,int path[],int cur) //调度过程
{
int m,i;
if(pos<n)
{
   Push(pos+1);    //一个数进栈后,要么立刻出栈,要么进行下一个数的进栈
   Attemper(pos+1,path,cur);
   Pop();
}
if(!StackEmpty())
{
   m=Pop();       //一个数出栈后,要么继续出栈(栈不空),要么继续下一个数的进栈
   path[cur++]=m;
   Attemper(pos,path,cur);
   Push(m);
}
if(pos==n && StackEmpty())   //一种可能输出序列产生
{
   cout<<"\t\t\t";
   cout<<AllPath.number+1<<":";
   for(i=0;i<cur;i++)
   {
    cout<<path[i]<<" ";
    AllPath.paths[AllPath.number][i]=path[i]; //将每种序列保存在二维数组里
   }
   cout<<endl;
   AllPath.number++;
}
}

void Print()   //一个栈打印操作
{
int i;
for(i=S.top;i>=0;i--)
   cout<<"\t\t\t "<<"|"<<S.data[i]<<"|\n";
}

void DisplayOnly(int k,int Output,int Input) //显示操作序列的状态的变化过程
{ 
int j;
getchar();    //每按一次回车,就有一次变化
for(j=0;j<=Output;j++)
   cout<<"<----"<<AllPath.paths[k][j];   //负责显示输出序列的状态变化
cout<<endl;
Print();         //栈的状态变化
cout<<"\t\t\t\t\t";
for(j=Input;j<=n;j++)      //负责显示输入序列的状态变化
   cout<<"<----"<<j;   
cout<<endl;
}

void ChooseDisplay()    //状态变化过程
{
int k,Output,Input=1;
cout<<"请输入你想要查看序列状态变化过程的序号:";
cin>>k;
k=k-1;
InitStack();
cout<<"\n    输出序列\t           栈\t\t 输入序列";
DisplayOnly(k,-1,1);
for(Output=0;Output<n;Output++)
{ 
   if(AllPath.paths[k][Output]>=Input)          //当输出序列中当前的数据大于等于入口处
   {                                          //的数据时, 入口处的数据要一直压栈,
    while(AllPath.paths[k][Output]>=Input)    //直到当前的数据小于入口处的数据
    {
     Push(Input);
     Input++;
     DisplayOnly(k,Output-1,Input); 
    }
    Pop();
    DisplayOnly(k,Output,Input); 
   }   
    else                                  //当序列中当前的数据小于入口处
      {                                   //的数据时,弹出栈顶,重新显示结果
   Pop();
   DisplayOnly(k,Output,Input); 
      }
   }
}


void message() //菜单显示
{
cout<<endl;
cout<<"*******************************"<<endl;
cout<<"*           车厢调度          *"<<endl;
cout<<"*   1:输入火车的长度          *"<<endl;
cout<<"*   2:输出所有可能序列        *"<<endl;
cout<<"*   3:演示一个序列变化        *"<<endl;
cout<<"*   4:退出本程序              *"<<endl;
cout<<"*******************************"<<endl;
cout<<endl;
}

void InputNumber() //输入序列的长度
{
cout<<"请输入火车车厢的长度N:";
cin>>n;
}

void DisplayAll() //显示所有输出序列
{
AllPath.number=0;
InitStack();
Push(1);
cout<<"所有可能的输出序列如下:\n";
Attemper(1,path,0);
}

void main() //主函数 
{
int flag;
message();
cin>>flag;
while(flag!=4)
{
   switch(flag)
   {
    case 1: InputNumber();break;
    case 2: DisplayAll();break;
    case 3: ChooseDisplay();break;
   }
    message();
    cin>>flag;
   }
}