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

news/2024/11/15 4:52:07/

判断循环双链表是否对称

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

算法思想

让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.ppmy.cn/news/1546390.html

相关文章

【AI技术】PaddleSpeech部署方案

【AI技术】PaddleSpeech部署方案 技术介绍优点缺点 部署基础环境的搭建分步详解国内镜像源切换所需环境1 g所需环境2 vim所需环境3 cuda所需环境4 cudnn所需环境5 ssl源码拉取PaddleSpeech环境安装 部署文件分享DockerHub 技术介绍 PaddleSpeech是飞浆平台的一款TTS框架。 优…

flink sql同步mysql数据表到mysql

1. 关闭防火墙和selinux systemctl stop firewalld systemctl disable firewalld systemctl status firewalld2.安装java8 yum list java-1.8* yum install java-1.8.0-openjdk* -yjava -version3.下载和部署mysql yum -y install wget wget https://dev.mysql.com/get/Down…

linux-c 使用c语言操作sqlite3数据库-1

一、练习目标 1、目标 1、使用sqlite3_exec执行查询语句&#xff0c;并将查询结果insert到链表中&#xff0c;最后打印链表的内容&#xff1b; 2、使用sqlite3_get_table执行查询语句&#xff0c;并以key&#xff1a;value的方式&#xff0c;打印查询结果。 2、环境准备 2.1、…

嵌入式采集网关(golang版本)

为了一次编写到处运行&#xff0c;使用纯GO编写&#xff0c;排除CGO&#xff0c;解决在嵌入式中交叉编译难问题 硬件设备&#xff1a;移远EC200A-CN LTE Cat 4 无线通信模块&#xff0c;搭载openwrt操作系统&#xff0c;90M内存

青少年编程与数学 02-003 Go语言网络编程 17课题、Go语言Cookie编程

青少年编程与数学 02-003 Go语言网络编程 17课题、Go语言Cookie编程 课题摘要:一、Cookie编程1. 发送Cookies2. 接收Cookies3. 删除Cookies4. Cookie的安全性5. 使用第三方库总结 二、应用场景1. 会话管理&#xff08;Session Management&#xff09;2. 个性化设置3. 追踪用户行…

ajax关于axios库的运用小案例

AJAX案例 图书管理 四大功能&#xff1a; 展示图书删除图书编辑图书信息新增图书 步骤 1.bootstrap弹窗来实现新增和编辑图书时出现的弹窗 有两种方案&#xff1a; a.可以用自带的属性来进行弹窗的显示和隐藏 b.可以通过JS进行控制&#xff0c;此操作可以进行自定义&am…

Ceph MDS高可用架构探索:从零到一构建多主一备MDS服务

文章目录 Ceph实现MDS服务多主一备高可用架构当前 mds 服务器状态添加 MDS 服务器验证ceph集群当前状态当前的文件系统状态设置处于激活状态 mds 的数量MDS 高可用优化分发配置文件并重启 mds 服务 Ceph实现MDS服务多主一备高可用架构 Ceph 的元数据服务&#xff08;MDS&#…

Python学习从0到1 day27 Python 高阶技巧 ④ 设计模式 — 工厂模式

目录 一、什么是工厂模式 二、工厂模式的优点 三、代码示例 总结 1.什么是工厂模式 2.好处 或许总要彻彻底底地绝望一次&#xff0c;才能重新再活一次 —— 24.11.11 一、什么是工厂模式 当需要大量创建一个类的实例的时候&#xff0c;可以使用工厂模式 即&#xff0c;从原生…