stacks.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 Out(std::ofstream &fout);				   		
};
template<class T>
Stack<T>::Stack(int n)
{
	MaxTop=n-1;
	stack=new T[n];
	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>::Out(std::ofstream &fout)
{
    for(int i=top;i>0;i--)
        fout<<stack[i]<<" ";
    fout<<stack[0];
}
void perm(int *pos,int k,int n,int index,int &count,std::ofstream &fout,Stack<int> &s)//pos数组储存排列，index控制pos数组下标,k代表进栈次数
{
    int temp;
    if(k>=n){        
        for(int i=1;i<index && i<=n-1;i++)
            fout<<pos[i]<<" ";//输出前面有空格的数 
        if(!s.Empty())//如果栈非空，那么输出 
            s.Out(fout);
        else fout<<pos[n];//否则输出最后一个元素 
        fout<<std::endl;
        count++;//计数器加
    }
    else{       //若未到达终点时
        if(!s.Empty()){//若栈非空
            s.Pop(temp);//弹出并储存于pos数组
            pos[index]=temp;
            perm(pos,k,n,index+1,count,fout,s);//访问右子树，k不变，因为没有进栈
			s.Push(temp);//重新将刚才弹出的元素压回，回溯
        }      
        s.Push(k+1);//进栈
        perm(pos,k+1,n,index,count,fout,s);//访问左子树，因为有进栈动作发生,所以k+1 
		s.Pop(temp);//重新弹出，回溯
    }
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"error"<<endl;
        exit(1);
    }
    int n;
    while(fin>>n){
        int count=0;
        int *pos=new int[n+1];
        Stack<int> s(n);
        int i=n;             
        perm(pos,0,n,1,count,fout,s);        
        fout<<count<<endl;
        delete []pos;
    }
    return 0;
}