双向链表下的简单迭代器实现

缺乏、安全感 2022-06-05 10:22 171阅读 0赞

因为实验课上要求用迭代器实现链表的逆序输出，所以采用双向链表，加个简单的迭代器。

#include<iostream>
    #include<cmath>
    using namespace std;
    //*******************************************************
    //链表的节点结构 ,此处用的双向链表 
    //*******************************************************
    template <class T>
    struct chainNode
    {
     T element;
     chainNode<T> *next;//后节点
     chainNode<T> *pre;//前节点
     chainNode(){}
     chainNode(const T& element)
     {this->element=element;
     }
     chainNode(const T& element,chainNode<T>* next,chainNode<T>* pre)
     {
      this->element=element;
      this->next=next;
      this->pre=pre;
     }
    }; 
    
    //*****************************************************************
    //线性表类 
    //*****************************************************************
    template<class T>
    class linearList
    { friend class sparseMatrix;
       public:
     
     linearList();
     //linearList(const chain<T>&);
     ~linearList(){};
    //************************************** 
    //
     void empty() const
     {   if(listSize==0)
      cout<<"yes,it's empty";
      else
      cout<<"no,it's not empty";
     } 
    //**********************************************
     int size() const
     {  
       return listSize;
     }
    //**********************************************
     T& get(int theIndex) const
     { 
       if(theIndex<listSize)
       {
        chainNode<T>* currentNode=firstNode;
        for(int i=0;i<theIndex;i++)
        {
         currentNode=currentNode->next;
        }
      return currentNode->element;
       }  
       else
       {
        cout<<"enter a correct number:";
       }
     }
    //************************************************** 
     int indexOf(const T& theElement) const
     {
            chainNode<T>* currentNode=firstNode;
      int i=0;
      while(currentNode!=NULL&¤tNode->element!=theElement)
      {   currentNode=currentNode->next;
          i++;
      }  
      if(currentNode==NULL)//线性表中不存在此元素 
      return -1; 
      else
      return i;
     }
     //void erase(int theIndex);
    //***************************************************** 
     void erase(int theElement)
     {   if(listSize<=0)//如果线性表为空 
           cout<<"it's empty"<<endl;
         else if(listSize==1)//如果表中只有一个元素 
              { if(firstNode->element==theElement)//当表头为所要删除的元素时 
          {
       firstNode=lastNode=NULL;
          listSize--;
       }
       else
       cout<<"there is not theElement"<<endl;
           }
         else//多个元素的情况 
      { if(firstNode->element==theElement)//如果第一个元素为要删除的元素 
         {firstNode=firstNode->next;
          firstNode->pre=NULL;
          listSize--;
         }
        else if(lastNode->element==theElement)//如果最后一个元素为要删除的元素 
          {lastNode=lastNode->pre;
           lastNode->next=NULL;
           listSize--;
          }
        else{//其他情况 
       chainNode<T>* currentNode=firstNode->next;
       chainNode<T>* p=firstNode;
       while(currentNode!=NULL&¤tNode->element!=theElement)//元素不相等就继续循环 
        { 
          currentNode=currentNode->next;
       p=p->next; 
           } 
       if(currentNode==NULL)//如果线性表中没有这个元素 
       cout<<"there is no thelement in it"<<endl;
       else
        {currentNode->pre->next=currentNode->next;
         currentNode->next->pre=currentNode->pre;
         //p->next=currentNode->next;
         listSize--; 
        }
         }
      }
         
     }
    //****************************************************************此插入方法为从表头插入，所以正向输出的时候是和你输进去的方向反的
    // void insert(int theIndex,const T& theElement);
     void insert(int theElement)
     { if(firstNode==NULL)
        { 
          firstNode=new chainNode<T>(theElement,firstNode,NULL);
          lastNode=firstNode;
        } 
       else
       {
        chainNode<T>* currentNode=new chainNode<T>(theElement,NULL,NULL);
        firstNode->pre=currentNode;
           currentNode->next=firstNode;
            firstNode=currentNode;
       }
       listSize++;
     }
     
    //***************************************
    //迭代器类 
    //****************************************
     class iterator
     {
      public:
       iterator(chainNode<T>* theNode=NULL)
       { node=theNode;
       }
       T& operator*() const {return node->element;}//取值
       T* operator->() const{return &node->element;}
         iterator& operator++()
       {
        node=node->next;
        return *this;
       }
       iterator& operator--()
       {
        node=node->pre;
        return *this;
       }
       bool operator!=(const iterator right)const
       {
        return node !=right.node;
       }
       bool operator==(const iterator right)const
       {
        return node==right.node;
       }
       
      private:
        chainNode<T>* node;
     };
    //******************************************************* 
     iterator begin()//头指针 
       {
         return iterator(firstNode);
       }
       
     iterator end()//尾指针 
       {
        return iterator(lastNode);
       } 
    //********************************************************
    //未使用迭代器的输出函数
    //******************************************************
     /*void output() const
     {  if(listSize==NULL)//如果链表为空 
         cout<<"it's empty"<<endl; 
          chainNode<T>* currentNode=firstNode;
       while(currentNode!=NULL)
         {    cout<<currentNode->element;
          currentNode=currentNode->next; 
      } 
     }*/
    //*******************************
    //使用迭代器的输出函数，使用迭代器就比较方便了，特别是反序的时候
    //******************************** 
     void output()//正序输出 
     {
        for(iterator iter=begin();iter!=NULL;++iter) 
        cout<<*iter<<" ";
        cout<<endl;
     } 
    //反序输出 
     void reoutput()
     {
      for(iterator iter=end();iter!=NULL;--iter)
      cout<<*iter<<" ";
      cout<<endl;
     }
    //************************************************
    void sort()
    { linearList<T> c;
      for(iterator i=begin();*i!=NULL;++i)
      {   T min=*i,r;
        for(iterator j=++i;*j!=NULL;++j)
       {
       if(min>*j)
     {
      min=*j;
      r=min;
        } 
       }
       erase(r);
       insert(min);
      }
      c.reoutput();
    }
    //***************************************************
    //两个有序链表使用迭代器的归并，
    //*************************************************** 
     void merge(linearList<T> a,linearList<T> b)
    {
     linearList<T> c;
     if(a.size()==0&&b.size()==0)//都为空时
     cout<<"they are null";
     else if(a.size()==0)//有一个为空时
     c=b;
     else if(b.size()==0)
     c=a;
     else
     {
      iterator i=a.begin();
      iterator j=b.begin();
      while(i!=NULL&&j!=NULL)
      {
      if(*i<*j)
      {c.insert(*i);
       ++i;
      }
      else
      {c.insert(*j);
       ++j;
      }
         }
         if(i==NULL)
        {
      while(j!=NULL)
      {
       c.insert(*j);
       ++j;
      }
        }
      else 
     { while(i!=NULL)
      {
      c.insert(*i);
      ++i;
      } 
     }
     }
      c.reoutput();
    }
    //********************************* 
    //数据成员
    //******************************** 
     private:
      int listSize;
      chainNode<T>* firstNode;
      chainNode<T>* lastNode;
    };
    //**************************************8
    template<class T>
    linearList<T>::linearList()
    {
     //if(initialCapicity<1)
     //cout<<"the length must be >0"; 
      listSize=0;
     firstNode=lastNode=NULL;
    }
    //******************************************