数据结构之单链表

🕗 发布于 2024-11-06 19:22 数据结构 开发语言 笔记

前言：上一篇文章我们了解到顺序表，这一次来看另一种线性表-------单链表。

1. 单链表的概念

单链表，想必很多人会感到陌生吧。那么，到底什么是单链表呢？先了解清楚单链表的概念及特性，才能够更好的实现单链表。

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

单链表就像火车车厢一样，每节车厢都通过链条进行链接。

在这里插入图片描述

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

在这里插入图片描述

不过，在数据结构里“车厢”有一个专属名词-----节点（结点）。与顺序表不同的是，链表里的每节车厢都是独立申请下来的空间，我们称之为节点。

节点主要由两部分组成，当前节点要保存的数据和保存下一个节点的地址。

链表的性质：

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

2.节点一般是从堆上申请的。

3.从堆上申请出来的空间可能连续也可能不连续。

现在我们已经了解到了链表的结构，接下来要该如何设计链表呢？在节点里需要保存数据及保存下一个节点的地址。这是两个不同的数据类型，因此使用结构体，也便于代码的可读性与可维护性。

2. 单链表的实现

2.1 单链表的定义

//链表存储数据类型
typedef int SLDataType;
//单链表的定义
typedef struct SinglyLinkedList
{
SLDataType data;//保存的数据
struct SinglyLinkedList* next;//存储下一个节点的地址
}SList;

2.2 单链表的接口

//打印单链表
void DisplaySList(SList* phead);

//尾插
void SListPushBack(SList** pphead, SLDataType x);

//尾删
void SListPopBack(SList** pphead);

//头插
void SListPushFront(SList** pphead, SLDataType x);

//头删
void SListPopFront(SList** pphead);

//单链表查找
SList* SListFind(SList* phead, SLDataType x);

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x);

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos);

//销毁链表
void SListDestroy(SList** pphead);

2.2.1 单链表尾插

//尾插
void SListPushBack(SList** pphead, SLDataType x)
{
assert(pphead);
//开辟一个节点大小的空间，开辟失败就退出程序。
/*SList* newnode = (SList*)malloc(sizeof(SList));
if (NULL == newnode)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;*/

//SListBuyNewNode是一个创建新节点的函数，不仅仅在尾插
//中需要创建节点，在头插中也需要。因此为了避免代码冗余以
//及代码的可读性与可维护性，将创建新节点的功能封装成一个
//函数来实现。
SList* newnode = SListBuyNewNode(pphead, x);
//单链表为空的情况
if (NULL == *pphead)
{
//plist为空，让plist指向newnode,指向链表的头结点
*pphead = newnode;
}
else
{
SList* tail = *pphead;
//找尾节点
while (NULL != tail->next)
{
tail = tail->next;
}
//连接新的节点
tail->next = newnode;
}
 }

在这里插入图片描述

尾插数据需要一个节点大小的空间，用来存储数据及保存下一个节点的地址。因此首先申请一块节点大小的空间。

接下来又分两种情况：

1.plist指向空，需要让plist指向链表头结点。

2.plist不指向空，新申请的结点直接连接在链表尾节点的后面。

在这里插入图片描述

assert(pphead);
pphead保存的是一级指针变量plist的地址，所以pphead一定不为
空。对pphead进行断言，是为了防止参数传输错误。

还有一个问题，不知道大家发现没有。这里为什么要用二级指针呢？答案很简单。plist是一个结构体指针，在尾插中有可能要改变plist，因此要用二级指针。这涉及到了实参与形参的关系。

2.2.2 创建新节点

//创建新节点
SList* SListBuyNewNode(SList** pphead,SLDataType x)
{
SList* newnode = (SList*)malloc(sizeof(SList));
if (NULL == newnode)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}

2.2.3 打印单链表

