实习2.3.cpp

用栈的形式实现车厢调度,火车入口处的车厢序列编号为1到n

# include<iostream.h>
#define   OK     1
#define   ERROR  0
typedef struct{
	int * base;
	int *top;
}SqStack;
void init(SqStack &S)
{
	S.base=new int [100];
	if(!S.base)
		return ;
	S.top=S.base;
}
void push(SqStack &S,int n)
{
	*S.top++=n;
}
int  pop(SqStack &S)
{
	int e;
	if(S.top==S.base)
		return -1;
	e=*--S.top;
	return e;
}
bool IsEmpty(SqStack S)
{
	if(S.top==S.base)
		return OK;
	else
		return ERROR;
}
void display(SqStack S)
{
	int *p=S.base;
	while(p!=S.top)
	{
		cout<<*p<<"  ";
		p++;
	}
	cout<<endl;
}
int total=0;
void Arrange( SqStack &sSource, SqStack &sDest, SqStack &sFinal )
{
   if ( !IsEmpty(sSource) ) 
   { 
     push(sDest,pop(sSource)); 
     Arrange(sSource, sDest, sFinal);
     push(sSource,pop(sDest));
   }
   if ( !IsEmpty(sDest) ) 
   { 
	 push(sFinal,pop(sDest)); 
	 Arrange(sSource, sDest, sFinal);
     push(sDest,pop(sFinal));
   }
   if ( IsEmpty(sSource) && IsEmpty(sDest)) 
   { 
	   total++;
	   cout<<"第"<<total<<"种输出序列是:"<<endl;
	   display(sFinal);
   }
}
main()
{
    cout<<"********************欢迎进入车厢调度程序********************"<<endl;
	char c;
	for(int a=0;a<100;a++)
	{
	 cout<<"若要退出实验，请输入Q,若要继续请输入其他任何一个字母:";
	 cin>>c;
	 if(c=='Q'||c=='q')
		return ERROR;
	 else
	 {
		cout<<"请输入要调度的车厢数: ";
	    int n;
	    cin>>n;
		SqStack input,temp,output;
	    init(input);
	    init(temp);
	    init(output);
	    for(int i=n;i>=1;i--)
		{
			 push(input,i);
		}
	    total=0;
        Arrange(input,temp,output);
        cout<<"共有"<<total<<"种调度方法."<<endl;
	 }
	}
return OK;
}