statin.cpp

这是数据结构中模拟栈的一个精典例子利用火车进站出站模拟出栈和入栈

//计科二班  633寝室
// 章健军  20020810227
// 钟俊    20020810228
// 王重阳  20020810222
// 叶文华  20020810225
//
//  本实验解决火车进出站排列次序的问题,采用栈结构存储“火车次序”，用递归算法实现
//
// 递归函数stat()的参数中三个栈S1,S2,S3分别存储火车进站前、进站后与出站后的火车排列次序,
// total存储出站时可能的火车排序种数
// 递归函数stat()中，根据s1,s2,s3的四种不同状态分别处理：
//     1、S1,S2均为空;
//     2、S1为空，S2不为空；
//     3、S1不为空，S2为空；
//     4、S1,S2均不为空。
//

#include<iostream.h>
#include"station.h"


int stat(AStack s1,AStack s2,AStack s3,int &total)
{
    if(s1.isEmpty()&&s2.isEmpty())//s1,s2均为空，则完成一次递归，打印一种结果
	{
		total++;
		cout<<"第"<<total<<"种排列情况: ";
		s3.print();
		
		return 0;
	}

	if(s1.isEmpty()&&!s2.isEmpty())//s1为空,s2不为空
	{
		char c;	
		s2.pop(c);                 // 调整S2，S3继续递归
		s3.push(c);				   //	
        
		stat(s1,s2,s3,total);      //

		s3.pop(c);				   // 还原S2，S3
		s2.push(c);                //
	}

	if(!s1.isEmpty()&&s2.isEmpty())//s1不为空,s2为空
	{
		char c;
		s1.pop(c);                  // 调整S1，S2继续递归
		s2.push(c);                 //
                                    //   
		stat(s1,s2,s3,total);       //

		s2.pop(c);                  // 还原S1，S2
		s1.push(c);                 // 
	}	

	if(!s1.isEmpty()&&!s2.isEmpty())//s1,s2都不为空
	{
		char c;

		s1.pop(c);                  // 调整S1，S2继续递归
		s2.push(c);	                // 

		stat(s1,s2,s3,total);	    //   

        s2.pop(c);                  // 还原S1，S2
		s1.push(c);                 //

		s2.pop(c);                  // 调整S2，S3继续递归
		s3.push(c);                 //
		
		stat(s1,s2,s3,total);       //

		s3.pop(c);                  // 还原S2，S3
		s2.push(c);                 //
	}

	return 0;
}

void main()
{
	AStack s1(20),s2(20),s3(20);

	int t=0;
    cout<<"请输入火车名称及初始排列次序(以一个字符代表一列火车)：\n输入字符Z结束\n";

	char c;
	cin>>c;
    while(c!='z')
	{
		s1.push(c);
		cin>>c;
	}
	stat(s1,s2,s3,t);
	cout<<"可能的排列种数共为："<<t<<endl;
}