//打印单链表
//这里也可以用二级指针来接收，保持代码风格的一致性
void DisplaySList(SList* phead)
{
SList* cur = phead;
while (NULL != cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}

SList* cur=phead,此时cur指向了链表的头结点，只要cur不等于
NULL，就打印链表节点里的数据。然后更新cur,指向下一个节点。

2.2.4 单链表尾删

//尾删
void SListPopBack(SList** pphead)
{
assert(pphead);
//单链表为空的情况
assert(*pphead);
//单链表至少有一个节点
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
}
else
{
SList* tail = *pphead;
SList* prev = NULL;
//找尾节点
while (NULL != tail->next)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
//释放尾节点的空间
free(tail);
tail = NULL;
}
}

这里包含了3种情况：

1.plist指向空，代表没有链表（没有数据可以删除）

2.有多个节点

3.只有一个节点

画图分析：

在这里插入图片描述

1.尾删节点首先将尾节点的空间还给操作系统，然后再让尾节点的前
一个节点指向空（防止野指针的出现）
2.一直尾删，直到剩下一个节点。这个时候再尾删就要改变plist指针
了，因此尾删也需要二级指针
3.在尾删节点的时候，需要找到尾节点才能删除，由于单链表具有单
向性，因此还需要一个前驱指针，用来记录尾节点的前一个节点。

2.2.5 单链表头插

//头插
void SListPushFront(SList** pphead, SLDataType x)
{
assert(pphead);
//创建新节点
SList* newnode = SListBuyNewNode(pphead, x);
//新节点成为链表的头结点
newnode->next = *pphead;
//plist指向链表的头结点
*pphead = newnode;
}

在这里插入图片描述

注意：一定要先让新节点的next保存当前plist的值，再更新plist，指向新的头结点。

2.2.6 单链表头删

//头删
void SListPopFront(SList** pphead)
{
assert(pphead);
//单链表为空的情况
assert(*pphead);
//记录当前头结点
SList* cur = *pphead;
//更新plist
*pphead = (*pphead)->next;
//释放头结点的空间
free(cur);
cur = NULL;
}

在这里插入图片描述

注意：
1.先让plist指向当前头结点的下一个节点，如果先删除当前头
结点，就找不到下一个节点了。
2.释放当前头结点的空间。
2.plist为空，说明链表为空，没有数据删除。

2.2.7 单链表查找

//单链表查找
SList* SListFind(SList* phead, SLDataType x)
{
//单链表为空不查找
assert(phead);

SList* cur = phead;
while (NULL != cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}

从头结点开始遍历进行查找，找到了就返回该节点的地址，否则返回NULL。

2.2.8 从指定位置之后开始插入数据

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)
{
assert(pphead);
//创建新节点
SList* newnode = SListBuyNewNode(pphead, x);
//链表为空
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SList* cur = *pphead;
//找pos位置
while (NULL != cur)
{
if (cur == pos)
{
newnode->next = cur->next;
cur->next = newnode;
}
cur = cur->next;
}
}
}

在这里插入图片描述

从头结点开始遍历找pos位置，找到pos位置将新节点插入进去。

注意：让新节点的next保存pos位置下一个节点的地址，再让pos位置的节点的next保存新节点的地址。

2.2.9 从指定位置之前插入数据

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x)
{
assert(pphead);
//创建新节点
SList* newnode = SListBuyNewNode(pphead, x);
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SList* cur = *pphead;
//记录pos位置前一个节点
SList* prev = NULL;
while (NULL != cur)
{
if (cur == pos)
{
newnode->next = prev->next;
prev->next = newnode;
}
prev = cur;
cur = cur->next;
}
}
}

在这里插入图片描述

从头结点开始遍历找pos位置，找到pos位置，让pos位置的前一个节点的next保存新节点的地址，新节点的next保存pos位置节点的地址。

2.2.10 从指定位置删除数据

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos)
{
assert(pphead);
//单链表为空
assert(*pphead);

SList* cur = *pphead;
//找pos位置
while (NULL != cur->next)
{
if (cur->next == pos)
{
cur->next = pos->next;
free(pos);
pos = NULL;
}
cur = cur->next;
}
}

在这里插入图片描述

