0
0

单链表详解

一、什么是链表

1、数据结构概要

数据结构就是用某种结构去储存数据：

1、物理结构(数据在内存中的存储)

2、逻辑结构(由人为想象出来的)

顺序表就是逻辑和物理都连续的一种线性表。说明白一点顺序表就是玩数组。

链表就是逻辑连续，物理不一定连续的线性表。如下图，逻辑上是利用指针将其串联起来的，物理上却是杂乱的，最后以NULL空指针结束。

2、功能

大致了解什么是链表后，我们还需要知道链表的大概的功能有哪些？

1、首先清楚它是用于储存数据的一种结构

2、尾部插入数据，尾部删除数据，头部插入数据，头部删除数据，任意位置的插入，任意位置的删除，查找数据位置，修改数据的功能。

二、实现链表

1、定义一个具有结点特征的结构体

因为结构体内储存的数据类型不是确定的，为了避免以后维护起来太麻烦，所幸将类型重定义一下。

在链表中这样的一个结构体类型称为一个结点，我们需要这个结点指向下一个结点，所以需要定义一个结点类型的指针。

typedef int SListDateType;
//结点
typedef struct SListNode
{
    SListDateType date;
    struct SListNode* Next;
}SListNode;

2、定义一个头指针

这是最简单的单链表结构，相当于是一个空单链表

3、实现尾插

实现尾插有两种情况：1、phead头指针为NULL。2、phead头指针为非空。

尾插代码实现如下：

void SListPushBack(SListNode** pphead, SListDateType x)
{
    //创建结点
    SListNode* newnode = BuySListNode(x);
    //第一种情况
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    //第二种情况
    else
    {
        SListNode* tail = *pphead;
        while (tail->Next != NULL)
        {
            tail = tail->Next;
        }

        tail->Next = newnode;
    }
}

4、结点的创建：

创建节点代码实现：

//创建一个结点
static SListNode* BuySListNode(SListDateType x)
{
    SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
    if (NewNode == NULL)
    {
        printf("开辟空间失败\n");
        exit(-1);
    }
    NewNode->date = x;
    NewNode->Next = NULL;

    return NewNode;
}

5、实现尾删

实现尾删分三种情况：1、phead头指针为空指针。2、phead头指针不为空指针，只有一个结点。3、phead不为空指针、有多个结点。

尾删代码实现：

//尾删
void SListPopBack(SListNode** pphead)
{
    //如果是空链表
    if (*pphead == NULL)
    {
        return;
    }
    //如果只有一个结点
    else if ((*pphead)->Next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    //如果有多个结点
    else
    {
        SListNode* prev = NULL;//前一个结点
        SListNode* tail = *pphead;//尾结点
        while (tail ->Next != NULL)
        {
            prev = tail;
            tail = tail->Next;
        }

        free(tail);
        tail = NULL;
        prev->Next = NULL;
    }
}

6、实现头插

实现头插分两种情况：1、phead == NULL。2、phead != NULL。

由图解分析：两种情况用代码实现其实是一种逻辑。

头插代码实现：

//头插
void SListPushFront(SListNode** pphead, SListDateType x)
{
    //创建结点
    SListNode* newnode = BuySListNode(x);
    newnode->Next = *pphead;
    *pphead = newnode;
}

7、实现头删

实现头删有三种情况：1、phead == NULL。2、phead != NULL ,有一个结点。3、phead != NULL,有多个结点。

又图解分析，后面两种也可划分为一种代码实现逻辑：1、phead == NULL。2、phead != NULL,一个节点 + 多个结点的情况。

头删代码实现：

//头删
void SListPopFront(SListNode** pphead)
{
    //1.phead == NULL
    //2.有一个结点 + 有多个结点
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode* cur = *pphead;
        *pphead = (*pphead)->Next;
        free(cur);
        cur = NULL;
    }
}

8、实现任意结点位置的后的插入

因为单链表的缺陷（后一个结点无法找到前一个结点）所以只能实现结点后的插入，无法实现结点前的插入。

