stacks_another.cpp

设计一个算法

#include<iostream>
#include<fstream>

template<class T>
class Stack
{
    private:
		int top;
		int MaxTop;
		T *stack;
	public:
		Stack(int n=10);
		~Stack(){delete [] stack;}
		bool Empty() const {return top==-1;}
		bool Full() const {return top==MaxTop;}
		T Top() const;
		Stack<T>& Push(const T &x);
		Stack<T>& Pop(T &x);
		void check(int result[],int n,std::ofstream &fout,int &count);	
};
template<class T>
Stack<T>::Stack(int n)
{
	MaxTop=n+1;
	stack=new T[MaxTop];
	top=-1;
}
template<class T>
T Stack<T>::Top() const
{
	return stack[top];
}
template<class T>
Stack<T>& Stack<T>::Push(const T &x)
{	
	stack[++top]=x;
	return *this;
}
template<class T>
Stack<T>& Stack<T>::Pop(T &x)
{	
	x=stack[top--];
	return *this;
}
template<class T>
void Stack<T>::check(int result[],int n,std::ofstream &fout,int &count)
{
    int i=1,j=0,temp;//i代表现在从左边进来的车皮序数, j代表排列的第j个数，temp存放结果 
    while(i<=n){//i要一直到n才结束 
        if(Empty()){//空栈 
            if(i==result[j]){//如果排列现在头部这个数和进来的车皮序数是一样的 
                i++;        //就判断排列里的下一个数，同时判断下一个车皮 
                j++;
            }
            else
                Push(i++);  //如果不等的话，就让这个数进栈保存，判断后面的数 
        }
        else{//不是空栈 
            if(i==result[j]){//同上 
                i++;
                j++;
            }
            else if(Top()==result[j]){//如果栈顶元素和排列的头部元素是一样的，那么就出栈 
                Pop(temp);              //同时判断排列中的下一个数 
                j++;
            }    
            else
                Push(i++);        //如果不等的话，就让这个数进栈保存，判断后面的数
        }
    }
    bool yes=true;
    while(!Empty()){//所有车皮已经按顺序进来了，如果中转栈不为空，就按顺序输出，判断是否和排列一样 
         Pop(temp);//同时要将栈清空，以便验证下一个排列 
         if(temp!=result[j++])
             yes=false;
    }      
    if(yes){//如果yes没成false，就代表栈里的顺序和排列是一样的，那么这个排列是可行的，输出 
        for(i=0;i<n-1;i++)
            fout<<result[i]<<" ";//前n-1个元素后面都有空格 
        fout<<result[i]<<std::endl;//输出最后一个元素，并回车 
        count++;//计数器加1 
    }               
}
using namespace std;
int main()
{
    void perm(int,int,bool [],int [],Stack<int> &,std::ofstream &,int &);
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"input.txt is not exist"<<endl;
        exit(1);
    }
    int n;
    while(fin>>n){
        Stack<int> s(n);
        bool *used=new bool[n]; //用来产生全排列的判断工具 
        int *result=new int[n]; //存放排列结果 
        int count=0;//记录数目 
        memset(used,0,n); //对used数组初始化为0 
        perm(n,0,used,result,s,fout,count); //程序开始 
        fout<<count<<endl;
        delete []used;
        delete []result;
    }
    fin.close();
    fout.close();
    return 0;
} 

void perm(int n,int k,bool used[],int result[],Stack<int> &s,std::ofstream &fout,int &count)
{//递归求全排列 
    if(k==n) //产生一个排列时就进行验证 
        s.check(result,n,fout,count);
    else{ 
        for(int i=0;i<n;i++){ 
            if(!used[i]){ 
                used[i]=1;
                result[k]=i+1; 
                perm(n,k+1,used,result,s,fout,count);
                used[i]=0;
            } 
        }
    } 
}