单链表不能为空，为空说明没有数据可以删除。找到pos位置，让pos位置的前一个节点的next指向pos位置节点的下一个节点，然后再释放掉pos位置的节点。

2.2.11 销毁链表

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

从头结点开始遍历，先让cur指向头结点的下一个节点，再释放掉当前
的头结点。最后再让*pphead=NULL。在循环过程中，*pphead的指
向一直没有发生改变，销毁链表时，也要让plist指向空，防止出现野
指针。

3. 单链表完整代码的实现

SList.h的实现

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

typedef int SLDataType;

typedef struct SinglyLinkedList
{
SLDataType data;
struct SinglyLinkedList* next;//存储下一个节点的地址
}SList;


//打印单链表
void DisplaySList(SList* phead);

//尾插
void SListPushBack(SList** pphead, SLDataType x);

//尾删
void SListPopBack(SList** pphead);

//头插
void SListPushFront(SList** pphead, SLDataType x);

//头删
void SListPopFront(SList** pphead);

//单链表查找
SList* SListFind(SList* phead, SLDataType x);

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x);

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos);

//销毁链表
void SListDestroy(SList** pphead);

SList.c实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

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

//创建新节点
SList* SListBuyNewNode(SList** pphead,SLDataType x)
{
SList* newnode = (SList*)malloc(sizeof(SList));
if (NULL == newnode)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}

//尾插
void SListPushBack(SList** pphead, SLDataType x)
{
assert(pphead);
/*SList* newnode = (SList*)malloc(sizeof(SList));
if (NULL == newnode)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;*/
SList* newnode = SListBuyNewNode(pphead, x);
//单链表为空的情况
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SList* tail = *pphead;
while (NULL != tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
 }

//尾删
void SListPopBack(SList** pphead)
{
assert(pphead);
//单链表为空的情况
assert(*pphead);
//单链表至少有一个节点
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
}
else
{
SList* tail = *pphead;
SList* prev = NULL;
while (NULL != tail->next)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}

//头插
void SListPushFront(SList** pphead, SLDataType x)
{
assert(pphead);
/*SList* newnode = (SList*)malloc(sizeof(SList));
if (NULL == newnode)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;*/
SList* newnode = SListBuyNewNode(pphead, x);
//至少有一个节点
/*if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}*/

newnode->next = *pphead;
*pphead = newnode;
}

//头删
void SListPopFront(SList** pphead)
{
assert(pphead);
//单链表为空的情况
assert(*pphead);

SList* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);
cur = NULL;
}

//单链表查找
SList* SListFind(SList* phead, SLDataType x)
{
//单链表为空不查找
assert(phead);

SList* cur = phead;
while (NULL != cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)
{
assert(pphead);
SList* newnode = SListBuyNewNode(pphead, x);
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SList* cur = *pphead;
while (NULL != cur)
{
if (cur == pos)
{
newnode->next = cur->next;
cur->next = newnode;
}
cur = cur->next;
}
}
}

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x)
{
assert(pphead);
SList* newnode = SListBuyNewNode(pphead, x);
if (NULL == *pphead)
{
*pphead = newnode;
}
else
{
SList* cur = *pphead;
SList* prev = NULL;
while (NULL != cur)
{
if (cur == pos)
{
newnode->next = prev->next;
prev->next = newnode;
}
prev = cur;
cur = cur->next;
}
}
}

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos)
{
assert(pphead);
//单链表为空
assert(*pphead);

SList* cur = *pphead;
while (NULL != cur->next)
{
if (cur->next == pos)
{
cur->next = pos->next;
free(pos);
pos = NULL;
}
cur = cur->next;
}
}

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

test.c的实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void TestSList1()
{
SList* plist = NULL;

SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);

DisplaySList(plist);

SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);

DisplaySList(plist);

}

