inver.cpp

这是一个关于逆序表问题的程序

#include <iostream>
#include <fstream>
using namespace std;

	template <class T> class List;
	template <class T> class Iterator;
	template <class T> class Stack;
	template <class T> class Queue;
	template <class T>
	class Node
	{
		friend List<T>;
		friend Iterator<T>;
		friend Stack<T>;
		friend Queue<T>;
		private:
			T data;
			Node<T> *next;
	};
	template <class T>
	class List
	{
		friend Iterator<T>;
		private:
			Node<T> *first;
		public:
			List(){first=0;}
			~List();
			bool Empty() const {return first==0;}
			int Length () const ;
			bool Retrieve(int,T &)const;
			int Locate(const T & ) const;
			List<T> & Insert(int ,const T&);
			List<T> & Delete(int,T&);
			void PrintList(ostream &) const;
		public:
			void SPLIT(List<T> *&,List<T> *&) const;
	};
	template <class T>
	class Iterator
	{
		public:
			T * Init(const List<T> & c)
			{
				location=c.first;
				if(location) return &location->data;
				return 0;
			}
			T * Next()
			{
				if(!location) return 0;
				location =location->next;
				if(location) return & location->data;
				return 0;
			}
		private:
			Node<T> *location;
	};
	template <class T>
	class Stack
	{
		public:
			Stack() {top = 0;}
			~Stack();
			bool Empty() const {return top == 0;}
			bool Full() const;
			T Top() const;
			Stack<T> & Push(const T &);
			Stack<T> & Pop(T &);
		private:
			Node<T> *top;
	};
	template <class T> 
	class Queue
	{
		public:
			Queue() {front = rear = 0;}
			~Queue();
			bool Empty() const {return ((front) ? false : true);}
			bool Full() const;
			T First() const;
			T Last() const;
			Queue<T> & EnQueue(const T &);
			Queue<T> & DeQueue(T &);
		private:
			Node<T> *front;
			Node<T> *rear;
	};

	template <class T>
	List<T>::~List()
	{
		Node<T> *next;
		while(first)
		{
			next=first->next;
			delete first;
			first=next;
		}
	}
	template <class T>
	int List<T>::Length() const
	{
		Node<T> *current=first;
		int len=0;
		while(current)
		{
			len++;
			current=current->next;
		}
		return len;
	}
	template <class T>
	bool List<T>::Retrieve(int k,T & x) const
	{
		if(k<1) return false;
		Node<T> *current=first;
		int index=1;
		while(index < k && current)
		{
			current=current->next;
			index++;
		}
		if(current)
		{
			x=current->data;
			return true;
		}
		return false;
	}
	template <class T>
	int List<T>::Locate (const T & x) const
	{
		Node<T> *current = first;
		int index = 1;
		while(current && current->data != x)
		{
			current = current->next;
			index++;
		}
		if(current)
			return index;
		return 0;
	}
	template <class T>
	List<T> & List<T>::Insert(int k,const T & x)
	{
		if( k < 0 ){exit(0);}
		Node<T> *p = first;
		for(int index = 1;index < k && p;index++)
			p=p->next;
		if( k > 0 && !p){ exit(0);}
		Node<T> *y = new Node<T>;
		y->data = x;
		if( k)
		{
			y->next = p->next;
			p->next = y;
		}
		else
		{
			y->next = first;
			first = y;
		}
		return *this;
	}
	template <class T>
	List<T> & List<T>::Delete (int k,T & x)
	{
		if(k < 1|| !first) {exit(0);}
		Node<T> *p = first;
		if( k == 1)
			first = first->next;
		else
		{
			Node<T> * q=first;
			for(int index = 1;index < k-1 && q;index++)
				q = q->next;
			if( !q || !q->next)
				exit(0);
			p = q->next;
			q->next = p->next;
		}
		x=p->data;
		delete p;
		return *this;
	}
	template <class T>
	void List<T>::PrintList(ostream & out) const
	{
		Node<T> * current;
		for(current = first;current ;current = current->next)
			out<<current->data<<"  ";
		out<<endl;
	}	
	template <class T>
	void List<T>::SPLIT(List<T> *& A,List<T> *& B) const
	{
		int i=3;
		A = new List<T>,B = new List<T>;
		Node<T> *pA,*pB,*temp;
		if( !first ) return ;
		A->first = pA = new Node<T>;
		pA->data = first->data;
		pA->next = 0;
		Node<T> * current=first->next;
		if( !current ) return ;
		B->first = pB = new Node<T>;
		pB->data = current->data;
		pB->next = 0;
		current = current ->next;
		while(current)
		{
			temp = new Node<T>;
			temp->data = current->data;
			temp->next = 0;
			if(i % 2)
			{
				pA->next = temp;
				pA = temp;
			}
			else
			{
				pB->next = temp;
				pB = temp;
			}
			current = current->next;
			i++;
		}
	}

	template <class T>
	Stack<T>::~Stack()
	{
		Node<T> *next;
		while(top)
		{
			next = top->next;
			delete top;
			top = next;
		}
	}
	template <class T>
	bool Stack<T>::Full () const
	{
		Node<T> *p = new Node<T>;
		if(!p) 
			return true;
		delete p;
		return false;
	}
	template <class T>
	T Stack<T>::Top() const
	{
		if(Empty()) 
			exit(0);
		return top->data;
	}
	template<class T>
	Stack<T> & Stack<T>::Push(const T & x)
	{
		Node<T> *p = new Node<T>;
		p->data = x;
		p->next = top;
		top = p;
		return *this;
	}
	template <class T>
	Stack<T> & Stack<T>::Pop(T & x)
	{
		if(Empty()) 
			exit(0);
		x = top->data;
		Node<T> *p = top;
		top = top->next;
		delete p;
		return *this;
	}

	template <class T>
	Queue<T>::~Queue()
	{
		Node<T> *next;
		while(front)
		{
			next = front->next;
			delete front;
			front =next;
		}
	}
	template <class T>
	bool Queue<T>::Full () const
	{
		Node<T> * p = new Node<T>;
		if(!p) 
			return true;
		return false;
	}
	template <class T>
	T Queue<T>::First () const
	{
		if(Empty()) 
			exit(0);
		return front->data;
	}
	template <class T>
	T Queue<T>::Last () const
	{
		if(Empty())
			exit(0);
		return rear->data;
	}
	template <class T>
	Queue<T> & Queue<T>::EnQueue (const T & x)
	{
		Node<T> * p = new Node<T>;
		p->data = x;
		p->next = 0;
		if(front) 
			rear->next = p;
		else 
			front = p;
		rear = p;
		return *this;
	}
	template <class T>
	Queue<T> & Queue<T>::DeQueue (T & x)
	{
		if(Empty()) 
			exit(0);
		x = front->data;
		Node<T> *p = front;
		front = front->next;
		delete p;
		return *this;
	}



