当前位置： 首页 > news >正文

数据结构 ——— C语言实现无哨兵位单向不循环链表

news 来源：原创 2024/9/30 8:28:36

目录

前言

动态顺序表的缺陷

单链表的概念

单链表中节点的结构

单链表逻辑结构示意图​编辑

实现单链表前的准备工作

实现单链表

1. 定义节点的指针

2. 创建节点

 3. 打印单链表中的所有数据

4. 在单链表头部插入数据

5. 在单链表尾部插入数据

6. 在单链表头部删除数据

7. 在单链表尾部删除数据

8. 在单链表中查找指定的节点

9. 在单链表中 pos 节点插入数据

1. 在 pos 节点之前插入

 2. 在 pos 节点之后插入

10. 在单链表中 pos 节点删除数据

1. 删除 pos 节点

2. 删除 pos 节点后一个节点

11. 释放单链表的所有节点

SList.h 的所有代码

SList.c 的所有代码

前言

在前几章，讲解了动态顺序表的实现和相关oj题

数据结构 ——— C语言实现动态顺序表-CSDN博客

数据结构 ——— 顺序表oj题：移除 nums 数组中的 val 元素（快慢指针）-CSDN博客

数据结构 ——— 顺序表oj题：编写函数，删除有序数组中的重复项-CSDN博客

接下来讲解的是动态顺序表的缺陷和单链表的概念以及实现

动态顺序表的缺陷

  1. 顺序表中间部分的插入删除函数和头部插入删除函数，时间复杂度都为O(N)
  2. 增容需要申请新的空间，拷贝数据，释放旧空间，会有不小的空间消耗，且还存在原地扩容或者异地扩容的问题
  3. 合理的增容机制一般是乘以原空间的2倍的增长，但势必还是会有一定的空间浪费

由以上的顺序表的缺陷，给出了新的数据结构 —— 单链表，单链表的结构可以完美的解决以上问题

单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，那么链表的顺序逻辑是通过链表中的指针链接（串联）次序实现的，且链表中的每一个节点都是独立的空间

链表这样设计的好处有：

  1. 解决了头部/中部插入删除时需要挪动数据的问题
  2. 按需申请或释放，不会存在浪费空间的问题
  3. 不会扩容，也不会存在扩容时的原地扩容或者异地扩容

单链表中节点的结构

// 单链表中数据的类型
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data; //单链表的数据struct SListNode* next; //指向下一个节点的指针
}SLTNode;

以上的结构是单链表中每一个节点的结构
节点的结构由两部分组成：当前节点的数据和指向下一个节点的指针

通过 next 指针把各个节点串联起来，最后一个节点的指针指向 NULL 表示链表的尾节点，这样的结构就称之为单链表

单链表逻辑结构示意图

单链表中的每一个节点存储的都是数据和下一个节点的地址（指针）

只有最后一个节点的地址存储的是NULL（作用是用来标记结束） 

实现单链表前的准备工作

和实现顺序表一样，需要准备3个文件

test.c 文件：用来测试代码功能的完善性

SList.h 文件：用来声明头文件和定义单链表的结构以及函数的声明

SList.c 文件：用来实现单链表的功能函数

实现单链表

1. 定义节点的指针

SLTNode* plist = NULL;

2. 创建节点

