数据结构--＞线性表--＞单链表

 

链表的定义

链表：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

与顺序表不同的是，链表里的每节都是独立申请下来的空间，我们称之为“节点、结点”。

节点的组成主要由两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。

链表的节点（结点）

链表中的每个节点都是独立申请的（需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

给出每个节点对应的结构体代码：以保存的节点是整形为例：

struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。

链式结构在逻辑上是连续的，在物理结构上不一定连续

节点一般是从堆上申请的

从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

链表的分类 

对于链表的分类来说：一共有8种

最常用的两种链表结构 

虽然链表结构很多，但最常用的只有两种结构
单链表：也叫无头单向非循环链表，结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个链表虽然结构复杂，但是使用代码实现以后会发现法结构会带来更多优势。
 

首先我们给出我们要实现的单链表的头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SList
{SLDataType data;struct SList* next;
}SL;
//打印
void SLPrint(SL* phead);
//销毁
void SLDestroy(SL** pphead);
//开辟新链表节点
SL* Buynode(SLDataType x);
//链表头插
void SLPushFront(SL** pphead,SLDataType x);
//链表尾插
void SLPushBack(SL** pphead,SLDataType x);
//链表头删
void SLPopFront(SL** pphead); 
//链表尾删
void SLPopBack(SL** pphead);
//链表对节点的查找
SL* SLFind(SL** pphead,SLDataType x);
//对指定位置之前插入数据
void SLInsert(SL** pphead,SL* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x);
//删除pos节点
void SLErase(SL** pphead,SL* pos);
//删除pos之后的节点
void SLEraseafter(SL* pos);

对单链表打印


这里直接进行遍历就ok

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

销毁单链表 

逐个销毁，销毁某一个节点时，保存他的下一个节点的地址。

//销毁
void SLDestroy(SL** pphead)
{assert(pphead);assert(*pphead);SL* pcur = *pphead;while (pcur){SL* next = (*pphead)->next;free(pcur);pcur = next;}*pphead = NULL;
}

 开辟节点空间

为新的数据开辟空间

//开辟节点空间
SL* Buynode(SLDataType x)
{SL* newnode = (SL*)malloc(sizeof(SL));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

 单链表头插

记得先后顺序，个人感觉容易犯错

//链表头插
void SLPushFront(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);//个人觉得易错new->next = *pphead;*pphead = new;
}

单链表尾插

如果头结点为空，则相当于头插

如果头结点不为空，就正常找尾节点然后插入。

//链表尾插
void SLPushBack(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);if (*pphead == NULL){*pphead = new;return;}SL* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = new;
}

 单链表头删

 对于删除来说，需要断言pphead和*pphead，pphead是存放*pphead的地址不能为NULL，

*pphead是为了判断单链表不能为NULL

//链表头删
void SLPopFront(SL** pphead)
{assert(pphead);assert(*pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}

 单链表尾删

如果只有一个元素，就相当于头删，否则就相当于尾删

//链表尾删
void SLPopBack(SL** pphead)
{assert(pphead);assert(*pphead);if (((*pphead)->next) == NULL){free(*pphead);*pphead = NULL;}SL* prev = NULL;SL* pcur = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;
}

单链表对节点的查找

遍历查找与目标值相同的，然后返回存储该值的地址

//链表对节点的查找
SL* SLFind(SL** pphead, SLDataType x)
{assert(pphead);SL* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

对指定位置插入数据

1.pos在*pphead，相当于头插

2.pos不在*pphead，就正常插入

//对指定位置之前插入数据
void SLInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SL* new = Buynode(x);if (pos == *pphead){SLPushFront(pphead, x);return;}SL* pcur = *pphead;while (pcur->next!=pos){pcur = pcur->next;}pcur->next = new;new->next = pos;
}

 在指定位置后插入

没什么好说的，直接找到指定位置，然后插入即可

//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x)
{assert(pos);SL* new = Buynode(x);new->next = pos->next;pos->next = new;
}

 删除pos节点的值

如果pos为*pphead就头删，否则就正常删除pos节点的值

//删除pos节点
void SLErase(SL** pphead, SL* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);return;}SL* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SL* next = pos->next;pcur->next = next;free(pos);pos=NULL;
}

 删除pos节点之后的值

找到pos节点，当然联系pos和pos->next->next的值