void TestSList2()
{
SList* plist = NULL;

SListPushFront(&plist, 10);
SListPushFront(&plist, 20);
SListPushFront(&plist, 30);
SListPushFront(&plist, 40);

DisplaySList(plist);

SListPopFront(&plist);

DisplaySList(plist);

SList* pos = SListFind(plist, 50);
if (NULL != pos)
{
printf("%d\n", pos->data);
}
else
{
printf("找不到\n");
}

}

void TestSList3()
{
SList* plist = NULL;

SListInsertAfter(&plist, NULL, 10);

DisplaySList(plist);

SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);

SList* pos = SListFind(plist, 4);

SListInsertAfter(&plist, pos, 20);

DisplaySList(plist);

pos = SListFind(plist, 2);

SListInsert(&plist, pos, 30);

DisplaySList(plist);

pos = SListFind(plist, 3);

SListErase(&plist, pos);

DisplaySList(plist);

SListDestroy(&plist);

}

int main()
{
//TestSList1();

//TestSList2();

TestSList3();

return 0;
}

原文地址：https://blog.csdn.net/2402_84532723/article/details/143448727

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

上一篇：asp.net文件防盗链
下一篇：qt QAbstractItemModel详解

Linux系统下svn新建目录
Linux安装svn自行查找。
阅读更多2024-11-14
Scala的不可变Map常用操作
/3.1 get方法：输入key，如果找到，就返回包装数据，如果没有找到，就返回None。val map1 = Map("鄂"->"湖北省","
阅读更多2024-11-14
mqtt学习笔记（一）
mqtt相关笔记（一）之mqtt初探，以提出、解决问题的方式来逐步学习
阅读更多2024-11-14
Ken和Bwk趣说UNIX
[肯汤普森和布莱恩(AWK作者之一)趣说UNIX](https://www.bilibili.com/video/BV1nP411t7gt/ “肯汤普森和布莱恩(AWK作者之一 “肯汤普森和布莱恩(A
阅读更多2024-11-14
【CentOS】中的Firewalld：全面介绍与实战应用（上）
本文深入探讨了CentOS操作系统中Firewalld防火墙的全面功能与实战应用。首先，文章概述了Firewalld的基本概念，强调了它在现代Linux系统中作为动态管理防火墙规则的重要工具的地位。与
阅读更多2024-11-14
新手小白学习docker第七弹------安装redis集群大厂面试
新手小白学习docker第七弹----安装redis集群大厂面试
阅读更多2024-11-14
/// ts中的三斜线指令 | 前端
包），你需要在你的项目中以某种方式告诉TypeScript编译器这些类型定义的存在。三斜线指令是一种在单个文件中这样做的方式，虽然在实际项目中，更常见的是通过。1. 这行代码是TypeScript中
阅读更多2024-11-14
快速掌握——python类封装[私有属性方法]、继承【python进阶】(内附代码)
python类的封装【私有属性、私有方法、属性装饰器】类的继承
阅读更多2024-11-14
2024年5款大屏可视化工具多维分析对比
经过对市场上多款大屏可视化工具的深入研究和对比，强烈推荐FineVis作为您的首选。无论您是希望快速搭建大屏项目、展示复杂3D模型还是实现多屏适应和实时数据分析，FineVis都能满足您的需求。文章中
阅读更多2024-11-14
计算机网络-mac地址与ip地址的区别总结
mac地址在OSI模型中的第二层数据链路层工作，数据链路层基于mac地址进行转发数据帧【交换机基于mac地址表转发数据】ip地址在OSI模型中的第三层网络层工作，网络层基于ip地址转发报文【路由器
阅读更多2024-11-14

数据结构之单链表

1. 单链表的概念

2. 单链表的实现

2.1 单链表的定义

2.2 单链表的接口

2.2.1 单链表尾插

2.2.2 创建新节点

2.2.3 打印单链表

2.2.4 单链表尾删

2.2.5 单链表头插

2.2.6 单链表头删

2.2.7 单链表查找

2.2.8 从指定位置之后开始插入数据

2.2.9 从指定位置之前插入数据

2.2.10 从指定位置删除数据

2.2.11 销毁链表

3. 单链表完整代码的实现

相关文章