static SLTNode* BuyLTNode(SLTDataType x)
{// 开辟节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));// 判断是否开辟成功if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}

添加 static 关键字用作保护，因为 创建节点函数 只会在 插入节点相关的函数 中使用，避免被用户直接使用，防止内存泄漏

newnode->data 存储数据 X
newnode->next 默认指向 NULL

 3. 打印单链表中的所有数据

void SLTPrint(SLTNode* phead)
{// 判断 phead 指针的有效性assert(phead != NULL);SLTNode* cur = phead;// 当前单链表中无数据时if (cur == NULL){printf("当前链表无数据\n");return;}while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

一般在操作单链表时，不会直接使用 phead 指针，而是将 phead 指针赋值给同类型的 cur 指针来进行操作（因为会对指针的指向进行改动）

cur->data 是当前节点的数据，先打印当前数据
cur->next 是指向下一个节点的地址（指针）
cur->next 的类型是 struct SListNode* ，cur 的类型同样是 struct SListNode* ，所以把 cur->next 赋值给 cur ，那么 cur 这个指针就指向了下一个节点
直到 cur 为 NULL 就停止，因为单链表最后一个节点的 next 是NULL

4. 在单链表头部插入数据

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{// 申请新节点SLTNode* newnode = BuyLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

plist 本身就是 SLTNode* 类型的指针，且不论是头插还是尾插，只要涉及到要改变 plist 的指向或者节点中的数据时，那么就要传递 plist 指针的地址才可以，所以函数的形参部分就要用二级指针接收（*pphead == plist）

第一次头插时：将 newnode 的 next 指向 *pphead（因为第一次头插时的 *pphead 就是 NULL ，那么 newnode 就是尾节点，所以刚好让尾节点的 next 指向了 NULL）
最后将 *pphead 指向新节点 newnode ，这样就完成了在单链表的头部插入数据

多次头插时：*pphead 就是原链表头节点的地址，直接将要头插的新节点 newnode 的 next 指向 *pphead ，这样就完成了头插和节点的链接，最后再将 *pphead 指向新的头节点 newnode

测试代码：

5. 在单链表尾部插入数据

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{// 申请新节点SLTNode* newnode = BuyLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;// 找到尾节点while (cur->next != NULL)cur = cur->next;cur->next = newnode;}
}

尾插数据要分两种情况看待：

当单链表为空链表时：那么直接将 *pphead 指向 newnode 即可

当单链表不为空链表时：先要找到尾节点，再把尾节点的 next 指向 newnode ，这样就实现了在单链表尾部插入数据

测试代码：

6. 在单链表头部删除数据

void SLTPopFront(SLTNode** pphead)
{// 当链表为空时if (*pphead == NULL){printf("无数据可删除\n");return;}SLTNode* cur = *pphead;*pphead = cur->next;free(cur);
}

头删数据要分两种情况看待：

当单链表为空时：没有数据可删除，提醒用户后返回即可

当单链表不为空时（一个或多个节点时）：利用 cur 指针记录头节点的地址也就是 *pphead ，cur->next 就是第二个节点的地址，直接赋值给 *pphead 即可，这样就改变了 plist 的指向，最后再用 free 把头节点释放掉（以上代码逻辑在只有一个节点时同样适用）

测试代码：

7. 在单链表尾部删除数据

void SLTPopBack(SLTNode** pphead)
{// 当前链表为空时if (*pphead == NULL){printf("无数据可删除\n");return;}// 当只有一个节点时if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else // 有多个节点时{SLTNode* cur = *pphead;// 找到尾节点的前一个节点while (cur->next->next != NULL)cur = cur->next;free(cur->next);cur->next = NULL;}
}

尾删数据要分三种情况看待：

当单链表为空时：没有数据可删除，同样提醒用户后返回即可

当单链表只有一个节点时：直接 free 当前节点，也就是 *pphead 指向的节点，再置空

当单链表有多个节点时：利用 cur->next->next != NULL 找到尾节点的前一个节点，找到后，那么 cur->next 就是尾节点的地址，直接 ferr 再置空即可

测试代码：

8. 在单链表中查找指定的节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

根据数据找指定的节点，数据 X 和每个节点依次比较，找到了指定节点就返回指定节点的地址（指针），没有找到就返回 NULL 

且 SLTFind 函数同时具备读和写的功能，因为返回的是一个节点的指针，所以可以接收返回值对节点的数据进行修改

9. 在单链表中 pos 节点插入数据

1. 在 pos 节点之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{// pos 节点会通过 SLTFind 函数查找，所以要确保 pos 节点的存在assert(pos != NULL);// 当第一个节点就是 pos 时if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* cur = *pphead;SLTNode* prev = NULL;// 找到 pos 节点的前一个节点while (cur->next != pos)cur = cur->next;prev = cur;// 申请新节点SLTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->next = pos;}
}

当第一个节点就是 pos 时：在 pos 之前插入就是头插的逻辑，直接调用 SLTPushFont 函数即可

其他情况：先要从头找到 pos 节点的前一个节点 prev，再通过各自的 next 串联起来

测试代码：

 2. 在 pos 节点之后插入

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{// pos 节点会通过 SLTFind 函数查找，所以要确保 pos 节点的存在assert(pos != NULL);// 找到 pos 节点的下一个节点SLTNode* nextnode = pos->next;// 申请新节点SLTNode* newnode = BuyLTNode(x);pos->next = newnode;newnode->next = nextnode;
}

需要注意先后顺序，要先找到 pos 节点的下一个节点 nextnode，再通过各自的 next 串联起来

测试代码：

10. 在单链表中 pos 节点删除数据

1. 删除 pos 节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos != NULL);/// 当第一个节点就是 pos 时if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;SLTNode* prev = NULL;// 找到 pos 节点的前一个节点while (cur->next != pos)cur = cur->next;prev = cur;prev->next = pos->next;free(pos);}
}

当第一个节点就是 pos 时：删除 pos 节点就是头删的逻辑，调用 SLTPopFront 函数即可

其他情况：先要找到 pos 节点的前一个节点 prev ，再和 pos 的下一个节点通过 next 串联

测试代码： 

2. 删除 pos 节点后一个节点

void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos != NULL);// 当 pos 是最后一个节点时if (pos->next == NULL){printf("无数据可删除\n");return;}else{// 找到 pos 节点的下两个节点SLTNode* nextnode = pos->next->next;free(pos->next);pos->next = nextnode;}
}

