【数据结构】万字深入浅出讲解单链表(附原码 | 超详解)

在这里插入图片描述

🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:C语言实现数据结构
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

文章目录

  • 前言
  • 一、链表概念
  • 二、链表的分类
    • 1. 单向或者双向
    • 2. 带头或者不带头
    • 3. 循环或者非循环
  • 三、链表的实现
    • 函数接口汇总SList.h
    • 函数接口实现SList.c
    • 代码实践Test.c
  • 代码汇总
  • 总结


前言

这几天看了数据结构的单链表这一节,真的收获很大,第一次看没有动手敲代码就是感觉学了和没学一样,今天也是从新又看了一遍,并且边学边敲代码,终于算是非常理解单链表这个东西了,今天就把我所学到的知识给大家分享一下。


一、链表概念

链表是一种物理存储结构非连续非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针
接次序实现的 。
在这里插入图片描述

二、链表的分类

1. 单向或者双向

在这里插入图片描述

2. 带头或者不带头

在这里插入图片描述

3. 循环或者非循环

在这里插入图片描述
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构

1.无头单向链表

2.双向循环链表
在这里插入图片描述

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

三、链表的实现

函数接口汇总SList.h


typedef int SLTDataType;

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

//打印
void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
//增
void SLTPushBack(SLTNode** pphead,SLTDataType x);
void SLTPushFront(SLTNode** pphead,SLTDataType x);
//删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos);
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos);

函数接口实现SList.c


//--------------------------手动分割线---------------------------
//打印
void SLTPrint(SLTNode* phead)
{
    assert(phead);
    SLTNode* cur=phead;
    while(cur)
    {
        printf("%d ",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
    if(newnode==NULL) 
    {
        printf("malloc fail\n");
        return NULL;
    }
    newnode->data=x;
    newnode->next=NULL;

    return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
	assert(pphead);
    SLTNode* newnode=BuySLTNode(x);

    if(*pphead==NULL)
    {
        *pphead=newnode;
    }
    else
    {
        //找尾
        SLTNode* cur=*pphead;
        while(cur->next!=NULL)
        {
            cur=cur->next;
        }
        cur->next=newnode;
    }
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
	assert(pphead);
    SLTNode* newnode=BuySLTNode(x);
    newnode->next=*pphead;
    *pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{
    // 暴力检查
	assert(pphead);
	assert(*pphead);

    SLTNode* cur=*pphead;
    if(*pphead->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode* cur=*pphead;
        while(cur->next->next!=NULL)
        {
            cur=cur->next;
        }
        SLTNode* tmp=cur->next;
        free(tmp);
        cur->next=NULL;
    }
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead);
	assert(*pphead);
    if(*pphead->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode* tmp=*pphead;
        free(tmp);
        tmp=NULL;
        *pphead=*pphead->next;
    }
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
    SLTNode* cur=phead;
    while(cur)
    {
        if(cur->data==x) return cur;
        cur=cur->next;
    }
    return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
    SLTNode* newnode=BuySLTNode(x);

    if(*pphead==pos)
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        SLTNode* prev=*pphead;
        while(prev->next!=pos)
        {
            prev=prev->next;
        }
        prev->next=newnode;
        newnode->next=pos;
    }
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
    SLTNode* cur=*pphead;
    if(*pphead==pos)
    {
        SLTPopFront(pphead);
    }
    else
    {
        while(cur->next!=pos)
        {
            cur=cur->next;
        }
        cur->next=pos->next;
        free(pos);
        pos=NULL;
    }
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//--------------------------手动分割线-----------------------------

代码实践Test.c

#include"SList.h"

void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
}

int main()
{
	TestSList3();

	return 0;
}

代码汇总

#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)
{
    assert(phead);
    SLTNode* cur=phead;
    while(cur)
    {
        printf("%d ",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");
}
//--------------------------手动分割线-----------------------------
//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
    if(newnode==NULL) 
    {
        printf("malloc fail\n");
        return NULL;
    }
    newnode->data=x;
    newnode->next=NULL;

    return newnode;
}
//--------------------------手动分割线-----------------------------
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
    SLTNode* newnode=BuySLTNode(x);

    if(*pphead==NULL)
    {
        *pphead=newnode;
    }
    else
    {
        //找尾
        SLTNode* cur=*pphead;
        while(cur->next!=NULL)
        {
            cur=cur->next;
        }
        cur->next=newnode;
    }
}
//--------------------------手动分割线-----------------------------
//前插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
    SLTNode* newnode=BuySLTNode(x);
    newnode->next=*pphead;
    *pphead=newnode;
}
//--------------------------手动分割线-----------------------------
//尾删
void SLTPopBack(SLTNode** pphead)
{
    //暴力检查
    assert(*pphead);

    SLTNode* cur=*pphead;
    if(*pphead->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode* cur=*pphead;
        while(cur->next->next!=NULL)
        {
            cur=cur->next;
        }
        SLTNode* tmp=cur->next;
        free(tmp);
        cur->next=NULL;
    }
}
//--------------------------手动分割线-----------------------------
//前删
void SLTPopFront(SLTNode** pphead)
{
    assert(*pphead);
    if(*pphead->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode* tmp=*pphead;
        free(tmp);
        tmp=NULL;
        *pphead=*pphead->next;
    }
}
//--------------------------手动分割线-----------------------------
//查找
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
    SLTNode* cur=phead;
    while(cur)
    {
        if(cur->data==x) return cur;
        cur=cur->next;
    }
    return NULL;
}
//--------------------------手动分割线-----------------------------
//任意位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    SLTNode* newnode=BuySLTNode(x);

    if(*pphead==pos)
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        SLTNode* prev=*pphead;
        while(prev->next!=pos)
        {
            prev=prev->next;
        }
        prev->next=newnode;
        newnode->next=pos;
    }
}
//--------------------------手动分割线-----------------------------
//删除某个节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    SLTNode* cur=*pphead;
    if(*pphead==pos)
    {
        SLTPopFront(pphead);
    }
    else
    {
        while(cur->next!=pos)
        {
            cur=cur->next;
        }
        cur->next=pos->next;
        free(pos);
        pos=NULL;
    }
}
//--------------------------手动分割线-----------------------------
//在后面插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//--------------------------手动分割线-----------------------------
//删除pos后面这一个节点
void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//--------------------------手动分割线-----------------------------


