0
0

P3—＜单链表＞《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之单链表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之单链表（增删查改）功能实现

完整源码如下，欢迎复制测试指正！

单链表（增删查改）功能实现测试示例：

完整源码：

Test.c:

#include "SList.h"
//单链表
//打印测试
void TestSList1()
{
    SListNode* slist = NULL;
    //malloc需要检查，防止开辟失败
    SListNode* n1 = malloc(sizeof(SListNode));
    SListNode* n2 = malloc(sizeof(SListNode));
    SListNode* n3 = malloc(sizeof(SListNode));
    n1->data = 1;
    n2->data = 2;
    n3->data = 3;
    n1->next = n3;
    n3->next = n2;
    n2->next = NULL;
    slist = n1;

    //SListNode* slist = NULL;
    //SListNode* n1 = malloc(sizeof(SListNode));
    //SListNode* n2 = malloc(sizeof(SListNode));
    //SListNode* n3 = malloc(sizeof(SListNode));
    //n1->data = 1;
    //n2->data = 2;
    //n3->data = 3;
    //n1->next = n2;
    //n2->next = n3;
    //n3->next = NULL;
    //slist = n1; 

    SListPrint(slist);
}

//尾插测试
void TestSList2()
{
    SListNode* slist = NULL; //空链表
    //一个一个创建
    /*SListPushBack(slist, 1);
    SListPushBack(slist, 2);
    SListPushBack(slist, 3);
    SListPushBack(slist, 4);*/
    //使用循环创建
    for (int i = 0; i < 4; ++i)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
}
//头插测试
void TestSList3()
{
    SListNode* slist = NULL; //空链表
    //使用循环创建
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
}
//尾删测试
void TestSList4()
{
    SListNode* slist = NULL; //空链表
    //使用尾插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    //尾删5次
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPrint(slist);

}
//头删测试
void TestSList5()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    //头删
    SListPopFront(&slist);
    SListPrint(slist);
    SListPopFront(&slist);
    SListPopFront(&slist);
    SListPrint(slist);
    SListPopFront(&slist);
    SListPrint(slist);

}
//查找（按值查找）测试
void TestSList6()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    //查找
    SListNode* pos = SListFind(slist, 2);
    if (pos)
    {
        printf("找到了:%p\n", pos);
        // 修改
        pos->data *= 10; //扩大10倍
    }
    SListPrint(slist);
}
//在指定数据（pos）位置插入数据测试
void TestSList7()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    //在指定数据（pos）位置插入数据
    //查找（按值查找）
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListInsert(&slist, pos, 30);
    }
    SListPrint(slist);
    //查找（按值查找）
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListInsert(&slist, pos, 50);
    }
    SListPrint(slist);

}
// 在指定数据位置（pos）后插测试
void TestSList8()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    // 在指定数据位置（pos）后插
    //查找（按值查找）
    SListNode* pos = SListFind(slist, 2);
    if (pos)
    {
        SListInsertAfter(pos, 30);
    }
    SListPrint(slist);

}
// 在指定数据位置（pos）删除测试
void TestSList9()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    // 在指定数据位置（pos）删除
    //查找（按值查找）
    SListNode* pos = SListFind(slist, 2);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);
    //查找（按值查找）
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);

}
// 在指定数据位置（pos）位置后删测试
void TestSList10()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    //在指定数据位置（pos）位置后删
    //查找（按值查找）
    SListNode* pos = SListFind(slist, 2);
    if (pos)
    {
        SListEraseAfter(pos);
    }
    SListPrint(slist);
    //查找（按值查找）
    pos = SListFind(slist, 3);
    if (pos)
    {
        SListEraseAfter(pos);
    }
    SListPrint(slist);

}
//销毁单链表测试
void TestSList11()
{
    SListNode* slist = NULL; //空链表
    //使用头插+循环创建 4个数据
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
    //销毁单链表
    SListDestroy(&slist);

}

int main()
{
    TestSList1();
    TestSList2();
    TestSList3();
    TestSList4();
    TestSList5();
    TestSList6();
    TestSList7();
    TestSList8();
    TestSList9();
    TestSList10();
    TestSList11();
    return 0;
}

** SList.c:**

#include "SList.h"
//单链表
//打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
    //assert(phead);  //没必要暴力终止程序,空链表也可打印
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
//动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    //检查是否开辟成功
    if (newnode == NULL)
    {
        printf("malloc fail！\n");
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    return newnode;
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
    assert(pphead);
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}


//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    assert(pphead);
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        // 找尾-需要从头遍历
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾插-传参有误
//void SListPushBack(SListNode* phead, SLTDataType x)
//{  
//    //根据需要动态开辟新结点
//    SListNode* newnode = BuySListNode(x);
//    if (phead == NULL)
//    {
//        phead = newnode;
//    }
//    else
//    {
//        // 找尾-需要从头遍历
//        SListNode* tail = phead;
//        while (tail->next != NULL)
//        {
//            tail = tail->next;
//        }
//        tail->next = newnode;
//    }
//}

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

    // 也可以暴力检查为空的情况
    //assert(*pphead != NULL);

    // 1、空
    // 2、一个节点
    // 3、多个节点
    if (*pphead == NULL)  // 温柔检查
    {
        return;
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //写法1——使用双指针
        /*SListNode* prev = NULL;
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
        prev = tail;
        tail = tail->next;
        }

        free(tail);
        tail = NULL;
        prev->next = NULL;*/

        //写法2——提前控制指针
        SListNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }

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

    // 1、空
    // 2、非空
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode* next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}
//查找（按值查找）
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
// 在指定位置（pos）位置插入数据
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    // 1、pos是第一个节点
    // 2、pos不是第一个节点
    if (pos == *pphead)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        //根据需要动态开辟新结点
        SListNode* newnode = BuySListNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);

    SListNode* next = pos->next;
    写法1
    根据需要动态开辟新结点
    //SListNode* newnode = BuySListNode(x);
    改动顺序随意
    //pos->next = newnode;
    //newnode->next = next;
    
    
    //写法2
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    //改动顺序指定
    newnode->next = pos->next;
    pos->next = newnode;
}

// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos)
{
    assert(pphead);
    assert(pos);

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

        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos)
{
    assert(pos);
    //注：这个不会是头删
    SListNode* next = pos->next;
    if (next)
    {
        pos->next = next->next;
        free(next);
        next = NULL;
    }
}
//销毁单链表
void SListDestroy(SListNode** pphead)
{
    assert(pphead);

    SListNode* cur = *pphead;
    while (cur)
    {
        SListNode* next = cur->next;
        free(cur);
        cur = next;
    }

    *pphead = NULL;
}

** SList.h:**

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

typedef int SLTDataType;  //以后可以更改int为char或者double等

typedef struct SListNode
{
    SLTDataType data; // val
    struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头删
void SListPopFront(SListNode** pphead);
//查找（按值查找）
//查找可以传二级指针，但没必要，因为不会改变数据，只是进行查找
SListNode* SListFind(SListNode* phead, SLTDataType x);

// 在指定位置（pos）位置前插
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos);
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos);
//销毁单链表
void SListDestroy(SListNode** pphead);

二、实现分析：

问题导引：

**顺序表的问题及思考 **

问题：

  1. 中间/头部的插入删除，时间复杂度为O(N)

  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们

再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

**3.****链表 **

**3.1 ****链表的概念及结构 **

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

也可以这样：

单链表实现测试：

测试示例：** Test.c：**

#include "SList.h"

void TestSList1()
{
    SListNode* slist = NULL;
    SListNode* n1 = malloc(sizeof(SListNode));
    SListNode* n2 = malloc(sizeof(SListNode));
    SListNode* n3 = malloc(sizeof(SListNode));
    n1->data = 1;
    n2->data = 2;
    n3->data = 3;
    n1->next = n3;
    n3->next = n2;
    n2->next = NULL;
    slist = n1;

    SListPrint(slist);
}

int main()
{
    TestSList1();
    return 0;
}

** SList.c:**

#include "SList.h"

void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

** SList.h:**

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

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data; // val
    struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);

单链表不需要初始化，即使最初为空，也是一个空指针，而顺序表最初为空是一个结构体！

举例传参分析：

1.

2.

单链表尾插：

测试示例：

Test.c:

#include "SList.h"
//单链表尾插数据测试
void TestSList2()
{
    SListNode* slist = NULL; //空链表
    //一个一个创建
    /*SListPushBack(slist, 1);
    SListPushBack(slist, 2);
    SListPushBack(slist, 3);
    SListPushBack(slist, 4);*/
    //使用循环创建
    for (int i = 0; i < 4; ++i)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
}

int main()
{
    TestSList2();
    return 0;
}

SList.c:

#include "SList.h"

//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
    //assert(phead);  //不需要暴力终止程序,空链表也可打印
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    //检查是否开辟成功
    if (newnode == NULL)
    {
        printf("malloc fail！\n");
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    return newnode;
}

//单链表尾插数据
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        // 找尾-需要从头遍历
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

SList.h:

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

typedef int SLTDataType;  //以后可以更改int为char或者double等

typedef struct SListNode
{
    SLTDataType data; // val
    struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

单链表头插：

测试示例：

Test.c:

#include "SList.h"

//单链表头插数据测试
void TestSList3()
{
    SListNode* slist = NULL; //空链表
    //使用循环创建
    for (int i = 0; i < 4; ++i)
    {
        SListPushFront(&slist, i);
    }
    SListPrint(slist);
}
int main()
{
    TestSList3();
    return 0;
}

SList.c:

#include "SList.h"

//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
    //assert(phead);  //不需要暴力终止程序,空链表也可打印
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    //检查是否开辟成功
    if (newnode == NULL)
    {
        printf("malloc fail！\n");
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    return newnode;
}
//单链表头插数据
void SListPushFront(SListNode** pphead, SLTDataType x)
{
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

SList.h:

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

typedef int SLTDataType;  //以后可以更改int为char或者double等

typedef struct SListNode
{
    SLTDataType data; // val
    struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

单链表尾删：

单链表头删:

单链表查找（按值查找）:

单链表在指定数据位置（pos）插入数据：

单链表在指定数据位置（pos）后插：

单链表在指定数据位置（pos）删除：

单链表在指定数据位置（pos）后删：

单链表销毁：

单链表动态开辟新结点：

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

——By 作者：新晓·故知

标签： 数据结构 c语言 链表
本文转载自: https://blog.csdn.net/m0_57859086/article/details/123452664
版权归原作者 新晓·故知 所有， 如有侵权，请联系我们删除。
登录后发布评论

“P3&mdash;＜单链表＞《数据结构(C语言版)》”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

【IntelliJ IDEA】IntelliJ IDEA中文语言包不起作用

vscode gitlens收费破解

是时候用开源降低AI落地门槛了

毕设开源 深度学习手写数字识别系统(源码+论文)

毕业设计 大数据电商用户行为分析及可视化(源码+论文)

文章导航