链表创建的陷阱与细节

链表是线性表的一种，它在逻辑结构上是连续的，在物理结构上是非连续的。

也就是说链表在物理空间上是独立的，可能是东一块西一块的。如下顺序表和链表在内存空间上的对比：

而链表的每一块空间是如何产生联系实现在逻辑结构上是连续的呢？

链表的每一块内存称为一个结点(或节点)，结点我们用结构体类型的变量来申请空间，其中的一个(或多个)成员用来存放有效数据，另一个成员来存放下一个结点的地址，那样的话我们就可以通过地址访问到下一个结点。

如下：

本章只是对链表创建过程的细节和陷阱进行分析解决，并不会对链表的各种增删查改进行一一讲解，但这些操作会在文章末尾给出原码。

关于一个简单的链表，以下是头文件的声明：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;
typedef struct SLNode
{
	SLDatatype val;
	struct SLNode* next;
}SLNode;
void SLN_HeadAdd(SLNode** pphead, SLDatatype x);//插入结点(头插)
void SLN_EndAdd(SLNode** pphead, SLDatatype x);//插入结点(尾插)
SLNode* SLN_Find(SLNode** pphead, SLDatatype x);//查找元素所在的结点
void SLN_fLocAdd(SLNode** pphead, SLNode* Loc, SLDatatype x);//指定位置后插入
void SLN_pLocAdd(SLNode* Loc, SLDatatype x);//指定位置后插入

void SLN_Print(SLNode* phead);//打印链表

void SLN_HeadDele(SLNode** pphead);//删除结点(头删)
void SLN_EndDele(SLNode** pphead);//删除结点(尾删)
void SLN_LocDele(SLNode** pphead, SLNode* Loc);//指定位置删除

void SLN_Free(SLNode** pphead);//销毁链表释放内存

 细节1：成员类型的重命名

在这个声明结点的过程把int类型重命名为SLDatatype，后面要改储存的数据类型的话，不必再去写的函数中一个一个的修改，只需要在重命名这里一次性修改就可以。

然后这里还把 struct SLNode 重命名为SLNode可以方便后面简写。

现在我们来看插入

因为每次插入必然需要申请结点空间很繁琐，所以我们来封装一个函数专门用来申请结点空间

如下：

SLNode* SLNAdd(SLDatatype x)//x为需要储存的元素
{
	SLNode* pk = (SLNode*)malloc(sizeof(SLNode));
	assert(pk);
	pk->val = x;
	pk->next = NULL;
	return pk;
}

头插

陷阱1：是否使用二级指针

你真正理解什么情况需要传二级指针参数，什么情况不用，为什么用吗？

对于头插，初学者可能会写出下面这样的代码：

void SLN_HeadAdd(SLNode* phead, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	if (ps==NULL)
		phead = padd;
	else
	{
		padd->next = phead;
		phead = padd;
	}
}

可以看出这里对参数phead做了更改，如这个表达式

                phead = padd;

但显然这里phead是临时变量，当函数结束后就销毁了，而实参并没有任何变化。

                                                        注意：malloc申请的空间并没有销毁

如何解决？

有两个方法：

就是把更改后的头结点返回去，再用原头结点去接收，如下：

SLNode* SLN_HeadAdd(SLNode* phead, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	if (phead==NULL)
		phead = padd;
	else
	{
		padd->next = phead;
		phead = padd;
	}
    return phead;
}

此外还可以通过直接改变原头结点解决，即通过对指针的解引用来实现在函数内改变，而头结点是一个指向结构体的地址(即一个一级指针)，改变它就需要一个二级指针参数来接收头结点的地址，然后对这个参数解引用从而达到改变头结点(也就是结构体的地址)的目的。

如下：

void SLN_HeadAdd(SLNode** pphead, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	if (*pphead==NULL)
		*pphead = padd;
	else
	{
		padd->next = *pphead;
		*pphead = padd;
	}
}

细节2：指针作为形参目的

下面函数实现的是链表的尾删：


