[数据结构与算法]C++实现单循环链的各种操作

1.什么是单链

????????如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的下一跳指向头结点。

????????????????????????

2.循环单链表节点结构体

?????????循环单链表的节点与普通单链表的节点相同并无本质的区别！

struct LNode {
	int data;    // 数据域
	LNode* next; // 指针域
};

typedef LNode LNode;     // LNode表示单链表的一个结点
typedef LNode* LinkList; // LinkList表示一个单链表

????????对循环单链表节点进行初始化：主要还是为了避免异常！

bool InitList(LinkList& L) {
	L = new LNode;//C/语言中使用：L = (LNode *)malloc(sizeof(LNode));与前者作用等价申请新节点
	if (!L) {
		cout << "申请节点失败！" << endl;
		return false;
	}
	L->next = NULL;//初始化节点的后继指针为空，避免引起错误！
	return true;
}

3.对循环单链表的操作

?3.1打印循环单链表

bool PrintList(const LinkList& L) {
	LNode* p = L->next;//p是第一个节点
	LNode* r = L;//r是头节点
	cout << "该循环单链表的值为：";
	while (p->next != r->next) {//如果头节点的后继指针与首节点的指针指向同一个节点，证明已经到了链尾
		cout << p->data<<" ";//输出该节点的数据
		p = p->next;//未到链尾，移动指针向后移动到下一个节点
	}	
	cout << endl;
	return true;
}

3.2 求出循环单链表的长度

int Length(const LinkList& L) {
	LNode* p = L->next;//p是第一个节点
	LNode* r = L;//r是头节点
	int i=0;//记录长度
	while (p)//能进入此循环证明p存在
	{
		i++;//p存在，让长度加一
		p = p->next;//p向后移动
		if (p->next == r->next) {//如果头节点的后继指针与首节点的指针指向同一个节点，证明已经到了链尾
			//cout << "该循环单链表的长度为:"<<i << endl;//输出长度
			return i;//返回长度
		}
	}
}

3.3 使用尾插法创建单循环链表

bool TailCirculateList(LinkList& L) {
	LNode* p = L;//p是头节点
	LNode* t = L;//t是头节点
	int x;
	cout << "使用尾插法实现的单链表，请输入要创建的个数：" ;
	cin >> x;
	if (x < 1) {
		cout << "您输入的个数无效！" << endl; 
		return false; 
	}
	else if (x == 1) {//只输入一个节点时是特殊情况，进行特殊处理
		LNode* r = new LNode;
		cout << "请输入要输入的值：";
		cin >> r->data;
		p->next = r;
		r->next = t->next;
		return true;
	}
	cout << "请输入要输入的值：";
	while (x) {//x>1的情况
		LNode* r = new LNode;//申请新节点r
		cin >> r->data;//为新节点r填充数据
		p->next = r;//让头节点指向新的节点
		p = r;//p移动到新节点，尾插法在链尾插入新节点，所以头节点（其实只是个工作指针）也要移动到链尾，便于第下次添加
		x--;
	}
	p->next = t;//此时p是链尾节点，为了构造成循环链，让尾节点指向头节点

	PrintList(L);//打印单循环链
	return true;
}

3.4 使用头插法创建单循环链表

bool HeadCirculateList(LinkList& L){

	LNode* t = L;//t是头节点
	LNode* h = L;//h是头节点
	LNode* p = new LNode;//申请一个新节点p
	int x;
	cout << "使用头插法实现的单链表，请输入要创建的个数：";
	cin >> x;
	if (x < 1) {
		cout << "您输入的个数无效！" << endl;
		return false;
	}
	else if (x == 1) {//只输入一个数据时，特殊情况，进行处理
		LNode* p = new LNode;
		cout << "请输入要输入的值：";
		cin >> p->data;
		t->next = p;
		p->next = t->next;
		return true;
	}
	cout << "请输入要输入的值：";
	while (x) {
		LNode* r = new LNode;//申请一个新节点r
		cin >> r->data;//为新节点填充数据
		t->next = r;//头节点指向新节点
		r->next = h;//让新节点指向头节点
		h = t->next;//让工作指针回到头节点
		x--;
	}
	PrintList(L);//打印单循环链
	return true;
}

3.5?按值查找循环单链表

bool GetValueElem(LinkList& L) {
	LNode* p = L->next;
	LNode* t = L;
	int x,i=0;
	cout << "请输入您要查找的值：";
	cin >> x;
	while (p)
	{
		i++;
		if (p->data == x) {
			cout << "恭喜您要查找的值在该单链表中且在该链表的第"<<i<<"位！" << endl;
			return true;
		}
		else
		{
			p = p->next;
			if (p->next == t->next) {
				cout << "抱歉您要查找的值不在该单链表中！" << endl;
				return false;
			}
		}
		
	}
}

