C语言：详解单链表与例题

C语言：详解单链表与例题

1.单链表的实现
2.例题：移除链表元素

1.单链表的实现

链表根据带头或不带头、单向或双向、循环或不循环分类为8种，最常用的是单链表和双向链表，单链表是 不带头单向不循环 链表。

链表由节点组成，节点分为两部分，数据和指向下一节点的指针。

链表示意图如下：
在这里插入图片描述

创建头文件SList.h，包含stdio.h、stdlib.h、assert.h，在文件中定义节点结构，声明函数打印链表、尾/头插、尾/头删、查找、定位前插入、定位后插入、删除pos节点、删除pos后节点、销毁链表。

//SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode   //定义节点结构
{                          SLTDataType data;      //数据struct SListNode* next;//指向下一节点的指针
}SLTNode;
void SLTPrint(SLTNode* phead);//打印链表void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插void SLTPopBack(SLTNode** pphead);//尾删void SLTPopFront(SLTNode** pphead);//头删SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//定位前插入void SLTInsertAfter(SLTNode* pos, SLTDataType x);//定位后插入void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点void SLTEraseAfter(SLTNode* pos);//删除pos后一个节点void SListDesTroy(SLTNode** pphead);//销毁链表

创建SList.c文件，在文件中编写函数。

打印链表：定义一个指针pcur指向链表首节点，遍历并打印。
在这里插入图片描述
在这里插入图片描述

void SLTPrint(SLTNode* phead)//打印
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

创建节点：接下来的函数在使用时常常需要创建节点，所以另写一个函数用于创建节点。用malloc函数动态开辟空间，定义指针newnode指向这块空间，把所需的数据和指向下一个节点指针赋给data和next。

SLTNode* SLTBuyNode(SLTDataType x)//创建节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

尾插：尾插的关键是找到最后一个节点，让这个尾节点的指向下一节点的指针next不再指向NULL，而是指向新节点newnode，此时newnode成为新的尾节点，所以最后还要让newnode指向NULL。
在这里插入图片描述

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{                                                //*pphead为指向第一个节点的指针assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)//若为空链表*pphead = newnode;else //若为非空链表{SLTNode* ptail = *pphead;while (ptail->next)  //找尾ptail = ptail->next;ptail->next = newnode;}
}

尾插函数SLTPushBack的一个参数是二级指针，这个参数表示我们传过去的是指向第一个节点的指针的地址。假设用的是一级指针phead，指向链表第一个节点的指针为plist，plist是实参，phead为形参，当为空链表时，phead被赋值为newnode，出了函数后形参phead被销毁，实参plist仍指向NULL。

所以，要使形参的改变影响实参，就要传地址。

头插：先让创建的新节点newnode的next指针指向原链表的第一个节点，再让指向原链表第一个节点指针pphead指向newnode即可。这两步的先后顺序不可调换，若先让pphead指向newnode，就无法找到原链表的第一个节点。
在这里插入图片描述

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾删：定义指针ptail，把*pphead赋值ptail，用ptail遍历链表，使ptail指向最后一个节点，然后用free释放ptail指向的节点。这时还需要一个指针prev指向ptail指向节点的上一个节点，在尾节点被释放后，prev指向的节点的next置为NULL。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void SLTPopBack(SLTNode** pphead)//尾删
{assert(pphead && *pphead);   //链表不为空if ((*pphead)->next == NULL) //只有一个节点{free(*pphead);*pphead = NULL;}else      //不止一个节点{SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)  //使ptail指向最后一个节点{prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}

头删：定义指针next保存链表的第二个节点，释放第一个节点后再把next赋值给*pphead。

void SLTPopFront(SLTNode** pphead)//头删
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

查找节点：假设要找到data为x的节点，让指针pcur=phead，遍历链表，直到pcur->data等于x，找到了返回指向该节点的指针，没找到返回NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x)return pcur;  //找到了pcur = pcur->next;}return NULL;
}

定位前插入：给一个指向某个节点指针pos，若pos指向的是第一个节点，直接调用头插函数SLTPushFront；若pos指向的不是第一个节点，则定义指针prev，遍历链表，使prev指向pos指向节点的上一节点，然后插入新节点。
在这里插入图片描述

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
//定位前插入，即pos之前插入，通过SLTFind得到pos
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead)SLTPushFront(pphead, x);//头插else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos,pos的前一个节点为prevprev = prev->next;newnode->next = pos;prev->next = newnode;}
}

定位后插入：给一个指向某个节点指针pos，在pos指向的节点和pos->next指向的节点之间插入新节点newnode即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)//定位后插入，即pos后插入
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

