手撕单链表（C语言）

目录

1.单链表的物理结构

2.头文件的实现

3.SList.c文件的实现

3.1尾插、创建节点

3.2打印

3.3头插

3.4尾删

3.5头删

3.6查找

3.7指定位置之前插入数据

3.8指定位置之后插入数据

3.9删除指定位置节点

3.10删除pos之后的节点

3.11销毁链表

4 所有的代码

1.单链表的物理结构

众所周知单链表是线性表的一种，线性表是逻辑结构连续、物理结构不一定连续的结构，我们的单链表就是逻辑上连续但物理结构上不一定连续的结构。

那么它的逻辑图长什么样呢？（如下图所示）

上面的图片中我们展示的是一种无头单向不循环链表，plist指针指向的就是单链表头节点的空间的地址。我们将每一个小方格称为节点，每个节点的结构中包括数据值和指向下一个节点的地址。

上面的代码就是我们这无头单向不循环链表的结构，我们重命名int型是为了以后改数据类型的时候不要改太多次，只用在这一行把int换掉就可以了。然后我们把单链表结构体重命名也是为了我们书写方便。我们这里使用三个文件来实现无头单向不循环链表的内容。分别是test.c源文件（用来测试代码的文件）、SList.c源文件（用来实现接口的文件）、SList.h头文件（用来进行接口的声明，各种头文件的调用，定义数据结构）。最后我会把代码全部放上来，那么我们开始来体会这个过程。

2.头文件的实现

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;
}SLNode;//创建几个节点组成一个链表，并打印链表
void SLNPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//删除
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);SLNode* SLFind(SLNode** pphead, SLDataType x);//指定位置的插入和删除//在指定位置之前插入数据
void SLInsert(SLNode** pphead,SLNode* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x);//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后节点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SListDesTroy(SLNode** pphead);

引用头文件我们就不多说了，单链表的结构我们上面也讲过了，接下来就来讲解一下声明这些接口的时候我们要注意的事项：由于在test.c文件中我们定义的是SLNode*指针，我们知道使用函数传参时，形参是实参的一份临时拷贝，所以为了修改我们的链表我们要传二级指针才能修改链表。

3.SList.c文件的实现

3.1尾插、创建节点

我们执行尾插前要先进行断言一下，这是为了防止传进来一个空指针，接下来就是创建节点：

创建节点我们只需要传一个x值就可以了，然后把返回值类型定位SLNode*型，在这个接口中我们先用malloc开辟出一块空间，然后再把x的值给到结构体中的data，之后我们再把next指针置为NULL，接下来就可以把节点指针返回了。

我们再回到上面，创建好节点后我们还要看一看是否传进来的是空链表，如果是的话我们把新的节点给头节点然后返回头节点，如果不是空链表的话，我们用pcur指针来遍历整个链表进行找尾操作，找到尾指针之后我们把尾指针的next指向新的节点。

3.2打印

我们的尾插操作有没有成功可以通过两种方式，一种是调试，一种是打印出来看看（粗略检查）。

我们还是让pcur指针来进行遍历，每遍历一个节点我们就打印一个节点，最后打印一个NULL，如果是空链表我们就会直接打印NULL。

这样我们就可以看出确实是尾插成功了。

3.3头插

头插的操作跟尾插差不多，我们先断言指针是否为NULL，不是的话我们创建一个新的节点，这里我们注意一下顺序，我们要先把新节点的next指向原来的头节点，再把头节点指针指向新的节点，倘若我们先进行把头节点指针指向新的节点我们就会发现我们找不到原来的头节点了，这就是我们要注意的一个地方。

好，让我们来看看效果：

3.4尾删

尾删的操作我们不需要传入x值了，只需要二级指针就行了，第一步还是要进行断言，我们这里我们还需要断言一下它的一级指针，因为我们既然要进行删除操作，我们的链表总不能是空链表吧，接下来我们处理只有一个节点的情况，只有一个节点的话，我们直接把头节点空间释放，地址指向空就可以了，如果节点不只有一个，我们就需要找尾节点和尾节点的前一个节点，我们先创建一个ptail进行遍历，ptail指向的是最后一个节点，prev则是前一个节点，我们把我们把将要成为尾节点的next指向原尾节点的next，再把原尾节点的空间释放掉，我们就完成了尾删的操作。

3.5头删

