循環鏈表:最後一個結點的指針域的指針又指回第一個結點的鏈表;
循環單鏈表與單鏈表的區別在於:表中最有一個節點的指針不再是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;
}
//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 *operator->() throw (std::out_of_range);
//重載 ++operator
ListIterator &operator++() throw (std::out_of_range);
//注意:此處返回的是值,而不是reference
ListIterator operator++(int) throw (std::out_of_range);
bool isEmpty() const;
private:
const MyList &list;
Node *currentNode;
};
template
bool ListIterator::isEmpty() const
{
// ++ 注意:判空條件改為list.first
if (currentNode == list.first)
return true;
return false;
}
template
const Type &ListIterator::operator*() const
throw (std::out_of_range)
{
if (isEmpty())
throw std::out_of_range(iterator is out of range);
// 返回當前指針指向的內容
return currentNode->data;
}
template
Type &ListIterator::operator*()
throw (std::out_of_range)
{
//首先為*this添加const屬性,
//以調用該函數的const版本,
//然後再使用const_case,
//將該函數調用所帶有的const屬性轉除
//operator->()的non-const版本與此類同
return
const_cast(
static_cast &>(*this).operator*()
);
}
template
const Node *ListIterator::operator->() const
throw (std::out_of_range)
{
if (isEmpty())
throw std::out_of_range(iterator is out of range);
//直接返回指針
return currentNode;
}
template
Node *ListIterator::operator->()
throw (std::out_of_range)
{
// 見上
return
const_cast *> (
static_cast >(*this).operator->()
);
}
template
ListIterator &ListIterator::operator++()
throw (std::out_of_range)
{
if (isEmpty())
throw std::out_of_range(iterator is out of range);
//指針前移
currentNode = currentNode->next;
return *this;
}
template
ListIterator ListIterator::operator++(int)
throw (std::out_of_range)
{
ListIterator tmp(*this);
++ (*this); //調用前向++版本
return tmp;
}
#endif // MYLIST_H_INCLUDED
附-測試代碼:
int main()
{
MyList iMyList;
for (int i = 0; i < 10; ++i) //1 2 3 4 5 6 7 8 9 10
iMyList.insert(i+1, i+1);
for (int i = 0; i < 5; ++i) //40 30 20 10 0 1 2 3 4 5 6 7 8 9 10
iMyList.insertFront(i*10);
iMyList.insertFront(100);//100 40 30 20 10 0 1 2 3 4 5 6 7 8 9 10
iMyList.remove(10); //100 40 30 20 0 1 2 3 4 5 6 7 8 9
iMyList.remove(8); //100 40 30 20 0 1 2 3 4 5 6 7 9
cout << ------------ MyList ------------ << endl;
for (ListIterator iter(iMyList);
!(iter.isEmpty());
++ iter)
cout << *iter << ' ';
cout << endl;
cout << Test:
<< iMyList << endl;
return 0;
}
