首页 > 编程语言 >单向循环链表的实现及相关算法

单向循环链表的实现及相关算法

时间：2024-10-24 13:21:01浏览次数：7  
标签：Node head val int 单向 结点 next 链表 算法

1.单向循环链表

特点： 每一个节点除了数据域，还有一个next指针域指向下一个节点(存储了下一个节点的地址)，末尾节点的指针域指向了头节点

1.1实现过程

1.1.1、构建结点
struct Node
{
	Node(int value = 0) :
		val(value),
		next(nullptr)
	{}
	int val;
	Node* next;
};
1.1.2、构建操作对象
class circleLink
{
	friend void text01();
public:
	circleLink();
	~circleLink();
public:
	//尾插法O(1)
	void InsertTail(int val);
	//头插法O(1)
	void InsertHead(int val);
	//删除结点
	void deleteNode(int value);
	//查询
	bool FindNode(int val);
	//显示
	void showNode();
private:
	Node* head;
	Node* tail;
};
1.1.3、构造函数
circleLink(){
	this->head = new Node;
	this->tail = this->head;
	head->next = this->head;
}

创建头结点，让指向尾结点的指针指向头结点，头结点的下一个结点指向头结点

1.1.4、析构函数
~circleLink() {
	Node* p = this->head->next;
	while (p != head) {
		this->head->next = p->next;
		delete p;
		p = this->head->next;
	}
	delete this->head;
}

先让头结点指向p->next，再回收p指向的结点内存，回收完后，将p重新指向头结点的下一个结点，循环该过程，直到p指向头结点，退出循环后最后回收头结点指向的内存空间

1.1.5、尾插元素

时间复杂度O(1)

void InsertTail(int val) {
	Node* tem = new Node(val);
	tem->next = this->head;
	this->tail->next = tem;
	this->tail = tem;
}

创建一个新结点，用指针tem维护，将该结点的next指向头结点，将之前的尾结点的next指向新结点，并更新尾结点的指向为tem

1.1.6、头插元素

时间复杂度O(1)

void InsertHead(int val) {
	Node* tem = new Node(val);
	tem->next = this->head->next;
	head->next = tem;
	if (this->tail == this->head) {
		this->tail = tem;
	}
}

创建一个新结点，将该结点的next指向头结点的next，头结点的next指向新结点，还需要判断原来的链表存不存在有效结点，不存在的话需要将尾结点重新更新指向成tem

1.1.7、删除结点
void deleteNode(int value) { //删除结点
	Node* q = this->head;
	Node* p = this->head->next;
	while (p != this->head) {
		if (p->val == value) {
			q->next = p->next;
			delete p;
			if (q->next == this->head) {
				this->tail = q;
			}
			return;
		}
		else {
			q = q->next;
			p = p->next;
		}
	}
}

删除结点需要两个指针，遍历链表，如果找到值为value的结点，删除它，如果被删的结点是尾结点，需要更新尾指针的指向

1.1.8、查询结点
bool FindNode(int val) { //查询
	for (Node* p = this->head->next; p != this->head; p = p->next) {
		if (p->val == val) {
			return true;
		}
	}
	return false;
}

循环结束条件是p回到了头结点

遍历链表，若存在值为val的结点返回true，循环结束后没找到，则返回false

3.1.9、打印链表
void showNode() { //打印
	for (Node* p = this->head->next; p != this->head; p = p->next) {
		cout << p->val << ' ';
	}
	cout << endl;
}

遍历链表，打印链表每个元素的值

1.1.10、完整代码
#include<iostream>
using namespace std;

struct Node
{
	Node(int value = 0) :
		val(value),
		next(nullptr)
	{}
	int val;
	Node* next;
};

