【数据结构实战】从零开始打造你的专属链表

🕗 发布于 2024-11-10 15:26 数据结构 链表 c语言 数据挖掘 机器学习

🏝️专栏：【数据结构实战篇】

🌅主页：f狐o狸x

本期我们接着上期的来，开始我们的链表环节

一、链表的概念及结构

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

我们可以看出：

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

2. 现实中，每一个节点都需要用malloc向堆栈申请

3. 申请出来的空间可能连续，也有可能是不连续的

二、链表的分类

实际中链表的结构非常多样，这里介绍几种类别

2.1 单向的或双向的

2.2 带头的或不带头的

带头的链表也被称为哨兵位

2.3 循环或非循环

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三、链表的实现

我们先实现单链表

typedef int SLDataType;

typedef struct SListNode
{
SLDataType data;
struct SList* next;
}SListNode;

先在头文件中声明好单链表

3.1 打印和动态申请一个结点

// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("\n");
}

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
if (newcode == NULL)
{
perror("SListPushBack::malloc");
return NULL;
}
newcode->next = NULL;
newcode->data = x;
return newcode;
}

3.2 尾插一个数

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
SListNode* newcode = BuySListNode(x);
//检查单链表是否为空
if (*pplist == NULL)
{
*pplist = newcode;
}
else
{
SListNode* tail = *pplist;
//找尾
while (tail->next)
{
tail = tail->next;
}
tail->next = newcode;
}
}

3.3 头插一个数

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
SListNode* NewCode = BuySListNode(x);
NewCode->next = *pplist;
*pplist = NewCode;
}

3.4 尾删一个数

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
//只有一个节点
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
//找尾
SListNode* tail = *pplist;
SListNode* prev = NULL;;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
//删除节点
free(tail);
tail = NULL;
prev->next = NULL;
}

}

也可以这样尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
//只有一个节点
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
找尾
//SListNode* tail = *pplist;
//SListNode* prev = NULL;;
//while (tail->next)
//{
//prev = tail;
//tail = tail->next;
//}
删除节点
//free(tail);
//tail = NULL;
//prev->next = NULL;

SListNode* tail = *pplist;
while (tail->next->next)
{
tail = tail->next;
}
//删除节点
free(tail->next);
tail->next = NULL;


}

}

3.5 头删一个数

// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* del = *pplist;
*pplist = (*pplist)->next;
free(del);
del = NULL;
}

3.6 查找数据

找到数据返回该节点的地址，找不到则返回null

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}

3.7 pos位置插入数据

利用查找函数找到数据的地址之后，在该节点前面插入数据

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
assert(pplist);
assert(pos);
//申请一个节点
SListNode* NewNode = BuySListNode(x);
//找到pos前的位置
SListNode* prev = NULL;
SListNode* cur = *pplist;
//第一个位置插入
if (pos == *pplist)
{
//直接头插
SListPushFront(pplist, x);
}
//其他位置插入
else
{
while (cur)
{
if (cur == pos)
{
prev->next = NewNode;
NewNode->next = cur;
}
prev = cur;
cur = cur->next;
}
}
}

3.8 pos位置删除数据

同理，先找到数据节点的位置，再删除

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
assert(pplist);
assert(pos);
//pos是第一个节点
if (pos == *pplist)
{
//直接头删
SListPopFront(pplist);
}
//其他位置删除
else
{
//找到pos前的位置
SListNode* prev = *pplist;
SListNode* cur = *pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
free(cur);
cur = NULL;
}
}

3.9 销毁链表

每次申请一个节点我们都用到了malloc开辟了一块空间，记得归还，有借有还，再借不难~

void DestorySList(SListNode** pplist)
{
SListNode* del = NULL;
while (*pplist)
{
del = *pplist;
*pplist = (*pplist)->next;
free(del);
del = NULL;
}
pplist = NULL;
}

四、链表代码

#define  _CRT_SECURE_NO_WARNINGS 1;

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos);


#define  _CRT_SECURE_NO_WARNINGS 1;

#include "SList.h"

// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("\n");
}

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
if (newcode == NULL)
{
perror("SListPushBack::malloc");
return NULL;
}
newcode->next = NULL;
newcode->data = x;
return newcode;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
SListNode* newcode = BuySListNode(x);
//检查单链表是否为空
if (*pplist == NULL)
{
*pplist = newcode;
}
else
{
SListNode* tail = *pplist;
//找尾
while (tail->next)
{
tail = tail->next;
}
tail->next = newcode;
}
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
SListNode* NewCode = BuySListNode(x);
NewCode->next = *pplist;
*pplist = NewCode;
 }

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
//只有一个节点
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
//多个节点

else
{
找尾
//SListNode* tail = *pplist;
//SListNode* prev = NULL;;
//while (tail->next)
//{
//prev = tail;
//tail = tail->next;
//}
删除节点
//free(tail);
//tail = NULL;
//prev->next = NULL;

SListNode* tail = *pplist;
while (tail->next->next)
{
tail = tail->next;
}
//删除节点
free(tail->next);
tail->next = NULL;


}

}

// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* del = *pplist;
*pplist = (*pplist)->next;
free(del);
del = NULL;
}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
assert(pplist);
assert(pos);
//申请一个节点
SListNode* NewNode = BuySListNode(x);
//找到pos前的位置
SListNode* prev = *pplist;
SListNode* cur = *pplist;
//第一个位置插入
if (pos == *pplist)
{
//直接头插
SListPushFront(pplist, x);
}
//其他位置插入
else
{
while (cur!=pos)
{
prev = cur;
cur = cur->next;
}
prev->next = NewNode;
NewNode->next = cur;
}
}

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
assert(pplist);
assert(pos);
//pos是第一个节点
if (pos == *pplist)
{
//直接头删
SListPopFront(pplist);
}
//其他位置删除
else
{
//找到pos前的位置
SListNode* prev = *pplist;
SListNode* cur = *pplist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
free(cur);
cur = NULL;
}
}

// 销毁链表
void DestorySList(SListNode** pplist)
{
SListNode* del = NULL;
while (*pplist)
{
del = *pplist;
*pplist = (*pplist)->next;
free(del);
del = NULL;
}
pplist = NULL;
}

坚持学习！当你快扛不住的时候，困难也快扛不住了！

留下你宝贵的三连叭~ QAQ

原文地址：https://blog.csdn.net/m0_74779094/article/details/143610349

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：使用软件要不要All In One
下一篇：带宽与下载速度的对应关系

[CUDA] cuda kernel开发记录
包括kernel的一些使用注意事项， launch_bound, __device__, debug排查技巧
阅读更多2024-11-16
【python】掌握 Flask：轻量级 Web 开发框架解析
路由是 Web 开发的基础，负责管理 URL 到视图函数的映射。在 Flask 中，路由定义非常简单，只需使用装饰器即可。这个代码段定义了一个路由，访问该路径时会返回 “Hello, Flask!通过
阅读更多2024-11-16
AI图片分析接口LiteAIServer摄像机实时接入分析平台未戴安全帽检测算法
随着人工智能技术的飞速发展，摄像机实时接入分析平台LiteAIServer工地未佩戴安全帽检测算法应运而生，为工地安全管理带来了革命性的变革。
阅读更多2024-11-16
2024新版pycharm如何切换anaconda虚拟环境
回归正题，导入项目后点击文件=>设置，找到解释器。不得不说这界面改的真不错，看着很舒服。另外在终端用指令切换也是可以的。添加解释器=>添加本地解释器。
阅读更多2024-11-16
计算机提示mfc140u.dll丢失的五种解决方法，了解mfc140u.dll错误的几种修复方法
当你尝试打开某些程序时，突然出现错误提示，告知你系统缺少 mfc140u.dll 文件，这可能让你感到困惑和无助。mfc140u.dll 是 Microsoft Foundation Class (M
阅读更多2024-11-16
k8s 中传递参数给docker容器
在 Kubernetes 中，可以通过多种方式将参数传递给 Dockerfile 或其运行的容器，常见的方式包括使用环境变量、命令行参数、配置文件等。
阅读更多2024-11-16
设计模式之工厂模式，但是宝可梦
作为一个细分了三个种类的设计模式，到底该如何取舍？比起直接new一个对象，使用对应模式的好处到底在哪？简单工厂模式：根据传入的参数决定产出的对象，可以隐藏一些创建的细节适用于需要根据条件创建不同对象的
阅读更多2024-11-16
【深度学习】wsl-ubuntu深度学习基本配置
这里注意一点，你换了源之后就最好不要开代理了，要不然搞不好下载失败，pip和conda都是。
阅读更多2024-11-16
nodejs和npm在gitbash中提示Not Found情况的解决办法
很多小伙伴学习了node以后，在cmd命令行中可以正常的获取node版本和npm版本，但是我们经常使用gitbash来管理git，这时候下载完gitbash后，在gitbash中输入node -v和n
阅读更多2024-11-16
判断子序列
给定一个长度为 n的整数序列 a1,a2,…,an以及一个长度为 m的整数序列 b1,b2,…,bm。请你判断 a序列是否为 b序列的子序列。子序列指序列的一部分项按原有次序排列而得的序列，例如序列
阅读更多2024-11-16

【数据结构实战】从零开始打造你的专属链表

一、链表的概念及结构

二、链表的分类

2.1 单向的或双向的

2.2 带头的或不带头的

2.3 循环或非循环

三、链表的实现

3.1 打印和动态申请一个结点

3.2 尾插一个数

3.3 头插一个数

3.4 尾删一个数

3.5 头删一个数

3.6 查找数据

3.7 pos位置插入数据

3.8 pos位置删除数据

3.9 销毁链表

四、链表代码

相关文章