[数据结构]单链表详解

embedded/2025/2/21 20:00:03/

目录

一、顺序表的问题及思考

二、单链表的实现

1.结构体内容的定义（typedef struct SListNode）

2.链表的打印（void SLTPrint(SLTNode* phead)）

​编辑3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）

3.1尾插错误示范：

3.2注意事项：

3.3修改后的尾插函数：

3.4打印结果：

 3.5知识梳理：

4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

6.链表的头删：（void SListPopFront(SLTNode** pphead)）

7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)）

8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）

9.在指定位置（pos）位置删除:（void SLTErase(SLTNode** pphead, SLTNode* pos)）

10.在指定位置（pos）后面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)）

11.链表的销毁：（void SLTDestroy(SLTNode* phead)）

三、单链表功能汇总

SList.h：

SList.c

test.c

一、顺序表的问题及思考

问题：
1. 中间 / 头部的插入删除，时间复杂度为 O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到
200 ，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。
上一个节点存着下一个结点的地址，每一个结点都是一个结构体

二、单链表的实现

1.结构体内容的定义（typedef struct SListNode）

#pragma once
#include <stdlib.h>
#include<stdio.h>
typedef int SLTDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* Next;//这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型//SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下
}SListNode;

2.链表的打印（void SLTPrint(SLTNode* phead)）

void SLTPrint(SLTNode* phead)
{//不需要assert断言，因为空的链表可以打印，只是没有数据而已SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->Next;//Next是下一个节点的地址}printf("NULL\n");
}

3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）

尾插本质：原尾结点中要存储新的尾结点的地址

3.1尾插错误示范：

void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");}newnode->data = x;newnode->Next = NULL;//找尾SLTNode* tail = phead;while (tail->Next != NULL){tail = tail->Next;}tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址
}

3.2注意事项：

test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}
int main()
{TestSList1();return 0;
}

这里phead的改变不会引起plist的改变，现在要改变的是SLTNode*，传进去SLTNode*根本不起作用，应该传SLTNode**

3.3修改后的尾插函数：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");}newnode->data = x;newnode->Next = NULL;if (*pphead == NULL){*pphead = newnode;}。else{//找尾SLTNode* tail = *pphead;while (tail->Next != NULL){tail = tail->Next;}tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，//tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址}}

3.4打印结果：

改变传过去的指针，那么就要传指针的地址，不改变就可以不传，所以print函数就没有传

 3.5知识梳理：

空链表可以打印，不用断言
空链表可以尾插，不用assert(*pphead),但是需要assert(pphead)
空链表可以头插，不用assert(*pphead),但是需要assert(pphead)把
空链表不能尾删，assert(pphead)和assert(*pphead)都需要，且pphead断言在*pphead之前

4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址*pphead = newnode;// 把头指针的地址改成新插入的指针的地址//这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
}

5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址*pphead = newnode;// 把头指针的地址改成新插入的指针的地址//这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
}
// 单链表的尾删
void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//1.只有一个结点//2.有多个结点if ((*pphead)->Next == NULL){free(*pphead);}//找尾SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->Next != NULL){prev = tail;//tail在每次往下走之前先把值留给prevtail = tail->Next;}free(tail);tail = NULL;prev->Next = NULL;}
为什么需要 prev？
单链表的单向性：单链表的每个节点只有 Next 指针，指向下一个节点，而没有指向前一个节点的指针。因此，当你找到尾节点（tail）时，无法直接知道它的前一个节点是谁。
删除尾节点的操作：
删除尾节点时，需要将尾节点的前一个节点（prev）的 Next 指针置为 NULL，以表示它是新的尾节点。如果不记录 prev，就无法修改前一个节点的 Next 指针，链表会处于一个不正确的状态。
释放尾节点的内存：
在释放尾节点的内存之前，必须确保前一个节点的 Next 指针已经被正确修改，否则会导致链表断裂或内存泄漏。
tail 和 prev 的关系：
tail 是用来遍历链表的指针，最终会指向尾节点（即要删除的节点）。
prev 是用来记录 tail 的前一个节点的指针。
tail = NULL 的作用：
tail = NULL 只是将局部变量 tail 置为 NULL，并不会影响链表的结构。
链表的结构是由节点的 Next 指针决定的，而不是由局部变量 tail 决定的
还有一种写法： 
SLTNode* tail = *pphead;while (tail->Next->Next != NULL){tail = tail->Next;}free(tail->Next);tail->Next = NULL;

