循环链表与单链表的主要区别和完整实现代码。

---

前置文章：单链表

循环链表(Circular Link List)

初始循环链表的头结点的后继指向自己

与单链表主要区别

• 在遍历时判断结点是否为头结点 而不是 是否为空
• 空的双向循环链表的头结点的前驱和后继都指向自己
• 两个循环链表可以合并为一个，循环链表A、B 定义指针 p
• p指向B链表的最后一个结点指向的下下个结点的地址，即B的头结点指向的第一个数据
• 把A链表的最后一个结点的后继（A的头结点）赋值给 B链表的最后一个结点的后继（B的头结点）
• 把p的地址赋值给A链表的最后一个结点的后继
• p = B->next->next;//把B的头结点地址指向给p
• B->next = A->next; //把B的尾结点地址指向A的头结点
• A->next = p;//把A的尾结点地址指向B的头结点指向的地址（B的第一个有值结点）

代码不同处

//初始化 有头结点
Status InitList(LinkList &L)
{
	L = new LNode;
	L->next = L;
	return 1;
}

Status GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p = L->next;
	int j = 1;
	while (p!=L && j<i)//这里的改动！类似这种循环遍历的地方都要改
	{
		p = p->next;
		j++;
	}
	if (p==L || j > i) 
	{
		return 0;
	}
	e = p->data;
	return p->data;
}

完整实现代码

#include<iostream>
#include<string>

using namespace std;

/*
	循环链表 Circular Link List
*/


typedef int ElemType;
typedef int Status;

typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

//初始化循环链表 有头结点
Status InitList(LinkList &L)
{
	L = new LNode;
	L->next = L;
	return 1;
}

/*
	循环链表的取值（按位查找）: 时间复杂度O(n)
	参数一：要取值的循环链表
	参数二：要取值的位置
	参数三：待保存的对象
	注意：成功：返回1；失败：返回0。
*/
Status GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p = L->next;
	int j = 1;
	while (p!=L && j<i)//循环链表修改处！！！
	{
		p = p->next;
		j++;
	}
	if (p==L || j > i) //循环链表修改处！！！
	{
		return 0;
	}
	e = p->data;
	return p->data;
}

/*
	循环链表的查找（按值查找）:   时间复杂度O(n)
	参数一：要查找的循环链表
	参数二：要查找的数据
	注意：成功：返回下标地址；失败：返回NULL。
*/
LNode* LocateElem(LinkList L, ElemType e)
{
	LNode* p = L->next;//创建新结点，并指向第一块数据
	while (p && p->data!=e)//如果p不为空且data == e,返回p的地址
	{
		p = p->next;
	}
	return p;
}

/*
	循环链表的插入（按位序插入）:时间复杂度O(n)
	参数一：要插入的循环链表
	参数二：要插入的位置
	参数三：要插入的数据
	注意：成功：返回1；失败：返回0。
*/
Status ListInsert(LinkList& L, int i, ElemType e)
{
	if (i<1)
	{
		return 0;
	}
	LNode* p = L;//创建临时结点指向头结点，头结点不存数据
	int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
	//循环链表修改处！！！
	while (p->next!=L && (j<i-1))//循环找到第i-1个结点
	{
		p = p->next;
		j++;
	}
	//循环链表修改处！！！
	if (p==L || j>i-1)//如果地址p为NULL就退出，头结点的地址也不为空
	{
		return 0;
	}
	LNode* s = new LNode; //创建新结点
	s->data = e;//新结点存放新数据e
	s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;//p的指针指向新节点s

	return 1;
}


/*
	循环链表的删除:   时间复杂度O(n)
	参数一：要删除的循环链表
	参数二：要删除的位置
	注意：成功：返回1；失败：返回0。
*/
Status ListDelete(LinkList& L, int i)
{
	LNode* p = L;//创建临时结点指向头结点，头结点不存数据
	int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
	//循环链表修改处！！！
	while (p->next != L &&(j<i-1))//循环找到第i-1个结点的前一个结点
	{
		p = p->next;
		j++;
	}
	//循环链表修改处！！！
	if (p->next == L||(j>i-1))
	{
		return 0;
	}
	LNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
	p->next = q->next;//p的指针指向q的指针指向的下一个数据地址
	delete q;//释放q结点

	return 1;
}



int main()
{
	LinkList L;
	//初始化循环链表
	InitList(L);
	//插入循环链表
	for (int i = 1; i < 6; i++)
	{
		ListInsert(L, 1, i);
	}
	//取值
	int e;
	for (int i = 1; i <= 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}
	
	//查找
	cout << "5的地址为：" << LocateElem(L, 5) << endl;
	//删除
	ListDelete(L, 1);
	cout << "删除第一个元素5：" << endl;
	for (int i = 1; i < 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}
	
	return 1;
}