双向循环链表
写在前面
双向循环链表（Double Circular Linked List)是每个节点有前趋指针和后继指针，且后继指针和前趋指针各自构成自己的单循环链表的链表。
在单链表中查找当前节点的后继节点并不困难，可以通过当前节点的next指针进行，但要查找当前节点的前趋节点就要从头指针head开始重新进行。对于一个要进行频繁查找当前节点的后继节点和当前节点的前趋节点的应用来说，使用单链表的时间效率是非常低的，双向链表是有效解决这类问题的选择。
在双向链表中，每个节点包括三个域，分别是data,next,prior。其中data为数据域，next为后继节点指针，prior为前趋节点指针。
双向链表通常均为双向循环链表，这是因为读双向循环链表，不论是插入还是删除，对第一个节点、最后一个节点的操作和对链表中间任意一个节点的操作过程是一样的。而双向非循环链表对这些节点的操作是不同的。
1.节点类的定义和实现
template<class T>
class DCirlist;
template<class T>
class DLnode
{
friend class DCirlist<T>;
public:
T data;
//构造函数，无数据域的头结点
DLnode<T>(DLnode<T> *ptrn = NULL, DLnode<T> *ptrp = NULL){};
//构造函数，非头节点的节点
DLnode<T>( T item, DLnode<T> *ptrn = NULL, DLnode<T> *ptrp = NULL);
//析构函数
~DLnode() {};
private:
DLnode<T> *next;
DLnode<T> *prior;
};
template<class T>
inline DLnode<T>::DLnode(T item, DLnode<T>* ptrn, DLnode<T>* ptrp)
{
this->data = item;
this->next = ptrn;
this->prior = ptrp;
}
双向循环链表只是在单循环链表的基础上又增加了一个指向前趋节点的指针，而且指向前趋节点指针也构成了自己的单循环链表。双循环链表的定义与单循环链表的定义非常相似。
2.双向循环链表类的定义
template <class T>
class DCirlist
{
public:
DCirlist();//构造函数
~DCirlist();//析构函数
int listsize() const;//返回链表长度
bool empty() const;//判断链表是否为空
DLnode<T> *index(int pos) const;//返回指向第pos个节点的指针
void insert(const T &item, int pos);//在第pos个节点插入item
T del(int pos);//删除第pos个节点，并返回数据域
T getdata(int pos) const;//返回第pos个节点的值
void clearlist();//清空表
DLnode<T> *reset(int pos = 0);
DLnode<T> *next();
DLnode<T> *prior();
bool EndOfList() const;//是否到链表尾
bool nextEndoflist() const;//currPtr->next是否到链表尾
bool PriorEndoflist() const;//currPtr->prior是否到链表尾
T deleprior();//删除currPtr节点，新currPtr是原currPtr的前趋，返回数据域
private:
DLnode<T> *head;
DLnode<T> *currPtr;
int size;
};
3.双向循环链表类的实现
template<class T>
inline DCirlist<T>::DCirlist()
{
head = new DLnode<T>();
head->next = head;
head->prior = head;
size = 0;
}
template<class T>
inline DCirlist<T>::~DCirlist()
{
clearlist();
delete head;
head = NULL;
}
template<class T>
inline int DCirlist<T>::listsize() const
{
return size;
}
template<class T>
inline bool DCirlist<T>::empty() const
{
return (size == 0);
}
template<class T>
inline DLnode<T>* DCirlist<T>::index(int pos) const
{
if (pos == -1)
{
return head;
}
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
int i = 0;
DLnode<T> *p = head->next;
while (i < pos&&p != head)
{
p = p->next;
i++;
}
return p;
}
template<class T>
inline void DCirlist<T>::insert(const T & item, int pos)
{
DLnode<T> *p = index(pos-1);
DLnode<T> *new_node = new DLnode<T>(item, NULL, NULL);
new_node->prior = p;
p->next->prior = new_node;
new_node->next = p->next;
p->next = new_node;
size++;
}
template<class T>
inline T DCirlist<T>::del(int pos)
{
if (size == 0)
{
cout << "list is empty" << endl;
exit(1);
}
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
DLnode<T> *p = index(pos);
p->prior->next = p->next;
p->next->prior = p->prior;
T data = p->data;
delete p;
size--;
return data;
}
template<class T>
inline T DCirlist<T>::getdata(int pos) const
{
DLnode<T> *p = index(pos);
return p->data;
}
template<class T>
inline void DCirlist<T>::clearlist()
{
DLnode<T> *p1, *p2;
p1 = head->next;
while (p1 != head)
{
p2 = p1;
p1 = p1->next;
delete p2;
}
size = 0;
}
template<class T>
inline DLnode<T>* DCirlist<T>::reset(int pos)
{
if (pos == -1)
{
return head;
}
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
int i = 0;
currPtr = head->next;
while (i < pos&&currPtr != head)
{
currPtr = currPtr->next;
i++;
}
return currPtr;
}
template<class T>
inline DLnode<T>* DCirlist<T>::next()
{
if (currPtr!= NULL)
{
currPtr = currPtr->next;
}
return currPtr;
}
template<class T>
inline DLnode<T>* DCirlist<T>::prior()
{
if (currPtr != NULL)
{
currPtr = currPtr->prior;
}
return currPtr;
}
template<class T>
inline bool DCirlist<T>::EndOfList() const
{
return (currPtr == head);
}
template<class T>
inline bool DCirlist<T>::nextEndoflist() const
{
return (currPtr->next == head);
}
template<class T>
inline bool DCirlist<T>::PriorEndoflist() const
{
return (currPtr->prior == head);
}
template<class T>
inline T DCirlist<T>::deleprior()
{//删除当前节点的前一节点
DLnode<T> *p = currPtr->prior;
currPtr->prior->next = currPtr->next;
currPtr->next->prior = currPtr->prior;
T data = currPtr->data;
delete currPtr;
size--;
currPtr = p;
return currPtr;
}
4.测试主函数
void test()
{
DCirlist<int> list;
for (int i = 0; i < 10; i++)
{
list.insert(i * 10, i);
}
cout << "list中元素的个数为：" << list.listsize() << endl;
DLnode<int> *p = list.reset();
while (!list.EndOfList())
{
cout << p->data << endl;
p = list.next();
}
p = list.next();
cout << list.del(1) << "已被删除" << endl;
cout << "list中元素的个数为：" << list.listsize() << endl;
while (!list.EndOfList())
{
cout << p->data << endl;
p = list.next();
}
cout << list.getdata(1) << endl;
cout << list.index(2)->data << endl;
}
int main()
{
test();
system("pause");
return EXIT_SUCCESS;
}
输出结果如下：
