inver_first.cpp

设计一个算法

#include<iostream>
#include<fstream>
template<class T>
class List;
template<class T>
class Node{
    private:
        T m;
        T n;
        Node<T> *next;
        Node<T> *pre;
    public:
        Node<T>* Insert(Node<T> &x);
        friend class List<T>;        
        friend std::ofstream &operator<<(std::ofstream &fout,Node<int> &node);       
};
template<class T>
Node<T>* Node<T>::Insert(Node<T>&x)
{
    if(m<=x.m){
        x.m-=m;
        if(next)
            next->Insert(x);
        else{
            next=&x;
            x.pre=this;
        }
        return this;
    }
    else{
        m=m-x.m-1;
        x.next=this;
        x.pre=pre;
		if(pre)pre->next=&x;
        pre=&x;
        return &x;
    }
}
std::ofstream &operator<<(std::ofstream &fout,Node<int> &node)
{
	fout<<node.n;
	return fout;
}
template<class T>
class List{
    private:
        Node<T>*first;
    public:
        List(){first=0;}
        ~List();
        void Insert(std::ifstream &fin,int now);
        bool Empty()const{return first==0;}
        void Output(std::ofstream &fout);
};
template<class T>
List<T>::~List()
{
    Node<T> *next;
    while(first){
        next=first->next;
        delete first;
        first=next;
    }
}
template<class T>
void List<T>::Insert(std::ifstream &fin,int now)
{
    Node<T> *newnode=new Node<T>;
    fin>>newnode->m;
    newnode->n=now;
    newnode->next=newnode->pre=0;
    if(!first)        
        first=newnode; 
    else        
        first=first->Insert(*newnode);    
}
template<class T>
void List<T>::Output(std::ofstream &fout)
{
    Node<T> *p=first;
    if(!first)
        fout<<"list is empty"<<std::endl;
    else{
        while(first->next){
            fout<<(*first)<<" ";
            first=first->next;
        }
        fout<<(*first)<<std::endl;
    }
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"open error"<<endl;
        exit(1);
    }
    int n;
    while(fin>>n){
        int now=1;
        List<int> inver;
        while(n--)
            inver.Insert(fin,now++);
        inver.Output(fout);
    }
    fin.close();
    fout.close();    
    return 0;
}