class circleLink
{
	friend void text01();
public:
	circleLink(){
		this->head = new Node;
		this->tail = this->head;
		head->next = this->head;
	}
	~circleLink() {
		Node* p = this->head->next;
		while (p != head) {
			this->head->next = p->next;
			delete p;
			p = this->head->next;
		}
		delete this->head;
	}
public:
	//尾插法O(1)
	void InsertTail(int val) {
		Node* tem = new Node(val);
		tem->next = this->head;
		this->tail->next = tem;
		this->tail = tem;
	}
	//头插法O(1)
	void InsertHead(int val) {
		Node* tem = new Node(val);
		tem->next = this->head->next;
		head->next = tem;
		if (this->tail == this->head) {
			this->tail = tem;
		}
	}
	//删除结点
	void deleteNode(int value) {
		Node* q = this->head;
		Node* p = this->head->next;
		while (p != this->head) {
			if (p->val == value) {
				q->next = p->next;
				delete p;
				if (q->next == this->head) {
					this->tail = q;
				}
				return;
			}
			else {
				q = q->next;
				p = p->next;
			}
		}
	}
	//查询
	bool FindNode(int val) {
		for (Node* p = this->head->next; p != this->head; p = p->next) {
			if (p->val == val) {
				return true;
			}
		}
		return false;
	}
	//显示
	void showNode() {
		for (Node* p = this->head->next; p != this->head; p = p->next) {
			cout << p->val << ' ';
		}
		cout << endl;
	}
private:
	Node* head;
	Node* tail;
};
void text01() {
	circleLink cl;
	for (int i = 1; i < 11; i++) {
		cl.InsertHead(i);
	}
	cl.showNode();
	cl.deleteNode(4);
	cl.showNode();
}
int main() {
	text01();
	system("pause");
	return 0;
}
1.1.11、测试

运行结果：

10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 3 2 1

符合预期结果

1.2约瑟夫环

不带头节点的单向循环链表

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）
围坐在一张圆桌周围，从编号为k的人开始报数，数到m的那个人出列，
它的下一个人又从1开始报数，数到m的那个人又出列，
依此规律重复下去，直到圆桌周围的人全部出列，输出人的出列顺序

代码实现：

Node* Joseph(Node* head, int k, int m) {
	if (k < 1 || k > N) {
		return nullptr;
	}
	Node* p = head->next;
	Node* q = head;
	//先让p指向编号为k那个人
	for (int i = 1; i < k; i++) {
		p = p->next;
		q = q->next;
	}
	int num = 1;
	while (p != q) {
		//删除数到m的那个人
		for (int i = 1; i < m; i++) {
			p = p->next;
			q = q->next;
		}
		cout << "第" << num++ << "个出列：" << p->value << endl;
		//删除报数为m的那个人
		q->next = p->next;
		delete p;
		p = q->next;
	}
	return p;
}

问题分析

if (k < 1 || k > N) {
	return nullptr;
}
Node* p = head->next;
Node* q = head;
//先让p指向编号为k那个人
for (int i = 1; i < k; i++) {
	p = p->next;
	q = q->next;
}

先判断k的有效性，因为需要删除结点，需要两个指针，先让p指向编号为k的那个人，q紧随其后

int num = 1;
while (p != q) {
	//删除数到m的那个人
	for (int i = 1; i < m; i++) {
		p = p->next;
		q = q->next;
	}
	cout << "第" << num++ << "个出列：" << p->value << endl;
	//删除报数为m的那个人
	q->next = p->next;
	delete p;
	p = q->next;
}
return p;

先让指针p走到数到m的那个人，删除它，之后将q->next赋值给p，循环上述过程，直到p、q指针重合，这个指针指向的值则为最终存活的

测试

Node* head = initList();
Node* p = head;
//构建1-8的环
for (int i = 1; i <= N; i++) {
	Node* tem = new Node(i);
	p->next = tem;
	p = p->next;
}
p->next = head->next;

cout<< "最终剩余的是：" << Joseph(head, 1, 10)->value << endl;

先构建环结构，将他们赋值1-8

测试结果：

第1个出列：2
第2个出列：5
第3个出列：1
第4个出列：8
第5个出列：4
第6个出列：6
第7个出列：3
最终剩余的是：7

符合预期结果

1.3相关算法

1.3.1判断单链表是否存在环

问题描述：判断单链表是否存在环，并且返回环的入口结点

代码实现：

