inver.cpp

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

#include <iostream>
#include <fstream>
using namespace std;
template <class T> 
class Queue;
template <class T>
class Node
{
        friend Queue<T>;
		private:
			T data;
			Node<T> *next;
};
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>
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;
};
void ftwo(Queue<element> &s,Queue<element> &t,Queue<element> &r)
{
	element e1,e2;
	s.DeQueue(e1);
	t.DeQueue(e2);
	while(!(s.Empty()&&e1.x<=e2.x||t.Empty()&&e1.x>e2.x))
	{
		if(e1.x<=e2.x)
		{
			r.EnQueue(e1);
			e2.x-=e1.x;
			s.DeQueue(e1);
		}
		else
		{
			r.EnQueue(e2);
			e1.x-=(e2.x+1);
			t.DeQueue(e2);
		}
	}
    if(e1.x<=e2.x)//当s串为空
	{
		r.EnQueue(e1);
		e2.x-=e1.x;
		r.EnQueue(e2);
		while(!t.Empty())
		{
			t.DeQueue(e2);
            r.EnQueue(e2);
		}
	}
	else//当t串为空
	{
		r.EnQueue(e2);
		e1.x-=(e2.x+1);
        r.EnQueue(e1);
		while(!s.Empty())
		{
			s.DeQueue(e1);
			r.EnQueue(e1);
		}
	}
}
void findper(Queue<element> &s,Queue<element> &t,Queue<element> &r,int n,element *b)
{
	    if(n==0) ftwo(s,t,r);
		else if(n==1) r.EnQueue(b[0]);
	    else if(n==2) 
		{
			if(b[0].x<=b[1].x)
			{
				r.EnQueue(b[0]);
				b[1].x-=b[0].x;
				r.EnQueue(b[1]);
			}
			else
			{
				r.EnQueue(b[1]);
				b[0].x-=(b[1].x+1);
				r.EnQueue(b[0]);
			}
		}
		else
		{
			int m=n/2;
			n-=m;
			Queue<element> r1,r2;
			findper(s,t,r1,m,b);
			findper(s,t,r2,n,b+m);
			ftwo(r1,r2,r);
		}
}
void main()
{
    int n;
	element e,*b;
	Queue<element> s,t,r;
	ifstream in("input.txt");
    ofstream out("output.txt");
	in>>n;
    b=new element[n];
    for(int i=0;i<n;i++)
	{
		in>>e.x;
	    e.y=i+1;
		s.EnQueue(e);
		b[i]=e;
	}
    findper(s,t,r,n,b);
	while(!r.Empty())
    {
		r.DeQueue(e);
	    out<<e.y<<" ";
	}
}