3.6?按位查找循环单链表? ?

bool GetBitElem(LinkList& L) {
	LNode* p = L;
	int x;
	cout << "请输入您要查找的位：";
	cin >> x;
	int k = x;
	if (x<1 || x>Length(L)) {
		cout << "您输入的位数无意义或不存在！" << endl;
		return false;
	}
	while (x)
	{
		p = p->next;
		x--;
	}
	cout << "您要查找的第" << k << "位的数据为:" << p->data << endl;
	return true;
}

3.7 在循环单链表中按位插入节点

bool Insert(LinkList& L) {
	LNode* p = L;
	LNode* r = L;
	cout << "请输入你要插入的位数:";
	int x;
	cin >> x;
	if (x<=0 || x>Length(L)) {
		cout << "您插入的位数无意义或不存在！" << endl;
		return false;
	}
	cout << "请输入你要插入的值：";
	if (x < Length(L)) {
		LNode *q = new LNode;
		cin >> q->data;
		if (x == 1) {
			q->next = p->next;
			 p->next=q;
			 q = p;
			PrintList(L);//打印单循环链
			return true;
		}
		while (x)
		{
			p = p->next;
			x--;
		}
		q->next=p->next;
		p->next = q;
		PrintList(L);//打印单循环链
		return true;
	}
	else if (x == Length(L)) {//在链尾插入
		LNode* q = new LNode;
		cin >> q->data;
		while (x)
		{
			p = p->next;
			x--;
		}
		p->next = q;
		q->next = r;
		PrintList(L);//打印单循环链
		return true;
	}
}

3.8 在单循环链表中按位删除节点

bool DeleteBit(LinkList& L) {
	int n;
	LNode* p = L;
	LNode* r;
	InitList(r);
	cout << "请输入你要删除的节点的位数;";
	cin >> n;
	int k = n;
	if (n <1 || n> Length(L)) {
		cout << "您想删除的节点不存在" << endl;
		return false;
	}
	else if (n == Length(L)) {
		while (n)
		{
			p = p->next;
			n--;
		}
		r->next = p->next;
		r->data = p->next->data;
		p->next = r->next->next;
		cout << "要删除第" << k << "位的值" << p->data << "删除成功！";
		free(r);
		PrintList(L);//打印单链表
		return true;
	}
	while (n) {
		if (n == 1) {
			r->next = p->next;
			r->data = p->next->data;
			p->next = r->next->next;	
			cout << "要删除第"<<k<<"位的值" << r->data << "删除成功！" ;
			free(r);
			PrintList(L);//打印单链表
			return true;
		}
		n--;
		p = p->next;//节点向后移动
	}
}

3.8 在单循环链表中按值删除节点

bool DeleteValue(LinkList& L) {
	LNode* p = L;
	LNode* r;
	InitList(r);
	int v,x=Length(L);
	cout << "请输入你要删除的值;";
	cin >> v;
	while (x)
	{
		if (p->next->data == v) {
			r->data = p->next->data;
			r->next = p->next->next;
			p->next = r->next;
			free(r);
			cout << "要删除值为" << v << "的节点删除成功！";
			PrintList(L);//打印单链表
			return true;
		}
		p = p->next;
		x--;
	}
	cout << "要删除值为" << v << "的节点在单链表中不存在！";
	return false;
}

3.8 在单循环链表中按位修改节点的值

bool ReviseBit(LinkList& L) {
	int n,v;
	LNode* p = L;
	cout << "请输入你要修改的节点的位数;";
	cin >> n;
	if (n<1 || n>Length(L)) {
		cout << "你要修改的节点的位数不存在或无意义！"<<endl;
		return false;
	}
	cout << "请输入你要修改的节点的值;";
	cin >> v;
	while (n)
	{
		p = p->next;
		n--;
	}
	p->data = v;
	PrintList(L);//打印单链表
	return true;
}

3.8 在单循环链表中按值修改节点的值

bool ReviseValue(LinkList& L) {
	int n=Length(L),q,h;
	LNode* p = L;
	cout << "请输入你要修改的前的值和修改后的值;";
	cin >> q;
	cin >> h;
	while (n)
	{
		if (p->next->data == q) {
			p->next->data = h;
			PrintList(L);//打印单链表
			return true;
		}
		p = p->next;
		n--;
	}
	cout << "该单链表中不存在值为"<<q<<"的节点！" << endl;
	return false;
}

4.完整代码

#include<iostream>

using namespace std;

struct LNode {
	int data;    // 数据域
	LNode* next; // 指针域
};

