C++ 模版类的单向循环链式线性表数据结构和算法

基于之前做的单向链式线性表http://blog.csdn.net/shiwazone/article/details/47000191，改进下，实现了循环链表，相对应单向链表，循环链表将尾节点的指针域指向头节点，加入循环，可以让我们在查找某一个index的节点时，可以先判断一下位置和链表长度的关系，如果index处于链表的前半部分，我们可以从头节点遍历查找，如果处于后半部分，我们可以从尾节点往前查找，当然此时我们需要使用双向链表。双向链表的操作，下次给出吧！循环链表给了我们一种思路，如果我们在一个数据块中，加入一个或一些标志节点，我们可以判断我们需要的操作是在哪个区间，可以实现提高工作效率！
代码中重载了加号运算符，实现两个链表的相加。其实我们还可以有更多的操作，但是很多操作都是基于我们的插入删除操作的！所以我们在做数据结构分析的时候，我们要注意到插入和删除的通用性！

#pragma once #include using namespace std; template class CircleList { public: struct Node { EleType _data; Node* _next; Node(){ _next = nullptr; } Node(EleType data){ _data = https://www.it610.com/article/data; _next = nullptr; } }; CircleList(); ~CircleList(); bool GetElem(EleType& e, int index = 1)const; //得到List中第index个元素，把元素的_data赋给e; bool InsertElem(const EleType e, int index = 1); //在List的第index个位置插入一个节点，节点的数据为e bool DeleteElem(EleType& e, int index = 1); //在List的第index个位置删除一个节点，删除节点的数据赋给e bool InsertHead(const EleType& e); //在头部插入数据 bool InsertTail(const EleType& e); //在尾部插入数据 bool Clear(); //清空List void ShowList()const; //显示List的所有元素的数据 CircleList* operator+(CircleList& addList); //重载运算符 private: bool Empty()const; //判断List是否为空 CircleList* AddList(CircleList& addList); //加上addList的数据，相当于把addList的数据从尾部插入到原List中 //在List中查找第index个位置的节点，把该节点的地址赋给n，此处需传入指针的引用，才能保证n可以被修改，不然只能保证*n可以被修改，也就是n指向的节点可以被修改 bool Find(int index, Node*& n)const; bool CheckIndex(int index)const; //检查List是否为空，index是否合法 Node* Head; //头指针 Node* Tail; //尾指针 int Length; };

#include "CircleList.h" #include using namespace std; template bool CircleList::CheckIndex(int index) const { if (Empty()) { cout << "Find: the List is Empty!\n"; return false; } if (index<1 || index>Length) { cout << "the index is invalid!\n"; return false; } return true; }template bool CircleList::Find(int index, Node*& n)const//index [1,Length]; { if (CheckIndex(index)) { int i = 1; Node * temp = Head; while (i < index) { temp = temp->_next; ++i; } n = temp; return true; } return false; }template void CircleList::ShowList() const { Node * temp = nullptr; if (Empty()) { cout << "The list is empty!\n"; } else { for (int i = 1; i <= Length ; ++i) { Find(i, temp); cout << temp->_data << " "; } cout << endl; } }template bool CircleList::Clear() { if (Empty()) { return true; } else { while (Length) { EleType m; DeleteElem(m); } return true; }}template bool CircleList::DeleteElem(EleType& e, int index = 1) { if (CheckIndex(index)) { Node* temp = nullptr; Node* pre_temp = nullptr; if (Find(index, temp)) { if (index == 1) { Find(index + 1, Head); } else { if (index == Length) { Find(index - 1, Tail); } else { Find(index - 1, pre_temp); pre_temp->_next = temp->_next; } } e = temp->_data; delete temp; --Length; return true; } return false; } return false; }template bool CircleList::InsertElem(const EleType e, int index) { Node *insertNode = new Node(e); if (Empty()) { if (index < 1) return false; Head = Tail = insertNode; insertNode->_next = insertNode; ++Length; return true; } if (index == 1) { insertNode->_next = Head; Head = insertNode; Tail->_next = Head; ++Length; return true; } if (index == Length + 1) { Tail->_next = insertNode; insertNode->_next = Head; Tail = insertNode; ++Length; return true; } Node*temp = nullptr; if (Find(index - 1, temp)) { insertNode->_next = temp->_next; temp->_next = insertNode; ++Length; return true; } return false; }template bool CircleList::GetElem(EleType& e, int index) const { if (CheckIndex(index)) { Node* temp = nullptr; if (Find(index, temp)) e = temp->_data; return true; } return false; }template CircleList::~CircleList() { Clear(); }template CircleList::CircleList() :Length(0), Head(nullptr), Tail(nullptr) {}template bool CircleList::Empty() const { return(Length == 0); }template bool CircleList::InsertTail(const EleType& e) { return InsertElem(e, Length + 1); }template bool CircleList::InsertHead(const EleType& e) { return InsertElem(e); }template CircleList* CircleList::AddList(CircleList& addList) { if (Empty()) { if (addList.Empty()) { return this; } Node* temp = addList.Head; for (int i = 1; i <= addList.Length; ++i) { InsertTail(temp->_data); temp = temp->_next; }return this; } else { if (addList.Empty()) { return this; } else { Node* temp = addList.Head; for (int i = 1; i <= addList.Length; ++i) { InsertTail(temp->_data); temp = temp->_next; } return this; } } }template CircleList* CircleList::operator+(CircleList& addList) { return AddList(addList); }

#include "CircleList.cpp"int main() { CircleList IntList1; IntList1.ShowList(); IntList1.InsertElem(155); IntList1.InsertElem(5); IntList1.InsertElem(55); IntList1.InsertElem(15); IntList1.InsertElem(99); IntList1.ShowList(); CircleList IntList2; IntList2.InsertElem(11); IntList2.InsertElem(11); IntList2.InsertElem(11); IntList2.InsertElem(11); IntList2.InsertElem(11); IntList2.ShowList(); CircleList *IntList3; IntList3 = IntList2 + IntList1; IntList3->ShowList(); return 0; }

【C++ 模版类的单向循环链式线性表】