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

链表的实现

ds 2025/7/3 11:47:09

一、链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表

中的指针链接次序实现的 。

链表的结构跟或车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

车厢是独立存在的，且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁上的状 态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放⼀把下⼀节车厢的钥匙。

在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置？

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

结合前，面学到的结构体知识，我们可以给出每个节点对应的结构体代码：

假设当前保存的节点为整型:

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

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

当我们想要从第⼀个节点走到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。

补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、节点⼀般是从堆上申请的

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

二、单链表的实现

2.1 单链表的数据结构

代码实现如下：

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

2.2 单链表的打印SLTPrint

代码实现如下：

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

2.3 尾插SLTPushBack

代码实现如下：

SLTNode* BuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL) {//如果头结点是空*pphead = newnode;}else {//链表中有节点，开始找尾节点SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}
}

2.4 尾删SLTPopBack

代码实现如下：

void SLTPopBack(SLTNode** pphead) {assert(pphead);assert(*pphead);if ((*pphead)->next == NULL) {//链表中只有一个节点free(*pphead);*pphead = NULL;}else {//链表中的节点大于1个,就需要找尾节点和尾节点的前一个SLTNode* tail = *pphead;SLTNode* prevtail = *pphead;while (tail->next != NULL) {prevtail = tail;tail = tail->next;}prevtail->next = NULL;free(tail);}
}

2.5 头插SLTPushFront

代码实现如下：

SLTNode* BuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL) {*pphead = newnode;}else {newnode->next = *pphead;*pphead = newnode;}
}

2.6 头删SLTPopFront

代码实现如下：

void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);if ((*pphead)->next == NULL) {//链表中只有一个节点free(*pphead);*pphead = NULL;}else {//链表中的节点大于1个,就需要保存头结点的下一个节点，把头结点释放，然很头结点指向下一个节点。SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}

2.7 查找SLTFind

代码实现如下：

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

2.8 在指定位置之前插入SLTInsert

代码实现如下：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(*pphead);assert(pos);SLTNode* newnode = BuyNode(x);if (pos == *pphead) {//如果在第一个位置之前插入数据，就需要改变头指针newnode->next = pos;*pphead = newnode;}else {//如果不是在第一个位置之前插入数据，就需要找pos的前一个节点SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

2.9 在指定位置之后插入SLTInsertAfter

代码实现如下：

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {SLTNode* newnode = BuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.10 删除SLTErase

代码实现如下：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead) {//如果删除的是第一个节点，就需要改变头指针*pphead = pos->next;free(pos);}else {//如果删除的不是是第一个节点，就需要找它的前一个节点SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}
}

2.11 删除指定位置后的一个节点SLTEraseAfter

代码实现如下：

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos节点不能是最后一个SLTNode* del = pos->next;pos->next = pos->next->next;free(del);
}

2.12 销毁SListDesTroy

代码实现如下：

//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead);SLTNode* cur = *pphead;while (cur != NULL) {SLTNode* next = cur->next;free(cur);cur = next;}
}

三、链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

 

四、代码

4.1 ListNode.h

#pragma once
#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);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

4.2 ListNode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListNode.h"
//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead);SLTNode* cur = *pphead;while (cur != NULL) {SLTNode* next = cur->next;free(cur);cur = next;}
}
//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
SLTNode* BuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL) {//如果头结点是空*pphead = newnode;}else {//链表中有节点，开始找尾节点SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL) {*pphead = newnode;}else {newnode->next = *pphead;*pphead = newnode;}
}
void SLTPopBack(SLTNode** pphead) {assert(pphead);assert(*pphead);if ((*pphead)->next == NULL) {//链表中只有一个节点free(*pphead);*pphead = NULL;}else {//链表中的节点大于1个,就需要找尾节点和尾节点的前一个SLTNode* tail = *pphead;SLTNode* prevtail = *pphead;while (tail->next != NULL) {prevtail = tail;tail = tail->next;}prevtail->next = NULL;free(tail);}
}
void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);if ((*pphead)->next == NULL) {//链表中只有一个节点free(*pphead);*pphead = NULL;}else {//链表中的节点大于1个,就需要保存头结点的下一个节点，把头结点释放，然很头结点指向下一个节点。SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur != NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(*pphead);assert(pos);SLTNode* newnode = BuyNode(x);if (pos == *pphead) {//如果在第一个位置之前插入数据，就需要改变头指针newnode->next = pos;*pphead = newnode;}else {//如果不是在第一个位置之前插入数据，就需要找pos的前一个节点SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead) {//如果删除的是第一个节点，就需要改变头指针*pphead = pos->next;free(pos);}else {//如果删除的不是是第一个节点，就需要找它的前一个节点SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {SLTNode* newnode = BuyNode(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 = pos->next->next;free(del);
}

