数据结构基础(12) --双向循环链表的设计与实现(二)

查看是否存在于链表中:

template 
  
   
bool DoubleList
   
    ::search(const Type &searchData) const { DoubleListNode
    
      *searchNode = first->next; while (searchNode != first) { if (searchNode->data == searchData) return true; searchNode = searchNode->next; } return false; }
    
   
  

输出链表所有元素(测试用):

template 
  
   
ostream &operator<<(ostream &os, const DoubleList
   
     &list) { for (DoubleListNode
    
      *currentNode = (list.first)->next; currentNode != list.first; currentNode = currentNode->next) os << currentNode->data << ' '; return os; }
    
   
  

双向循环链表迭代器的设计与实现:

//除了添加了operator--, 几乎没做任何改变
template 
  
   
class ListIterator
{
public:
    ListIterator(const DoubleList
   
     &_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 DoubleListNode
    
      *operator->() const throw (std::out_of_range); DoubleListNode
     
       *operator->() throw (std::out_of_range); //重载 ++operator ListIterator &operator++() throw (std::out_of_range); //注意:此处返回的是值,而不是reference ListIterator operator++(int) throw (std::out_of_range); //重载 --operator, // 其实这个版本的--operator是不完美的, // 因为他没有做任何的判错控制 ListIterator &operator--(); //注意:此处返回的是值,而不是reference ListIterator operator--(int); bool isEmpty() const { return (currentNode == list.first); } private: const DoubleList
      
        &list; DoubleListNode
       
         *currentNode; };
       
      
     
    
   
  

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) { return const_cast
      
       ( static_cast
       
         &>(*this).operator*() ); }
       
      
     
    
   
  

template 
  
   
const DoubleListNode
   
     *ListIterator
    
     ::operator->() const throw (std::out_of_range) { if (isEmpty()) throw std::out_of_range("iterator is out of range"); //直接返回指针 return currentNode; } template 
     
       DoubleListNode
      
        *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 
  
   
ListIterator
   
     &ListIterator
    
     ::operator--() { //指针前移 currentNode = currentNode->prev; return *this; } template 
     
       ListIterator
      
        ListIterator
       
        ::operator--(int) { ListIterator
        
          tmp(*this); -- (*this); return tmp; }
        
       
      
     
    
   
  

测试代码:

int main()
{
    cout << "-------- 1 --------" << endl;
    DoubleList
  
    myList;

    for (int i = 0; i < 3; ++i)
        myList.push_back(i+1);
    for (int i = 0; i < 5; ++i)
        myList.push_front(10+i);
    for (int i = 0; i < 3; ++i)
        myList.push_back(i+1);

    ListIterator
   
     iter(myList), iter2(myList); while (!iter.isEmpty()) { cout << *iter << ' '; ++ iter; ++ iter2; } cout << endl; -- iter2; while (!iter2.isEmpty()) { cout << *iter2 << ' '; iter2 --; } cout << endl; cout << "-------- 2 --------" << endl; cout << myList << endl; cout << "Test insert..." << endl; myList.insert(1, 14); myList.insert(2, 13); myList.insert(2, 13); myList.insert(88, 88); cout << myList << endl; myList.pop_back(); myList.pop_front(); cout << myList << endl; for (int i = 0; i < 5; ++i) { if (myList.search(i)) cout << i << ": Have found!" << endl; else cout << i << ": Not in the list!" << endl; } cout << "Test remove..." << endl; cout << myList << endl; int value; while (cin >> value) { try { myList.remove(value); } catch (const std::exception &e) { cerr << e.what() << endl; } cout << myList << endl; if (myList.isEmpty()) { cout << "empty" << endl; } else { cout << "not empty" << endl; } } return 0; }