為了向?STL 致敬(O(∩_∩)O~), 我們模仿STL中的list的迭代器,?我們也自己實現一個MyList的迭代器,?以供遍歷整個鏈表的所有元素:

首先:Node節點需要做如下修改(注意后綴有+的代碼)

//鏈表節點 template <typename Type> class Node {friend class MyList<Type>;friend class ListIterator<Type>; //+template <typename T>friend ostream &operator<<(ostream &os, const MyList<T> &list); private:Node(const Type &dataValue):data(dataValue), next(NULL) {}Type data; //數據域:節點數據Node *next; //指針域:下一個節點 };

然后:MyList類同樣也需要做修改,但是由于MyList類過長,?修改之處也較少,?因此在此就不貼出,?完整代碼會附到博客最后

?

ListIterator的設計

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

ListIterator類的實現

template <typename Type> const Type &ListIterator<Type>::operator*() const throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");// 返回當前指針指向的內容return currentNode->data; }template <typename Type> Type &ListIterator<Type>::operator*() throw (std::out_of_range) {//首先為*this添加const屬性,//以調用該函數的const版本,//然后再使用const_case,//將該函數調用所帶有的const屬性轉除//operator->()的non-const版本與此類同returnconst_cast<Type &>(static_cast<const ListIterator<Type> &>(*this).operator*()); }
template <typename Type> const Node<Type> *ListIterator<Type>::operator->() const throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");//直接返回指針return currentNode; }template <typename Type> Node<Type> *ListIterator<Type>::operator->() throw (std::out_of_range) {// 見上returnconst_cast<Node<Type> *> (static_cast<const ListIterator<Type> >(*this).operator->()); }
template <typename Type> ListIterator<Type> &ListIterator<Type>::operator++() throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");//指針后移currentNode = currentNode->next;return *this; } template <typename Type> ListIterator<Type> ListIterator<Type>::operator++(int) throw (std::out_of_range) {ListIterator tmp(*this);++ (*this); //調用前向++版本return tmp; }
//判空 template <typename Type> bool ListIterator<Type>::isEmpty() const {if (currentNode == NULL)return true;return false; }

附-ListIterator測試代碼:

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

附-MyList完整源代碼