void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
}

int main()
{
	TestSList3();

	return 0;
}

总结

  今天学习了单链表的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将多画图,多敲代码来学习,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。

  我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬能一键三连支持一下博主,hhhh~我们下期见喽
在这里插入图片描述
如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下

👍 点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!

⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!

✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/1131.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

进程和线程的区别和联系

进程和线程的区别和联系1. 认识线程2. 进程和线程的关系3. 进程和线程的区别4. 线程共享了进程哪些资源1. 上下文切换2. 线程共享了进程哪些资源1.代码区2. 数据区3. 堆区1. 认识线程 线程是进程的一个实体,它被包含在进程中,一个进程至少包含一个线程,一个进程也可以包含多个…

Python数据分析案例22——财经新闻可信度分析(线性回归,主成分回归,随机森林回归)

本次案例还是适合人文社科领域&#xff0c;金融或者新闻专业。本科生做线性回归和主成分回归就够了&#xff0c;研究生还可以加随机森林回归&#xff0c;其方法足够人文社科领域的硕士毕业论文了。 案例背景 有八个自变量&#xff0c;[微博平台可信度,专业性,可信赖性,转发量,…

什么是栈,如何实现?

欢迎来到 Claffic 的博客 &#x1f49e;&#x1f49e;&#x1f49e; “但有一枝堪比玉&#xff0c;何须九畹始征兰?” 前言&#xff1a; 栈是一种特殊的线性表&#xff0c;就像开盖的桶一样&#xff0c;从底部开始放数据&#xff0c;从顶部开始取数据&#xff0c;那么栈具体是…

最适合游戏开发的语言是什么?

建议初学者学习主流的开发技术 主流开发技术有大量成熟的教程、很多可以交流的学习者、及时的学习反馈等&#xff1b;技术的内里基本都是相同的&#xff0c;学习主流技术的经验、知识可以更好更快地疏通学习新知识和技术。 因此&#xff0c;对C#或者C二选一进行学习较好。 Un…

Linux: 以太网 PHY 驱动简析

文章目录1. 前言2. 背景3. 硬件拓扑4. 以太网卡 PHY 驱动实现4.1 MDIO 总线对象的创建和注册4.2 MDIO 总线从设的 创建注册 和 驱动注册的加载4.2.1 以太网的 PHY 设备创建和注册4.2.2 以太网的 PHY 设备驱动注册和加载4.3 绑定以太网卡的 MAC 和 PHY4.4 以太网卡 PHY 和 MAC 的…

2022-2023 年度广东省职业院校学生专业技能大赛中职组“网络安全”赛项竞赛任务书(样题)

2022-2023 年度广东省职业院校学生专业技能大赛中职组“网络安全”赛项竞赛任务书&#xff08;样题&#xff09; 一、竞赛时间 总计&#xff1a;210 分钟 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 A 模块 A-1 登录安全加固 90 分钟 200…

重构·改善既有代码的设计.03之重构手法(上)

1. 前言 之前的重构系列中&#xff0c;介绍了书中提到的重构基础&#xff0c;以及识别代码的坏味道。今天继续第三更&#xff0c;讲述那些重构手法&#xff08;上&#xff09;。看看哪些手法对你的项目能有所帮助… 2. 重新组织函数 对函数进行整理&#xff0c;使之更恰当的…

51单片机入门 -驱动 8x8 LED 点阵屏

