链表相关题目(数据结构期末复习)

2023-12-20 17:57:29

题目要求

下面算法 FB1 将一个带头节点的单链表LA 分解为两个具有相同结构的单链表 LB,LC, 其中LB中节点为LA中值小于0的节点,而LC中节点为LA中值大于或等于0的节点。请在空白处填上合理的语句。

翻译:LA 初始链表;LB.val from LA which <0; LC.val >=0 from LA ,too.

void FB1(LinkList &LA,LinkList &LB,LinkList &LC){
	LinkList p,q;
	LB=LA;
	p=__①__;
	LB->next=NULL;
	LC=new LNode;
	LC->next=NULL;
	while(p){
		q=p->next;
		if(__②__){
			p->next=LB->next;
			LB->next=p; 
		}else{
			p->next=LC->next;
			LC->next=p;
		}
		__③__; 
	}
}

做题思路

自己假设多组数据,跟着代码去走一走,想着这行代码怎么写,才能正确处理咱自己写的数据,
看第一空吧先

第一空(假设链表LA为空)

处理结果应该是怎样的?LB和LC最后应该变成什么样?

在这里插入图片描述

先给极端数据求好求的空:也就是第一空
如果咱的LA链表 只有一个头结点,后边儿 啥也没有
在这里插入图片描述
那调用完FB1函数,LB和LC应该也和LA长的很像,都是只有头结点,然后直接指到空

在这里插入图片描述
那咱第一空,该怎么填才能让函数实现这种效果?

p=LA->next;
//或者让p=LB->next,因为上边先让LB=LA了,所以LA的next和LB的next暂时相等

因为 LA只有一个头结点,所以LA->next 指向的是空,p也就为空,
就一次也进不去while循环了,也不用进(不理解为什么不用进while循环,往下继续看)
因为while循环上边几行代码已经把LB和LC处理成咱想要的结果了

while循环上边几行代码都干了什么?

LB=LA;//把LA赋给LB, 也就是我们现在拿着LB用,就和拿着LA用效果一样。

上面画的LB的图其实有点问题,再给你重画一个
在这里插入图片描述

而LC创建的时候,

LC=new LNode; //LC的头结点有了
LC->next=NULL;//LC的next也指到空了,
				//已经实现最后的LC只有一个头结点的结果,不用再考虑
				//(一会儿填后两个空,再考虑)

为什么不用进while循环?

在C语言里边儿,0和空 到了 布尔表达式里 都可以起到false的效果,让判断条件为假,跳过循环。
咱通过 p=LA.next,让p指到了空,到了while循环判断的时候,直接就跳过循环了。

调用函数,实现了功能就该返回了,再进循环里边儿转,不就浪费时间了吗?(本来就该这样设计程序的。)

后两空(还是通过给具体的数据求解)

先再写一下FB1的代码

void FB1(LinkList &LA,LinkList &LB,LinkList &LC){
	LinkList p,q;
	LB=LA;
	p=LA.next;//已经写上①了
	LB->next=NULL;
	LC=new LNode;
	LC->next=NULL;
	while(p){
		q=p->next;
		if(__②__){
			p->next=LB->next;
			LB->next=p; 
		}else{
			p->next=LC->next;
			LC->next=p;
		}
		__③__; 
	}
}

假设LA 为[1],只有一个元素 正1

首先进到循环中
刚才不是说
p指向的是LA的next吗?
在这里插入图片描述
p的next 为null

q=p->next;

现在q也是null了

然后再接着往下看
呃,先考虑最后LB和LC该张什么样吧

在这里插入图片描述
应该是 LC里有一个1,LB还是光个头结点

那咱肯定是让 if()这里为假,然后走else 去操作LC呀
if语句里边 都是 LB的事儿,走它没用,

抛开代码不谈,但看题目要求,那也是根据元素的正负 来看它该进LB 还是该进 LC的

②这里应该和元素的正负关联起来,大于等于0的时候,就让布尔表达式的结果为假,走else语句,否则就走if
(自己捋一捋就好了,它题里已经把LB写在if里了,只能顺着它的来写if的判断语句)

在这里插入图片描述
谁能表示这个元素,有很多,这里咱先用p.val表示(value,值)

if(p.val<0){
}else{
}

这样写好像可以让这个元素(红色的1)去到else里边 操作
(如果②写成p.val不行,一会儿出问题了,咱在回来找别的能表示元素值的方法。如果没问题,一会儿把③也填了,这里也还能填它,那就它了)

else 语句执行效果演示

...
else{
	p->next=LC->next;
	LC->next=p;
}
...
原来的

在这里插入图片描述

p->next=LC->next;之后

LC的next是什么意思?
LC是LC这个链表的头结点,LC的next 连着的是一整个链表
LC->next 可以理解为 LC这个链子上,头结点后边的整个链
也就是这个部分(这里咱用的都是比较简单的特殊情况,数据量有点少,你可以当LC后边有1万个节点,然后再接着往下看)
在这里插入图片描述
p->next=LC->next;整体是什么意思?
让p的next指针 指向 LC->next这个链,↓
在这里插入图片描述

LC->next=p

LC是LC链表的头结点,头结点的next 指到一个节点上,其实挺好理解的
在这里插入图片描述
拉直一下
在这里插入图片描述
看清了吧。

因为我们这里只假设LA有一个元素,所以处理了一个节点之后,也就该退出循环了,而且现在p->next不就指向null嘛,一会儿再进行while循环条件判断的时候,结果也是假,也会出循环的,就结束了。

第三空

现在已经出来if-else了
该执行第三空的语句了
刚才给的两组数据分别是空 和 1
这次咱就给两个数吧[1,2]

刚进循环
注意乃条红线,咱代码里面有一句 LB->next=NULL,就相当于是把红线给断了,让LB的next 指到空,不然就会出现上图乃种情况——到最后LB 还有根线连着1,和正确结果不一样。
在这里插入图片描述

处理完1之后三个链表应该是什么样?
在这里插入图片描述
现在,假如没有第③句,那p还是指向1,循环判断的还是1,又重复对1操作,死循环了
所以在③这里我们需要的操作应该是让p指针“往后移”,指到原来1后边乃个元素也就是2
怎么指过去?
你猜q是干嘛的?
让p=q不就行了
在这里插入图片描述
然后再接着走循环
处理元素2
在这里插入图片描述
在这里插入图片描述

回顾

带头结点的链表长什么样?
分别画出链表为 没有元素、[1]、[1,2],的图

补全代码,设计几组特殊数据,一点一点看代码就行,可以一组数据针对一个空。

文章来源:https://blog.csdn.net/m0_69886881/article/details/135107376
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。