//MyList.h #ifndef MYLIST_H_INCLUDED #define MYLIST_H_INCLUDED#include <iostream> #include <stdexcept> using namespace std;//前向聲明 template <typename Type> class MyList; template <typename Type> class ListIterator;//鏈表節點 template <typename Type> class Node {//可以將MyList類作為Node的友元//同時也可以將Node類做成MyList的嵌套類, 嵌套在MyList中, 也可以完成該功能friend class MyList<Type>;friend class ListIterator<Type>;template <typename T>friend ostream &operator<<(ostream &os, const MyList<T> &list); private://constructor說明://next = NULL; //因為這是一個新生成的節點, 因此下一個節點為空Node(const Type &dataValue):data(dataValue), next(NULL) {}Type data; //數據域:節點數據Node *next; //指針域:下一個節點 };//鏈表 template <typename Type> class MyList {template <typename T>friend ostream &operator<<(ostream &os, const MyList<T> &list);friend class ListIterator<Type>; public:MyList();~MyList();//將元素插入表頭void insertFront(const Type &data);//將元素插入到位置index上(index從1開始)void insert(const Type &data, int index);//刪除表中所有值為data的節點void remove(const Type &data);bool isEmpty() const;//鏈表反轉void invort();//將鏈表(list)鏈接到本條鏈表的末尾void concatenate(const MyList<Type> &list);private://指向第一個節點的指針Node<Type> *first; };template <typename Type> MyList<Type>::MyList() {//first指向一個空節點first = new Node<Type>(0);first -> next = NULL; } template <typename Type> MyList<Type>::~MyList() {Node<Type> *deleteNode = NULL;while (first != NULL){deleteNode = first;first = first -> next;delete deleteNode;} }template <typename Type> void MyList<Type>::insertFront(const Type &data) {Node<Type> *newNode = new Node<Type>(data);newNode -> next = first -> next;first -> next = newNode; }template <typename Type> void MyList<Type>::insert(const Type &data, int index) {//由于我們在表頭添加了一個空節點//因此如果鏈表為空, 或者在鏈表為1的位置添加元素//其操作與在其他位置添加元素相同int count = 1;//此時searchNode肯定不為NULLNode<Type> *searchNode = first;// 找到要插入的位置// 如果所給index過大(超過了鏈表的長度)// 則將該元素插入到鏈表表尾// 原因是 searchNode->next != NULL 這個條件已經不滿足了// 已經到達表尾while (count < index && searchNode->next != NULL){++ count;searchNode = searchNode->next;}// 插入鏈表Node<Type> *newNode = new Node<Type>(data);newNode->next = searchNode->next;searchNode->next = newNode; }template <typename Type> void MyList<Type>::remove(const Type &data) {if (isEmpty())return ;Node<Type> *previous = first; //保存要刪除節點的前一個節點for (Node<Type> *searchNode = first->next;searchNode != NULL;searchNode = searchNode->next){if (searchNode->data == data){previous->next = searchNode->next;delete searchNode;//重新調整searchNode指針//繼續遍歷鏈表查看是否還有相等元素//如果當前searchNode已經到達了最后一個節點//也就是searchNode->next已經等于NULL了, 則下面這條語句不能執行if (previous->next == NULL)break;searchNode = previous->next;}previous = searchNode;} } template <typename Type> bool MyList<Type>::isEmpty() const {return first->next == NULL; }template <typename Type> void MyList<Type>::concatenate(const MyList<Type> &list) {if (isEmpty())//如果自己的鏈表為空{first = list.first;return ;}else if (list.isEmpty()) //如果第二條鏈表為空{return ;}Node<Type> *endNode = first->next;//找到第一條鏈表的末尾節點while (endNode->next != NULL){endNode = endNode->next;}//找到第二條鏈表的第一個真實元素Node<Type> *secondListNode = (list.first)->next;//注意: 需要將第二個鏈表中的元素值copy出來//不能直接將第二條鏈表的表頭鏈接到第一條鏈表的表尾//不然在析構函數回收內存時會發生錯誤(即:同一段內存釋放兩次)while (secondListNode != NULL){Node<Type> *newNode = new Node<Type>(secondListNode->data);newNode->next = NULL;endNode->next = newNode;//兩條鏈表同時前進endNode = endNode->next;secondListNode = secondListNode->next;} }template <typename Type> void MyList<Type>::invort() {if (!isEmpty()){//p指向正向鏈表的第一個真實節點//隨后, p也會沿正方向遍歷到鏈表末尾Node<Type> *p = first->next;//q會成為倒向的第一個真實節點//首先將q設置為NULL: 保證反向之后//最后一個元素的指針域指向NULL, 以表示鏈表結束Node<Type> *q = NULL;while (p != NULL){Node<Type> *r = q; //暫存q當前指向的節點//q后退(沿著正向后退)q = p;//p前進(沿著正向前進), 保證p能夠始終領先q一個位置p = p -> next;//將指針逆向反轉//注意:一點要保證這條語句在p指針移動之后運行,//不然p就走不了了...(因為q改變了指針的朝向)q -> next = r;}//此時q成為反向鏈表的第一個真實元素//但是為了維護像以前一樣的first指針指向一個無用的節點(以使前面的操作不會出錯)//于是我們需要將first的指針域指向qfirst->next = q;} }//顯示鏈表中的所有數據(測試用) template <typename Type> ostream &operator<<(ostream &os, const MyList<Type> &list) {for (Node<Type> *searchNode = list.first -> next;searchNode != NULL;searchNode = searchNode -> next){os << searchNode -> data;if (searchNode -> next != NULL) //尚未達到鏈表的結尾cout << " -> ";}return os; }//ListIterator的設計與實現 template <typename Type> class ListIterator { public:ListIterator(const MyList<Type> &_list):list(_list),currentNode((_list.first)->next) {}//重載 *operatorconst Type &operator*() const throw (std::out_of_range);Type &operator*() throw (std::out_of_range);//重載 ->operatorconst Node<Type> *operator->() const throw (std::out_of_range);Node<Type> *operator->() throw (std::out_of_range);//重載 ++operatorListIterator &operator++() throw (std::out_of_range);//注意:此處返回的是值,而不是referenceListIterator operator++(int) throw (std::out_of_range);bool isEmpty() const;private:const MyList<Type> &list;Node<Type> *currentNode; };template <typename Type> const Type &ListIterator<Type>::operator*() const throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");// 返回當前指針指向的內容return currentNode->data; } template <typename Type> Type &ListIterator<Type>::operator*() throw (std::out_of_range) {//首先為*this添加const屬性,//以調用該函數的const版本,//然后再使用const_case,//將該函數調用所帶有的const屬性轉除//operator->()的non-const版本與此類同returnconst_cast<Type &>(static_cast<const ListIterator<Type> &>(*this).operator*()); }template <typename Type> const Node<Type> *ListIterator<Type>::operator->() const throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");//直接返回指針return currentNode; }template <typename Type> Node<Type> *ListIterator<Type>::operator->() throw (std::out_of_range) {// 見上returnconst_cast<Node<Type> *> (static_cast<const ListIterator<Type> >(*this).operator->()); }template <typename Type> ListIterator<Type> &ListIterator<Type>::operator++() throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("iterator is out of range");//指針前移currentNode = currentNode->next;return *this; } template <typename Type> ListIterator<Type> ListIterator<Type>::operator++(int) throw (std::out_of_range) {ListIterator tmp(*this);++ (*this); //調用前向++版本return tmp; } template <typename Type> bool ListIterator<Type>::isEmpty() const {if (currentNode == NULL)return true;return false; }#endif // MYLIST_H_INCLUDED

總結

以上是生活随笔為你收集整理的数据结构基础(10) --单链表迭代器的设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。