头删操作要简单的多，它不需要考虑只有一个节点的情况，跟尾删一样，我们先断言两次，然后创建一个del指针指向头节点，然后将头节点指向新的头节点，也就是原头节点的下一个节点，然后把del释放掉，我们再出于规范把这个野指针置为NULL。

3.6查找

这里我们查找的标准就定为查找是否有x这个元素，然后我们的第一步还是断言，之后创建一个pcur来遍历整个链表，如果找到了就返回这个地址，如果没有找到就返回NULL。

3.7指定位置之前插入数据

这里我们要多传一个参数pos，因为pos就是我们的指定位置的节点。好我们开始断言，断言之后我们创建新的节点，然后处理只有一个节点的情况，如果只有一个头节点我们就把新节点的next指向头节点，然后再让头节点的指针指向新节点；如果不只有一个节点，那么我们就创建一个指针prev来找到pos节点的前一个，然后把新节点的next指向pos，再把原来的前一个节点的next指向新的节点。

3.8指定位置之后插入数据

这个操作我们就要简单的多，我们先进行断言，然后创建一个新的节点，让新的节点的next指向pos节点的下一个节点，再把pos的next指向新的节点。

3.9删除指定位置节点

老操作，先进行断言如果我们删除的是头节点，那么我们直接把头节点指向头节点的下一个节点，然后释放pos，返回无值就可以了；如果不是头节点，那么我们就要先创建一个prev指针来找pos的前一个节点，把prev的next指向pos的下一个，再释放掉pos就可以了，我们也可以为了规范再把pos置为NULL。

3.10删除pos之后的节点

这个就要节点的多，我们只需要断言一下pos和pos的下一个节点就行了，然后我们再创建一个del指针指向pos的下一个节点，然后把pos的next指向pos的下一个的下一个节点，我们再释放掉del。

3.11销毁链表

我们进行一下断言，再创建一个指针进行遍历，每遍历一次就销毁一个节点。

4 所有的代码

//SList.h头文件#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;
}SLNode;//创建几个节点组成一个链表，并打印链表
void SLNPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//删除
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);SLNode* SLFind(SLNode** pphead, SLDataType x);//指定位置的插入和删除//在指定位置之前插入数据
void SLInsert(SLNode** pphead,SLNode* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x);//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后节点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SListDesTroy(SLNode** pphead);
//SList.c源文件#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"void SLNPrint(SLNode* phead)
{//循环打印SLNode* pcur = phead;while (pcur){printf("%d ->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLNode* SLBuyNode(SLDataType x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));node->data = x;node->next = NULL;return node;
}//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node = SLBuyNode(x);if (*pphead == NULL){*pphead = node;return;}//说明链表不为空，找尾SLNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = node;
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node = SLBuyNode(x);//新节点跟头节点连接起来node->next = *pphead;//让新的节点成为头节点*pphead = node;
}
//删除
void SLPopBack(SLNode** pphead)
{assert(pphead);//第一个节点不能为空assert(*pphead);//只有一个节点的情况if ((*pphead)->next==NULL){//直接把头节点删除free(*pphead);*pphead = NULL;}else{//找尾节点和尾节点的前一个节点SLNode* prev = NULL;SLNode* ptail = *pphead;while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}//prev的next指针不再指向ptail，指向下一个节点prev->next = ptail->next;free(ptail);ptail = NULL;}}
void SLPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;//出于代码规范
}SLNode* SLFind(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead);//约定链表不为空，pos也不能为空assert(pos);assert(*pphead);SLNode* node = SLBuyNode(x);//处理只有一个节点+pos指向第一个节点if (pos==*pphead){node->next = *pphead;*pphead = node;return;}//找pos的前一个节点SLNode* prev = *pphead;while(prev->next!=pos){prev = prev->next;}//prev node posnode->next = pos;prev->next = node;
}//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* node = SLBuyNode(x);node->next = pos->next;pos->next = node;
}//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){*pphead = (*pphead)->next;free(pos);return;}//找pos的前一个节点SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos)
{assert(pos&&pos->next);SLNode* del = pos->next;pos->next = del->next;free(del);
}//销毁链表
void SListDesTroy(SLNode** pphead)
{assert(pphead);SLNode* pcur = *pphead;while (pcur){SLNode* next = pcur->next;free(pcur);pcur = next;}pcur = NULL;
}

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

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

相关文章

百分点科技|怎样做数据运营，才能让数据中台真正用起来？

