数据结构基础(10) --单链表迭代器的设计与实现(二)
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
&list); private: //指向第一个节点的指针 Node
*first; }; template
MyList
::MyList() { //first指向一个空节点 first = new Node
(0); first -> next = NULL; } template
MyList
::~MyList() { Node
*deleteNode = NULL; while (first != NULL) { deleteNode = first; first = first -> next; delete deleteNode; } } template
void MyList
::insertFront(const Type &data) { Node
*newNode = new Node
(data); newNode -> next = first -> next; first -> next = newNode; } template
void MyList
::insert(const Type &data, int index) { //由于我们在表头添加了一个空节点 //因此如果链表为空, 或者在链表为1的位置添加元素 //其操作与在其他位置添加元素相同 int count = 1; //此时searchNode肯定不为NULL Node
*searchNode = first; // 找到要插入的位置 // 如果所给index过大(超过了链表的长度) // 则将该元素插入到链表表尾 // 原因是 searchNode->next != NULL 这个条件已经不满足了 // 已经到达表尾 while (count < index && searchNode->next != NULL) { ++ count; searchNode = searchNode->next; } // 插入链表 Node
*newNode = new Node
(data); newNode->next = searchNode->next; searchNode->next = newNode; } template
void MyList
::remove(const Type &data) { if (isEmpty()) return ; Node
*previous = first; //保存要删除节点的前一个节点 for (Node
*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
bool MyList
::isEmpty() const { return first->next == NULL; } template
void MyList
::concatenate(const MyList
&list) { if (isEmpty())//如果自己的链表为空 { first = list.first; return ; } else if (list.isEmpty()) //如果第二条链表为空 { return ; } Node
*endNode = first->next; //找到第一条链表的末尾节点 while (endNode->next != NULL) { endNode = endNode->next; } //找到第二条链表的第一个真实元素 Node
*secondListNode = (list.first)->next; //注意: 需要将第二个链表中的元素值copy出来 //不能直接将第二条链表的表头链接到第一条链表的表尾 //不然在析构函数回收内存时会发生错误(即:同一段内存释放两次) while (secondListNode != NULL) { Node
*newNode = new Node
(secondListNode->data); newNode->next = NULL; endNode->next = newNode; //两条链表同时前进 endNode = endNode->next; secondListNode = secondListNode->next; } } template
void MyList
::invort() { if (!isEmpty()) { //p指向正向链表的第一个真实节点 //随后, p也会沿正方向遍历到链表末尾 Node
*p = first->next; //q会成为倒向的第一个真实节点 //首先将q设置为NULL: 保证反向之后 //最后一个元素的指针域指向NULL, 以表示链表结束 Node
*q = NULL; while (p != NULL) { Node
*r = q; //暂存q当前指向的节点 //q后退(沿着正向后退) q = p; //p前进(沿着正向前进), 保证p能够始终领先q一个位置 p = p -> next; //将指针逆向反转 //注意:一点要保证这条语句在p指针移动之后运行, //不然p就走不了了...(因为q改变了指针的朝向) q -> next = r; } //此时q成为反向链表的第一个真实元素 //但是为了维护像以前一样的first指针指向一个无用的节点(以使前面的操作不会出错) //于是我们需要将first的指针域指向q first->next = q; } } //显示链表中的所有数据(测试用) template
ostream &operator<<(ostream &os, const MyList
&list) { for (Node
*searchNode = list.first -> next; searchNode != NULL; searchNode = searchNode -> next) { os << searchNode -> data; if (searchNode -> next != NULL) //尚未达到链表的结尾 cout << " -> "; } return os; } //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
*operat