inver.cpp

设计一个算法

#include <fstream.h>
#include <Stdlib.h>
//declaration
template <class T>
class List;

template <class T>
class Node{
	friend class List<T>;
private:
	T data;
	Node<T> *next;
};

template <class T>
class List{
	private:
		Node<T> *first;
		int n;
	public:
		List(){first=0; n=0;}
		~List();
		bool Empty()const{return first==0;}
		int Length()const{return n;}
		List<T>& Insert(int k,const T &x);
		void PrintList()const;
};
template <class T>
List<T>::~List()
{
	Node<T> *next;
	while(first){
		next=first->next;
		delete first;
		first=next;
	}
}

template <class T>
List<T>& List<T>::Insert(int k,const T &x)
{
	if(k<0){
		cout<<"OutOfBounds"<<endl;
		exit(1);
	}
	Node<T> *p=first;
	for(int index=1;index<k&&p;index++)
		p=p->next;
	if(k>0&&!p){
		cout<<"OutOfBounds"<<endl;
		exit(1);
	}
	Node<T> *y=new Node<T>;
	y->data=x;
	if(k){
		y->next=p->next;
		p->next=y;
	}
	else{
		y->next=first;
		first=y;
	}
	n++;
	return *this;
}
template <class T>
void List<T>::PrintList()const
{
	ofstream cout("output.txt");
	Node<T> *current;
	for(current=first;current;current=current->next)
		cout<<current->data<<' ';
	cout<<endl;
}

void main(){
	ifstream cin("input.txt");
	ofstream cout("output.txt");
	int n;
	cin>>n;
	int *p=new int[n+1];
	for(int i=1;i<=n;i++)
		cin>>p[i];
	List<int> l;
	for(i=n;i>0;i--)
	{
		if(p[i]>l.Length())
			l.Insert(l.Length(),i);
		else l.Insert(p[i],i);
	}
	l.PrintList();
}