循环链表模板种

循环链表模板类

相对于单链表，循环链表的最后一个结点的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插入循环链表，执行成功返回０，失败返回-1template <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);}