这种功能的实现也有三种情况：

如下图解分析：

图解分析：后只有一个结点 + 有多个结点）的代码逻辑相同

任意插入代码实现：

//任意插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SListNode* cur = *pphead;
        while (cur->date != pos)
        {
            cur = cur->Next;
        }
        newnode->Next = cur->Next;//这里使用第二种避免找不到地址的方法
        cur->Next = newnode;
    }
}

9、实现任意结点位置后的删除

实现删除：3种情况：1、phead == NULL。 2、phead != NULL,一个结点。 3、phead != NULL,多个结点。

由图解分析：

任意删除代码实现：

//任意结点后删除
void SListEraseAfter(SListNode** pphead, SListDateType pos)
{
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->Next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode* cur = *pphead;
        while (cur->date != pos)
        {
            cur->Next;
        }
        SListNode* next = cur->Next;
        SListNode* nextnext = next->Next;
        free(next);
        next = NULL;
        cur->Next = nextnext;
    }
}

10、实现打印

由图解分析：三种情况下的开始。迭代，结束条件都是相同的，所以代码实现逻辑相同。

打印代码实现：

//打印
void SListPrint(SListNode* phead)
{
    SListNode* Cur = phead;
    while (Cur != NULL)//遍历
    {
        printf("%d->", Cur->date);
        Cur = Cur->Next;
    }
    printf("NULL\n");
}

11、实现查找某一数据的结点

查找代码实现：

SListNode* SListFind(SListNode* phead, SListDateType x)
{
    assert(phead);
    SListNode* cur = phead;
    while (cur)
    {
        if (cur->date == x)
        {
            return cur;
        }
        cur = cur->Next;
    }
    return NULL;
}

12、实现某一位置结点数据的修改

修改其实可以说和查找差不多，一模一样，只是在找到后，在对其的数据行修改即可。

修改数据代码实现：

//任意结点数据的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x)
{
    SListNode* cur = phead;
    while (cur->date != pos)
    {
        cur = cur->Next;
    }
    cur->date = x;
}

三、全部代码附上

SList.h部分：

#pragma once

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

typedef int SListDateType;
//结点
typedef struct SListNode
{
    SListDateType date;
    struct SListNode* Next;
}SListNode;
//尾插
void SListPushBack(SListNode** pphead, SListDateType x);
//尾删
void SListPopBack(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SListDateType x);
//头删
void SListPopFront(SListNode** pphead);
//打印
void SListPrint(SListNode* phead);
//查找
SListNode* SListFind(SListNode* phead, SListDateType x);
//任意结点后的插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x);
//任意结点后的删除
void SListEraseAfter(SListNode** pphead, SListDateType pos);
//任意位置的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x);

SList.c部分：

#define  _CRT_SECURE_NO_WARNINGS 1

#include "Slist.h"

//创建一个结点
static SListNode* BuySListNode(SListDateType x)
{
    SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
    if (NewNode == NULL)
    {
        printf("开辟空间失败\n");
        exit(-1);
    }
    NewNode->date = x;
    NewNode->Next = NULL;

    return NewNode;
}
//打印
void SListPrint(SListNode* phead)
{
    SListNode* Cur = phead;
    while (Cur != NULL)//遍历
    {
        printf("%d->", Cur->date);
        Cur = Cur->Next;
    }
    printf("NULL\n");
}
//尾插
void SListPushBack(SListNode** pphead, SListDateType x)
{
    //创建结点
    SListNode* newnode = BuySListNode(x);
    //第一种情况，phead == NULL
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    //第二种情况，phead != NULL
    else
    {
        SListNode* tail = *pphead;
        while (tail->Next != NULL)
        {
            tail = tail->Next;
        }

        tail->Next = newnode;
    }
}