6.链表的头删：（void SListPopFront(SLTNode** pphead)）

void SListPopFront(SLTNode** pphead)
{assert(*pphead != NULL);SLTNode* first = *pphead;*pphead = first->Next;free(first);first = NULL;
}

7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)）

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

8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）

这个函数一般配合SListFind函数一起使用

pos是第几个位置，如果pos=3，那么就是在2和3之间插入，但是：单链表不适合在前面插入，因为有了3的位置却找不到2的位置，需要从头开始遍历

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表）assert(pphead != NULL);assert(pos);if (pos == *pphead)//如果pos为头指针，那么类似于头插{SListPushFront(pphead, x);}else{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->Next != pos){prev = prev->Next;}SLTNode* newnode = BuySLTNode(x);prev->Next = newnode;newnode->Next = pos;}
}

9.在指定位置（pos）位置删除:（void SLTErase(SLTNode** pphead, SLTNode* pos)）

void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置
{assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead){SListPopFront(pos);}else{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->Next != pos){prev = prev->Next;}prev->Next = pos->Next;free(pos);//pos = NULL;这句话其实没用因为形参的改变不影响实参}
}

10.在指定位置（pos）后面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)）

void SLTInsertAfter(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);SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失pos->Next = pos->Next->Next;free(del);del = NULL;
}

11.链表的销毁：（void SLTDestroy(SLTNode* phead)）

注意用完这个函数后得把实参置空，因为这个函数里面phead=NULL这句话是没意义的，因为形参改变不会改变实参。或者用二级指针。

void SLTDestroy(SLTNode* phead)
{SLTNode* cur = phead;while (cur){SLTNode* tmp = cur->Next;free(cur);cur = tmp;}}

 //删除的经典错误：
        // 1.
        // free(cur);
        // cur=cur->Next;  野指针，cur的使用权被释放了，这行代码是非法操作
        // 2.
        // SLTNode *tmp=cur;
        // free(cur);
        // cur=tmp->Next;  和上面一样，tmp和cur指向的是同一块内存空间，如果释放就一起释放了
        //你退房了，把房卡给别人，别人也不能开酒店的房门，一样的道理
        //最好的方法不是保存cur而是保存cur的next

三、单链表功能汇总

SList.h：

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <errno.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; // 数据域struct SListNode* Next; // 这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型// SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下
} SLTNode;
// 打印链表
void SLTPrint(SLTNode* phead);
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
void SListPopBack(SLTNode** pphead);
// 单链表头删
void SListPopFront(SLTNode** pphead);
// 单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在pos后面插入
void SLTInsertAfter(SLTNode*pos, SLTDataType x);
//在pos位置后面删除
void SLTEraseAfter(SLTNode* pos);//链表的删除
void SLTDestroy(SLTNode* phead);

SList.c

#include "SList.h"
//创建插入元素的封装节点 函数
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");}newnode->data = x;newnode->Next = NULL;return newnode;
}
//打印
void SLTPrint(SLTNode* phead)
{//不需要assert断言，因为空的链表可以打印，只是没有数据而已SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->Next;//Next是下一个节点的地址}printf("NULL\n");
}
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* tail = *pphead;while (tail->Next != NULL){tail = tail->Next;}tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，//tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址}
}
// 单链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址*pphead = newnode;// 把头指针的地址改成新插入的指针的地址//这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
}
// 单链表的尾删
void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//1.只有一个结点//2.有多个结点if ((*pphead)->Next == NULL){free(*pphead);}//找尾SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->Next != NULL){prev = tail;//tail在每次往下走之前先把值留给prevtail = tail->Next;}free(tail);tail = NULL;prev->Next = NULL;}
// 单链表头删
void SListPopFront(SLTNode** pphead)
{assert(*pphead != NULL);SLTNode* first = *pphead;*pphead = first->Next;free(first);first = NULL;
}
// 单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}else{cur = cur->Next;}}return NULL;
}
//在pos之前插入,配合SListFind函数一起使用
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表）assert(pphead != NULL);assert(pos);if (pos == *pphead)//如果pos为头指针，那么类似于头插{SListPushFront(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位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置
{assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead){SListPopFront(pos);}else{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->Next != pos){prev = prev->Next;}prev->Next = pos->Next;free(pos);//pos = NULL;这句话其实没用因为形参的改变不影响实参}
}
//在pos后面插入
void SLTInsertAfter(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);SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失pos->Next = pos->Next->Next;free(del);del = NULL;
}
//链表的删除
void SLTDestroy(SLTNode* phead)
{SLTNode* cur = phead;while (cur){SLTNode* tmp = cur->Next;free(cur);cur = tmp;}}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SListPopFront(&plist);SLTPrint(plist);SLTNode* ret=SListFind(plist, 2);SLTPrint(plist);SLTInsert(&plist, ret, 20);SLTPrint(plist);
}
int main()
{TestSList1();return 0;
}