删除pos节点：给一个指向某个节点指针pos，定义指针prev，遍历链表，使prev指向pos指向节点的上一节点，再让prev指向pos后的节点，最后free释放pos。
在这里插入图片描述

void SLTErase(SLTNode** pphead, SLTNode* pos)//删pos节点
{assert(pphead && *pphead);assert(pos);if (pos == *pphead)     //pos为头节点SLTPopFront(pphead);//头删else     //pos不为头节点{SLTNode* prev = *pphead;while (prev->next != pos)prev = prev->next;prev->next = pos->next;//prev  pos  pos->nextfree(pos);pos = NULL;}
}

删除pos之后节点：先定义指针del指向pos之后节点，在用free释放del之前，先pos->next指向del->next指向的节点，最后即可释放del。

void SLTEraseAfter(SLTNode* pos)//删pos之后的节点
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;//pos  del  del->nextfree(del);del = NULL;
}

销毁链表：循环遍历链表，循环一次，销毁一次。

void SListDesTroy(SLTNode** pphead)//销毁链表
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur)  //循环一次，销毁一个节点{SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

在SList.c文件中代码如下：

//SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)//打印
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)//创建节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{                                                //*pphead为指向第一个节点的指针assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)//若为空链表*pphead = newnode;else //若为非空链表{SLTNode* ptail = *pphead;while (ptail->next)  //找尾ptail = ptail->next;ptail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)//尾删
{assert(pphead && *pphead);   //链表不为空if ((*pphead)->next == NULL) //只有一个节点{free(*pphead);*pphead = NULL;}else      //不止一个节点{SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)  //使ptail指向最后一个节点{prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}
void SLTPopFront(SLTNode** pphead)//头删
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x)return pcur;  //找到了pcur = pcur->next;}return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//定位前插入，即pos之前插入，通过SLTFind得到pos
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead)SLTPushFront(pphead, x);//头插else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos,pos的前一个节点为prevprev = prev->next;newnode->next = pos;prev->next = newnode;}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//定位后插入，即pos后插入
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//删pos节点
{assert(pphead && *pphead);assert(pos);if (pos == *pphead)     //pos为头节点SLTPopFront(pphead);//头删else     //pos不为头节点{SLTNode* prev = *pphead;while (prev->next != pos)prev = prev->next;prev->next = pos->next;//prev  pos  pos->nextfree(pos);pos = NULL;}
}
void SLTEraseAfter(SLTNode* pos)//删pos之后的节点
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;//pos  del  del->nextfree(del);del = NULL;
}
void SListDesTroy(SLTNode** pphead)//销毁链表
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur)  //循环一次，销毁一个节点{SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

创建test.c文件进行测试。

例如：测试头插和尾插

#include"SList.h"
void test1()
{SLTNode* phead = NULL;SLTPushBack(&phead, 2);SLTPushFront(&phead, 1);SLTPrint(phead);SListDesTroy(&phead);
}
int main()
{test1()return 0;
}

在这里插入图片描述

2.例题：移除链表元素

给一个链表的头节点head和一个整数val，删除链表中所有满足Node.data==val的节点，返回新的头节点，节点数目在[ 0, 10^4 ]内。
例如：

  • 输入 head=[1,2,6,3,4,5,6]，val=6
  • 输出 [ 1,2,3,4,5 ]

方法：找值不为val的节点，尾插到新链表中。

#include<stdio.h>
typedef struct ListNode  //节点结构体
{int data;struct ListNode* next;
}ListNode;
ListNode* removeElements(ListNode* head,int val)
{ListNode* newHead;ListNode* newTail;  //定义两个指向节点的指针newHead=newTail=NULL;ListNode* pcur=head;  //遍历原链表while(pcur)  //pcur指向尾节点时跳出循环{if(pcur->data!=val){if(newHead==NULL)newHead=newTail=pcur;else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;}if(newTail)newTail->next=NULL;return newHead;
}

以head=[1,2,6,3,4,5,6]，val=6为例分析：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
此时pcur->data==6，第三次循环后newTail不移动，pcur->data为3。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
第七次循环后，pcur为NULL，newTail不移动，跳出循环，newTail->next赋为NULL。

在这里插入图片描述
构建的新链表如下：
在这里插入图片描述
输入head=[1,2,6,3,4,5,6]，val=6，vs2022中结果如图：
在这里插入图片描述

拙作一篇，望诸位同道不吝斧正。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/diannao/93564.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/93564.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

从0开始学习R语言--Day62--RE插补

