数据结构之单链表

news/2025/3/15 13:21:28/

文章目录

  • 前言：
  • 一.链表的概念及结构
    • 1.何为链表
    • 2.链表常见的几种形式
  • 二.无头单向非循环链表的实现
    • 1.定义节点
    • 2.创建一个新节点
    • 3.单链表打印
    • 4.单链表尾插
    • 5.单链表尾删
    • 6.单链表头插
    • 7.单链表头删
    • 8.单链表查找
    • 9.在pos之前插入
    • 10.在pos之前删除
    • 11.在pos之后插入
    • 12.在pos之后删除
    • 13.assert( )断言的使用
  • 三.源码
    • 1.SList.h
    • 2.SList.c

前言：

书接上文，顺序表的问题及思考：

  1. 中间或头部的插入删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

为了更好的解决上述问题，本文我们来学习链表：

一.链表的概念及结构

1.何为链表

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

如图为单链表的两种结构：
①物理结构
在这里插入图片描述
②逻辑结构
在这里插入图片描述
注意：

  1. 链表的链式结构在逻辑上是连续的，但在物理上不一定连续。
  2. 现实中的节点一般都是从堆上申请出来的。
  3. 从堆上申请的节点，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

2.链表常见的几种形式

实际中链表的结构非常多样，各种情况组合起来就有8种链表结构：
①单向或者双向
在这里插入图片描述
②带头或者不带头
在这里插入图片描述
③循环或者非循环
在这里插入图片描述
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

  1. 无头单向非循环链表
    结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    在这里插入图片描述

  2. 带头双向循环链表
    结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
    在这里插入图片描述

二.无头单向非循环链表的实现

函数接口：

typedef int SLTDataType;//定义节点
typedef struct SListNode
{SLTDataType data;   //存放数据struct SListNade* next;  //指向下一个节点
}SLTnode;//申请节点
SLTnode* BuySLTNode(SLTDataType x);
//打印
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);
//在pos之前插入
void SLTInsert(SLTnode** pphead, SLTnode* pos, SLTDataType x);
//删除pos之前的节点
voide SLTErase(SLTnode** pphead, SLTnode* pos);
//在pos之后插入
void SLTInsertAftter(SLTnode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTnode* pos);

1.定义节点

//节点
typedef struct SListNode
{SLTDataType data;   //存放数据struct SListNade* next;  //指向下一个节点
}SLTnode;
  1. 链式结构由一个个的节点链接而成，节点中存放当前的数据data和指向下一个节点的指针。
  2. 链表正是有节点串联而成，所以只需记住排在最前面的头节点的位置，就能访问链表中的任意一个节点

注：这里的头节点指的是链表中第一个节点，它本身也会存储数据，而后面讲的带头双向循环链表中的头节点仅是链表起始的标志，并不会存储有效数据

2.创建一个新节点

后面我们要在单链表中进行插入和删除，此时的插入删除是针对节点进行的，这个结点是包括SLTDateType数据以及SLTDateType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。

