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

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

article 2025/1/13 13:12:57

在这里插入图片描述

🚀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}{评论，你的意见是我进步的财富！} 评论，你的意见是我进步的财富！


http://www.kler.cn/a/1098.html

相关文章：

  • 小目标检测难点分析和解决策略
  • 如何修改 Go 结构体的私有字段
  • LeetCode刷题——贪心法(C/C++)
  • 【Linux】Linux项目自动化构建工具make makefile
  • 【码字必看】一篇文章带你轻松上手MarkDown
  • 华为nat配置实验：内网能够访问外网，内网服务器80端口映射出去
  • Django 4.0文档学习（一）
  • 移动端适配
  • openstack
  • Kaggle实战入门：泰坦尼克号生生还预测
  • 小黑子—多媒体技术与运用基础知识：一
  • VSCode 开发配置，一文搞定（持续更新中...）
  • SparkSQL-SparkOneHive
  • 使用busybox构建根文件系统
  • python 正则表达式
  • Springboot 整合dom4j 解析xml 字符串 转JSONObject
  • Android开发 Layout布局 ScrollView
  • linux操作系统lVM扩容
  • VI的常用命令
  • get table meta failed, please check whether the table xxx exists
  • Nuxt.js项目开发过程遇到的问题以及对Nuxt.js的学习与总结
  • WEB前端第三次作业——CSS样式案例