链表类模板的实现

任务描述

本关任务：实现双向链表类模板。

相关知识

为了完成本关任务，你需要掌握：1.复习C语言链表的实现。2.对链表的数据属性和功能进行封装。3.利用模板实现数据类型的参数化。
主程序main()中定义通用算法如下：

1. template<class Iterator> //在指定范围内输出元素
2. void display(Iterator first, Iterator last)
3. {
4. for (; first != last; ++first)
5. cout << *first << ' ';
6. cout << endl;
7. }

该算法能够输出链表模板类对象中存放的元素。

编程要求

根据提示，在右侧编辑器补充代码，实现链表类模板的定义。

测试说明

平台会对你编写的代码进行测试：

预期输出：
109 108 107 106 105 104 103 102 101 100
108 107 106 105 104 103 102 101 100
108 107 106 105 104 103 102 101 100
38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0 108 107 106 105 104 103 102 101 100
36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0 108 107 106 105 104 103 102 101 100
36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0 108 107 106 105 104 103 102 101 100

/***************Node结点的定义************/
/*************Begin**********************/
template<class T>
struct Node
{
    T data;
    Node<T>* prev, * next;
    Node(T d = 0, Node<T>* p = NULL, Node<T>* n = NULL) :data(d), prev(p), next(n) {}
};




/************End************************/

/***************迭代器的定义************/
/*************Begin**********************/
template<class T> class List;

template<class T>
class const_iterator
{
protected:
    Node<T>* current;
    T& retrive()const { return current->data; }
    
    const_iterator(Node<T>* p) :current(p) {}
    friend class List<T>;
public:
 
    const_iterator() :current(NULL) {}
   
    const T& operator*()const { return retrive(); }
  
    const_iterator& operator++()
    {
        current = current->next;
        return *this;
    }
    
    const_iterator operator++(int)
    { 
       
        const_iterator old = *this;
      
        ++(*this);
        return old;
    }
    
    const_iterator& operator--()
    {
        current = current->prev;
        return *this;
    }
  
    const_iterator operator--(int)
    {
        
        const_iterator old = *this;
     
        --(*this);
        return old;
    }
    
    bool operator==(const const_iterator& rhs)const
    {
        return current == rhs.current;
    }
 
    bool operator!=(const const_iterator& rhs)const
    {
        return current != rhs.current;
    }
};
template<class T> class List;

template<class T>
class iterator : public const_iterator<T>
{
protected:
 
    iterator(Node<T>* p) :const_iterator<T>(p) {}
    friend class List<T>;
public:
    iterator() {};

    T& operator*()
    {
        return const_iterator<T>::retrive();
    }
    
    const T& operator*()const
    {
        return const_iterator<T>::operator*();
    }
    
    iterator& operator++()
    {
        const_iterator<T>::current = const_iterator<T>::current->next;
        return *this;
    }
 
    iterator operator++(int)
    {
       
        iterator old = (*this);
      
        ++(*this);
        return old;
    }
    iterator& operator--()
    {
        const_iterator<T>::current = const_iterator<T>::current->prev;
        return *this;
    }

    iterator operator--(int)
    {

        iterator old = *this;
        --(*this);
        return old;
    }

};



/************End************************/
/***************链表类模板的定义************/
/*************Begin**********************/
template<class T>
class List
{
private:
    Node<T>* head;
    Node<T>* tail;
    int size;
   
    void init()
    {
        head = new Node<T>;
        tail = new Node<T>;
        size = 0;
        
        head->next = tail;
        tail->prev = head;
    }
public:

    List() { init(); }
    
    List(const List<T>& l)
    {
     
        init();
     
        operator=(l);
    }

    const List& operator=(const List& L);

    iterator<T> Begin() { return iterator<T>(head->next); }
    const_iterator<T> Begin()const { return const_iterator<T>(head->next); }
   
    iterator<T> End() { return iterator<T>(tail); }
    const_iterator<T> End()const { return const_iterator<T>(tail); }
    
    T& front() { return *Begin(); }
    const T& front() const { return *Begin(); }
    
    T& back() { return *(--End()); }
    const T& back()const { return *(--End()); }
  
    void push_front(const T& item)
    {
        Insert(Begin(), item);
    }
    
    void push_back(const T& item)
    {
        Insert(End(), item);
    }

    void pop_front()
    {
        Erase(Begin());
    }
   
    void pop_back()
    {
        Erase(--End());
    }
 
    iterator<T> Erase(iterator<T> itr);
  
    iterator<T> Insert(iterator<T> itr, const T& item);
   
    int Size()const { return size; }
  
    bool empty()const { return size == 0; }

    void clear() { while (!empty()) { pop_front(); } }
};

template<class T>
iterator<T> List<T>::Insert(iterator<T> itr, const T& item)
{
   
    Node<T>* p = itr.current;
    p->prev->next = new Node<T>(item, p->prev, p);
    p->prev = p->prev->next;
    size++;
   
    return iterator<T>(p->prev);
}


template<class T>
iterator<T> List<T>::Erase(iterator<T> itr)
{
    
    Node<T>* p = itr.current;
    iterator<T> re(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    size--;
    return re;
}


template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
   
    clear();
  
    for (const_iterator<T> itr = L.Begin(); itr != L.End(); ++itr)
    {
        push_back(*itr);
    }
    return *this;
}




/************End************************/