链表循环及差集相关算法题|判断循环双链表是否对称|两循环单链表合并成循环链表|使双向循环链表有序|单循环链表改双向循环链表|两链表的差集(C)

判断循环双链表是否对称

设计一个算法用于判断带头节点的循环双链表是否对称

算法思想

让left从左向右扫描,right从右向左扫描,直到它们指向同一个节点:left == right
或相邻left->next == right,或right->prev == left,为止
若它们所指节点值相同,则继续下去,否则返回false,若比较全部相等,则返回true
![[Pasted image 20241111143209.png]]

当节点个数是奇数
![[Pasted image 20241111143238.png]]

直到left == right时,循环结束
![[Pasted image 20241111143329.png]]

当节点个数是偶数
![[Pasted image 20241111143359.png]]

直到发生交错后,right的next指向left,循环结束

bool Symmetry(DLinkList &L)
{// 初始化左右指针,指向链表的首尾节点DNode* left = L->next, *right = L->prev;// 当左右指针未相遇,且未交错while (left != right && right->next != left){// 如果左右数据相等if (left->data == right->data){// 左指针右移left = left->next;// 右指针左移right = right->prev;}// 如果不相等,则链表不对称elsereturn false;}// 循环结束,说明链表对称return true;
}

两循环单链表合并成循环链表

有两个循环单链表,链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后,要求连接后的链表仍保持循环链表的形式

算法思想

先找到两个链表的尾指针,将第一个链表的尾指针与第二个链表的头指针链接起来,再使之成为循环链表
![[Pasted image 20241111144227.png]]

找尾
![[Pasted image 20241111144245.png]]

将cur1的next指向h2
![[Pasted image 20241111144324.png]]

将cur2的next指向h1
![[Pasted image 20241111144347.png]]

构成循环链表

LinkList Link(LinkList &h1, LinkList &h2)
{// 创建两个工作指针cur1和cur2LNode* cur1, cur2;cur1 = h1;// 寻找h1的尾节点while (cur1->next != h1){cur1 = cur1->next;}cur2 = h2;// 寻找h2的尾节点while (cur2->next != h2){cur2 = cur2->next;}// 将h2链接到h1之后cur1->next = h2;// 令h2的尾节点指向h2cur2->next = h1;return h1;
}

使双向循环链表有序

已知一双向循环链表,从第二个节点至表尾递增有序
将第一个节点删除并插入表中适当位置,使整个链表递增有序

算法思想

应该先将第一节点从链表上摘下来,再将其插入到链表中相应的位置,由于是双向链表,不必像单链表那样插入节点的前驱
![[Pasted image 20241111145739.png]]

断开tmp和链表
cur的prev指向L的prev
![[Pasted image 20241111145942.png]]

L的prev的next指向cur
![[Pasted image 20241111150019.png]]

查插入位置
直到cur的data大于等于x后停下,之后把原第一个节点插在cur的前一个位置
tmp的next指向cur,tmp的prev指向cur的prev
![[Pasted image 20241111150227.png]]

cur的前一个的next指向tmp,cur的prev指向tmp
![[Pasted image 20241111150320.png]]

void DInsert(DLinkList &L)
{// tmp暂存第一节点的指针DNode* tmp = L;int x = L->data;// 将第一个节点从链表上摘下DNode* cur = L->next;cur->prev = L->prev;L->prev->next = cur;// 查插入位置while (cur && cur->data < x){cur = cur->next;}// 插入原第一节点tmp->next = cur;tmp->prev = cur->prev;cur->prev->next = tmp;cur->prev = tmp;
}

单循环链表改双向循环链表

假设一个单循环链表,其节点含有三个域,prev,data,next,prev为空指针,next指向后继节点
将此表改为双向循环链表
![[Pasted image 20241111153358.png]]

cur的next的prev指向cur
直到cur的next的prev不为空
![[Pasted image 20241111153514.png]]

cur正好遍历完链表

算法思想

关键是控制每个节点均置上指向前驱的指针,而且每个节点的前驱指针置且仅置一次

void StoDouble(LinkList &L)
{LNode* cur = L;while (cur->next->prev == NULL){cur->next->prev = cur;cur = cur->next;}
}

两链表的差集

已知递增有序的单链表A,B分别存储了一个集合,请设计算法以求出两个集合A和B的差集,A-B,并以同样的方式存储,同时返回该集合的元素个数