//尾删
void SListPopBack(SListNode** pphead)
{
    //如果是空链表
    if (*pphead == NULL)
    {
        return;
    }
    //如果只有一个结点
    else if ((*pphead)->Next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    //如果有多个结点
    else
    {
        SListNode* prev = NULL;//前一个结点
        SListNode* tail = *pphead;//尾结点
        while (tail ->Next != NULL)
        {
            prev = tail;
            tail = tail->Next;
        }

        free(tail);
        tail = NULL;
        prev->Next = NULL;
    }
}

//头插
void SListPushFront(SListNode** pphead, SListDateType x)
{
    //创建结点
    SListNode* newnode = BuySListNode(x);
    newnode->Next = *pphead;
    *pphead = newnode;
}
//头删
void SListPopFront(SListNode** pphead)
{
    //1.phead == NULL
    //2.有一个结点 + 有多个结点
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode* cur = *pphead;
        *pphead = (*pphead)->Next;
        free(cur);
        cur = NULL;
    }
}
//查找
SListNode* SListFind(SListNode* phead, SListDateType x)
{
    assert(phead);
    SListNode* cur = phead;
    while (cur)
    {
        if (cur->date == x)
        {
            return cur;
        }
        cur = cur->Next;
    }
    return NULL;
}
//任意插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SListNode* cur = *pphead;
        while (cur->date != pos)
        {
            cur = cur->Next;
        }
        newnode->Next = cur->Next;
        cur->Next = newnode;
    }
}
//任意结点后删除
void SListEraseAfter(SListNode** pphead, SListDateType pos)
{
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->Next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode* cur = *pphead;
        while (cur->date != pos)
        {
            cur->Next;
        }
        SListNode* next = cur->Next;
        SListNode* nextnext = next->Next;
        free(next);
        next = NULL;
        cur->Next = nextnext;
    }
}
//任意结点数据的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x)
{
    SListNode* cur = phead;
    while (cur->date != pos)
    {
        cur = cur->Next;
    }
    cur->date = x;
}

text.c部分：

#define  _CRT_SECURE_NO_WARNINGS 1

#include "Slist.h"

void TextSList(SListNode* phead)
{
    SListPushBack(&phead, 1);
    SListPushBack(&phead, 2);
    SListPushBack(&phead, 3);
    SListPrint(phead);
    SListPushFront(&phead, 22);
    SListPrint(phead);
    SListPopFront(&phead);
    SListPrint(phead);
}
void TextSListFind(SListNode* phead)
{
    SListPushBack(&phead, 1);
    SListPushBack(&phead, 2);
    SListPushBack(&phead, 3);
    SListPrint(phead);
    SListPushFront(&phead, 22);
    SListPrint(phead);
    SListPopFront(&phead);
    SListPrint(phead);
    SListNode* ret = SListFind(phead, 3);
    if (ret != NULL)
    {
        ret->date = 100;
    }

    SListPrint(phead);

    SListChange(phead, 1, 1000);
    SListPrint(phead);
    SListEraseAfter(&phead, 1000);
    SListPrint(phead);
    SListInsertAfter(&phead, 1000, 2);
    SListPrint(phead);
    CSList(&phead);
    SListPrint(phead);
}
int main()
{
    //头指针：最简单的单链表
    //SListNode* pList = NULL;
    SListNode* phead = NULL;

    //TextSList(phead);
    TextSListFind(phead);

    return 0;
}

运行结果附上：

标签： 链表 数据结构 散列表
本文转载自: https://blog.csdn.net/weixin_63246064/article/details/122753974
版权归原作者 绅士·永 所有， 如有侵权，请联系我们删除。
登录后发布评论

“单链表详解”的评论:

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

C#与C++交互开发系列（二十）：跨进程通信之共享内存（Shared Memory）

hadoop技术实验- 第4章 HBase 开发：使用Java操作HBase

智能对话微信前端小程序设计与开发

前端配置开发环境：新电脑配置前端开发环境，Vue开发环境配置的详细过程

SpringBoot集成MQTT服务器和客户端并通过WebSocket将消息实时发送到前端（本地搭建MQTT服务器）

idea | 搭建 SpringBoot 项目之配置 Maven

Python毕业设计选题：基于django+vue的全国民宿信息管理系统

文章导航