4.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListNode.h"
void test01()//测试尾插
{SLTNode* sl=NULL;SLTPushBack(&sl, 1);SLTPushBack(&sl, 2);SLTPushBack(&sl, 3);SLTPushBack(&sl, 4);SLTPushBack(&sl, 5);SLTPrint(sl);
}
void test02()//测试尾删
{SLTNode* sl = NULL;SLTPushBack(&sl, 1);SLTPushBack(&sl, 2);SLTPushBack(&sl, 3);SLTPushBack(&sl, 4);SLTPushBack(&sl, 5);SLTPrint(sl);SLTPopBack(&sl);SLTPrint(sl);SLTPopBack(&sl);SLTPrint(sl);SLTPopBack(&sl);SLTPrint(sl);SLTPopBack(&sl);SLTPrint(sl);SLTPopBack(&sl);SLTPrint(sl);}
void test03()//测试头插
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTPrint(sl);}
void test04()//测试头删
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTPrint(sl);SLTPopFront(&sl);SLTPrint(sl);SLTPopFront(&sl);SLTPrint(sl);SLTPopFront(&sl);SLTPrint(sl);SLTPopFront(&sl);SLTPrint(sl);SLTPopFront(&sl);SLTPrint(sl);}
void test05()//测试查找
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTNode* ret = SLTFind(sl, 4);if (ret == NULL) {printf("找不到\n");}else {printf("找到了\n");}SLTNode* ret1 = SLTFind(sl, 10);if (ret1 == NULL) {printf("找不到\n");}else {printf("找到了\n");}
}void test06()//测试在指定位置之前插入数据
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTPrint(sl);SLTNode* ret = SLTFind(sl, 1);SLTInsert(&sl, ret, 99);//在最后一个位置插入数据SLTPrint(sl);ret = SLTFind(sl, 5);SLTInsert(&sl, ret, 54);//在第一个位置插入数据SLTPrint(sl);ret = SLTFind(sl, 3);SLTInsert(&sl, ret, 34);//在第中间位置插入数据SLTPrint(sl);}
void test07()//测试删除pos节点
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTPrint(sl);SLTNode* ret = SLTFind(sl, 5);SLTErase(&sl, ret);//在第一个位置删除数据SLTPrint(sl);ret = SLTFind(sl, 1);SLTErase(&sl, ret);//在最后一个位置删除数据SLTPrint(sl);ret = SLTFind(sl, 3);SLTErase(&sl, ret);//在中间位置删除数据SLTPrint(sl);}
void test08()//测试在指定位置之后插入数据
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTNode* ret = SLTFind(sl, 5);SLTInsertAfter(ret, 90);//在第一个位置之后插入数据SLTPrint(sl);ret = SLTFind(sl, 1);SLTInsertAfter(ret, 60);//在最后一个位置之后插入数据SLTPrint(sl);ret = SLTFind(sl, 3);SLTInsertAfter(ret, 70);//在中间位置插入数据SLTPrint(sl);}
void test09()//测试删除pos之后的节点
{SLTNode* sl = NULL;SLTPushFront(&sl, 1);SLTPushFront(&sl, 2);SLTPushFront(&sl, 3);SLTPushFront(&sl, 4);SLTPushFront(&sl, 5);SLTPrint(sl);SLTNode* ret = SLTFind(sl, 5);SLTEraseAfter(ret);//删除第一个节点之后的那一个节点SLTPrint(sl);//ret = SLTFind(sl, 1);//SLTEraseAfter(ret);//删除最后一个节点后的节点，会报断言错误//SLTPrint(sl);}
int main() {//test01();//测试尾插//test02();//测试尾删//test03();//测试头插//test04();//测试头删//test05();//测试查找//test06();//测试在指定位置之前插入数据//test07();//测试删除pos节点//test08();//测试在指定位置之后插入数据//test09();//测试删除pos之后的节点return 0;
}

http://www.xdnf.cn/news/14943.html

相关文章：

  • Flink-1.19.0源码详解5-JobGraph生成-前篇
  • Node.js-http模块
  • Appium 简介
  • 大语言模型：是逐字生成还是一次多词？
  • GO Web 框架 Gin 完全解析与实践
  • 【NLP第二期中文分词技术：规则、统计与混合方法全解】
  • 笨方法学python-习题12
  • Disruptor架构哲学
  • 结构体实战：用Rust编写矩形面积计算器
  • MySQL 中 InnoDB 存储引擎与 MyISAM 存储引擎的区别是什么？
  • 8.Docker镜像讲解
  • 阿里巴巴 Qwen 系列大模型发展时间线与主要特性
  • 数字图像处理学习笔记
  • C#.Net筑基-优雅LINQ的查询艺术
  • 算法-每日一题（DAY12）最长和谐子序列
  • TypeScript 安装使用教程
  • 电子面单系统开发全解析
  • 深度学习进阶：自然语言处理的推荐点评
  • 杭州来未来科技 Java 实习面经
  • STM32——代码开发顺序
  • 模型部署与推理--利用python版本onnxruntime模型部署与推理
  • 【仿muduo库实现并发服务器】Acceptor模块
  • 微信小程序21~30
  • grom使用mysql快速上手
  • nginx配置websocket
  • 如何在电脑上完全抹去历史记录
  • Ubuntu 20.04 下 OpenVINO 2024 安装与配置
  • 与后端现场联调mock数据
  • 内网ubuntu系统安装mysql
  • 直播 APP 开发需要多少成本