算法思想

在A中删除A和B中共有的元素,由于是单链表,删除节点要记住被删除节点的前驱,两个链表都开始遍历,直到一个链表遍历结束

void Difference(LinkList &A, LinkList &B, int* n)
{// cura和curb分别是链表A和B的工作指针LNode* cura = A->next;LNode* curb = B->next;// prev为链表A中cur所指节点的前一个节点LNode* prev = A;while (cura && curb){if (cura->data < curb->data){prev = cura;cura = cura->next;*n++;}else if (cura->data > curb->data){curb = curb->next;}// 元素值相同的节点,删除else{prev->next = cura->next;LNode* del = cura;cura = cura->next;free(del);}}while (cura){cura = cura->next;*n++;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/12385.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

基于STM32的智能声控分类垃圾桶(论文+源码)

1系统的功能及方案设计 本次课题为基于STM32的智能声控分类垃圾桶&#xff0c;其系统整体架构如图2.1所示&#xff0c;整个系统包括了stm32f103单片机主控制器&#xff0c;LU-ASR01语音识别模块&#xff0c;WT588语音播报模块&#xff0c;舵机等器件&#xff0c;用户可以通过语…

华大单片机跑历程IO口被写保护怎么解决

一&#xff0c;说明 使用的单片机是HC32F460KETA华大单片机&#xff0c;使用的代码历程是小华单片机历程&#xff0c;具体历程在小华官网都可以找到。   在使用小华历程跑模拟IIC时&#xff0c;SCL时钟是有的&#xff0c;但是IO输入被LOCK了&#xff0c;所以在跑历程进行断点…

网络与通信实验一 网络协议分析

Wireshark的安装 https://www.wireshark.org/&#xff08;下载链接&#xff09; 具体安装步骤参考 安装步骤 点击即可自动跳转 安装后打开 输入ipconfig 选择ipv4网卡存在的设备&#xff08;我的电脑选择WiFi&#xff09; 过滤条件选择 icmp cmd下输入 ping www.baidu.com…

电脑网络丢包怎么排查优化

上网已经成为必不可少的一部分,无论是看视频、玩游戏还是办公,网络的稳定性直接影响到我们的体验。然而有时候会遇到一些问题,比如网页加载慢、视频卡顿、游戏掉线等。这些问题的背后,往往是因为网络丢包。 网络丢包检测工具分享 什么是网络丢包? 网络丢包,简单来说,就是…

从0开始学习Linux——进程管理

往期目录&#xff1a; 从0开始学习Linux——简介&安装 从0开始学习Linux——搭建属于自己的Linux虚拟机 从0开始学习Linux——文本编辑器 从0开始学习Linux——Yum工具 从0开始学习Linux——远程连接工具 从0开始学习Linux——文件目录 从0开始学习Linux——网络配置 从0开…

QT6.5+qt-quick+qml+cmake的Item布局学习

Item 是一个基础元素&#xff0c;它本身不会渲染任何东西&#xff0c;也不会提供一个窗口来显示其内容。Window 是一个可以显示内容的顶级元素&#xff0c;它通常会包含一个或多个子元素来构建用户界面。Item是全部QML可视化对象的根&#xff0c;所有可视化类型都由该类型派生出…

Cameralink转MIPI,Cameralink视频识别分析

CameraLink视频输入转MIPI极简方案&#xff0c;可直接输入到处理芯片中进行视频目标识别与跟踪

【算法】【优选算法】二分查找算法(下)

目录 一、852.⼭脉数组的峰顶索引1.1 二分查找1.2 暴力枚举 二、162.寻找峰值2.1 二分查找2.2 暴力枚举 三、153.寻找旋转排序数组中的最⼩值3.1 二分查找3.2 暴力枚举 四、LCR 173.点名4.1 二分查找4.2 哈希表4.3 暴力枚举4.4 位运算4.5 数学&#xff08;求和&#xff09; 一、…

递归函数学习 part1

一&#xff0c;初始递归&#xff1a;阶乘 1&#xff0c;原理 n的阶乘等于n乘以n-1的阶乘&#xff0c;而0的阶乘等于1. 2&#xff0c;代码展示 #include <iostream> using namespace std;int fact(int); int main() {cout<<fact(5);return 0; }int fact(int n) …

开源 - Ideal库 -获取特殊时间扩展方法(四)

书接上回&#xff0c;我们继续来分享一些关于特殊时间获取的常用扩展方法。 01、获取当前日期所在月的第一个指定星期几 该方法和前面介绍的获取当前日期所在周的第一天&#xff08;周一&#xff09;核心思想是一样的&#xff0c;只是把求周一改成求周几而已&#xff0c;当然其…

Python练习18

Python日常练习 题目&#xff1a; 请编fun函数&#xff0c;求44整型数组的主对角线元素的和。 说明&#xff1a; 如下图所示为一个44整型数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 测试用例&#xff1a; 1 2 3 4 5 6 7 8…

智防未戴帽,安全无死角

在追求高效与安全并重的现代工业环境中&#xff0c;员工佩戴安全帽作为最基本的防护措施&#xff0c;其重要性不言而喻。为了有效杜绝员工未佩戴安全帽的现象&#xff0c;我们提出了一套以AI视频分析与安全教育培训系统为核心的综合解决方案&#xff0c;旨在通过智能化手段与系…

C++ 优先算法 —— 四数之和(双指针)

目录 题目&#xff1a;四数之和 1. 题目解析 2. 算法原理 Ⅰ. 暴力枚举 Ⅱ. 双指针算法 不漏的处理&#xff1a; 去重处理&#xff1a; 3. 代码实现 Ⅰ. 暴力枚举 Ⅱ. 双指针算法 题目&#xff1a;四数之和 1. 题目解析 题目截图&#xff1a; 这道题与三数之和&am…

[vulnhub] Corrosion: 2

https://www.vulnhub.com/entry/corrosion-2,745/ 提示&#xff1a;枚举才是神 主机发现端口扫描 使用nmap扫描网段类存活主机 因为靶机是我最后添加的&#xff0c;所以靶机IP是6 &#xff0c;kali是10 nmap -sP 192.168.56.0/24 Starting Nmap 7.94SVN ( https://nmap.org ) …

前端请求后端php接口跨域 cors问题

只需要后端在网站的入口文件 一般都是 index.php 加上 这几行代码就可以了 具体的参数可以根据需要去修改 header("Access-Control-Allow-Origin: *"); header(Access-Control-Allow-Methods: GET, POST, PUT, DELETE, OPTIONS); header(Access-Control-Allow-Heade…

【星闪EBM-H63开发板】AT固件的配置与测试

引言 前面的博客已经介绍了【星闪EBM-H63开发板】小熊派固件中心的使用_bearpi-bm h63固件烧录工具-CSDN博客和【星闪EBM-H63开发板】固件的烧录-CSDN博客&#xff0c;今天来测试一下另一种固件&#xff0c;也就是AT固件。有关AT固件的介绍参见&#xff1a;【星闪EBM-H63开发板…

Linux基础(十四)——BASH

BASH 1.BASH定义2.shell的种类3.bash的功能3.1 命令记录功能3.2 命令补全功能3.3 命令别名设置3.4 工作控制、 前景背景控制3.5 程序化脚本&#xff1a; &#xff08; shell scripts&#xff09;3.6 万用字符 4.bash的内置命令5.shell的变量功能5.1 变量的取用5.2 新建变量5.3 …

【前端学习笔记】JavaScript学习一【变量与数据类型】

一、变量 变量是计算机中用来存储数据的“容器”&#xff0c;通俗的理解变量就是使用【某个符号】来代表【某个具体的数值】&#xff08;数据&#xff09; 声明&#xff1a;声明(定义)变量有两部分构成&#xff1a;关键字 变量名 JavaScript 使用关键字 let 和 var 来声明&am…

使用Git工具在GitHub的仓库中上传文件夹(超详细)

如何使用Git工具在GitHub的仓库中上传文件夹&#xff1f; 如果觉得博主写的还可以&#xff0c;点赞收藏关注噢~ 第一步&#xff1a;拥有一个本地的仓库 可以fork别人的仓库或者自己新创建 fork别人的仓库 或者自己创建一个仓库 按照要求填写完成后&#xff0c;点击按钮创建…

Linux kernel 堆溢出利用方法(二)

前言 本文我们通过我们的老朋友heap_bof来讲解Linux kernel中off-by-null的利用手法。在通过讲解另一道相对来说比较困难的kernel off-by-null docker escape来深入了解这种漏洞的利用手法。&#xff08;没了解过docker逃逸的朋友也可以看懂&#xff0c;毕竟有了root权限后&a…