【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 效果...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...