百分点科技|怎样做数据运营，才能让数据中台真正用起来？

导读&#xff1a;大多数企业用户已完成数据平台初步建设工作&#xff0c;但数据在业务运营和管理中没有发挥应有价值。数据开发工作繁重&#xff0c;数据质量问题严重&#xff0c;IT、数据和业务协作不畅&#xff0c;诸多问题依然困扰着企业用户的IT部门和数据部门。数据运营成…
阅读更多...
Spring注解开发

Spring注解开发

注解开发 注解开发定义bean 使用Component定义bean 核心配置文件中通过组件扫描加载bean Spring提供Component注解的三个衍生注解 Controller&#xff1a;用于表现层bean定义Service&#xff1a;用于业务层bean定义Repository&#xff1a;用于数据层bean定义 纯注解开发 Spr…
阅读更多...
在VSCode创建vue项目，出现“因为在此系统上禁止运行脚本”问题

在VSCode创建vue项目，出现“因为在此系统上禁止运行脚本”问题

问题&#xff1a;vue : 无法加载文件 C:\Users\***\***\Roaming\npm\vue.ps1&#xff0c;因为在此系统上禁止运行脚本。有关详细信息&#xff0c;请参阅 ht tps:/go.microsoft.com/fwlink/?LinkID135170 中的 about_Execution_Policies。 所在位置 行:1 字符: 1 解决&#xff…
阅读更多...
Ubuntu——卸载、安装CUDA

Ubuntu——卸载、安装CUDA

【注】WSL的Ubuntu是不用安装CUDA的&#xff0c;因为它使用的是Windows的显卡驱动&#xff0c;所以如果WSL的CUDA出了问题&#xff0c;重新安装WSL即可&#xff01; 如果nvidia-smi有显示&#xff0c;只是需要使用nvcc&#xff0c;那么就需要安装。安装的时候不要选Driver即可…
阅读更多...
Android Termux安装MySQL，内网穿透实现公网远程访问

Android Termux安装MySQL，内网穿透实现公网远程访问

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…
阅读更多...
会议剪影 | 思腾合力受邀出席第四届长三角文博会并作主题演讲

会议剪影 | 思腾合力受邀出席第四届长三角文博会并作主题演讲

以“担当新使命:长三角文化产业的力量”为主题的「第四届长三角国际文化产业博览会」于2023年11月16日-19日在国家会展中心&#xff08;上海&#xff09;成功举办。思腾合力作为行业领先的人工智能基础架构解决方案商出席本次盛会。 此次展会的面积首次超过10万平米&#xff0c…
阅读更多...
Python如何将项目直接打包为一键整合包

Python如何将项目直接打包为一键整合包

目录 一、准备项目 二、创建打包文件 三、创建安装脚本 四、执行安装 五、测试安装 六、常见问题与解决方案 总结 Python项目打包成一键整合包是一个比较复杂的任务&#xff0c;需要考虑到项目的各个方面&#xff0c;包括依赖项、配置文件、静态文件、数据库等等。下面是…
阅读更多...
[C++ 从入门到精通] 12.重载运算符、赋值运算符重载、析构函数

[C++ 从入门到精通] 12.重载运算符、赋值运算符重载、析构函数

&#x1f4e2;博客主页&#xff1a;https://loewen.blog.csdn.net&#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;本文由 丶布布原创&#xff0c;首发于 CSDN&#xff0c;转载注明出处&#x1f649;&#x1f4e2;现…
阅读更多...
基于安卓android微信小程序的好物分享系统

基于安卓android微信小程序的好物分享系统

运行环境 开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&a…
阅读更多...
提升工作效率，使用AnyTXT Searcher实现远程办公速查公司电脑文件——“cpolar内网穿透”

提升工作效率，使用AnyTXT Searcher实现远程办公速查公司电脑文件——“cpolar内网穿透”

文章目录 前言1. AnyTXT Searcher1.1 下载安装AnyTXT Searcher 2. 下载安装注册cpolar3. AnyTXT Searcher设置和操作3.1 AnyTXT结合cpolar—公网访问搜索神器3.2 公网访问测试 4. 固定连接公网地址 前言 你是否遇到过这种情况&#xff0c;异地办公或者不在公司&#xff0c;想找…
阅读更多...
命令执行无回显的判断方法及dnslog相关例题的讲解

命令执行无回显的判断方法及dnslog相关例题的讲解

命令无回显的情况
阅读更多...
短视频账号矩阵系统源码