从0开始学习R语言--Day62--RE插补

对于会有多次测量值的数据&#xff0c;用普通的回归去插补&#xff0c;往往会忽略掉数据个体本身的特点&#xff0c;毕竟多次的测量值其实就代表了数据个体的不稳定性&#xff0c;存在额外的干扰。而RE的插补原理是结合个体本身的随机效应和群体的固体效应再加上截距进行插补的…
阅读更多...
RESTful API开发指南：使用Spring Boot构建企业级接口

RESTful API开发指南：使用Spring Boot构建企业级接口

目录 1. 引言2. RESTful API基础概念3. Spring Boot环境搭建4. 项目结构设计5. 核心组件开发6. 数据库集成7. 安全认证8. 异常处理9. API文档生成10. 测试策略11. 部署与监控12. 最佳实践 1. 引言 在现代软件开发中&#xff0c;RESTful API已成为构建分布式系统和微服务架构…
阅读更多...
从 Print 到 Debug：用 PyCharm 掌控复杂程序的调试之道

从 Print 到 Debug：用 PyCharm 掌控复杂程序的调试之道

目录摘要调试工具窗口会话工具栏调试工具栏单步工具栏调试器选项卡调用栈帧&#xff08;Frames&#xff09;变量&#xff08;Variables&#xff09;&#x1f4a1; 表达式求值区域&#xff08;Evaluate expression field&#xff09;&#x1f5b1;️ 右键菜单&#xff08;Contex…
阅读更多...
用于前列腺活检分级的分层视觉 Transformer：迈向弥合泛化差距|文献速递-医学影像算法文献分享

用于前列腺活检分级的分层视觉 Transformer：迈向弥合泛化差距|文献速递-医学影像算法文献分享

Title题目Hierarchical Vision Transformers for prostate biopsy grading: Towardsbridging the generalization gap用于前列腺活检分级的分层视觉 Transformer&#xff1a;迈向弥合泛化差距01文献速递介绍前列腺癌是全球男性中第二常见的确诊癌症&#xff0c;也是第五大致命癌…
阅读更多...
Apple基础（Xcode②-Flutter结构解析）

Apple基础（Xcode②-Flutter结构解析）

&#x1f3d7;️ 目录结构速查表&#xff08;your_project/ios/ 下&#xff09;ios/ ├── Runner/ ← 原生 iOS 工程根目录&#xff08;Xcode 打开它&#xff09; │ ├── AppDelegate.swift ← App 入口&#xff08;类似 Android 的 MainActivity&…
阅读更多...
X00229-基于深度强化学习的车联网资源分配python完整

X00229-基于深度强化学习的车联网资源分配python完整

X00229-基于深度强化学习的车联网资源分配python完整
阅读更多...
面向多模态自监督学习的共享表示与独有表示解耦

面向多模态自监督学习的共享表示与独有表示解耦

通俗说法&#xff1a;在多模态自监督学习中&#xff0c;将共享信息和独有信息分离开来 Abstract 问题&#xff1a; 传统方法通常假设在训练和推理阶段都可以访问所有模态信息&#xff0c;这在实际应用中面对模态不完整输入时会导致性能显著下降。 解决方法&#xff1a;提出了一…
阅读更多...
【iOS】weak修饰符

【iOS】weak修饰符

前言前面我们已经学习了解了sideTable&#xff0c;今天来看看在OC中&#xff0c;sideTable是如何在我们使用weak时工作的。在OC中&#xff0c;weak修饰符是一种用于声明“弱引用”的关键字&#xff0c;其核心特性是不参与对象的引用计数管理&#xff0c;而且当被引用的对象被释…
阅读更多...
【JVM篇10】：三种垃圾回收算法对比详解

【JVM篇10】：三种垃圾回收算法对比详解

文章目录1. 标记-清除算法2. 复制算法3. 标记-整理算法总结与面试要点在通过 可达性分析等算法识别出所有存活对象和垃圾对象后&#xff0c;垃圾收集器&#xff08;GC&#xff1a;Garbage Collector&#xff09;就需要执行回收操作来释放垃圾对象所占用的内存。以下是三种最基础…
阅读更多...
JXD进步25.7.30

JXD进步25.7.30

1.为啥是update&#xff0c;因为你if判断有问题。或者是你上来就给id赋值了。2. 这个是清空network历史3.断点位置打在这里&#xff1a;打在上面它进不来4.
阅读更多...
Flutter开发实战之网络请求与数据处理

Flutter开发实战之网络请求与数据处理

