【5.线性表-链式表示-王道课后算法题】
王道数据结构-第二章-链式表示算法题
- 1.在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。
- 2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一)。
- 3. 试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为O(1)。
- 3.1 反向断链的方式
- 4. 设在一个带表头结点的单链表中,所有结点的元素值无序,试编写一个函数,删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。
- 5. 给定两个单链表,试分析找出两个链表的公共结点的思想(不用写代码)。
- 6. 设C={a1,b1,a2,b2,…,an,bn}为线性表,采用带头结点的单链表存放,设计一个就地算法,将其拆分为两个线性表,使得A{a1,a2,…,an},B={bn,…,b2,b1}。
- 7. 在一个递增有序的单链表中,存在重复的元素。设计算法删除重复的元素,例如(7,10,10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。
1.在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。
bool delteElement(LinkList &L, int x) {LNode *p = L->next;LNode *pre = L, *q;while (p != NULL) {if (p->data == x) {q=p;p=p->next;pre->next = p;free(q);} else {pre = p;p = p->next;}}return true;
}
2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一)。
bool deleteMin(Linklist &L) {LNode *p = L->next;int value = 9999999;LNode *pre = L, *min = L->next, *preMin = L;while (p != NULL) {if (p->data < value) {value=p->data;min = p;preMin = pre;p = p->next;} else {pre = p;p = p->next;}}preMin->next = min->next;free(min);return true;
}
3. 试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为O(1)。
//头插法
bool invertList(Linklist &L) {LNode *p = L->next, *q ;L->next = NULL;while (p != NULL) {//q指向p的下一个 防止断链q=p->next;//将p插入到头结点之后p->next=L->next;L->next=p;p=q;}return true;
}
3.1 反向断链的方式
//反向断链 1 2 3 4
bool invertList2(Linklist &L) {// 空链表或只有一个节点的链表不需要反转if (L == NULL || L->next == NULL) {return true;}LNode *p = L->next;LNode *pre;LNode *r ;L->next = nullptr;while (p != NULL) {r = p->next; // 先保存下一个节点p->next = pre; // 反转当前节点的 next 指针pre = p; // 移动 pre 到当前节点p = r; // 移动 p 到下一个节点}L->next = pre; // 将头节点的 next 指向新的头节点return true;
}
4. 设在一个带表头结点的单链表中,所有结点的元素值无序,试编写一个函数,删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。
bool deleteBetween(Linklist &L, int x, int y) {if (x >= y) {return false;}if (L->next == nullptr) {return false;}LNode *p = L->next, *pre = L, *q;while (p != nullptr) {if (x <= p->data && p->data <= y) {q = p;p = p->next;pre->next = p;free(q);} else {pre = p;p = p->next;}}return true;
}
5. 给定两个单链表,试分析找出两个链表的公共结点的思想(不用写代码)。
- 两个单链表有公共结点,即两个链表从某一结点开始,它们的 next 都指向同一结点。由于每
个单链表结点只有一个 next 域,因此从第一个公共结点开始,之后的所有结点都是重合的,不可
能再出现分叉。所以两个有公共结点而部分重合的单链表,拓扑形状看起来像Y,而不可能像X- 本题极容易联想到“蛮”方法:在第一个链表上顺序遍历每个结点,每遍历一个结点,在第
二个链表上顺序遍历所有结点,若找到两个相同的结点,则找到了它们的公共结点。显然,该算
法的时间复杂度为O(lenlxlen2)。- 接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化:如何判断两个单向链表
有没有公共结点?应注意到这样一个事实:若两个链表有一个公共结点,则该公共结点之后的所
有结点都是重合的,即它们的最后一个结点必然是重合的。因此,我们判断两个链表是不是有重
合的部分时,只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的,则说明它们有
公共结点,否则两个链表没有公共结点。
然而,在上面的思路中,顺序遍历两个链表到尾结点时,并不能保证在两个链表上同时到达
尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点,我们先在长
的链表上遍历k个结点,之后再同步遍历,此时我们就能保证同时到达最后一个结点。由于两个
链表从第一个公共结点开始到链表的尾结点,这一部分是重合的,因此它们肯定也是同时到达第
一公共结点的。于是在遍历中,第一个相同的结点就是第一个公共的结点。- 根据这一思路中,我们先要分别遍历两个链表得到它们的长度,并求出两个长度之差。在长
的链表上先遍历长度之差个结点之后,再同步遍历两个链表,直到找到相同的结点,或者一直到
链表结束。此时,该方法的时间复杂度为 O(lenl +len2)。
6. 设C={a1,b1,a2,b2,…,an,bn}为线性表,采用带头结点的单链表存放,设计一个就地算法,将其拆分为两个线性表,使得A{a1,a2,…,an},B={bn,…,b2,b1}。
bool splitList(Linklist &L, Linklist &L2) {//p指向首元结点 r是为指针LNode *p = L->next, *r = L, *q;L2 = (LNode *) malloc(sizeof(LNode));L2->next = NULL;int count = 1;while (p != NULL) {if (count % 2 != 0) {r->next = p;r = p;p = p->next;} else {q=p->next;p->next=L2->next;L2->next = p;p = q;}count++;}//第一个链表最后r尾指针指向NULLr->next = NULL;return true;
}
7. 在一个递增有序的单链表中,存在重复的元素。设计算法删除重复的元素,例如(7,10,10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。
bool deleteRepeat(Linklist &L) {LNode *p = L->next,*q;//这里判断条件为p->next!=NULL是为了让q有意义while (p->next!=NULL){q=p->next;//如果相同就删除当前相同元素的后一个 直到没有相同为止if (p->data==q->data){p->next=q->next;free(q);}else{p=p->next;}}return true;
}
相关文章:
【5.线性表-链式表示-王道课后算法题】
王道数据结构-第二章-链式表示算法题 1.在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一…...
存储过程及练习
1.存储过程 📖什么是存储过程? 存储过程和函数是事先经过编译并存储在数据库中的一段sql语句集合,调用存储过程函数可以简 化应用开发人员的很多工作,减少数据在数据库和应用服务器之间的传输,对于提高数据处理的 效率…...
【在Linux世界中追寻伟大的One Piece】多路转接epoll
目录 1 -> I/O多路转接之poll 1.1 -> poll函数接口 1.2 -> poll的优点 1.3 -> poll的缺点 1.4 -> poll示例 1.4.1 -> 使用poll监控标准输入 2 -> I/O多路转接之epoll 2.1 -> 初识epoll 2.2 -> epoll的相关系统调用 2.2.1 -> epoll_cre…...
设计模式-参考的雷丰阳老师直播课
一般开发中使用的模式为模版模式策略模式组合,模版用来定义骨架,策略用来实现细节。 模版模式 策略模式 与模版模式特别像,模版模式会定义好步骤定义好框架,策略模式定义小细节 入口类 使用模版模式策略模式开发支付 以上使用…...
Python +Pyqt5 简单视频爬取学习(一)
文章目录 前言 一、演示 二、查找网页视频流的索引文件 三、分析视频流的url和视频流索引文件的差异性 四、判断视频数据是否需要转化为ts 五、判断视频是否被加密,如若被加密,需要先解密 六、合并所有的ts视频,以MP4模式输出完整视频 总结 前…...
Python Requests模块全面教程
Python Requests模块全面教程 在现代软件开发中,网络请求是一个不可或缺的部分。无论是获取网页数据、调用API接口,还是进行数据交互,都会涉及到HTTP请求。Python的Requests模块是一个非常强大的库,能够让我们轻松地发送HTTP请求…...
PyQt入门指南六十 与Python其他库的集成方法
PyQt是一个强大的GUI库,它可以与Python的其他库无缝集成,以实现更复杂的功能。以下是一些常见的集成方法和示例: 1. NumPy NumPy是Python中用于科学计算的基础库。您可以在PyQt应用程序中使用NumPy来处理数据和进行数值计算。 import sys …...
Android15之解决:Dex checksum does not match for dex:framework.jar问题(二百三十九)
简介: CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布:《Android系统多媒体进阶实战》🚀 优质专栏: Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏: 多媒体系统工程师系列【…...
车企自动驾驶功能策略 --- 硬件预埋(卷传感器配置)
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...
【已为网站上传证书,却显示不安全】
已为网站上传证书,却显示不安全 错误显示解决办法分析原因 错误显示 此站点有一个由受信任的颁发机构颁发的有效证书但是网站的某些部分不安全 解决办法 删除浏览器所有历史记录, 如果是Edge浏览器显示不安全,那就删除Edge浏览器的所有历史记录; 如果是Google Chrome浏览器显…...
docker busybox作为initContainers
一、上传到私有仓储 docker pull busybox:1.33.1 docker tag busybox:1.33.1 192.168.31.185/public/busybox:1.33.1 docker push 192.168.31.185/public/busybox:1.33.1 --- apiVersion: apps/v1 kind: Deployment metadata:annotations: {}labels: {}name: saas-ali-apiname…...
20.UE5UI预构造,开始菜单
2-22 开始菜单、事件分发器、UI预构造_哔哩哔哩_bilibili 目录 1.UI预构造 2.开始菜单和开始关卡 2.1开始菜单 2.2开始关卡 2.3将开始菜单展示到开始关卡 3.事件分发器 1.UI预构造 如果我们直接再画布上设计我们的按钮,我们需要为每一个按钮进行编辑&#x…...
Electron教程1-初学入门
玩转Electron Electron 是什么注意事项环境安装安装 vscode安装 git 第一个实例第二个实例第二个实例解读 总结问题解答 Electron 是什么 Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个…...
从北美火到中国,大数据洞察品牌“STANLEY”的突围之路
保守直筒大头的“硬汉”外形,以百变颜色踩中时尚命脉,与各路大牌“梦幻联动”,不少时尚弄潮儿没能逃过其“真香”诱惑。 这就是今年以来从北美火到中国的STANLEY,在“巨无霸”水杯中突围出属于自己的一条路。 最近STANLEY又整活…...
深度学习之GAN应用
1 GAN的应用(文本生成) 1.1 GAN为什么不适合文本任务? GAN在2014年被提出之后,在图像生成领域取得了广泛的研究应用。然后在文本领域却一直没有很惊艳的效果。主要在于文本数据是离散数据,而GAN在应用于离散数据时…...
鸿蒙生态下的安全隐私保护:打造用户信任的应用体验
鸿蒙生态下的安全隐私保护:打造用户信任的应用体验 随着华为鸿蒙系统的快速发展,越来越多的设备开始支持这一操作系统,不仅限于智能手机,还包括智能穿戴设备、智能家居产品等。作为开发者,在享受鸿蒙生态系统带来的广…...
用pandoc工具实现ipynb,md,word,pdf之间的转化
Pandoc 是一个强大的工具,可以实现多种文件格式之间的转换,包括 Jupyter Notebook (.ipynb)、Markdown (.md)、Word (.docx)、PDF 等格式。以下是具体的实现方法: 1. 安装 Pandoc 确保已安装 Pandoc: Linux: sudo apt install p…...
第三十一天|贪心算法| 56. 合并区间,738.单调递增的数字 , 968.监控二叉树
目录 56. 合并区间 方法1:fff 看方法2:fff优化版 方法3: 738.单调递增的数字 968.监控二叉树(贪心二叉树) 56. 合并区间 判断重叠区间问题,与452和435是一个套路 方法1:fff 看方法2&am…...
力扣 最长公共前缀-14
最长公共前缀-14 class Solution { public:string longestCommonPrefix(vector<string>& strs) {//定义一个字符数组,用于存储strs字符串数组第一个字符串,方便与后面的字符串进行比较判断char s[200];//定义一个字符数组,用来返回…...
IDEA调整警告级别【IntelliJ IDEA 2024.2.0.1】
文章目录 目前现状鼠标悬停,选择配置筛选 > 取消选择OK效果 目前现状 需要把提示改成只要显示error的5个 鼠标悬停,选择配置 筛选 > 取消选择 OK 效果...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