void SLN_EndDele(SLNode* phead)
{
    SLNode* ph = phead;
    if (!ph)
        return;
    SLNode* pk = ph;
    while (ph->next)
    {
        pk = ph;
        ph = ph->next;
    }
    pk->next = NULL;
    free(ph);
} 

我们来思考这个函数为什么不用二级指针也不用返回头结点就能完成，又为什么不用指针完成不了。注意该过程只对结点的成员进行了改变和结点的销毁，而要在一个函数内改变结构体成员，是需要得到该成员的地址的，而一个一级指针就刚好满足了这个要求的->就相当于得到该成员的地址并且对他它解引用。而这里这个函数用一级指针作为参数的作用真正用于的是以下两部

                 pk->next = NULL;
                 free(ph);

一个是需要改变成员所以需要一级指针，另一个是需要释放内存所以需要一级指针，没有这两部这个函数的参数完全可以不是指针变量。

例如一个链表的打印函数可以这么写：

void SLN_Print(SLNode head)
{
	while (head.next)
	{
		printf("%d->", head.val);
		 head = *(head.next);
	}
	printf("NULL\n");
}

要注意的是这个表达式head = *(head.next);因为head.next是struct SLNode* 类型head是struct SLNode类型所以这个需要对head.next解引用。

总结：（1）当一个函数需要改变结点的地址时需要传二级指针(或传一级指针但要返回头结点)。（2）当一个函数只需要改变结点成员或销毁结点的时候只需要传一级指针。（3）当一个函数对结点以及成员不做任何改变的时候只需要传一个结构体变量。

注意：这里结点指的是结构体的地址。

 陷阱2：运算符优先级问题

下面是一个关于头插的函数：

void SLN_HeadDele(SLNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	SLNode* ph = (*pphead)->next;
	free(*pphead);
	*pphead = ph;
}

我们要注意的是这个语句：

        SLNode* ph = (*pphead)->next;

在初学者很容易写为 SLNode* ph = *pphead->next;但要注意->成员访问运算符的优先级是比解引用操作符的优先级要高的，这里要不要忘记用()明确运算的优先。

陷阱3：结点前驱丢失问题

在初学者经常犯的一个错误就在对链表进行增删查该等操作过程中常常会把操作的结点后面的结点给弄丢，一旦丢失再也无法找到。

例如一个链表的指定结点之后插入结点的函数这样写：

void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	Loc->next = padd;
}

或这么写：

void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	Loc->next = padd;
    padd->next=Loc->next;
}

两种写法都是错误的，第一种写法直接将Loc原本所指向的结点丢失

第二种写法相当于padd->next=padd;不仅丢失了Loc用来指向的结的，还造成打印和尾插等操作的死循环。

正确的写法是

void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{
    SLNode* padd = SLNAdd(x);
    padd->next = Loc->next;
    Loc->next = padd;
}

 陷阱4：不可逆向遍历缺陷

要知道链表不可逆向遍历的，得到一个结点是无法访问到上一个结点的，只能往下访问。所以如果害怕某个结点在遍历过程中丢失的话，就需要新的变量来把它储存。

例如一个链表的尾删函数：

void SLN_EndDele(SLNode* phead)
{
	SLNode* ph = phead;
	if (!ph)
		return;
	SLNode* pk = ph;
	while (ph->next)
	{
		pk = ph;
		ph = ph->next;
	}
	pk->next = NULL;
	free(ph);
	ph = NULL;
}

其中表达式

                pk = ph;

用变量pk对ph的值进行储存之后再改变ph。