第6章：网络请求与数据处理 “数据是应用的血液，网络是连接世界的桥梁。” 在移动应用开发中，与服务器进行数据交互是必不可少的功能。无论是获取用户信息、提交表单数据，还是上传图片、下载文件，都离不开网络请求。本章将带你深入掌握Flutter中的网络编程技巧。 6.1 网络…
阅读更多...
快速分页实现热点功能-索引和order by

快速分页实现热点功能-索引和order by

需求:分页求出进三天的发布视频的权重热度 权重 / 衰减时间 衰减时间 当前时间 - 视频发布时间 小根堆来实现这个公式可以很好的利用半衰期来进行解决难点:如果一次性加载太多到springBoot服务器里面会造成堆内存占用过多&#xff0c;分页又有可能造成深分页问题&#xff0c;…
阅读更多...
HAProxy（高可用性代理）

HAProxy（高可用性代理）

1 HAProxy 简介 HAProxy&#xff08; High Availability Proxy&#xff09;是一个高性能的负载均衡器和代理服务器&#xff0c;为基于 TCP 和 HTTP 的应用程序提供高可用性、负载平衡和代理&#xff0c;广泛应用于提高 web 应用程序的性能和可靠性。它支持多种协议&#xff0c…
阅读更多...
Vulnhub靶场:ica1

Vulnhub靶场:ica1

一、信息收集nmap扫描一下IP。&#xff08;扫不出来的可以看一下前面几篇找ip的步骤&#xff09;下面给了框架的版本是9.2的&#xff0c;我们去kali里搜一下有没有已经公开的漏洞。searchsploit qdPM 9.2 locate 50176.txt more /usr/share/exploitdb/exploits/php/webapps/50…
阅读更多...
【Dv3admin】ORM数据库无法查询的问题

【Dv3admin】ORM数据库无法查询的问题

Django 运行过程中&#xff0c;数据库连接的健康状态直接影响应用的稳定性和数据访问准确性。长时间空闲的数据库连接经常因外部机制被回收&#xff0c;进而引发数据查询异常和返回无效结果。 本文围绕 Django 中数据库连接长时间空闲导致的连接失效问题&#xff0c;介绍相关的…
阅读更多...
使用 Flownex 对机械呼吸机进行建模

使用 Flownex 对机械呼吸机进行建模

当患者无法独立呼吸时&#xff0c;机械呼吸机通过气管插管将富氧空气输送到患者的肺部。肺是敏感而复杂的器官&#xff0c;因此在无法忍受的压力和体积范围内提供空气&#xff0c;根据每分钟所需的呼吸次数计时&#xff0c;并适当加湿和加热。机械呼吸机的精确建模对于其安全有…
阅读更多...
力扣刷题日常(7-8)

力扣刷题日常(7-8)

力扣刷题日常(7-8) 第7题: 整数反转(难度: 中等) 原题: 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果. 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0. 假设环境不允许存储 64 位整数&#xff08;有符号或无符号&#xff09;.…
阅读更多...
串口接收数据包（协议带帧头帧尾）的编程实现方法：1、数据包格式定义结构体2、使用队列进行数据接收、校验解包

串口接收数据包（协议带帧头帧尾）的编程实现方法：1、数据包格式定义结构体2、使用队列进行数据接收、校验解包

这种带帧头帧尾的数据包处理流程可以简单概括为 “识别边界→提取有效数据→验证完整性” 三个核心步骤&#xff0c;具体操作如下&#xff1a;1. 数据包格式定义&#xff08;先约定规则&#xff09;首先明确一个 “合格数据包” 的结构&#xff0c;比如&#xff1a; 帧头&#…
阅读更多...
JSON 对象封装教程

JSON 对象封装教程

JSON 对象封装方法在 Java 中封装 JSON 对象通常使用第三方库&#xff0c;如 org.json、Gson 或 Jackson。以下是几种常见的方法&#xff1a;使用 org.json 库添加 Maven 依赖&#xff1a;<dependency><groupId>org.json</groupId><artifactId>json<…
阅读更多...
【WRF-Chem】EDGAR 排放数据处理：分部门合并转化为二进制（Python全代码）

【WRF-Chem】EDGAR 排放数据处理：分部门合并转化为二进制（Python全代码）

目录 process.py process_biofl.py process_fossil.py process_micro.py process_sector.py 参考 process.py 读取 EDGAR 排放数据库中 2000 至 2023 年间不同行业的甲烷（CH₄）排放数据，进行合并处理，并将总排放以二进制格式保存到文件中。 导入必要的库 import numpy as n…
阅读更多...
最新文章

Copyright @ 2022~2023