单循环链表

说明

单循环链表和单链表（参考单链表）大致一样，只是尾结点要指向头结点，本文是使用尾结点rear来表示，之所以使用尾指针，是因为如果使用头结点来寻找列表最后一个元素时间复杂度为O(n),如果使用尾结点来寻找列表最后一个元素时间复杂度为O(1)

注意

1. 第一个元素地址表示：rear->next->next;最后一个元素地址：rear
2. 头指针的表示，单链表使用front来标识头指针，单循环链表使用rear->next来表示
3. 单链表使用p->next=NULL判断是否为尾结点，单循环链表使用p==rear判断是否为尾结点

（一）无参构造函数

建立尾结点，使尾结点指针域指向自己，说明链表为空

template<class T>
CircleList<T>::CircleList()
{rear=new Node<T>;rear->next=rear;
}

（二）有参构造函数

这里的方法相当于单链表中使用的尾插法，

1. 为rear开辟空间
2. 创建头指针Headr，并把rear的地址赋给Headr
3. 使用for循环将数组依次加入到列表中
4. 创建一个临时结点temp
5. 为temp值域赋值，并把其地址赋给rear->next
6. 修改rear地址
7. 最后将rear指回头结点

template<class T>
CircleList<T>::CircleList(T a[],int len)
{rear = new Node<T>;Node<T>* Headr;Headr = rear;for (int i=0;i<len;i++){Node<T>* temp = new Node<T>;temp->data = a[i];rear->next = temp;rear = temp;}rear->next = Headr;
}

（三）析构函数

与单链表相似，只是最后rear要单独释放

template<class T>
CircleList<T>::~CircleList()
{Node<T>* p=rear->next;while(p!=rear){rear->next=p;p=p->next;delete rear->next;}delete rear;
}

（四）获取长度

与单链表相似，只是j的初始值要为1，因为while循环的终止条件为p!=rear,但是rear为最后一个元素，需要算上，所以j的初始值为1

template<class T>
int CircleList<T>::GetLength()const
{int j=1;Node<T>* p=rear->next->next;while(p!=rear){j++;p=p->next;}return j;
}

（五）打印数组

因为while循环的终止条件为p!=rear,但是rear为最后一个元素，所以需要单独打印rear；其中if(i%5==4)是控制5个元素为一行

template<class T>
void CircleList<T>::Print()const
{Node<T>* p=rear->next->next;int i=0;while(p!=rear){std::cout<<p->data<<" ";if(i%5==4)std::cout<<std::endl;p=p->next;i++;}std::cout<<rear->data<<std::endl;
}

（六）获取第i个元素的地址

与单链表相似，需要注意的是，如果取最后一个元素，需要使用if(GetLength()==i)return rear;单独判断

template<class T>
Node<T>* CircleList<T>::Get(int i)const
{int j=0;Node<T>* p=rear->next;if(GetLength()==i)return rear;while(p!=rear&&j!=i){p=p->next;j++;}return p;
}

（七）插入

和单链表略有不同

1. 先判断插入位置是否正确
2. 然后在插入

template<class T>
void CircleList<T>::Insert(int i,T x)
{Node<T>* p=rear->next;if(i<0||i>GetLength())throw"位置异常";if(i!=1)p=Get(i-1);Node<T>* s=new Node<T>;s->data=x;s->next=p->next;p->next=s;
}

（八）删除

1. 获取第i-1位置的地址
2. q表示第i个元素
3. 摘链
4. 释放

如果删除最后一个元素需要单独释放：

1. 用temp存储最后元素的地址
2. 让rear指向倒数第二个元素
3. 摘链，让倒数第二个元素指向头结点
4. 释放

template<class T>
void CircleList<T>::Delete(int i)
{Node<T>* p=rear->next;if(i!=1)p=Get(i-1);if(i==GetLength()){Node<T>* temp=rear;rear=p;rear->next=temp->next;delete temp;}else{Node<T>* q=p->next;p->next=q->next;delete q;}
}

（九）获取值为x的元素的位置

template<class T>
int  CircleList<T>::Location(T x)const
{int j=0;Node<T>* p=rear->next->next;if(x==rear->data)return GetLength();while(p!=rear){j++;if(p->data==x)return j;p=p->next;}
}

（十）排序

使用的是冒泡排序，循环的终止条件与单链表不同

template<class T>
void CircleList<T>::sort()
{for(int i=1;i<=CircleList<T>::GetLength();i++){Node<T>* p=rear->next->next;while(p!=rear){if(p->data>p->next->data){T t;t=p->next->data;p->next->data=p->data;p->data=t;}p=p->next;}}
}

（十一）连接

1. 保存b链的头结点
2. b链的尾指向当前链表的头
3. 当前链表的尾，指向b链的第一个元素
4. 修改尾指针
5. 将b链置空，并且把b.rear指向这个节点