#include"SLNode.h"
SLNode* SLNAdd(SLDatatype x)//
{
	SLNode* pk = (SLNode*)malloc(sizeof(SLNode));
	assert(pk);
	pk->val = x;
	pk->next = NULL;
	return pk;
}
void SLN_HeadAdd(SLNode** pphead, SLDatatype x)
{
	assert(pphead);
	SLNode* ps = *pphead;
	SLNode* padd = SLNAdd(x);
	if (!ps)//相当于if(pk==NULL)
		*pphead = padd;
	else
	{
		padd->next = ps;
		*pphead = padd;
	}
}
//SLNode* SLN_HeadAdd(SLNode* phead, SLDatatype x)
//{
//	SLNode* ph = SLNAdd(x);
//	if (phead == NULL)
//	{
//		return ph;
//	}
//	else
//	{
//		ph->next = phead;
//		return ph;
//	}
//
//}
void SLN_EndAdd(SLNode** pphead, SLDatatype x)
{
	assert(pphead);
	SLNode* ps = *pphead;
	SLNode* padd = SLNAdd(x);
	if (!ps)
		*pphead = padd;
	else
	{
		while (ps->next)
		{
			ps=ps->next;
		}
		ps->next = padd;
	}
}
void SLN_Print(SLNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->val);
		phead = phead->next;
	}
	printf("NULL\n");
}
//void SLN_Print(SLNode head)
//{
//	while (head.next)
//	{
//		printf("%d->", head.val);
//		 head = *(head.next);
//	}
//	printf("NULL\n");
//}
SLNode* SLN_Find(SLNode** pphead, SLDatatype x)
{
	assert(pphead);
	SLNode* ph = *pphead;
	while (ph)
	{
		if (ph->val == x)
			return ph;
		ph = ph->next;
	}
	return NULL;
}
void SLN_fLocAdd(SLNode** pphead, SLNode* Loc, SLDatatype x)
{
	assert(pphead);
	SLNode* ph = *pphead;
	SLNode* pd = ph, * padd = SLNAdd(x);
	if (Loc==ph)
	{
		SLN_HeadAdd(pphead, x);
		return;
	}
	while (ph->next)
	{
		if (ph == Loc)
		{
			padd->next = Loc;
			pd->next = padd;
			return;
		}
		pd = ph;
		ph = ph->next;
	}
}
void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{
	SLNode* padd = SLNAdd(x);
	padd->next = Loc->next;
	Loc->next = padd;
}
void SLN_HeadDele(SLNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	SLNode* ph = (*pphead)->next;//陷阱
	free(*pphead);
	*pphead = ph;
}
void SLN_EndDele(SLNode** pphead)
{
	assert(pphead);
	SLNode* ph = *pphead;
	if (!ph)
		return;
	SLNode* pk = ph;
	while (ph->next)
	{
		pk = ph;
		ph = ph->next;
	}
	pk->next = NULL;
	free(ph);
	ph = NULL;
}
//void SLN_EndDele(SLNode* phead)
//{
//	SLNode* ph = phead;
//	if (!ph)
//		return;
//	SLNode* pk = ph;
//	while (ph->next)
//	{
//		pk = ph;
//		ph = ph->next;
//	}
//	pk->next = NULL;
//	free(ph);
//	ph = NULL;
//}
void SLN_LocDele(SLNode** pphead, SLNode* Loc)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	SLNode* ph=*pphead,*pk=ph;
	if (Loc == ph)
	{
		SLN_HeadDele(pphead);
		return;
	}
	while (ph)
	{
		if (ph == Loc)
		{
			pk->next = ph->next;
			free(ph);
			ph = NULL;
			return;
		}
		pk = ph;
		ph = ph->next;
	}
}
void SLN_Free(SLNode** pphead)
{
	assert(pphead);
	while (*pphead)
	{
		SLNode* ph = (*pphead)->next;
		free(*pphead);
		*pphead = ph;
	}
	
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/545002.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

关于java中的线程池用法

关于java中的线程池用法

目录 线程池的参数介绍 线程池的工作流程 使用Executors创建常见的线程池 池的思想&#xff0c;在计算机中是非常普遍的概念。顾名思义&#xff0c;池是将一个或多个任务提前创建好&#xff0c;放入容器中&#xff0c;当程序运行的时候直接取出使用&#xff0c;这个容器就叫…
阅读更多...
Imagination APXM-6200 CPU：性能卓越，安全可信

Imagination APXM-6200 CPU：性能卓越，安全可信

随着消费类和工业应用行业的不断发展&#xff0c;对创新性能和效率的需求永不停歇&#xff0c;我们自豪地推出旗下 Catapult CPU 系列的第二款产品&#xff1a;Imagination APXM-6200 CPU 。这款 64 位的高效 RISC-V 应用处理器具有强大的 AI 功能及性能密度&#xff0c;能够为…
阅读更多...
基于Java+SpringBoot3+vue3健身房管理系统设计与实现

基于Java+SpringBoot3+vue3健身房管理系统设计与实现

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
使用openLayers报错Module parse failed: Unexpected token

使用openLayers报错Module parse failed: Unexpected token

引入OpenLayers时报错 JavaScript模块解析失败 在构建工具中配置 transpileDependencies 参数&#xff0c;因为 ol 依赖库基于一个目标环境不支持的 ES 版本撰写&#xff0c;将该依赖添加进 vue.config.js 中的 transpileDependencies 选项中 // including the package "…
阅读更多...
ruoyi单体+react+antdesign

ruoyi单体+react+antdesign

基于ruoyi vue和Ruoyi-React实现的快速开发工具。 源码地址&#xff1a;GitHub - hebian1994/ruoyi-react-single: use ruoyi to generage java backend code and reacr front end code 前端&#xff1a;基于ant-design-pro 后端&#xff1a;单体springboot项目(非cloud)mysq…
阅读更多...
亚马逊云科技数据工程师考试官方免费课程上线啦

亚马逊云科技数据工程师考试官方免费课程上线啦

自从上次小李哥分享了AWS Data Engineer Associate证书首通经验后&#xff0c;有非常多的小伙伴们问我&#xff0c;应该怎么复习这门考试呢&#xff1f; 这门考试是AWS针对最近大热&#x1f525;的AI、数据分析、数据科学等行业&#xff0c;推出的全新考试。因为刚刚推出&#…
阅读更多...
神经网络背后的数学原理

神经网络背后的数学原理

原文地址&#xff1a;The Math Behind Neural Networks 2024 年 3 月 29 日 深入研究现代人工智能的支柱——神经网络&#xff0c;了解其数学原理&#xff0c;从头开始实现它&#xff0c;并探索其应用。 神经网络是人工智能 &#xff08;AI&#xff09; 的核心&#xff0c;为…
阅读更多...
uni-start初始化后的微信登录问题

uni-start初始化后的微信登录问题

1.使用微信登录 一直提示“获取第三方账号失败”&#xff0c; 原来是在unicloud-->cloudfunctions-->common-->uni-config-center-->uni-id-->config.json文件中配置的微信的appid和appsecret有错误,配置好后就可以获取信息了。 2. 获取信息之后用真机调试报错…
阅读更多...
Node.js留言板（超详细注释）

Node.js留言板（超详细注释）

目录结构如下 app.js // 一.引入模块 var http require(http);// 用于创建 HTTP 服务器和处理 HTTP 请求 var fs require(fs);// 用于读取和写入文件 var url require(url);// 用于解析URL// 创建留言数据对象 var msgs [{ name: 牛二, content: "我是妞儿", cr…
阅读更多...
【无人机/平衡车/机器人】详解STM32+MPU6050姿态解算—卡尔曼滤波+四元数法+互补滤波（文末附3个算法源码）

【无人机/平衡车/机器人】详解STM32+MPU6050姿态解算—卡尔曼滤波+四元数法+互补滤波（文末附3个算法源码）

效果： MPU6050姿态解算-卡尔曼滤波+四元数+互补滤波 目录 基础知识详解 欧拉角
阅读更多...
【LeetCode】2635. 转换数组中的每个元素

【LeetCode】2635. 转换数组中的每个元素

转换数组中的每个元素 编写一个函数&#xff0c;这个函数接收一个整数数组 arr 和一个映射函数 fn&#xff0c;通过该映射函数返回一个新的数组。 返回数组的创建语句应为 returnedArray[i] fn(arr[i], i)。 请你在不使用内置方法 Array.map 的前提下解决这个问题。 示例 1:…
阅读更多...
Python爬虫-京东商品评论数据

Python爬虫-京东商品评论数据

前言 本文是该专栏的第68篇，后面会持续分享python爬虫干货知识，记得关注。 在本专栏之前，笔者有详细介绍京东滑块验证码的解决方法，感兴趣的同学，可以直接翻阅文章《Python如何解决“京东滑块验证码”(5)》进行查看。 而本文，笔者以京东商品详情页的评论数据为例，通过…
阅读更多...
【MySQL】索引篇

【MySQL】索引篇

SueWakeup 个人主页&#xff1a;SueWakeup 系列专栏&#xff1a;学习技术栈 个性签名&#xff1a;保留赤子之心也许是种幸运吧 本文封面由 凯楠&#x1f4f8;友情提供 目录 本系列传送门 1. 什么是索引 2. 索引的特性 3. 索引的分类 4. 索引的优点及缺点 优点 缺点 5.…
阅读更多...
全面的网络流量监控

全面的网络流量监控

流量监控指的是对数据流进行的监控&#xff0c;通常包括出数据、入数据的速度、总流量。通过网络流量监控&#xff0c;组织可以确保只有业务关键型流量通过网络传输&#xff0c;并限制不需要的网络流量&#xff0c;从而提高网络效率&#xff0c;又可以防止停机、减少 MTTR、帮助…
阅读更多...
【氮化镓】微波脉冲对GaN HEMT失效的影响

【氮化镓】微波脉冲对GaN HEMT失效的影响

本文是一篇关于高功率微波脉冲作用下GaN HEMT&#xff08;高电子迁移率晶体管&#xff09;热电多物理场耦合失效的实验研究。文章由Xiangdong Li等人撰写&#xff0c;发表在2023年11月的《IEEE Transactions on Electron Devices》上。文章通过实验研究了在高功率微波脉冲应力下…
阅读更多...
英特尔推出中国特供版Gaudi 3芯片，性能暴降92%以应对美国出口管制｜TodayAI

英特尔推出中国特供版Gaudi 3芯片，性能暴降92%以应对美国出口管制｜TodayAI

英特尔近期发布消息&#xff0c;其将在中国市场推出专为该地区定制的“特供版”Gaudi 3 AI芯片&#xff0c;以符合美国对AI芯片的出口管制。这一版本包括HL-328型号的OAM兼容夹层卡&#xff0c;预计将于6月24日发布&#xff1b;以及HL-388型号的PCIe加速卡&#xff0c;计划在9月…
阅读更多...
（二十八）Flask之wtforms库【上手使用篇】

（二十八）Flask之wtforms库【上手使用篇】

目录&#xff1a; 每篇前言&#xff1a;用户登录验证&#xff1a;用户注册验证&#xff1a;使用示例&#xff1a; 抽象解读使用wtforms编写的类&#xff1a;简单谈一嘴&#xff1a;开始抽象&#xff1a; 每篇前言&#xff1a; &#x1f3c6;&#x1f3c6;作者介绍&#xff1a;【…
阅读更多...
L3 【哈工大_操作系统】操作系统启动

L3 【哈工大_操作系统】操作系统启动

本节要点&#xff1a; 1、理解 OS 启动过程发生了什么&#xff0c;理解 OS 与 硬件 与 应用 之间的关系 2、本节讲解了 setup 模块 和 system 模块实现的功能 1、计算机上电时&#xff0c;操作系统在硬盘&#xff08;磁盘&#xff09;上&#xff0c;为了“取指执行”&#xff0…
阅读更多...
Vite多环境配置与打包：灵活高效的Vue开发工作流

Vite多环境配置与打包：灵活高效的Vue开发工作流

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…
阅读更多...
京东商品详情接口可以获取到那些数据?商品属性价格sku主图

京东商品详情接口可以获取到那些数据?商品属性价格sku主图

京东商品详情接口可以获取到关于商品的丰富数据&#xff0c;包括但不限于以下内容&#xff1a; 商品基本信息&#xff1a;例如商品标题、价格、销量等。商品详情描述&#xff1a;这包括商品的详细描述、规格参数、包装清单等。商品评价信息&#xff1a;比如商品的好评率、评价…
阅读更多...
最新文章

Copyright @ 2022~2023