一篇解单链表（0基础看）（C语言）《数据结构与算法》

谁都不能阻挡你成为更优秀的人。

链表

1. 链表的概念及结构

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

2. 链表的分类

2.1. 单向或者双向

2.2. 带头或者不带头

2.3. 循环或者非循环

2.4. 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3. 效果展示图

4. 接口实现

本篇幅是无头+单向+非循环链表增删查改实现，下一篇就是带头+双向+循环链表的实现哈。

对于接口的实现我们首先是要知道要实现什么，本文是对于链表的基本使用，让大家初步了解链表，所以就只实现顺序表的增删查改，还有特定位置前插入和删除特定位置值等当然代码也不一定要作者这么写，这里只是提供一种思路，废话不多说，看代码。

有什么不懂的欢迎到评论区交流哈，当然也可以私信作者。

4.01. 本文章要实现的接口

4.02. 链表的实现

4.03. 初始化

4.04. 销毁链表

4.05. 打印链表

4.06. 动态申请一个节点

4.07. 头插

4.08. 尾插

4.09. 头删

4.10. 尾删

4.11. 查找某个值并返回地址

4.12. 在pos位置之前插入某个值

4.13. 删除pos位置的值

5. 源代码

5.1. test.c

#include"SList.h"

int main()
{
    //直接初始化next为NULL就可以了
    SListNode* plist = NULL;
    //头插 1 2
    SListPushFront(&plist, 1);
    SListPushFront(&plist, 2);
    SListPushFront(&plist, 6);
    SListPrint(&plist);
    //尾插 3 4 5
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPushBack(&plist, 5);
    SListPrint(&plist);
    //头删一个数
    SListPopFront(&plist);
    SListPrint(&plist);
    //尾删两个个数
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPrint(&plist);
    //找 3 4 1
    SListFind(&plist, 3);
    SListFind(&plist, 4);
    SListFind(&plist, 1);
    //在 1 前面插入 8
    SListNode* pos=SListFind(&plist, 1);
    SListInsert(&plist, pos, 8);
    SListPrint(&plist);
    //删除 2  3
    pos = SListFind(&plist, 2);
    SListErase(&plist, pos);
    SListPrint(&plist);
    pos = SListFind(&plist, 3);
    SListErase(&plist, pos);
    SListPrint(&plist);
    //销毁链表
    SListDestory(&plist);
    return 0;
}

5.2. SList.h

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int SLTDateType;

typedef struct SListNode
{
    SLTDateType date;
    struct SListNode* next;
}SListNode;

//销毁
void SListDestory(SListNode** pphead);
//打印
void SListPrint(SListNode** pphead);

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
//查找某个值
SListNode* SListFind(SListNode** pphead, SLTDateType x);

//头插
void SListPushBack(SListNode** pphead,SLTDateType x);
//尾插
void SListPushFront(SListNode** pphead, SLTDateType x);

//头删
void SListPopFront(SListNode** pphead);
//尾删
void SListPopBack(SListNode** pphead);

//在pos位置之前插入某个值
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
//删除pos位置的值
void SListErase(SListNode** pphead,SListNode* pos);
//找到某个值并改变为某个值

5.3. SList.c

#include"SList.h"

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    (newnode)->next = NULL;
    newnode->date = x;
    return newnode;
}

//头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
    SListNode* newnode=BuySListNode(x);

    if (!(*pphead))
    {
        *pphead = newnode;
    }
    else
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
}

//打印
void SListPrint(SListNode** pphead)
{
    SListNode* cur = *pphead;
    while (cur)
    {
        //注意这里打印的 -> 和下面的 NULL 只是为了打印出来更像是链表
        printf("%d->", cur->date);
        cur = cur->next;
    }
    printf("NULL\n");
}

//尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
    SListNode* tail = *pphead;
    SListNode* newnode=BuySListNode(x);
    if (!tail)
    {
        tail = newnode;
    }
    else
    {
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

//头删
void SListPopFront(SListNode** pphead)
{
    assert(*pphead);
    
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

//尾删
void SListPopBack(SListNode** pphead)
{
    assert(*pphead);

    SListNode* tail = *pphead;
    SListNode* prev = *pphead;
    if (prev->next == NULL)  //一个节点的时候
    {
        //注意这里free是*pphead
        free(*pphead);
        *pphead = NULL;
        return;
    }
    else
    {
        //多个节点的时候(此时最少两个节点)
        tail = tail->next;
        while (tail->next)
        {
            tail = tail->next;
            prev = prev->next;
        }
        //这里只需要free最后面的一个空间
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

//查找某个值
SListNode* SListFind(SListNode** pphead, SLTDateType x)
{
    assert(*pphead);

    SListNode* cur = *pphead;
    while (cur != NULL)
    {
        if (cur->date == x)
        {
            printf("找到啦!\n");
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    printf("没有找到此值\n");
    return NULL;
}

//在pos位置之前插入某个值
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
    if (pos == *pphead)
    {
        SListPushFront(pphead, x);
    }
    else 
    {
        SListNode* prev = *pphead;
        SListNode* newnode = BuySListNode(x);
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = newnode;
        newnode->next = pos;
    }
}

//删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos)
{
    assert(*pphead);

    if (pos == *pphead)
    {
        SListPopFront(pphead);
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

//销毁
void SListDestory(SListNode** pphead)
{
    assert(*pphead);

    SListNode* pos = *pphead;
    SListNode* cur = *pphead;

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

今天的内容就到这里了哈！！！

要是认为作者有一点帮助你的话！

就来一个点赞加关注吧！！！当然订阅是更是求之不得！

赠人玫瑰，手有余香=。=！

最后的最后感谢大家的观看！！！

你们的支持是作者写作的最大动力！！！

下期见哈！！！