//删除pos之后的节点
void SLEraseafter(SL* pos)
{assert(pos);assert(pos->next);SL* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

 最终代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SList
{SLDataType data;struct SList* next;
}SL;
//打印
void SLPrint(SL* phead);
//销毁
void SLDestroy(SL** pphead);
//开辟新链表节点
SL* Buynode(SLDataType x);
//链表头插
void SLPushFront(SL** pphead,SLDataType x);
//链表尾插
void SLPushBack(SL** pphead,SLDataType x);
//链表头删
void SLPopFront(SL** pphead); 
//链表尾删
void SLPopBack(SL** pphead);
//链表对节点的查找
SL* SLFind(SL** pphead,SLDataType x);
//对指定位置之前插入数据
void SLInsert(SL** pphead,SL* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x);
//删除pos节点
void SLErase(SL** pphead,SL* pos);
//删除pos之后的节点
void SLEraseafter(SL* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//打印
void SLPrint(SL* phead)
{SL* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}
//销毁
void SLDestroy(SL** pphead)
{assert(pphead);assert(*pphead);SL* pcur = *pphead;while (pcur){SL* next = (*pphead)->next;free(pcur);pcur = next;}*pphead = NULL;
}
//开辟节点空间
SL* Buynode(SLDataType x)
{SL* newnode = (SL*)malloc(sizeof(SL));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;return newnode;
}
//链表头插
void SLPushFront(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);//个人觉得易错new->next = *pphead;*pphead = new;
}
//链表尾插
void SLPushBack(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);if (*pphead == NULL){*pphead = new;return;}SL* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = new;
}
//链表头删
void SLPopFront(SL** pphead)
{assert(pphead);assert(*pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//链表尾删
void SLPopBack(SL** pphead)
{assert(pphead);assert(*pphead);if (((*pphead)->next) == NULL){free(*pphead);*pphead = NULL;}SL* prev = NULL;SL* pcur = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;
}
//链表对节点的查找
SL* SLFind(SL** pphead, SLDataType x)
{assert(pphead);SL* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//对指定位置之前插入数据
void SLInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SL* new = Buynode(x);if (pos == *pphead){SLPushFront(pphead, x);return;}SL* pcur = *pphead;while (pcur->next!=pos){pcur = pcur->next;}pcur->next = new;new->next = pos;
}
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x)
{assert(pos);SL* new = Buynode(x);new->next = pos->next;pos->next = new;
}
//删除pos节点
void SLErase(SL** pphead, SL* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);return;}SL* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SL* next = pos->next;pcur->next = next;free(pos);pos=NULL;
}
//删除pos之后的节点
void SLEraseafter(SL* pos)
{assert(pos);assert(pos->next);SL* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
int main()
{SL* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);//1->2//SLPrint(plist);SLPushFront(&plist, 3);//3->1->2//SLPrint(plist);SLPushFront(&plist, 4);//SLPrint(plist);//4->3->1->2SLPopBack(&plist);//4->3->1//SLPrint(plist);SLPopFront(&plist);//3->1//SLPrint(plist);SL* new=SLFind(&plist, 3);SLInsert(&plist,new,4);//4->3->1//SLPrint(plist);SLInsertafter(new, 5);//4->3->5->1//SLPrint(plist);SLErase(&plist, new);//4->5->1SLPrint(plist);SLDestroy(&plist);return 0;
}

运行test函数：

以及测试过了，每个接口函数都没啥问题

 

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

机器翻译后的美赛论文怎么润色

机器翻译后的美赛论文怎么润色

美赛论文的语言表达一直是组委会看重的点&#xff0c;清晰的思路和地道的语言在评审中是重要的加分项。 今天我们就来讲讲美赛论文的语言问题。 我相信有相当一部分队伍在打美赛的时候&#xff0c;出于效率的考量&#xff0c;都会选择先写中文论文&#xff0c;再机翻成英文。 …
阅读更多...
ChatGPT4 教你如何完成SQL的实践应用

ChatGPT4 教你如何完成SQL的实践应用

对数据库的各项应用与操作都离不开SQL来对数据进行增删改查。 例如 &#xff1a; 有一张某公司职员信息表如下&#xff1a; 需求1&#xff1a;在公司职员信息表中&#xff0c;请统计各部门&#xff0c;各岗位下的员工人数。 如果这个SQL语句不会写或者不知道怎么操作可以交给…
阅读更多...
Linux运行级别 | 管理Linux服务

