💌前言

本文介绍了单链表的定义以及常用结点的实现。

一、定义

1.概念

顺序表最大缺点就是：插入和删除的时候需要移动大量的元素。
而单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

2.特点

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。
链表中每个元素本身由两部分组成：
● 数据域：存放数据。
● 指针域：存放指向后继结点的地址；
链表的第一个结点被称为：头节点

在这里插入图片描述

3.优点

①.链表是一个动态数据结构，无需给出链表的初始大小。
②.任意位置插入删除时间复杂度为O(1)。
与数组不同，在插入或删除元素后，我们不必移动元素。在链表中，我们只需要更新节点的下一个指针中存在的地址即可。
③.由于链表的大小可以在运行时增加或减小，因此不会浪费内存。

4.缺点

①.存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。
②.要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 O ( n) 在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为 O ( 1) 。双链表还允许在特定的数据元素之前插入或删除元素。
③.存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。

5.结点定义

typedef int LinkType; //数据类型
typedef struct SLlist {
    LinkType data;//数据域
    struct SLlist* next;//指针域
}SLlist;

利用typedef修改int类型的名字，下面int的地方全部可以用typedef后的名字代替，便于修改数据类型。
由于每个结点都是两部分，所以结构体内部有两部分：
一部分存储数据，另一部分存储下一个结点的地址。

二、接口实现

1.创建链表结点

创建单个结点

创建单个结点是我们实现后面接口的基础。

