stacks.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream.h>
#include<fstream.h>

int count;
template<class T>
class Stack{
public:
	Stack(int Max=10);
	Stack(Stack<T> & );
	~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);
private:
	int top;
	int MaxTop;
    T *stack;
};
template<class T>
Stack<T>::Stack(int Max)
{
	MaxTop=Max-1;
	stack=new T[Max];
	top=-1;
}
template<class T>
Stack<T>::Stack(Stack<T> &s)
{
	
	stack=new T[s.MaxTop+1];
	MaxTop=s.MaxTop;
	top=s.top;
	for(int i=0;i<=top;i++)
	{
		stack[i]=s.stack[i];
	}
}
template<class T>
T Stack<T>::Top()const
{
	if(Empty())throw OutOfBounds();
	else 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;
}

void cp(Stack<int> &jg,Stack<int> &zg,int *chu,int k,int n,ofstream &out,int j)
{
	int p,i;
	Stack<int> jg1(jg);
	Stack<int> zg1(zg);

	if(j==0)
	{
		jg1.Pop(p);
		zg1.Push(p);
	}
	else{
        zg1.Pop(chu[k]);
		k++;
	}
	if(jg1.Empty()&&zg1.Empty())
	{
		for(i=0;i<n;i++)
			out<<chu[i]<<" ";
		out<<endl;
	    count++;
		return;
	
	}
	if(!jg1.Empty())
	{
		cp(jg1,zg1,chu,k,n,out,0);}	
	if(!zg1.Empty())
	{
		cp(jg1,zg1,chu,k,n,out,1);}
}
		
	
void main()
{
	int n,i,k=0,j=0;
	ifstream in("input.txt");
	in>>n;
	ofstream out("output.txt");
	int *chu;
	chu=new int[n];
	for(i=0;i<n;i++)
		chu[i]=0;
	Stack<int> zg(n);
	Stack<int> jg(n);
	count=0;
	for(i=n;i>0;i--)
		jg.Push(i);
	cp(jg,zg,chu,k,n,out,j);
	out<<count;
	
}