Linux运行级别 | 管理Linux服务

Linux运行级别 级别&#xff1a; 0关机1单用户2多用户但是不运行nfs网路文件系统3默认的运行级别&#xff0c;给一个黑的屏幕&#xff0c;只能敲命令4未使用5默认的运行级别&#xff0c;图形界面6重启切换运行级别&#xff1a; init x管理Linux服务 systemctl命令&#xf…
阅读更多...
【北邮鲁鹏老师计算机视觉课程笔记】02 filter

【北邮鲁鹏老师计算机视觉课程笔记】02 filter

1 图像的类型 二进制图像&#xff1a; 灰度图像&#xff1a; 彩色图像&#xff1a; 2 任务&#xff1a;图像去噪 噪声点让我们看得难受是因为噪声点与周边像素差别很大 3 均值 滤波核 卷积核 4 卷积操作 对应相乘再累加起来 卷积核记录了权值&#xff0c;把权值套到要卷积…
阅读更多...
vivo发布2023 年度科技创新；阿里全新AI代理，可模拟人类操作手机

vivo发布2023 年度科技创新；阿里全新AI代理，可模拟人类操作手机

vivo 发布 2023 年度十大产品技术创新 近日&#xff0c;vivo 发布了「2023 年度科技创新」十大产品技术创新榜单&#xff0c;并将这些技术分为了 4 个板块。 「四大蓝科技」为 vivo 在去年推出的全新技术品牌&#xff0c;涵盖蓝晶芯片技术栈、蓝海续航系统、蓝心大模型、蓝河操…
阅读更多...
基于springboot会员制医疗预约服务管理信息系统源码和论文

基于springboot会员制医疗预约服务管理信息系统源码和论文

会员制医疗预约服务管理信息系统是针对会员制医疗预约服务管理方面必不可少的一个部分。在会员制医疗预约服务管理的整个过程中&#xff0c;会员制医疗预约服务管理系统担负着最重要的角色。为满足如今日益复杂的管理需求&#xff0c;各类的管理系统也在不断改进。本课题所设计…
阅读更多...
sqlmap 使用笔记（kali环境）

sqlmap 使用笔记（kali环境）

sqlmap使用 kali环境 -u或–url 直接扫描单个路径 //如果需要登录要有cookie sqlmap -u "http://10.0.0.6:8080/vulnerabilities/sqli/?id1" --cookie"PHPSESSIDisgvp2rv4uts46jbkb9bouq6ir; securitylow"-m 文件中保存多个url&#xff0c;工具会依次扫…
阅读更多...
93 log4j-slf4j-impl 搭配上 log4j-to-slf4j 导致的 StackOverflow

93 log4j-slf4j-impl 搭配上 log4j-to-slf4j 导致的 StackOverflow

前言 呵呵 最近想要 做一个 mongo 低版本的客户端读取高版本的服务端传递过来的数据造成的一个错误的时候, 出现了这样的问题 引入了 mongo-java-driver 之后, 使用相关 api 的时候会触发 com.mongo.internal.connection.BaseCluser 的初始化, 其依赖的 Loggers 间接的依赖…
阅读更多...
解决MapboxGL的Popup不支持HTMLDiv元素的问题

解决MapboxGL的Popup不支持HTMLDiv元素的问题

解决MapboxGL的Popup不支持HTMLDiv元素的问题 官网给出的文档是不支持HTMLDivElement的&#xff0c;只支持HTML标签。 如果单纯的只显示字符串&#xff0c;那就没问题&#xff0c;如果想在Popup中使用更强大的功能&#xff0c;此时就不行了&#xff0c;下面是源码的一部分显示…
阅读更多...
python从入门到精通（十）：python爬虫的BeautifulSoup4

python从入门到精通（十）：python爬虫的BeautifulSoup4

python爬虫的BeautifulSoup4 BeautifulSoup4导入模块解析文件创建对象python解析器beautifulsoup对象的种类Tag获取整个标签获取标签里的属性和属性值Navigablestring 获取标签里的内容BeautifulSoup获取整个文档Comment输出的内容不包含注释符号BeautifulSoup文档遍历Beautifu…
阅读更多...
金融信贷风控系统设计

金融信贷风控系统设计