SLTnode* BuySLTNode(SLTDataType x)
{SLTnode* newnode = (SLTnode*)malloc(sizeof(SLTnode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

3.单链表打印

void SLTPrint(SLTnode* phead)
{SLTnode* cur = phead;  //cur指向phead存放的地址while (cur != NULL)    //不为空{printf("%d->", cur->data);  //输出当前节点存的值cur=cur->next;    //该节点指向下一个节点}printf("NULL\n");
}

cur=cur->next; 这句话的含义是：
在这里插入图片描述

4.单链表尾插

//尾插
void SLTPushBack(SLTnode** pphead, SLTDataType x)
{assert(pphead);SLTnode* newnode = BuySLTNode(x);if (*pphead == NULL)  //空链表{*pphead = newnode;}else{//找到尾部SLTnode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

注意：

  1. 从代码中可以看出，我们使用了二级指针，这是因为我们要在原链表上做出修改，所以要传原链表头节点的地址，也就是一级指针的地址，要用二级指针来接收。
  2. 然后是找尾过程：
    在这里插入图片描述

5.单链表尾删

//尾删
void SLTPopBack(SLTnode** pphead)
{assert(pphead);//1.检查是否为空assert(*pphead);//2.只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTnode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

注意：

  1. 链表为空时，没东西可删，要特判一下
  2. 链表只有一个节点时，删完就空了，也特别处理一下
  3. tail->next->next != NULL这句循环条件的含义是：
    在这里插入图片描述

6.单链表头插

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

如下图所示：
在这里插入图片描述

7.单链表头删

//头删
void SLTPopFront(SLTnode** pphead)
{assert(pphead);//1.检查是否为空assert(*pphead);SLTnode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

先检查是否为空，如果不为空，则：
在这里插入图片描述
直接覆盖掉第一个节点以达到头删的效果。

8.单链表查找

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

9.在pos之前插入

//在pos之前插入
void SLTInsert(SLTnode** pphead, SLTnode* pos, SLTDataType x)
{assert(pos);  //pos这个节点存在assert(pphead);  //正确传值，不能为空if (pos == *pphead)  //pos在第一个节点处{SLTPushFront(pphead, x); //复用头插函数}else{//找到pos的前一个位置SLTnode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTnode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

在这里插入图片描述

10.在pos之前删除

//删除pos之前的节点
voide SLTErase(SLTnode** pphead, SLTnode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{//找到pos的前一个位置SLTnode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;  //覆盖掉posfree(pos);}
}

11.在pos之后插入

//在pos之后插入
void SLTInsertAftter(SLTnode* pos, SLTDataType x)
{assert(pos);SLTnode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

在这里插入图片描述

12.在pos之后删除

//删除pos之后的节点
void SLTEraseAfter(SLTnode* pos)
{assert(pos);assert(pos->next);  //保证pos之后有节点SLTnode* del = pos->next;pos->next = del->next;  //覆盖以删除free(del);del = NULL;
}

13.assert( )断言的使用

在上面代码中我们会发现，为什么有的代码需要断言指针，有的就不需要，有的要断言一级指针，有的要断言二级指针，也有的什么都不用断言，这是为什么呢？

  1. 首先，assert函数在调试的时候非常好用，一旦（）内为假，会立刻报错，而且会帮我们提示报错在哪个文件和在哪行代码。
  2. 一级指针也就是phead，当链表为空的时候，phead就是为NULL，此时需要根据函数要实现的实际功能来确定是否断言。比如：打印函数SLTPrint（），当传来的指针为空时，说明链表中没有元素，但是没有元素也是可以打印的，如果断言就会报错。
  3. 二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以有**pphead的地方就需要断言pphead，这样可以及时发现在传参时传成空指针的错误。

三.源码

1.SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;//定义节点
typedef struct SListNode
{SLTDataType data;   //存放数据struct SListNade* next;  //指向下一个节点
}SLTnode;//申请节点
SLTnode* BuySLTNode(SLTDataType x);
//打印
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);
//在pos之前插入
void SLTInsert(SLTnode** pphead, SLTnode* pos, SLTDataType x);
//删除pos之前的节点
voide SLTErase(SLTnode** pphead, SLTnode* pos);
//在pos之后插入
void SLTInsertAftter(SLTnode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTnode* pos);

2.SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"//申请一个新节点
SLTnode* BuySLTNode(SLTDataType x)
{SLTnode* newnode = (SLTnode*)malloc(sizeof(SLTnode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}
//打印
void SLTPrint(SLTnode* phead)
{SLTnode* cur = phead;  //临时指针while (cur != NULL)   //不为空{printf("%d->", cur->data);  //输出当前节点存的值cur=cur->next;    //该节点指向下一个节点}printf("NULL\n");
}
//尾插
void SLTPushBack(SLTnode** pphead, SLTDataType x)
{assert(pphead);SLTnode* newnode = BuySLTNode(x);if (*pphead == NULL)  //空链表{*pphead = newnode;}else{//找到尾部SLTnode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
//尾删
void SLTPopBack(SLTnode** pphead)
{assert(pphead);//1.检查是否为空assert(*pphead);//2.只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTnode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
//头插
void SLTPushFront(SLTnode** pphead, SLTDataType x)
{assert(pphead);SLTnode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
//头删
void SLTPopFront(SLTnode** pphead)
{assert(pphead);//1.检查是否为空assert(*pphead);SLTnode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}
//查找
SLTnode* SLTFind(SLTnode* phead, SLTDataType)
{SLTnode* cur = phead;while (cur){if (cur->data == x)  //找到了{return cur;}cur = cur->next;}return NULL; //没找到
}
//在pos之前插入
void SLTInsert(SLTnode** pphead, SLTnode* pos, SLTDataType x)
{assert(pos);  //pos这个节点存在assert(pphead);  //正确传值，不能为空if (pos == *pphead)  //pos在第一个节点处{SLTPushFront(pphead, x); //复用头插函数}else{//找到pos的前一个位置SLTnode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTnode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
//删除pos之前的节点
voide SLTErase(SLTnode** pphead, SLTnode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{//找到pos的前一个位置SLTnode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;  //覆盖掉posfree(pos);}
}
//在pos之后插入
void SLTInsertAftter(SLTnode* pos, SLTDataType x)
{assert(pos);SLTnode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}
//删除pos之后的节点
void SLTEraseAfter(SLTnode* pos)
{assert(pos);assert(pos->next);  //保证pos之后有节点SLTnode* del = pos->next;pos->next = del->next;  //覆盖以删除free(del);del = NULL;
}

本篇到此结束，码文不易，还请多多支持哦！！


http://www.ppmy.cn/news/29060.html

相关文章

IPv4地址细讲

IPv4地址细讲

文章目录一、IPv4地址简介二、IPv4地址的表示方法点分十进制记法三、IP地址的分类四、特殊IPv4地址&#xff1a;全 “0” 和全 “1”五、常用的三类IP地址使用范围六、五类IP地址的范围一、IPv4地址简介 IPv4地址分5类&#xff0c;每一类地址都由固定长度的字段组成&#xff1…
阅读更多...
k8s ConfigMap 中 subPath 字段和 items 字段

k8s ConfigMap 中 subPath 字段和 items 字段

Kubernetes中什么是subPath 有时&#xff0c;在单个 Pod 中共享卷以供多方使用是很有用的。volumeMounts.subPath 属性可用于指定所引用的卷内的子路径&#xff0c;而不是其根路径。 这句话理解了&#xff0c;基本就懂subPath怎么用了&#xff0c;比如我们要替换nginx.cnf, 挂…
阅读更多...
STM32开发（17）----CubeMX配置CRC

STM32开发（17）----CubeMX配置CRC

CubeMX配置CRC前言一、什么是CRC&#xff1f;二、实验过程1.STM32CubeMX配置2.代码实现重载printf3.实验结果总结前言 本章介绍使用STM32CubeMX对CRC进行配置的方法&#xff0c;CRC的目的是保证数据的完整性&#xff0c;所有的STM32芯片都内置了一个硬件的CRC计算模块&#xf…
阅读更多...
Python进阶-----高阶函数map() 简介和使用

Python进阶-----高阶函数map() 简介和使用

目录 简介&#xff1a; ​编辑 示例&#xff1a; 示例&#xff08;1&#xff09;&#xff1a;输出map()函数返回值&#xff08;迭代器&#xff09;结果 示例&#xff08;2&#xff09;&#xff1a;与循环对比 示例&#xff08;3&#xff09;&#xff1a;字符串转列表 示…
阅读更多...
【蓝桥杯入门到入土】最基础的数组你真的掌握了吗？

【蓝桥杯入门到入土】最基础的数组你真的掌握了吗？

文章目录一&#xff1a;数组理论基础二&#xff1a;数组知识点总结三&#xff1a;数组这种数据结构的优点和缺点是什么&#xff1f;四&#xff1a;实战解题1. 移除元素暴力解法双指针法2.有序数组的平方暴力解法双指针法最后说一句一&#xff1a;数组理论基础 首先要知道数组在…
阅读更多...
单目标应用：蜣螂优化算法DBO优化RBF神经网络实现数据预测（提供MATLAB代码）

单目标应用：蜣螂优化算法DBO优化RBF神经网络实现数据预测（提供MATLAB代码）

一、RBF神经网络 1988年&#xff0c;Broomhead和Lowc根据生物神经元具有局部响应这一特点&#xff0c;将RBF引入神经网络设计中&#xff0c;产生了RBF(Radical Basis Function)。1989年&#xff0c;Jackson论证了RBF神经网络对非线性连续函数的一致逼近性能。 RBF的基本思想是…
阅读更多...
如何使用C2concealer生成随机化的C2 Malleable配置文件

如何使用C2concealer生成随机化的C2 Malleable配置文件

关于C2concealer C2concealer是一款功能强大的命令行工具&#xff0c;在该工具的帮助下&#xff0c;广大研究人员可以轻松生成随机化的C2 Malleable配置文件&#xff0c;以便在Cobalt Strike中使用。 工具运行机制 开发人员对Cobalt Strike文档进行了详细的研究&#xff0c;…
阅读更多...
Elasticsearch：以 “Painless” 方式保护你的映射

Elasticsearch：以 “Painless” 方式保护你的映射

Elasticsearch 是一个很棒的工具&#xff0c;可以从各种来源收集日志和指标。 它为我们提供了许多默认处理&#xff0c;以便提供最佳用户体验。 但是&#xff0c;在某些情况下&#xff0c;默认处理可能不是最佳的&#xff08;尤其是在生产环境中&#xff09;&#xff1b; 因此&…
阅读更多...
最新文章

Copyright @ 2022~2023