SLlist* BuySLlist(LinkType x) {
    SLlist* newnode = (SLlist*)malloc(sizeof(SLlist));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

创建链表

这里我为了测试方便，每个结点的数据内容我并没有使用scanf函数输入，实际使用过程中大家可以在循环里面加入scanf函数。

SLlist* CreateSLlist(LinkType n)
{
    SLlist* phead = NULL, * ptail = NULL;
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        SLlist* newnode = BuySLlist(i);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;
}

打印链表

为了测试的结构直观显示，我就先把打印函数写出来。

void PrintSLlist(SLlist* phead) {
    SLlist* cur = phead;
    while (cur != NULL) {         //（1）
        printf("%d->", cur->data);//（2）
        cur = cur->next;          //（3）
    }
    printf("NULL!");              //（4）
}

（1）当指针为空时，结束循环
（2）打印当前指针指向的数据
（3）将当前指针修改为当前指针指针域指向的结点的地址
（4）为了方便测试，打印NULL代表结束

测试创建功能

为了防止错误堆积到最后，我们平时写代码的时候就应该这样。每写出一个函数就可以测试以下。防止最后错误太多，看都不想看了💔💔💔

void Test02()
{
    SLlist* n1 = CreateSLlist(10);
    PrintSLlist(n1);
}
int main()
{
    Test02();
    return 0;
}

在这里插入图片描述
如图，测试正常。

2.尾插尾删

尾部插入

void SLlistPushBack(SLlist** pphead, LinkType x)
{
    SLlist* newnode = BuySLlist(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLlist* tail = *pphead;
        // 找尾
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾部删除

void SLlistPopBack(SLlist** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLlist* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

尾插尾删测试

//测试尾插函数是否正常
void Test03()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPushBack(&n1, 10);
    PrintSLlist(n1);
}
//测试尾删函数是否正常
void Test04()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPopBack(&n1);
    PrintSLlist(n1);
}

测试尾部插入函数

//主函数实现
int main()
{
    Test03();
    return 0;
}

在这里插入图片描述
测试尾部删除函数

//主函数实现
int main()
{
    Test04();
    return 0;
}

在这里插入图片描述

3.头插头删

头部插入

//头插
void SLlistPushFront(SLlist** pphead, LinkType x)
{
    SLlist* newnode = BuySLlist(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

头部删除

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

头插头删测试

//测试头插函数是否正常
void Test05()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPushFront(&n1, 30);
    SLlistPushFront(&n1, 40);
    PrintSLlist(n1);
}
//测试头删函数是否正常
void Test06()
{
    SLlist* n1 = CreateSLlist(10);
    SLlistPopFront(&n1);
    SLlistPopFront(&n1);
    PrintSLlist(n1);
}

测试头部插入函数

//主函数实现
int main()
{
    Test05();
    return 0;
}

在这里插入图片描述
测试头部删除函数

//主函数实现
int main()
{
    Test06();
    return 0;
}

在这里插入图片描述

4.pos位的插入删除

想要在pos位置进行插入删除，我们首先就要明确pos位置在哪里。
同顺序表一样，我们需要先写一个find函数来找到pos位置。

查找pos位置

//单链表查找位置
SLlist* SLTFind(SLlist* phead, LinkType x)
{
    SLlist* cur = phead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }

        cur = cur->next;
    }

    return NULL;
}

在pos位置前插入

//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x)
{
    assert(pos);
    if (*pphead == pos)
    {
        SLlistPushFront(pphead, x);
    }
    else
    {
        SLlist* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        SLlist* newnode = BuySLlist(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

在pos位置后插入

//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x)
{
    assert(pos);
    SLlist* newnode = BuySLlist(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

删除pos位置的数

//删除pos位置的函数
void SLTErase(SLlist** pphead, SLlist* pos)
{
    assert(pos);
    assert(*pphead);
    if (pos == *pphead)
    {
        SLlistPopFront(pphead);
    }
    else
    {
        SLlist* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

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

删除pos位置后的数

//删除pos位置后的函数
void SLTEraseAfter(SLlist* pos)
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLlist* nextNode = pos->next;
        pos->next = nextNode->next;
        free(nextNode);
    }
}

pos位置上的插入删除测试

//测试在pos位置后插入函数是否正常
void Test07()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    PrintSLlist(n1);
}
//测试在pos位置前插入函数是否正常
void Test08()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
}
//测试删除pos位置后函数是否正常
void Test09()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
    printf("\n");
    SLTEraseAfter(p);
    PrintSLlist(n1);
}
//测试删除pos位置函数是否正常
void Test10()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
    printf("\n");
    SLlist* p2 = SLTFind(n1, 90);
    SLTErase(&n1, p2);
    PrintSLlist(n1);
}

和上面的测试一样，想测试那个，就把test函数修改为对于的函数。

//主函数实现
int main()
{
    Test10();
    return 0;
}

在这里插入图片描述

5.销毁链表

通过循环，使用free函数释放每一个空间即可。

void SLTDestroy(SLlist** pphead)
{
    SLlist* cur = *pphead;
    while (cur)
    {
        SLlist* next = cur->next;
        free(cur);
        cur = next;
    }

    *pphead = NULL;
}

三、代码汇总

SLlist.h用来声明函数

SLlist.c用来定义函数

test.c 用来测试函数

SLlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LinkType; //数据类型
typedef struct SLlist {
    LinkType data;//数据域
    struct SLlist* next;//指针域
}SLlist;
//创建单个结点
SLlist* BuySLlist(LinkType x);
//创建链表
SLlist* CreateSLlist(LinkType n);
//打印链表
void PrintSLlist(SLlist* phead);
//尾插
void SLlistPushBack(SLlist** pphead, LinkType x);
//尾删
void SLlistPopBack(SLlist** pphead);
//头插
void SLlistPushFront(SLlist** pphead, LinkType x);
//头删
void SLlistPopFront(SLlist** pphead);
//查找
SLlist* SLTFind(SLlist* phead, LinkType x);
//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x);
//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x);
//删除pos位置后的数据
void SLTEraseAfter(SLlist* pos);
//删除pos位置的数据
void SLTErase(SLlist** pphead, SLlist* pos);
//销毁单链表
void SLTDestroy(SLlist** pphead);

SLlist.c

#include"SLlist.h"
//创建单个结点
SLlist* BuySLlist(LinkType x) {
    SLlist* newnode = (SLlist*)malloc(sizeof(SLlist));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}
//创建链表
SLlist* CreateSLlist(LinkType n)
{
    SLlist* phead = NULL, * ptail = NULL;
    int x = 0;
    for (int i = 0; i < n; ++i)
    {
        SLlist* newnode = BuySLlist(i);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;
}
//打印链表
void PrintSLlist(SLlist* phead) {
    SLlist* cur = phead;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL!");
}
// 尾插
void SLlistPushBack(SLlist** pphead, LinkType x)
{
    SLlist* newnode = BuySLlist(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLlist* tail = *pphead;
        // 找尾
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}
//尾删
void SLlistPopBack(SLlist** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLlist* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}
//头插
void SLlistPushFront(SLlist** pphead, LinkType x)
{
    SLlist* newnode = BuySLlist(x);
    newnode->next = *pphead;
    *pphead = newnode;
}
//头删
void SLlistPopFront(SLlist** pphead)
{
    assert(*pphead);
    SLlist* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}
//单链表查找位置
SLlist* SLTFind(SLlist* phead, LinkType x)
{
    SLlist* cur = phead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }

        cur = cur->next;
    }

    return NULL;
}
//在pos位置后插入
void SLTInsertAfter(SLlist* pos, LinkType x)
{
    assert(pos);
    SLlist* newnode = BuySLlist(x);
    newnode->next = pos->next;
    pos->next = newnode;
}
//在pos位置前插入
void SLTInsert(SLlist** pphead, SLlist* pos, LinkType x)
{
    assert(pos);
    if (*pphead == pos)
    {
        SLlistPushFront(pphead, x);
    }
    else
    {
        SLlist* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        SLlist* newnode = BuySLlist(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}
//删除pos位置后的函数
void SLTEraseAfter(SLlist* pos)
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLlist* nextNode = pos->next;
        pos->next = nextNode->next;
        free(nextNode);
    }
}
//删除pos位置的函数
void SLTErase(SLlist** pphead, SLlist* pos)
{
    assert(pos);
    assert(*pphead);
    if (pos == *pphead)
    {
        SLlistPopFront(pphead);
    }
    else
    {
        SLlist* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        prev->next = pos->next;
        free(pos);
    }
}
//销毁单链表
void SLTDestroy(SLlist** pphead)
{
    SLlist* cur = *pphead;
    while (cur)
    {
        SLlist* next = cur->next;
        free(cur);
        cur = next;
    }

    *pphead = NULL;
}

test.c

#include"SLlist.h"
//测试创建结点函数是否正常
void Test01()
{
    SLlist* n1 = BuySLlist(1);
    PrintSLlist(n1);
}
//测试创建链表函数是否正常
void Test02()
{
    SLlist* n1 = CreateSLlist(10);
    PrintSLlist(n1);
}
//测试尾插函数是否正常
void Test03()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPushBack(&n1, 10);
    PrintSLlist(n1);
}
//测试尾删函数是否正常
void Test04()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPopBack(&n1);
    PrintSLlist(n1);
}
//测试头插函数是否正常
void Test05()
{
    SLlist* n1 = CreateSLlist(5);
    SLlistPushFront(&n1, 30);
    SLlistPushFront(&n1, 40);
    PrintSLlist(n1);
}
//测试头删函数是否正常
void Test06()
{
    SLlist* n1 = CreateSLlist(10);
    SLlistPopFront(&n1);
    SLlistPopFront(&n1);
    PrintSLlist(n1);
}
//测试在pos位置后插入函数是否正常
void Test07()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    PrintSLlist(n1);
}
//测试在pos位置前插入函数是否正常
void Test08()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
}
//测试删除pos位置后函数是否正常
void Test09()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
    printf("\n");
    SLTEraseAfter(p);
    PrintSLlist(n1);
}
//测试删除pos位置函数是否正常
void Test10()
{
    SLlist* n1 = CreateSLlist(10);
    SLlist* p = SLTFind(n1, 3);
    SLTInsertAfter(p, 30);
    SLTInsert(&n1, p, 90);
    PrintSLlist(n1);
    printf("\n");
    SLlist* p2 = SLTFind(n1, 90);
    SLTErase(&n1, p2);
    PrintSLlist(n1);
}
//测试销毁函数是否正常
void Test11()
{
    SLlist* n1 = CreateSLlist(10);
    SLTDestroy(&n1);
    PrintSLlist(n1);
}
//主函数实现
int main()
{
    Test10();
    return 0;
}