typedef LNode LNode;     // LNode表示单链表的一个结点
typedef LNode* LinkList; // LinkList表示一个单链表

//函数申明
int Length(const LinkList& L);
bool InitList(LinkList& L);
bool PrintList(const LinkList& L);




//1.初始化
bool InitList(LinkList& L) {
	L = new LNode;//C/语言中使用：L = (LNode *)malloc(sizeof(LNode));与前者作用等价申请新节点
	if (!L) {
		cout << "申请节点失败！" << endl;
		return false;
	}
	L->next = NULL;//初始化节点的后继指针为空，避免引起错误！
	return true;
}
//2.打印单链表
bool PrintList(const LinkList& L) {
	LNode* p = L->next;//p是第一个节点
	LNode* r = L;//r是头节点
	cout << "该循环单链表的值为：";
	while (p->next != r->next) {//如果头节点的后继指针与首节点的指针指向同一个节点，证明已经到了链尾
		cout << p->data<<" ";//输出该节点的数据
		p = p->next;//未到链尾，移动指针向后移动到下一个节点
	}	
	cout << endl;
	return true;
}
//3.求单链表的长度
int Length(const LinkList& L) {
	LNode* p = L->next;//p是第一个节点
	LNode* r = L;//r是头节点
	int i=0;//记录长度
	while (p)//能进入此循环证明p存在
	{
		i++;//p存在，让长度加一
		p = p->next;//p向后移动
		if (p->next == r->next) {//如果头节点的后继指针与首节点的指针指向同一个节点，证明已经到了链尾
			//cout << "该循环单链表的长度为:"<<i << endl;//输出长度
			return i;//返回长度
		}
	}
}
//4.使用尾插法创建单循环链 
bool TailCirculateList(LinkList& L) {
	LNode* p = L;//p是头节点
	LNode* t = L;//t是头节点
	int x;
	cout << "使用尾插法实现的单链表，请输入要创建的个数：" ;
	cin >> x;
	if (x < 1) {
		cout << "您输入的个数无效！" << endl; 
		return false; 
	}
	else if (x == 1) {//只输入一个节点时是特殊情况，进行特殊处理
		LNode* r = new LNode;
		cout << "请输入要输入的值：";
		cin >> r->data;
		p->next = r;
		r->next = t->next;
		return true;
	}
	cout << "请输入要输入的值：";
	while (x) {//x>1的情况
		LNode* r = new LNode;//申请新节点r
		cin >> r->data;//为新节点r填充数据
		p->next = r;//让头节点指向新的节点
		p = r;//p移动到新节点，尾插法在链尾插入新节点，所以头节点（其实只是个工作指针）也要移动到链尾，便于第下次添加
		x--;
	}
	p->next = t;//此时p是链尾节点，为了构造成循环链，让尾节点指向头节点

	PrintList(L);//打印单循环链
	return true;
}
//5.使用头插法创建单循环链
bool HeadCirculateList(LinkList& L){

	LNode* t = L;//t是头节点
	LNode* h = L;//h是头节点
	LNode* p = new LNode;//申请一个新节点p
	int x;
	cout << "使用头插法实现的单链表，请输入要创建的个数：";
	cin >> x;
	if (x < 1) {
		cout << "您输入的个数无效！" << endl;
		return false;
	}
	else if (x == 1) {//只输入一个数据时，特殊情况，进行处理
		LNode* p = new LNode;
		cout << "请输入要输入的值：";
		cin >> p->data;
		t->next = p;
		p->next = t->next;
		return true;
	}
	cout << "请输入要输入的值：";
	while (x) {
		LNode* r = new LNode;//申请一个新节点r
		cin >> r->data;//为新节点填充数据
		t->next = r;//头节点指向新节点
		r->next = h;//让新节点指向头节点
		h = t->next;//让工作指针回到头节点
		x--;
	}
	PrintList(L);//打印单循环链
	return true;
}
//6.按值查找单链表
bool GetValueElem(LinkList& L) {
	LNode* p = L->next;
	LNode* t = L;
	int x,i=0;
	cout << "请输入您要查找的值：";
	cin >> x;
	while (p)
	{
		i++;
		if (p->data == x) {
			cout << "恭喜您要查找的值在该单链表中且在该链表的第"<<i<<"位！" << endl;
			return true;
		}
		else
		{
			p = p->next;
			if (p->next == t->next) {
				cout << "抱歉您要查找的值不在该单链表中！" << endl;
				return false;
			}
		}
		
	}
}
//7.按位查找单链表
bool GetBitElem(LinkList& L) {
	LNode* p = L;
	int x;
	cout << "请输入您要查找的位：";
	cin >> x;
	int k = x;
	if (x<1 || x>Length(L)) {
		cout << "您输入的位数无意义或不存在！" << endl;
		return false;
	}
	while (x)
	{
		p = p->next;
		x--;
	}
	cout << "您要查找的第" << k << "位的数据为:" << p->data << endl;
	return true;
}