int IsCircle(Node* head) {
	Node* p = head;
	Node* q = head;
	do {
		if (p == nullptr || p->next == nullptr) {
			return -1;
		}
		p = p->next->next;
		q = q->next;
	} while (p != q);
	q = head;
	while (1) {
		q = q->next;
		p = p->next;
		if (p == q) {
			return q->value;
		}
	}
}

问题分析

Node* p = head;
Node* q = head;

引入p、q快慢指针，p每次走两个结点，q每次走一个结点

do {
	if (p == nullptr || p->next == nullptr) {
		return -1;
	}
	p = p->next->next;
	q = q->next;
} while (p != q);

如果p走到头了，返回-1，不存在环，p每次走两个节点，q每次走一个结点，p、q一定会相遇

模拟过程如下：

首先，p、q都指向头结点，如下图所示：

第一次循环：

第二次循环：

第三次循环：

第四次循环：

第五次循环：

第六次循环：

此时p、q相遇，退出循环

并且，p到环入口结点的距离=头结点到入口结点的距离

推导过程如下：

设头结点到入口结点距离为k，以环内顺时针为正方向，入口结点到二者相遇点的距离为x，二者相遇点到入口结点的距离为y

如下图所示：

根据等式：p走的距离等于两倍q走的距离

\Rightarrow k + x + y + x = 2 * (k + x)

\Rightarrow y = k

让q回到头结点，p保持不动

q = head;
while (1) {
	q = q->next;
	p = p->next;
	if (p == q) {
		return q->value;
	}
}

每循环一次，p、q都向后走一个结点，当他们相等时，则在环入口结点相遇

测试：

Node* head = new Node;
head->next = nullptr;
Node* p = head;
Node* x = nullptr;//环形链表的终点
for (int i = 0; i < 9; i++) {
	Node* tem = new Node;
	tem->value = i;
	p->next = tem;
	p = p->next;
	if (i == 3) {
		x = p;
	}
}
p->next = x;
//print(head);
cout << IsCircle(head) << endl;

先将结点值为3的结点保存在x中，等链表遍历完后，将尾结点的next指向x，这样就构建了环

经过测试，程序输出5，符合预期效果

1.1.2旋转链表

问题描述：

给定一个k，旋转链表
head = [1, 2, 3, 4]    k = 3
-> head = [2, 3, 4, 1]
head = [1, 2, 3, 4, 5, 6, 7, 8, 9]   k = 5
-> head = [5, 6, 7, 8, 9, 1, 2, 3, 4]

实现代码：

void rotateRight(Node*& head, int k) {
	if (head == nullptr) {
		return;
	}
	int listLen = 0;
	Node* q = nullptr;
	for (Node* p = head; p; p = p->next) {
		if (p->next == nullptr) {
			q = p;
		}
		listLen++;
	}
	q->next = head;
	k %= listLen;
	Node* p = head;
	for (int i = 1; i < listLen - k; i++) {
		p = p->next;
	}
	head = p->next;
	p->next = nullptr;
}

问题分析

if (head == nullptr) {
	return;
}
int listLen = 0;
Node* q = nullptr;
for (Node* p = head; p; p = p->next) {
	if (p->next == nullptr) {
		q = p;
	}
	listLen++;
}
q->next = head;
k %= listLen;

先判断链表是否为空，为空return，之后算出链表的长度listLen，遍历链表将链表的尾结点记录到q中，通过q->next = head，将链表头尾相链接形成环状，将k取模算出旋转的有效值(可能存在周期)

Node* p = head;
for (int i = 1; i < listLen - k; i++) {
	p = p->next;
}
head = p->next;
p->next = nullptr;

将p指向头结点，让p走到listLen - k的位置，该位置则指向旋转后的链表的尾结点，更新新链表的头结点地址，并且将尾节点的next置为nullptr

测试

Node* head = new Node;
head->next = nullptr;
Node* p = head;
head->val = 1;
for (int i = 2; i < 10; i++) {
	Node* tem = new Node;
	tem->val = i;
	p->next = tem;
	p = p->next;
}
p->next = nullptr;
print(head);
rotateRight(head, 5);
print(head);

输出结果：

1 2 3 4 5 6 7 8 9
5 6 7 8 9 1 2 3 4

符合预期结果

