循环链表:最后一个结点的指针域的指针又指回第一个结点的链表;
?
循环单链表与单链表的区别在于:表中最有一个节点的指针不再是NULL, 而改为指向头结点(因此要对我们原来的MyList稍作修改), 从而整个链表形成一个环.
因此, 循环单链表的判空条件不再是头结点的指针是否为空, 而是他是否等于头结点;
其实如果只是单纯的实现循环链表对单链表的性能提升是不明显的, 反而增加了代码上实现的复杂度, 但是如果与下一篇中的双向链表相结合的话, 在速度上的提升是十分惊人的, 因此这篇博客权当做是一个过渡吧, 为上一篇博客和下一篇博客的结合起着承上启下的作用.
?
下面是MyList.h的完整代码与解析, 由于代码较多, 希望能够仔细阅读, 但其实下面的大部分代码都与前面类似只是对其中几处稍作修改, 遇到与单链表的不同之处, 我会与++符号作为注释指出:
?
#ifndef MYLIST_H_INCLUDED #define MYLIST_H_INCLUDED #include#include using namespace std; //循环链表 //前向声明 template class MyList; template class ListIterator; //链表节点 template class Node { //可以将MyList类作为Node的友元 //同时也可以将Node类做成MyList的嵌套类, 嵌套在MyList中, 也可以完成该功能 friend class MyList ; friend class ListIterator ; template friend ostream &operator<<(ostream &os, const MyList &list); private: //constructor说明: //next = NULL; //因为这是一个新生成的节点, 因此下一个节点为空 Node(const Type &dataValue):data(dataValue), next(NULL) {} Type data; //数据域:节点数据 Node *next; //指针域:下一个节点 }; //链表 template class MyList { template friend ostream &operator<<(ostream &os, const MyList &list); friend class ListIterator ; 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; private: //指向第一个节点的指针 Node *first; }; template MyList ::MyList() { //first指向一个空节点 first = new Node (0); // ++ 这是一个关键点 //first的下一个元素就指向first //此时, 代表链表是否已经到达结尾处的判断已经不再是(是否等于NULL) //而改为(是否等于first) //因为此时first代表链表的最后一个元素 //同时,first又是第一个元素的前一个元素 first -> next = first; } template MyList ::~MyList() { Node *deleteNode = NULL; // ++ 保存链表尾元素 Node *tmp = first; // ++ first首先指向第一个真实的元素 first = first->next; //一路到达链表结尾 while (first != tmp) { deleteNode = first; first = first -> next; delete deleteNode; } // ++ 释放到链表的空节点 delete tmp; } //这一步与前一版链表相同 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肯定不为first Node *searchNode = first; //++ 注意:此处将NULL修改为first // 找到要插入的位置 // 如果所给index过大(超过了链表的长度) // 则将该元素插入到链表表尾 // 原因是 searchNode->next != first 这个条件已经不满足了 while (count < index && searchNode->next != first) { ++ 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; // ++ 注意此处不再是判断是否为NULL searchNode != first; // ++ 而是不能等于first, first代表链表的末尾 searchNode = searchNode->next) { if (searchNode->data == data) { previous->next = searchNode->next; delete searchNode; //重新调整searchNode指针 //继续遍历链表查看是否还有相等元素 // ++ 注意 //如果当前searchNode已经到达了最后一个节点 //也就是searchNode->next已经等于first了, 则下面这条语句不能执行 if (previous->next == first) break; searchNode = previous->next; } previous = searchNode; } } //注意判空条件 template bool MyList ::isEmpty() const { return first->next == first; } //显示链表中的所有数据(测试用) template ostream &operator<<(ostream &os, const MyList &list) { for (Node *searchNode = list.first -> next; searchNode != list.first; //++ 注意 searchNode = searchNode -> next) { os << searchNode -> data; if (searchNode -> next != list.first) // ++ 注意(尚未达到链表的结尾) cout << -> ; } return os; }