http://www.ppmy.cn/embedded/164144.html

相关文章

C语言中的链表封装

C语言中的链表封装

链表是一种常用的数据结构&#xff0c;在许多应用程序中都有广泛的应用。它由一系列节点组成&#xff0c;每个节点包含数据和指向下一个节点的指针。本篇文章将详细介绍如何在C语言中实现链表的封装&#xff0c;并提供一些基本的操作函数&#xff0c;如添加元素、删除元素、遍历…
阅读更多...
CSS盒模

CSS盒模

CSS盒模型就像一个快递包裹&#xff0c;网页上的每个元素都可以看成是这样一个包裹&#xff0c;它主要由以下几个部分组成&#xff1a; 内容&#xff08;content&#xff09;&#xff1a;就像包裹里真正装的东西&#xff0c;比如文字、图片等。在CSS里&#xff0c;可用width&a…
阅读更多...
音视频入门基础：RTP专题（9）——FFmpeg接收RTP流的原理和内部实现

音视频入门基础：RTP专题（9）——FFmpeg接收RTP流的原理和内部实现

一、引言 由《音视频入门基础&#xff1a;RTP专题&#xff08;2&#xff09;——使用FFmpeg命令生成RTP流》可以知道&#xff0c;推流端通过下面FFmpeg命令可以将一个媒体文件转推RTP&#xff0c;生成RTP流&#xff1a; ffmpeg -re -stream_loop -1 -i input.mp4 -vcodec cop…
阅读更多...
VBA脚本将DeepSeek嵌入Word中教程

VBA脚本将DeepSeek嵌入Word中教程

一、获取API-Key 目前我们可以直接只用官网的API来实现&#xff0c;申请这一步是关键 也可以直接访问官网的API平台&#xff1a;https://platform.deepseek.com/ &#xff0c;没注册的注册完登录一下&#xff0c;我们点击到左侧菜单的“APIKeys”按钮&#xff0c;然后点击右侧…
阅读更多...
C语言-----操作符的分类

C语言-----操作符的分类

1. 操作符的分类 •算术操作符&#xff1a; 、- 、 * 、/、% 移位操作符:<< >> 位操作符: & | ^ 赋值操作符: / 、 % 、 、- 、 *、/、 %、 <<、 >>、&、| 、 ^ 单⽬操作符&#xff1a;&#xff01;、 、- 、 & 、 * 、 、 …
阅读更多...
【够用就好002-2】发布github项目仓库补充

【够用就好002-2】发布github项目仓库补充

请原谅我的内容比较碎&#xff0c;确实自学最大的弊端就是知识不系统&#xff0c;但是正如我标题所说&#xff0c;够用就好。 本章的内容是对第一次发布项目到github上后续的补充。 现在我们已经知道如何提交自己的code代码&#xff0c;但是 即开即用的软件现在还没提交。 如…
阅读更多...
蓝桥杯篇---IAP15F2K61S2串口

蓝桥杯篇---IAP15F2K61S2串口

文章目录 前言简介串口通信的基本参数1.波特率2.数据位3.停止位4.校验位 串口相关寄存器1.SCON2.SBUF3.PCON4.TMOD5.TH1/TL1 串口使用步骤1.配置波特率2.配置串口模式3.使能串口中断4.发送数据5.接收数据6.处理中断 示例代码&#xff1a;串口发送与接收示例代码&#xff1a;串口…
阅读更多...
SQL FIRST() 函数详解

SQL FIRST() 函数详解

SQL FIRST() 函数详解 在SQL中&#xff0c;FIRST() 函数是一个用于处理查询结果的聚合函数。它通常与 GROUP BY 子句结合使用&#xff0c;用于返回每个分组中的第一个记录。本文将详细解释 FIRST() 函数的用法、参数、返回值以及与它的关联函数。 1. 函数概述 FIRST() 函数的…
阅读更多...
最新文章

Copyright @ 2022~2023