//8.插入节点
bool Insert(LinkList& L) {
	LNode* p = L;
	LNode* r = L;
	cout << "请输入你要插入的位数:";
	int x;
	cin >> x;
	if (x<=0 || x>Length(L)) {
		cout << "您插入的位数无意义或不存在！" << endl;
		return false;
	}
	cout << "请输入你要插入的值：";
	if (x < Length(L)) {
		LNode *q = new LNode;
		cin >> q->data;
		if (x == 1) {
			q->next = p->next;
			 p->next=q;
			 q = p;
			PrintList(L);//打印单循环链
			return true;
		}
		while (x)
		{
			p = p->next;
			x--;
		}
		q->next=p->next;
		p->next = q;
		PrintList(L);//打印单循环链
		return true;
	}
	else if (x == Length(L)) {//在链尾插入
		LNode* q = new LNode;
		cin >> q->data;
		while (x)
		{
			p = p->next;
			x--;
		}
		p->next = q;
		q->next = r;
		PrintList(L);//打印单循环链
		return true;
	}
}
//9.按位删除节点
bool DeleteBit(LinkList& L) {
	int n;
	LNode* p = L;
	LNode* r;
	InitList(r);
	cout << "请输入你要删除的节点的位数;";
	cin >> n;
	int k = n;
	if (n <1 || n> Length(L)) {
		cout << "您想删除的节点不存在" << endl;
		return false;
	}
	else if (n == Length(L)) {
		while (n)
		{
			p = p->next;
			n--;
		}
		r->next = p->next;
		r->data = p->next->data;
		p->next = r->next->next;
		cout << "要删除第" << k << "位的值" << p->data << "删除成功！";
		free(r);
		PrintList(L);//打印单链表
		return true;
	}
	while (n) {
		if (n == 1) {
			r->next = p->next;
			r->data = p->next->data;
			p->next = r->next->next;	
			cout << "要删除第"<<k<<"位的值" << r->data << "删除成功！" ;
			free(r);
			PrintList(L);//打印单链表
			return true;
		}
		n--;
		p = p->next;//节点向后移动
	}
}
//10. 按值删除节点
bool DeleteValue(LinkList& L) {
	LNode* p = L;
	LNode* r;
	InitList(r);
	int v,x=Length(L);
	cout << "请输入你要删除的值;";
	cin >> v;
	while (x)
	{
		if (p->next->data == v) {
			r->data = p->next->data;
			r->next = p->next->next;
			p->next = r->next;
			free(r);
			cout << "要删除值为" << v << "的节点删除成功！";
			PrintList(L);//打印单链表
			return true;
		}
		p = p->next;
		x--;
	}
	cout << "要删除值为" << v << "的节点在单链表中不存在！";
	return false;
}
//11.按位修改循环单链表的节点
bool ReviseBit(LinkList& L) {
	int n,v;
	LNode* p = L;
	cout << "请输入你要修改的节点的位数;";
	cin >> n;
	if (n<1 || n>Length(L)) {
		cout << "你要修改的节点的位数不存在或无意义！"<<endl;
		return false;
	}
	cout << "请输入你要修改的节点的值;";
	cin >> v;
	while (n)
	{
		p = p->next;
		n--;
	}
	p->data = v;
	PrintList(L);//打印单链表
	return true;
}
//12.按值修改循环单链表的节点
bool ReviseValue(LinkList& L) {
	int n=Length(L),q,h;
	LNode* p = L;
	cout << "请输入你要修改的前的值和修改后的值;";
	cin >> q;
	cin >> h;
	while (n)
	{
		if (p->next->data == q) {
			p->next->data = h;
			PrintList(L);//打印单链表
			return true;
		}
		p = p->next;
		n--;
	}
	cout << "该单链表中不存在值为"<<q<<"的节点！" << endl;
	return false;
}
int main() {
	LinkList(L);
	InitList(L);//初始化
	HeadCirculateList(L);//使用头插法
	cout << endl;//换行，为了美观
	TailCirculateList(L);//使用尾插法
	GetValueElem(L);//按值查找
	GetBitElem(L);//按位查找
	Insert(L);//插入节点
	DeleteBit(L);//按位删除节点
	DeleteValue(L);//按值删除节点
	ReviseBit(L);//按位修改值
	ReviseValue(L);//按值修改
}

5. 运行结果及截图

在windows11操作系统的Visual Studio 2019编译器中运行的结果如下图所示！