短视频账号矩阵系统源码

短视频账号矩阵系统源码搭建步骤包括以下几个方面&#xff1a; 1. 确定账号类型和目标受众&#xff1a;确定要运营的短视频账号类型&#xff0c;如搞笑、美食、美妆等&#xff0c;并明确目标受众和定位。 2. 准备账号资料&#xff1a;准备相关资质和资料&#xff0c;如营业执照…
阅读更多...
关于爬虫中的hook(defineProperty，hook cookies， hook载荷数据，hookXHR）

关于爬虫中的hook(defineProperty，hook cookies， hook载荷数据，hookXHR）

关于爬虫中的hook&#xff1a; defineProperty var people {age: 19, }; var count20; console.log(people.age) // 参数&#xff1a;对象 属性名字 函数 Object.defineProperty(people, age, {get: function () {console.log(获取值&#xff01;);return count;},// set: …
阅读更多...
前端本地存储数据库IndexedDB

前端本地存储数据库IndexedDB

前端本地存储数据库IndexedDB 1、前言2、什么是 indexedDB&#xff1f;3、什么是 localForage&#xff1f;4、localForage 的使用5、VUE 推荐使用 Pinia 管理 localForage 1、前言 前端本地化存储算是一个老生常谈的话题了&#xff0c;我们对于 cookies、Web Storage&#xff…
阅读更多...
酷开科技丨这么好用的酷开系统，不用真的会后悔！

酷开科技丨这么好用的酷开系统，不用真的会后悔！

掀开一幕幕精彩剧情&#xff0c;手机已经成为了我们身边必不可少的追剧神器。在这个信息爆炸的时代&#xff0c;我们渴望能够随时随地享受到精彩的影视作品&#xff0c;尤其是在家的休息的时候&#xff0c;希望电视也能同手机一样&#xff0c;想看啥就搜啥。酷开科技大内容战略…
阅读更多...
django理解02 前后端分离中的问题

django理解02 前后端分离中的问题

前后端分离相对于传统方式的问题 前后端数据交换的问题跨域问题 页面js往自身程序&#xff08;django服务&#xff09;发送请求&#xff0c;这是浏览器默认接受响应 而请求其它地方是浏览器认为存在潜在危险。自动隔离请求&#xff01;&#xff01;&#xff01; 跨域问题的解决…
阅读更多...
根据nginx日志统计页面访问次数

根据nginx日志统计页面访问次数

静态页面部署在nginx上&#xff0c;页面只有查看下载功能。 需求是统计每条访问次数和下载次数&#xff0c;根据日志分析写了一个shell脚本&#xff0c;触发脚本后生成一个html可以远程查看统计的数量。 #!/bin/bash # nginx日志文件路径 LOG_FILE"/usr/local/nginx/l…
阅读更多...
读像火箭科学家一样思考笔记04_第一性原理（下）

读像火箭科学家一样思考笔记04_第一性原理（下）

1. 来自无形规则的阻力 1.1. 无形规则 1.1.1. 僵化成规则的不必要习惯和行为 1.1.2. 不像有形的书面规则 1.1.2.1. 书面规则出现在标准操作流程中&#xff0c;可以修改或删除 1.1.3. 成文的规则可能会抗拒变革&#xff0c;但无形规则却更加顽固 1.1.4. 我们为强加在自己身…
阅读更多...
EtherCAT从站EEPROM分类附加信息详解：RXPDO（输入过程数据对象）

EtherCAT从站EEPROM分类附加信息详解：RXPDO（输入过程数据对象）

0 工具准备 1.EtherCAT从站EEPROM数据（本文使用DE3E-556步进电机驱动器）1 分类附加信息——RXPDO（输入过程数据对象） 1.1 分类附加信息规范 在EEPROM字64开始的区域存储的是分类附加信息，这里存储了包括设备信息、SM配置、FMMU配置在内的诸多信息。每个信息在一段连续的…
阅读更多...
人工智能的广泛应用与影响

人工智能的广泛应用与影响

目录 前言1 智能手机与个人助手2 医疗保健3 自动驾驶技术4 金融领域5 教育与学习6 智能家居与物联网7 娱乐与媒体8 环境保护结语 前言 人工智能&#xff08;Artificial Intelligence&#xff0c;AI&#xff09;是当今科技领域的璀璨明星&#xff0c;它不仅在技术创新方面掀起了…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023