【数据结构】单链表 — 纯C实现单链表

💌前言

一、定义

1.概念

2.特点

3.优点

4.缺点

5.结点定义

二、接口实现

1.创建链表结点

创建单个结点

创建链表

打印链表

测试创建功能

2.尾插尾删

尾部插入

尾部删除

尾插尾删测试

3.头插头删

头部插入

头部删除

头插头删测试

4.pos位的插入删除

查找pos位置

在pos位置前插入

在pos位置后插入

删除pos位置的数

删除pos位置后的数

pos位置上的插入删除测试

5.销毁链表

三、代码汇总

SLlist.h

SLlist.c

test.c

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】单链表 — 纯C实现单链表

💌前言

一、定义

1.概念

2.特点

3.优点

4.缺点

5.结点定义

二、接口实现

1.创建链表结点

创建单个结点

创建链表

打印链表

测试创建功能

2.尾插尾删

尾部插入

尾部删除

尾插尾删测试

3.头插头删

头部插入

头部删除

头插头删测试

4.pos位的插入删除

查找pos位置

在pos位置前插入

在pos位置后插入

删除pos位置的数

删除pos位置后的数

pos位置上的插入删除测试

5.销毁链表

三、代码汇总

SLlist.h

SLlist.c

test.c

热门文章

最新文章

相关课程

相关电子书