学习线性表_3

server/2024/12/2 14:56:33/

单链表的删除

  1. 直接删除即可
  2. 删除后要free
//删除第i个位置的元素
//删除时L是不会变的,所以不需要加引用
bool ListDelect(LinkList L,int i)
{//i = 1,即删除头指针//拿到要删除结点的前一个结点LinkList p= GetElem(L,i-1);if(NULL==p){return false;}//拿到要删除的结点指针LinkList q=p->next;//当链表只有5个结点,删除第6个结点,出现这种异常情况时,避免程序崩溃if(NULL==q){return false;}//断链p->next=q->next;//释放被删除结点的空间free(q);return true;
}

在这里插入图片描述

练习

设线性表L=(a1,a2,a4,…,an),采用带头结点的单链表存储,设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L=(a1,an,a2,an-1…)

分析:

  1. 空间复杂度是O(1),我们不能申请额外的空间
  2. 找到链表的中间结点,前面一半是链表 L
  3. 将链表的后半部分给一个新的头结点 L2
  4. 然后将链表 L2 进行原地逆置
  5. 再将 L 和 L2 链表进行合并
问题一:如何找到链表的中间结点
  1. 如果首先遍历一次链表,长度假如是20,再次遍历走到第10个,这样的缺点是遍历了两次链表。
  2. 更好的办法:双指针法,两个指针同步向后遍历的方法。
  3. 定义两个指针pcur,pprepcur指针每次走两步,
    ppre指针每次走一步
    ,这样当pcur指针走到最后,那么ppre指针刚好在中间。
  4. 注意,由于pcur每次循环是走两步的,因此每走一步都注意判断是否为NULL
  5. 画图证明,无论奇数还是偶数,都可实现
  6. 把前一个列表的元素放多1个更方便,但是其实哪个多都一样

在这里插入图片描述

问题二: 后一半链表设置为L2,如何让L2原地转置

在这里插入图片描述

  1. 以上步骤循环往复,直到t为NULL时,结束循环
  2. 这时s是最后一个结点,r是倒数第二个结点,需要再
    次执行一下s->next=r
  3. 最后需要L2->next->next=NULL;因为原有链表的头结点变成链表最后一个结点, 最后一个结点的next需要为NULL,这时让L2指向s,因为s是原链表最后一个结点
  4. 完成了逆置后,就是第一个结点,因此链表头结点L2指向s。
问题三:L和L2链表合并,轮流放结点
  1. 因为空间复杂度是O(1),不申请新空间,需要3个指针pcur,p,q
  2. 合并后的新链表让 pcur指针始终指向新链表尾部,初始化为pcur=L->next,使用p指针始终指向链表L待放入的结点,初始化值为p=L2->next
  3. q指针始终指向链表L2待放入的结点,初始化值为q=L2->next
  4. 因为链表L的第一个结点不动,所以p=p->next
  5. 开启循环,循环结束后,有可能L还剩余一个结点,也可能L2剩余一个结点,但是只会有一个剩余的有结点
  6. 因此判断p不为NULL,把p放入,如果q不为NULL,把q放入即可。

在这里插入图片描述


http://www.ppmy.cn/server/146746.html

相关文章

自由学习记录(26)

streamingAsset在ab包的参与的总结 意思是我正在做一个游戏,我目前就相当于在做种子库的ab包,最后游戏上线之后,在玩家那边,加载ab包,肯定会优先判断这个种子库,而我后期要改的话,就传新的ab包…

深度学习模型: BERT(Bidirectional Encoder Representations from Transformers)详解

一、引言 自然语言处理(NLP)领域在过去几十年取得了显著的进展。从早期基于规则的方法到统计机器学习方法,再到如今基于深度学习的模型,NLP 不断向着更高的准确性和效率迈进。BERT 的出现为 NLP 带来了新的突破,它能够…

一些面试问题的深入与思考

Bug排查 原问题:多个服务的bug你是怎么排查的。如果是内存泄漏这种情况看日志看不了怎么办。 题解:内存泄漏的问题往往不会直接从日志中体现,需要用更多手段来定位解决。如下: 1、使用 Go 自带的性能分析工具 (1) pprof 工具&a…

Spark优化--开发调优、资源调优、数据倾斜调优和shuffle调优等

针对Spark优化,我们可以从多个角度进行,包括开发调优、资源调优、数据倾斜调优和shuffle调优等。以下是一些具体的优化方法: 1. 开发调优 避免创建重复的RDD:对于同一份数据,只应该创建一个RDD,避免创建多…

【MySQL】库和表的基本操作

目录 库 库的增删查改 字符集与校验集 库的备份与恢复 表 表的创建和删除 用不同的存储引擎创建表的区别 查看表 修改表 添加删除属性 修改改变属性 上篇博客我们讲了数据库的基本理解,对数据库有了一个大致的概念,下面我们来介绍一下库和表的…

使用开源GCC编译微软WMI相关函数的示例代码

如下代码是使用国产RedPanda-Cpp的编译工具编译的,该工具使用简单; 该方式是调用微软的WMI接口相关函数 但是使用GCC编译会出现编译不过的问题,很多代码库的函数都不存在; 在编译时,需要添加这些库文件:…

【大数据学习 | Spark调优篇】Spark之JVM调优

1. Java虚拟机垃圾回收调优的背景 如果在持久化RDD的时候,持久化了大量的数据,那么Java虚拟机的垃圾回收就可能成为一个性能瓶颈。因为Java虚拟机会定期进行垃圾回收,此时就会追踪所有的java对象,并且在垃圾回收时,找…

Linux服务器安装Linux宝塔面板部署wordpress网站以及雷池WAF

一、Linux服务器安装Linux宝塔面板 这个步骤参考网上其他教程。 二、Linux宝塔面板部署wordpress网站 这个步骤参考网上其他教程,保证网站能够正常访问,并且使用Linux宝塔面板申请并部署了SSL证书,使用https协议正常访问。 三、Linux宝塔…