前言 近一年多以来在金融行业负责风控系统&#xff0c;根据自己工作中的经验&#xff0c;写下这篇文章。既是对自己在风控领域工作的总结&#xff0c;也是给刚入行和准备入行的朋友打个样&#xff0c;希望能有所帮助。 为什么要有风控系统 记得 2016 年信贷行业的发展形势还…
阅读更多...
JavaScript综合练习4

JavaScript综合练习4

JavaScript 综合练习 4 1. 案例演示 2. 代码实现 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title&…
阅读更多...
[职场] 如何通过运营面试_1 #笔记#媒体#经验分享

[职场] 如何通过运营面试_1 #笔记#媒体#经验分享

如何通过运营面试 盈利是公司的事情&#xff0c;而用户就是你运营的事情。你需要彻底建立一个庞大而有效的用户群&#xff0c;这样才能让你们的公司想盈利就盈利&#xff0c;想战略就战略&#xff0c;想融资就融资。 一般从事运营的人有着强大的自信心&#xff0c;后台数据分析…
阅读更多...
M1 Mac使用SquareLine-Studio进行LVGL开发

M1 Mac使用SquareLine-Studio进行LVGL开发

背景 使用Gui-Guider开发遇到一些问题，比如组件不全。使用LVGL官方的设计软件开发 延续上一篇使用的基本环境。 LVGL项目 新建项目 选择Arduino的项目，设定好分辨率及颜色。 设计UI 导出代码 Export -> Create Template Project 导出文件如图 将libraries下的ui文…
阅读更多...
微服务学习 | Spring Cloud 中使用 Sentinel 实现服务限流

微服务学习 | Spring Cloud 中使用 Sentinel 实现服务限流

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站https://www.captainbed.cn/kitie。 目录 前言 通过代码实现限流 定义资源 通过代码定义资源 通过注解方式定义资源 定义限流规则 通过…
阅读更多...
第三章：光效果产生立体感

第三章：光效果产生立体感

本文是《从0开始图形学》笔记的第三章&#xff0c;上一章中我们已经将箱子的整个形状“找出来”了&#xff0c;但是还仅仅只是一个色块区域。这一节我们就利用光将整个箱子的立体感凸显出来。涉及到布林冯光照模型以及向量的点乘运算。 概念解说 这里需要用到“布林冯”光照模…
阅读更多...
C语言函数（三）：数组和函数实现扫雷游戏

C语言函数（三）：数组和函数实现扫雷游戏

目录 1.扫雷游戏的分析和设计1.1.扫雷游戏的功能说明1.2.游戏的分析与设计1.2.1 数据结构的分析1.2.2 文件结构设计 2.扫雷游戏的代码实现 1.扫雷游戏的分析和设计 1.1.扫雷游戏的功能说明 使用控制台实现经典的扫雷游戏游戏可以通过菜单实现继续玩游戏或者退出游戏扫雷的棋盘…
阅读更多...
网课：数独挑战——牛客（题解与疑问）

网课：数独挑战——牛客（题解与疑问）

题目描述 数独是一种填数字游戏&#xff0c;英文名叫 Sudoku&#xff0c;起源于瑞士&#xff0c;上世纪 70 年代由美国一家数学逻辑游戏杂志首先发表&#xff0c;名为 Number Place&#xff0c;后在日本流行&#xff0c;1984 年将 Sudoku 命名为数独&#xff0c;即 “独立的数…
阅读更多...
刘谦春晚纸牌魔术背后的数学—海明码原理简介

刘谦春晚纸牌魔术背后的数学—海明码原理简介

在昨天2024年的春晚舞台上&#xff0c;魔术大师刘谦以一场令人拍案叫绝的纸牌魔术再度震撼全场。他巧妙地利用了数学原理&#xff0c;精准无误地让观众“随机”选择的纸牌完成了配对&#xff0c;尤其是令人忍俊不禁的是主持人尼格买提的纸牌却没有如愿配对&#xff0c;小尼碎了…
阅读更多...
机器学习复习（8）——逻辑回归

机器学习复习（8）——逻辑回归

目录 逻辑函数&#xff08;Logistic Function&#xff09; 逻辑回归模型的假设函数 从逻辑回归模型转换到最大似然函数过程 最大似然函数方法 梯度下降 逻辑函数&#xff08;Logistic Function&#xff09; 首先&#xff0c;逻辑函数&#xff0c;也称为Sigmoid函数&#…
阅读更多...
最新文章

Copyright @ 2022~2023