class element
{
public:
	int x,y;
};
class StackElement
{
public:
	element *a;
	int n;
	int index;
};

void solve(Queue<element> *& A,Queue<element>*& B,Queue <element> *&Q)
{
	element e1,e2;
	A->DeQueue(e1);
	B->DeQueue(e2);
	while((!A->Empty()||e1.x > e2.x)&&(!B->Empty()||e1.x <= e2.x))
	{
		if(e1.x <= e2.x)
		{
			Q->EnQueue(e1);
			e2.x -= e1.x;
			A->DeQueue(e1);
		}
		else 
		{
			Q->EnQueue(e2);
			e1.x -= (e2.x + 1);
			B->DeQueue(e2);
		}		
	}
	if(e1.x <= e2.x)
	{
		Q->EnQueue(e1);
		e2.x -= e1.x;
		Q->EnQueue(e2);
		while(!B->Empty())
		{
			B->DeQueue(e1);
			Q->EnQueue(e1);
		}
	}
	else 
	{
		Q->EnQueue(e2);
		e1.x -= (e2.x + 1);
		Q->EnQueue(e1);
		while(!A->Empty())
		{
			A->DeQueue(e1);
			Q->EnQueue(e1);
		}
	}
}
void solve(element * a,int n,Queue <element> *&Q)
{
	Stack<StackElement> S1;
	Stack<Queue<element>*> S2;
	Queue <element> *q,*q1,*q2;
	StackElement  se,set;
	int k = 1,m = 0;
	se.a = a;
	se.n = n;
	se.index = 1;
	S1.Push(se);
	while(!S1.Empty())
	{
		S1.Pop(se);
		if(se.n > 2)
		{
			set.a = se.a;
			set.n = se.n / 2;
			set.index = se.index * 2;
			S1.Push(set);
			se.a += set.n;
			se.n -= set.n;
			se.index = set.index + 1;
			S1.Push(se);
		}
		else if(se.n == 1)
		{
			q = new Queue <element>;
			q->EnQueue(se.a[0]);
			while(!(se.index % 2))
			{
				q2 = new Queue <element>;
				S2.Pop(q1);
				solve(q,q1,q2);
				delete q;
				delete q1;
			    q = q2;
				se.index /= 2;
				if(se.index == 1)
					break;
			}
			S2.Push(q);
		}
		else if(se.n == 2)
		{
			q = new Queue <element>;
			q1 = new Queue <element>;
			q2 = new Queue <element>;
			q->EnQueue(se.a[0]);
			q1->EnQueue(se.a[1]);
			solve(q,q1,q2);
			delete q;
			delete q1;
			q = q2;
			while(!(se.index % 2))
			{
				q2 = new Queue <element>;
				S2.Pop(q1);
				solve(q,q1,q2);
				delete q;
				delete q1;
			    q = q2;
				se.index /= 2;
				if(se.index == 1)
					break;
			}
			S2.Push(q);
		}
	}
	S2.Pop(Q);
}
void main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n;
	Queue<element> *q;
	element e,*a;
	in>>n;
	a=new element[n];
	for(int i=0;i<n;i++)
	{
		in>>e.x;
		e.y = i + 1;
		a[i]=e;
	}
	solve(a,n,q);
	while(!q->Empty())
	{
		q->DeQueue(e);
		out<<e.y<<" ";
	}
	delete q;
	delete [] a;
}