pos 节点为最后一个节点时：那么 pos 后就没有节点，提醒用户后返回即可

其他情况：先找到 pos 节点的后两个节点 nextnode，在释放 pos 节点的下一个节点，最后再将 pos 节点和 nextnode 节点串联

测试代码：

11. 释放单链表的所有节点

void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;SLTNode* prev = NULL;while (cur != NULL){prev = cur->next;free(cur);cur = prev;}
}

释放当前 cur 节点前要先存储下一个节点的地址到 prev ，否则释放了当前 cur 节点就找不到下一个节点了

SList.h 的所有代码

#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 SLTPushFront(SLTNode** pphead, SLTDataType x);// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);// 头删
void SLTPopFront(SLTNode** pphead);// 尾删
void SLTPopBack(SLTNode** pphead);// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// pos位置插入（在 pos 之前插入）
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// pos位置插入（在 pos 之后插入）
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);// pos位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);// 释放
void SLTDestroy(SLTNode** pphead);

SList.c 的所有代码

#include"SList.h"// 打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;// 当前单链表中无数据时if (cur == NULL){printf("当前链表无数据\n");return;}while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}// 创建节点
static SLTNode* BuyLTNode(SLTDataType x)
{// 开辟节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));// 判断是否开辟成功if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{// 申请新节点SLTNode* newnode = BuyLTNode(x);newnode->next = *pphead;*pphead = newnode;
}// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{// 申请新节点SLTNode* newnode = BuyLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;// 找到尾节点while (cur->next != NULL)cur = cur->next;cur->next = newnode;}
}
// 头删
void SLTPopFront(SLTNode** pphead)
{// 当前链表为空时if (*pphead == NULL){printf("无数据可删除\n");return;}SLTNode* cur = *pphead;*pphead = cur->next;free(cur);
}// 尾删
void SLTPopBack(SLTNode** pphead)
{// 当前链表为空时if (*pphead == NULL){printf("无数据可删除\n");return;}// 当只有一个节点时if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else // 有多个节点时{SLTNode* cur = *pphead;// 找到尾节点的前一个节点while (cur->next->next != NULL)cur = cur->next;free(cur->next);cur->next = NULL;}
}// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}// 任意位置插入（在 pos 之前插入）
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{// pos 节点会通过 SLTFind 函数查找，所以要确保 pos 节点的存在assert(pos != NULL);// 当第一个节点就是 pos 时if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* cur = *pphead;SLTNode* prev = NULL;// 找到 pos 节点的前一个节点while (cur->next != pos)cur = cur->next;prev = cur;// 申请新节点SLTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->next = pos;}
}// 任意位置插入（在 pos 之后插入）
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{// pos 节点会通过 SLTFind 函数查找，所以要确保 pos 节点的存在assert(pos != NULL);// 找到 pos 节点的下一个节点SLTNode* nextnode = pos->next;// 申请新节点SLTNode* newnode = BuyLTNode(x);pos->next = newnode;newnode->next = nextnode;
}// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos != NULL);/// 当第一个节点就是 pos 时if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;SLTNode* prev = NULL;// 找到 pos 节点的前一个节点while (cur->next != pos)cur = cur->next;prev = cur;prev->next = pos->next;free(pos);}
}// pos位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos != NULL);// 当 pos 是最后一个节点时if (pos->next == NULL){printf("无数据可删除\n");return;}else{// 找到 pos 节点的下两个节点SLTNode* nextnode = pos->next->next;free(pos->next);pos->next = nextnode;}
}// 释放
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;SLTNode* prev = NULL;while (cur != NULL){prev = cur->next;free(cur);cur = prev;}
}

