循环链表模板种

相对于单链表，循环链表的最后一个结点的next指针指向表头元素，而且每个结点还包含指向其前驱结点的prev指针。链表第一个结点的prev指针是链表的头结点，表头结点的prev指针指向链表最后一个结点。循环链表的插入和删除操作需要注意各指针的变化顺序，否则容易造成结点混乱。另外对循环链表来说，更容易找到指定结点的前驱。

/* * 循环链表模板类 */ #ifndef _DOUBLE_LIST_H_ #define _DOUBLE_LIST_H_ #include <iostream> using namespace std; template <typename TYPE> class DoubleList { private: struct ListNode { TYPE data; struct ListNode *prev; struct ListNode *next; }; int _size; ListNode *_head; int insert(ListNode *&h, TYPE &x); void traverse(ListNode *h) const; void erase(ListNode *&h, const TYPE &x); bool empty(ListNode *h) const; int at(ListNode *h, int idx, TYPE &x) const; bool getnext(ListNode *h, TYPE &cur, TYPE &nex) const; bool getprev(ListNode *h, TYPE &cur, TYPE &pre) const; public: DoubleList(); ~DoubleList(); // 将元素x插入循环链表 int insert(TYPE &x); void traverse() const; void erase(const TYPE &x); bool empty() const; int size() const; int at(int idx, TYPE &x) const; bool getnext(TYPE &cur, TYPE &nex) const; bool getprev(TYPE &cur, TYPE &pre) const; }; #endif // 构造函数 template <typename TYPE> DoubleList<TYPE>::DoubleList() { _head = new ListNode; _head->prev = _head->next = _head; _size = 0; } // 析构函数 template <typename TYPE> DoubleList<TYPE>::~DoubleList() { if(_head != NULL) { ListNode *p = _head->next; while(p != _head) { delete p; p = _head->next; } delete _head; } } // 将元素x插入循环链表，执行成功返回０，失败返回-1 template <typename TYPE> int DoubleList<TYPE>::insert(ListNode *&h, TYPE &x) { if(h == NULL) return -1; ListNode *p = new ListNode; p->data = x; p->prev = h->prev; h->prev->next = p; p->next = h; h->prev = p; _size++; return 0; } template <typename TYPE> int DoubleList<TYPE>::insert(TYPE &x) { return insert(_head, x); } // 遍历链表 template <typename TYPE> void DoubleList<TYPE>::traverse(ListNode *h) const { if(_head == NULL) return; ListNode *p = _head->next; while(p != _head) { cout << p->data << endl; p = p ->next; } } template <typename TYPE> void DoubleList<TYPE>::traverse() const { traverse(_head); } // 删除值为x的元素 template <typename TYPE> void DoubleList<TYPE>::erase(ListNode *&h, const TYPE &x) { if(h != NULL) { ListNode *p = h->next; while(p !=_head && p->data != x) { p = p->next; } if(p != _head) { p->prev->next = p->next; p->next->prev = p->prev; delete p; _size--; } } } template <typename TYPE> void DoubleList<TYPE>::erase(const TYPE &x) { erase(_head, x); } // 链表的大小 template <typename TYPE> int DoubleList<TYPE>::size() const { return _size; } // 取链表的idx元素 template <typename TYPE> int DoubleList<TYPE>::at(ListNode *h, int idx, TYPE &x) const { if(idx <= 0 || idx > _size) return 0; if(h == NULL) return -1; int i = 1; ListNode *p = h->next; while(p != _head && i < idx) { p = p->next; i++; } x = p->data; return 1; } template <typename TYPE> int DoubleList<TYPE>::at(int idx, TYPE &x) const { return at(_head, idx, x); } // 判断链表是否为空 template <typename TYPE> bool DoubleList<TYPE>::empty(ListNode *h) const { if(h == NULL) return true; if(_size == 0 || h->next == h) return true; return false; } template <typename TYPE> bool DoubleList<TYPE>::empty() const { return empty(_head); } // 返回元素cur所在结点的后继结点元素值并保存在nex中 template <typename TYPE> bool DoubleList<TYPE>::getnext(ListNode *h, TYPE &cur, TYPE &nex) const { if(h == NULL) return false; ListNode *p = h->next; while(p != h && p->data != cur) { p = p->next; } if(p->next == h) return false; nex = p->next->data; return true; } template <typename TYPE> bool DoubleList<TYPE>::getnext(TYPE &cur, TYPE &nex) const { return getnext(_head, cur, nex); } // 返回cur所在结点的前驱结点元素值并保存在prev中 template <typename TYPE> bool DoubleList<TYPE>::getprev(ListNode *h, TYPE &cur, TYPE &pre) const { if(h == NULL) return false; ListNode *p = h->next; while(p != h && p->data != cur) p = p->next; if(p->prev == h) return false; pre = p->prev->data; return true; } template <typename TYPE> bool DoubleList<TYPE>::getprev(TYPE &cur, TYPE &pre) const { return getprev(_head, cur, pre); }