inver.cpp

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

#include<iostream.h>
#include<fstream.h>
template<class T> class Queue;//为了下面的模板中用到的friend Queue;
template<class T>//队伍用到的指针
class Node{
	friend Queue;
	public:
		T data;
		Node<T> *next;
};
class Dui//定义一种新的类型，用于存放串
{
public:
	int x,y;
};
template<class T>//定义队伍
class Queue{
	public:
		Queue(){front=rear=0;}
		Queue<T>&EnQueue(const T&x);
		Queue<T>&DeQueue(T&x);
    private:
		Node<T>*front;
		Node<T>*rear;
};
template<class T>
Queue<T>&Queue<T>::DeQueue(T&x)
{
	x=front->data;
	Node<T>*p=front;
	front=front->next;
	delete p;
	return *this;
};
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;
};
void main()//主函数
{   ifstream input("input.txt");
    ofstream output("output.txt");
	int n,p;p=0;//判断循环是否开始的量
	input>>n;
	Dui a,m,q;//定义新类型的变量和数组
	Dui * L;//新类型数组
	L=new Dui[n+1];
	Queue<Dui>Q;
for(int i=0;i<n;i++)
{
	input>>a.x;
		a.y=i+1;
Q.EnQueue(a);//入队伍
}
for(int h=0;h<n;h++)
{
	Q.DeQueue(m);
	L[h]=m;p=p+1;//将出队的元素放进数组中以进行比较
	if(p>1)//判断循环是否进行的变量，只作用一次
{for(int j=0;j<h;j++)
{   
	if(L[j].x<=L[h].x)
	{L[h].x=L[h].x-L[j].x;continue;}//继续j的自加循环扫描，直到j<h
//	if(L[j].x==L[h].x&&L[h].x==0) continue;//继续扫描
	if(L[j].x>L[h].x)
{  q=L[h];L[j].x=L[j].x-L[h].x-1;
	for(int k=h;k>j;k--)
	{
		L[k]=L[k-1];//将数组中除L[j]都向后移动一个位置
	}L[j]=q;//将刚出队伍并比较过的元素放到L[j]中
break;}//跳出循环
}
}
}
for(int c=0;c<n;c++)
		output<<L[c].y<<" ";//输出各原始位置
}