数据结构基础(10) --单链表迭代器的设计与实现(一)

为了向 STL 致敬(O(∩_∩)O~), 我们模仿STL中的list的迭代器, 我们也自己实现一个MyList的迭代器, 以供遍历整个链表的所有元素:

首先:Node节点需要做如下修改(注意后缀有+的代码)

//链表节点
template 
  
   
class Node
{
    friend class MyList
   
    ; friend class ListIterator
    
     ; //+ template 
     
       friend ostream &operator<<(ostream &os, const MyList
      
        &list); private: Node(const Type &dataValue):data(dataValue), next(NULL) {} Type data; //数据域:节点数据 Node *next; //指针域:下一个节点 };
      
     
    
   
  

然后:MyList类同样也需要做修改,但是由于MyList类过长, 修改之处也较少, 因此在此就不贴出, 完整代码会附到博客最后

ListIterator的设计

template 
  
   
class ListIterator
{
public:
    ListIterator(const MyList
   
     &_list): list(_list), currentNode((_list.first)->next) {} //重载 *operator const Type &operator*() const throw (std::out_of_range); Type &operator*() throw (std::out_of_range); //重载 ->operator const Node
    
      *operator->() const throw (std::out_of_range); Node
     
       *operator->() throw (std::out_of_range); //重载 ++operator ListIterator &operator++() throw (std::out_of_range); //注意:此处返回的是值,而不是reference ListIterator operator++(int) throw (std::out_of_range); bool isEmpty() const; private: const MyList
      
        &list; Node
       
         *currentNode; };
       
      
     
    
   
  

ListIterator类的实现

template 
  
   
const Type &ListIterator
   
    ::operator*() const throw (std::out_of_range) { if (isEmpty()) throw std::out_of_range("iterator is out of range"); // 返回当前指针指向的内容 return currentNode->data; } template 
    
      Type &ListIterator
     
      ::operator*() throw (std::out_of_range) { //首先为*this添加const属性, //以调用该函数的const版本, //然后再使用const_case, //将该函数调用所带有的const属性转除 //operator->()的non-const版本与此类同 return const_cast
      
       ( static_cast
       
         &>(*this).operator*() ); }
       
      
     
    
   
  

template 
  
   
const Node
   
     *ListIterator
    
     ::operator->() const throw (std::out_of_range) { if (isEmpty()) throw std::out_of_range("iterator is out of range"); //直接返回指针 return currentNode; } template 
     
       Node
      
        *ListIterator
       
        ::operator->() throw (std::out_of_range) { // 见上 return const_cast
        
          *> ( static_cast
         
           >(*this).operator->() ); }
         
        
       
      
     
    
   
  

template 
  
   
ListIterator
   
     &ListIterator
    
     ::operator++() throw (std::out_of_range) { if (isEmpty()) throw std::out_of_range("iterator is out of range"); //指针后移 currentNode = currentNode->next; return *this; } template 
     
       ListIterator
      
        ListIterator
       
        ::operator++(int) throw (std::out_of_range) { ListIterator tmp(*this); ++ (*this); //调用前向++版本 return tmp; }
       
      
     
    
   
  

//判空
template 
  
   
bool ListIterator
   
    ::isEmpty() const { if (currentNode == NULL) return true; return false; }
   
  

附-ListIterator测试代码:

int main()
{
    std::list
  
    iStdList;
    MyList
   
     iMyList; for (int i = 0; i < 10; ++i) { iStdList.push_back(i+1); iMyList.insert(i+1, i+1); } for (std::list
    
     ::iterator iter = iStdList.begin(); iter != iStdList.end(); ++ iter) { cout << *iter << ' '; } cout << endl; for (ListIterator
     
       iter(iMyList); !iter.isEmpty(); ++ iter) { cout << *iter << ' '; } cout << endl; cout << "Test: \n\t" << iMyList << endl; ListIterator
      
        iter(iMyList); cout << "first = " << *iter << endl; }
      
     
    
   
  

附-MyList完整源代码

//MyList.h
#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED

#include 
  
   
#include 
   
     using namespace std; //前向声明 template 
    
      class MyList; template 
     
       class ListIterator; //链表节点 template 
      
        class Node { //可以将MyList类作为Node的友元 //同时也可以将Node类做成MyList的嵌套类, 嵌套在MyList中, 也可以完成该功能 friend class MyList
       
        ; friend class ListIterator
        
         ; template 
         
           friend ostream &operator<<(ostream &os, const MyList
          
            &list); private: //constructor说明: //next = NULL; //因为这是一个新生成的节点, 因此下一个节点为空 Node(const Type &dataValue):data(dataValue), next(NULL) {} Type data; //数据域:节点数据 Node *next; //指针域:下一个节点 }; //链表 template 
           
             class MyList { template 
            
              friend ostream &operator<<(ostream &os, const MyList
             
               &list); friend class ListIterator
              
               ; public: MyList(); ~MyList(); //将元素插入表头 void insertFront(