相关文章：

  • Linux基础命令lsblk详解
  • vue限定类型上传文件 最简单实践（单个可文件、可图片）
  • Hive数仓操作（五）
  • STM32--GPIO点亮LED灯（手把手，超详细）
  • @antv/x6 动态的修改attr与prop，以及动态改变节点的大小
  • 2024年_ChatGPT 及类似的人工智能技术带来的影响与改变 怎样利用 ChatGPT 提高学习效率
  • 【JAVA源码授权】
  • 计算机毕业设计Hadoop+Spark知识图谱美团美食推荐系统 美团餐厅推荐系统 美团推荐系统 美食价格预测 美团爬虫 美食数据分析 美食可视化大屏
  • ​IAR全面支持国科环宇AS32X系列RISC-V车规MCU
  • Spring Boot CLI命令行工具
  • Java中的PriorityQueue详解
  • 爬虫库是什么？是ip吗
  • 分享国产RISC-V单片机通用
  • 【MySQL】视图、用户和权限管理
  • 每一个云手机的ip是独立的吗
  • [PHP内核探索]PHP中的哈希表
  • 【mysql】环境安装、服务启动、密码设置
  • Android单元测试 - 几个重要问题
  • Django 博客开发教程 8 - 博客文章详情页
  • Docker 笔记（2）：Dockerfile
  • Github访问慢解决办法
  • HTTP传输编码增加了传输量，只为解决这一个问题 | 实用 HTTP
  • JAVA并发编程--1.基础概念
  • java概述
  • k8s如何管理Pod
  • PAT A1092
  • TiDB 源码阅读系列文章（十）Chunk 和执行框架简介
  • 多线程事务回滚
  • 番外篇1：在Windows环境下安装JDK
  • 函数式编程与面向对象编程[4]:Scala的类型关联Type Alias
  • 前端之Sass/Scss实战笔记
  • 悄悄地说一个bug
  • 如何利用MongoDB打造TOP榜小程序
  • 设计模式（12）迭代器模式（讲解+应用）
  • 再次简单明了总结flex布局，一看就懂...
  • HanLP分词命名实体提取详解
  • 仓管云——企业云erp功能有哪些？
  • # Redis 入门到精通（七）-- redis 删除策略
  • ### RabbitMQ五种工作模式：
  • #{}和${}的区别是什么 -- java面试
  • #pragma once
  • $(selector).each()和$.each()的区别
  • （aiohttp-asyncio-FFmpeg-Docker-SRS）实现异步摄像头转码服务器
  • (cljs/run-at (JSVM. :browser) 搭建刚好可用的开发环境!)
  • （pytorch进阶之路）CLIP模型 实现图像多模态检索任务
  • （第9篇）大数据的的超级应用——数据挖掘-推荐系统
  • （力扣）1314.矩阵区域和
  • (转)scrum常见工具列表
  • (转载)在C#用WM_COPYDATA消息来实现两个进程之间传递数据
  • .NET Core 中的路径问题
  • .NET Framework 的 bug？try-catch-when 中如果 when 语句抛出异常，程序将彻底崩溃
  • .net 反编译_.net反编译的相关问题
  • .net企业级架构实战之7——Spring.net整合Asp.net mvc
  • .vimrc php,修改home目录下的.vimrc文件，vim配置php高亮显示
  • // an array of int