单循环链表
写在前面
单循环链表，简称循环链表（circular linked list)，是表的一种链式存储结构。
设p是指向循环链表的指针，currPtr是当前指向对的循环链表的指针，head是指向循环链表的头指针，与链表判断是否到达链尾相比，循环链表中判断是否到达链表尾的条件是：p!=head或者是currPtr!=head。所以，循环链表类中成员函数的实现与链表类中的成员函数的实现差别不大，只是把p!=null换成了p!=head，把currPtr!=null换成了currptr!=head.
1.节点类的定义和实现
template<class T>
class CirList;
template<class T>
class ListNode
{
friend class CirList<T>;//声明友元类
public:
T data;//数据域
ListNode(ListNode<T> *ptrNext = NULL);//构造函数，用于构造头节点，头节点没有data参数
ListNode(const T &item, ListNode<T> *ptrNext = NULL);//构造函数，主要用于构造非头节点的节点
~ListNode() {};//析构函数
private:
ListNode<T> *next;//指向下一节点的指针
};
template<class T>
inline ListNode<T>::ListNode(ListNode<T>* ptrNext) :next(ptrNext)
{}
template<class T>
inline ListNode<T>::ListNode(const T & item, ListNode<T>* ptrNext)
{
this->data = item;
this->next = ptrNext;
}
2.循环链表类的定义
template <class T>
class CirList
{
public:
CirList();//构造函数
~CirList();//析构函数
int listsize();//长度
bool listempty() const;//是否为空
ListNode<T> *index(int pos);//返回指向位置pos的指针
void insert(const T& item, int pos);//在pos节点前插入一个节点
T del(int pos);//删除第pos个节点
T getdata(int pos) const;//返回pos节点的值域
void clearlist();//清空表为初始状态
ListNode<T> *reset();//currptr指向节点pos并返回currptr
ListNode<T> *next();//currptr指向下一节点并返回currptr
bool EndOfList() const;//判断是否到了尾部 ，currptr==head
bool nextEndofList() const;//currptr->next是否链表尾
T delAfter();//删除currptr->next所指节点并返回被删除节点的data
private:
ListNode<T> *head;//表头指针
int size;//链表的节点个数
ListNode<T> *currPtr;//当前节点指针
};
3.循环链表类的实现
template<class T>
inline CirList<T>::CirList()
{
head = new ListNode<T>();
size = 0;
head->next = head;
}
template<class T>
inline CirList<T>::~CirList()
{
clearlist();
delete head;
head = NULL;
}
template<class T>
inline int CirList<T>::listsize()
{
return size;
}
template<class T>
inline bool CirList<T>::listempty() const
{
return (size == 0);
}
template<class T>
inline ListNode<T>* CirList<T>::index(int pos)
{
if (pos == -1)
{
return head;
}
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
currPtr = head->next;
int i = 0;
while (currPtr != NULL & i < pos)
{
currPtr = currPtr->next;
i++;
}
return currPtr;
}
template<class T>
inline void CirList<T>::insert(const T & item, int pos)
{
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
ListNode<T> *p = index(pos - 1);
ListNode<T> *newnode = new ListNode<T>(item, p->next);
p->next = newnode;
size++;
}
template<class T>
inline T CirList<T>::del(int pos)
{
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
ListNode<T> *p = index(pos-1);
ListNode<T> *q;
q = p->next;
p->next = q->next;
T data = q->data;
delete q;
size--;
return data;
}
template<class T>
inline T CirList<T>::getdata(int pos) const
{
ListNode<T> *p = index(pos);
return p->data;
}
template<class T>
inline void CirList<T>::clearlist()
{
ListNode<T> *p, *p1;
p = head->next;
while (p != head)
{
p1 = p;
p= p->next;
delete p1;
}
size = 0;
}
template<class T>
inline ListNode<T>* CirList<T>::reset()
{
currPtr = head->next;
return currPtr;
}
template<class T>
inline ListNode<T>* CirList<T>::next()
{
if (currPtr != NULL)
{
currPtr = currPtr->next;
}
return currPtr;
}
template<class T>
inline bool CirList<T>::EndOfList() const
{
return (currPtr == head);
}
template<class T>
inline bool CirList<T>::nextEndofList() const
{
return (currPtr->next == head);
}
template<class T>
inline T CirList<T>::delAfter()
{//删除currpter->next,并返回currptr->next->data
if (currPtr->next != NULL)
{
ListNode<T> *p = currPtr->next;
currPtr->next = p->next;
T data = p->data;
delete p;
size--;
return data;
}
}
4.测试主函数
void test()
{
CirList<int> list;
cout << "当前链表中的元素有" << list.listsize() << endl;
for (int i = 0; i < 10; i++)
{
list.insert(10 * i, i);
}
list.insert(100, 0);
cout << "当前链表中的元素有" << list.listsize() << endl;
ListNode<int> *p = list.reset();
while (!list.EndOfList())
{
cout << p->data << endl;
p = list.next();
}
cout<< list.del(1)<<"已被删除"<<endl;
while (!list.EndOfList())
{
cout << p->data << endl;
p = list.next();
}
cout << list.index(5)->data << endl;
}
int main()
{
test();
system("pause");
return EXIT_SUCCESS;
}
输出结果如下：