硬件型号、软件版本、以及烧录流程 操作系统&#xff1a;Windows 10 x84-64单片机&#xff1a;STC89C52RC编译器&#xff1a;SDCC烧录软件&#xff1a;stcgal 1.6开发板&#xff1a;普中51单片机开发板A2套件&#xff08;2022&#xff09; 在 VS Code 中新建项目到烧录的过程…

[ROC-RK3568-PC] [Firefly-Android] 10min带你了解I2C的使用

&#x1f347; 博主主页&#xff1a; 【Systemcall小酒屋】&#x1f347; 博主追寻&#xff1a;热衷于用简单的案例讲述复杂的技术&#xff0c;“假传万卷书&#xff0c;真传一案例”&#xff0c;这是林群院士说过的一句话&#xff0c;另外“成就是最好的老师”&#xff0c;技术…

5.springcloud微服务架构搭建 之 《springboot集成Hystrix》

1.springcloud微服务架构搭建 之 《springboot自动装配Redis》 2.springcloud微服务架构搭建 之 《springboot集成nacos注册中心》 3.springcloud微服务架构搭建 之 《springboot自动装配ribbon》 4.springcloud微服务架构搭建 之 《springboot集成openFeign》 目录 1.项目…

C语言刷题(7)(字符串旋转问题)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰的内容依旧是复习之前的知识点&#xff0c;那么&#xff0c;就是做一道小小的题目啦&#xff0c;下面&#xff0c;让我们进入C语言的世界吧 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; A…

2023最新性能测试八股文【附答案】,软测人必备!

1. 请描述什么是性能测试、什么是负载测试、什么是压力测试&#xff1f;【参考答案】性能测试&#xff1a;性能测试是和功能测试相对应的。根据用户场景进行的单个用户操作&#xff0c;是属于功能测试领域&#xff0c;主要是验证软件是否可以满足用户的功能需求。比如&#xff…

【刷题之路Ⅱ】LeetCode 11.盛水最多的容器

【刷题之路Ⅱ】LeetCode 11.盛水最多的容器一、题目描述二、解题1、方法1——暴力法1.1、思路分析1.2、代码实现2、方法2——双指针2.1、思路分析2.2、代码实现一、题目描述 原题连接&#xff1a; 11.盛水最多的容器 题目描述&#xff1a; 给定一个长度为 n 的整数数组 height…

44岁了,我从没想过在CSDN创作2年,会有这么大收获

1998年上的大学&#xff0c;02年毕业&#xff0c;就算从工作算起&#xff0c;我也有20余年的码龄生涯了。 但正式开启博文的写作&#xff0c;却是2021年开始的&#xff0c;差不多也就写了2年的博客&#xff0c;今天我来说说我在CSDN的感受和收获。 我是真的没想到&#xff0c;…

QT串口助手开发3串口开发

系列文章目录 QT串口助手开发3串口开发 QT串口助手开发3系列文章目录一、UI界面程序的编写二、发送框程序编写一、UI界面程序的编写 根据上文的未解决问题&#xff1a;我们打开串口按钮打开后只能选择关闭串口&#xff0c;所以这个是循环的过程 上文链接 所以按钮对应的槽函数…

【C++】搜索二叉树(保姆教程)

&#x1f345;二叉树底层是堆&#xff0c;之前学习的简单二叉树不是大堆就是小堆&#xff0c;今天是二叉树进阶&#xff0c;一定要好好掌握&#xff01; 目录 ☃️1.搜索二叉树介绍 ☃️2.底层实现 ☃️3.key模型和key&#xff0c;value模型 ☃️1.搜索二叉树介绍 右>根&…

蜻蜓优化算法Python代码(详细注释)

1.代入例子&#xff0c;目标函数求最优解迭代过程&#xff1a;蜻蜓算法流程&#xff1a;蜻蜓算法&#xff08;Dragonfly Algorithm&#xff09;是一种基于种群的优化算法&#xff0c;灵感来自于蜻蜓的群集行为。该算法通过模拟蜻蜓之间的吸引力和斥力&#xff0c;以及蜻蜓的移动…

IDEA好用插件:MybatisX快速生成接口实体类mapper.xml映射文件

目录 1、在Idea中找到下载插件&#xff0c;Install&#xff0c;重启Idea 2、一个测试java文件&#xff0c;里面有com包 3、在Idea中添加数据库 --------以Oracle数据库为例 4、快速生成entity-service-mapper方法 5、查看生成的代码 6、自动生成&#xff08;增删查改&#xff0…

C++ | 对比inline内联函数和宏的不同点

文章目录一、前言二、宏的优缺点分析1、概念回顾2、宏的缺点3、宏的优点三、inline内联函数1、概念2、特性①&#xff1a;空间换时间&#x1f381;趣味杂谈&#xff1a;庞大的游戏更新包3、特性②&#xff1a;inline实现机制4、特性③&#xff1a;inline的声明与定义反汇编观察…

【链表OJ题(八)】相交链表

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(八)8. 相交…