标签：Node,head,val,int,单向,结点,next,链表,算法
From： https://blog.csdn.net/d6d4664948/article/details/143206615

相关文章

  • C#常见的四种经典查找算法
    前言在编程领域，数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚给大家分享四种C#中常见的经典查找算法。C#数据结构与算法实战入门指南：https://mp.weixin.qq.com/s/XPRmwWmoZa4zq29K......
  • 代码随想录算法训练营第九天|leetcode151.翻转字符串里的单词、卡码网55.右旋字符串
    1leetcode151.翻转字符串里的单词题目链接：151.反转字符串中的单词-力扣（LeetCode）文章链接：代码随想录视频链接：字符串复杂操作拿捏了！|LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili自己的思路：直接将空格去掉，然后分割字符串为列表，在列表中进行翻转，不在字符串内部操作，......
  • 烟火检测视频分析网关算法定制烟火识别技术在沿街商铺消防安全管理中的应用
    在沿街商铺的消防安全管理中，烟火检测视频分析网关算法的应用显得尤为重要。随着城市化进程的加快，沿街商铺数量激增，这些商铺在为居民生活带来便利的同时，也因店主安全意识不足、消防管理松散等问题，成为火灾隐患的高发区。因此，采用智能化的烟火识别技术，对于提升消防安全管理水平、预......
  • Photoshop图像算法（四）（代码在每个原理后面）
    色彩均衡化色彩均衡化（或称为直方图均衡化）是一种图像处理技术，目的是改善图像的对比度，使图像中的细节更加明显。它通过重新分配颜色通道的像素值，使得图像的直方图分布更均匀。以下是其基本原理：原理直方图计算：首先计算图像的颜色直方图，即统计每个像素值出现的频率。对于每个......
  • 局部路径规划(Local planning)算法之——TEB轨迹规划
    1TEB算法原理TEB全程为TimeElasticBand(时间弹力带)，通过对给定的全局轨迹进行修正，从而优化机器人的局部运动轨迹。他是常用的局部路径规划方法之一。TEB是基于图优化的方法，以g2o优化框架实现，它以机器人在各个离散时间的位姿和离散时刻之间的时间间隔为顶点，通过多目标优化，包括......
  • 2024年计算机科学与智能算法国际论坛(CSIA 2024) 2024 International Symposium on C
    @目录一、会议详情二、重要信息三、大会介绍四、出席嘉宾五、征稿主题一、会议详情二、重要信息大会官网：https://ais.cn/u/vEbMBz提交检索：EICompendex、IEEEXplore、Scopus三、大会介绍2024年计算机科学与智能算法国际论坛(CSIA2024)将作为主会议第六届智能控制、测......
  • 强化学习算法性能度量的常用方法
    本文介绍一下强化学习中的常用性能度量方法，或者说是强化学习中常用的性能测量标准。常用的两种RL训练过程中的算法性能度量方法/性能测试方法(两种性能曲线图的绘制)：训练过程中不对训练过程进行暂停，不单独测试算法性能而是使用训练过程的性能表现作为算法的性能表现，具体为取训......
  • LVS三种模式区别及负载均衡算法
    LVS简介LVS（LinuxVirtualServer）即linux虚拟服务器，是一个虚拟的服务器集群系统正向代理和反向代理 正向代理：只用于代理内部网络对internet的连接请求，客户机必须指定代理服务器，并将本来要直接发送到web服务器上的http请求发送到代理服务器，正向代理指的是客户端代理 反向代......
  • 计算机毕业设计Spark+大模型某音视频情感分析 某音可视化 某音舆情监测 预测算法 某音
    《Spark+大模型抖音视频情感分析》开题报告一、研究背景与意义随着移动互联网和社交媒体的快速发展，短视频平台如抖音（TikTok）已成为全球范围内广受欢迎的娱乐和信息获取渠道。用户在这些平台上发布的视频内容涵盖了娱乐、教育、新闻等各个领域，形成了海量的用户行为数据和视频内......
  • 代码随想录算法训练营第二十四天|Day24 回溯算法
    93.复原IP地址题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/思路char**result;intresultTop;intsegments[3];intisValid(char*s,intstart,intend){......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99