template<class T>
void CircleList<T>::Connect(CircleList<T> &b)
{if(b.rear==b.rear->next)return;Node<T>* p=b.rear->next;//保存b链的头结点b.rear->next=rear->next;//b链的尾指向当前链表的头rear->next=p->next;//当前链表的尾，指向b链的第一个元素rear=b.rear;//修改尾指针b.rear=p->next=p;//将b链置空，并且把b.rear指向这个节点
}

（十二）整个文件

CircleList.h

#ifndef CIRCLELIST_H_
#define CIRCLELIST_H_
#include<iostream>
template<class T>
struct Node
{T data;struct Node<T>* next;
};
template<class T>
class CircleList
{
private:Node<T>* rear;
public:CircleList();CircleList(T a[],int len);~CircleList();int GetLength()const;void Print()const;void Insert(int i,T x);void Delete(int i);Node<T>* Get(int i)const;int Location(T x)const;void sort();void Connect(CircleList<T> &b);
};
template<class T>
CircleList<T>::CircleList()
{rear=new Node<T>;rear->next=rear;
}
template<class T>
CircleList<T>::CircleList(T a[],int len)
{rear = new Node<T>;Node<T>* Headr;Headr = rear;for (int i=0;i<len;i++){Node<T>* temp = new Node<T>;temp->data = a[i];rear->next = temp;rear = temp;}rear->next = Headr;
}
template<class T>
CircleList<T>::~CircleList()
{Node<T>* p=rear->next;while(p!=rear){rear->next=p;p=p->next;delete rear->next;}delete rear;
}
template<class T>
int CircleList<T>::GetLength()const
{int j=1;Node<T>* p=rear->next->next;while(p!=rear){j++;p=p->next;}return j;
}
template<class T>
void CircleList<T>::Print()const
{Node<T>* p=rear->next->next;int i=0;while(p!=rear){std::cout<<p->data<<" ";if(i%5==4)std::cout<<std::endl;p=p->next;i++;}std::cout<<rear->data<<std::endl;
}
template<class T>
void CircleList<T>::Insert(int i,T x)
{Node<T>* p=rear->next;if(i<0||i>GetLength())throw"位置异常";if(i!=1)p=Get(i-1);Node<T>* s=new Node<T>;s->data=x;s->next=p->next;p->next=s;
}
template<class T>
void CircleList<T>::Delete(int i)
{Node<T>* p=rear->next;if(i!=1)p=Get(i-1);if(i==GetLength()){Node<T>* temp=rear;rear=p;rear->next=temp->next;delete temp;}else{Node<T>* q=p->next;p->next=q->next;delete q;}
}
template<class T>
Node<T>* CircleList<T>::Get(int i)const
{int j=0;Node<T>* p=rear->next;if(GetLength()==i)return rear;while(p!=rear&&j!=i){p=p->next;j++;}return p;
}
template<class T>
int  CircleList<T>::Location(T x)const
{int j=0;Node<T>* p=rear->next->next;if(x==rear->data)return GetLength();while(p!=rear){j++;if(p->data==x)return j;p=p->next;}
}
template<class T>
void CircleList<T>::sort()
{for(int i=1;i<=CircleList<T>::GetLength();i++){Node<T>* p=rear->next->next;while(p!=rear){if(p->data>p->next->data){T t;t=p->next->data;p->next->data=p->data;p->data=t;}p=p->next;}}
}
template<class T>
void CircleList<T>::Connect(CircleList<T> &b)
{if(b.rear==b.rear->next)return;Node<T>* p=b.rear->next;//保存b链的头结点b.rear->next=rear->next;//b链的尾指向当前链表的头rear->next=p->next;//当前链表的尾，指向b链的第一个元素rear=b.rear;//修改尾指针b.rear=p->next=p;//将b链置空，并且把b.rear指向这个节点
}
#endif // CIRCLELIST_H_

UseCircleList.cpp

#include<iostream>
#include"CircleList.h"
const int SIZE=10;
int main()
{using std::cout;using std::endl;int ss[SIZE]={9,3,4,1,5,0,8,6,2,7};int qq[5]={0,1,2,3,4};CircleList<int> Grade(ss,SIZE);CircleList<int> B(qq,5);cout<<"链表内容："<<endl;Grade.Print();cout<<"长度为："<<endl;cout<<Grade.GetLength()<<endl;cout<<"查找5的位置："<<endl;cout<<Grade.Location(5)<<endl;cout<<"删除第10个位置后的内容："<<endl;Grade.Delete(10);Grade.Print();cout<<"此时长度为："<<endl;cout<<Grade.GetLength()<<endl;cout<<"在第9个位置插入11的内容："<<endl;Grade.Insert(9,11);Grade.Print();cout<<"排序后："<<endl;Grade.sort();Grade.Print();Grade.Connect(B);cout<<"连接后："<<endl;Grade.Print();return 0;
}