学步园

最近要考数据结构了，哎，这么大了还考试，真烦。既然自己干这行的，数据结构又是那么基础和必要的东西，所以决定把一些数据结构用C++重写一遍，也算是加深学习吧。

说实话，真是没怎么写过这么基础的数据结构，如果有什么缺陷请大家多多提意见。日后还会继续写其他的

今天，给List加入了迭代器，可能会在今后的使用中更通用化

 

 

  1#pragma once;
  2template<typename T>
  3struct mynode
  4{
  5    mynode()
  6        :pNext(NULL),
  7        pPrior(NULL){}
  8
  9    T data;
 10    mynode<T> * pNext;    
 11    mynode<T> * pPrior;
 12};
 13
 14template<typename T>
 15class mylist
 16{
 17public:
 18    struct Iterator
 19    {
 20        explicit Iterator(mynode<T>* p)
 21            :m_pCurrent(p)
 22        {}
 23        
 24
 25        Iterator& operator ++()
 26        {
 27            m_pCurrent = m_pCurrent->pNext;
 28            return *this;
 29        }
 30
 31        Iterator operator ++(int)
 32        {
 33            mynode<T>* p = m_pCurrent;
 34            m_pCurrent = m_pCurrent->pNext;
 35            return Iterator(p);
 36        }
 37
 38        Iterator& operator --()
 39        {
 40            m_pCurrent = m_pCurrent->pPrior;
 41            return *this;
 42        }
 43
 44        Iterator operator --(int)
 45        {
 46            mynode<T>* p = m_pCurrent;
 47            m_pCurrent = m_pCurrent->pPrior;
 48            return Iterator(p);
 49        }
 50
 51        bool operator == (const Iterator& it)
 52        {
 53            return m_pCurrent == it.m_pCurrent;
 54        }
 55
 56        bool operator != (const Iterator& it)
 57        {
 58            return !(*this == it);
 59        }
 60
 61        T& operator*()
 62        {
 63            return m_pCurrent->data;
 64        }
 65
 66        bool hasNext()
 67        {
 68            return m_pCurrent!= NULL && m_pCurrent->pNext != NULL;
 69        }
 70        friend class mylist;
 71    private:
 72        mynode<T>* m_pCurrent;
 73        Iterator(){};
 74    };    
 75    mylist()
 76    {
 77        m_pHead = new mynode<T>();
 78        m_pTail = new mynode<T>();
 79        
 80        m_pHead->pNext = m_pTail;
 81        m_pTail->pPrior = m_pHead;
 82        
 83    }
 84
 85    ~mylist()
 86    {
 87        _Destory();
 88    }
 89
 90    //向尾部插入新节点
 91    void push_back(const T & data)
 92    {
 93        _insert(m_pTail->pPrior, data);
 94    }
 95
 96
 97
 98    Iterator insert(Iterator pWhere, const T& data)
 99    {
100        if(!isNode(pWhere.m_pCurrent))
101        {
102            return Iterator(NULL);
103        }
104
105        return Iterator(_insert(pWhere.m_pCurrent, data));
106    }
107
108    //向任意位置之后插入新节点
109    
110    //删除指定位置的节点
111    bool remove(Iterator iWhere)
112    {
113        mynode<T>* pWhere = iWhere.m_pCurrent;
114        if(pWhere == NULL)
115        {
116            return false;
117        }
118
119        if(empty())
120        {
121            return false;
122        }
123
124        if(isHead(pWhere) || isTail(pWhere))
125        {
126            return false;
127        }
128        
129
130        if(!isNode(pWhere))
131        {
132            return false;
133        }
134
135        pWhere->pPrior->pNext = pWhere->pNext;
136        pWhere->pNext->pPrior = pWhere->pPrior;
137        
138
139
140        delete pWhere;
141
142        return true;
143    }
144
145    Iterator begin()
146    {
147        return Iterator(m_pHead->pNext);
148    }
149
150    Iterator end()
151    {
152        return Iterator(m_pTail);
153    }
154    
155
156    //查找指定数据在链表中的位置
157    Iterator find(const T &data)
158    {
159        if(empty())
160        {
161            return Iterator(m_pTail);
162        }
163
164        mynode<T>* p = m_pHead->pNext;
165
166        while(!isTail(p))
167        {
168            if(p->data ==