AIPRO AIPRO

数据结构入门阶段的单链表剖析

7小时前发布 gsjqwyl
2 0 0

文章标题：

数据结构学习之初的单链表深度解析

文章内容：

在这里插入图片描述

文章目录

  • 单链表
    • 1. 链表的概念与结构
    • 2. 单链表的实现
    • 1.定义结点
    • 2.打印数据
    • 3.申请新节点
    • 4.尾插操作
    • 5.头插操作
    • 6.尾删操作
    • 7.头删操作
    • 8.查找节点
    • 9.指定位置前插入
    • 10.指定位置后插入
    • 11.指定位置前删除
    • 12.指定位置后删除
    • 13.链表销毁
    • 3.程序源码

单链表

1. 链表的概念与结构

概念阐释：链表属于一种在物理存储层面上并非连续且非顺序排列的存储构造，数据元素的逻辑顺序是借助链表内部的指针连接次序来得以实现的。

在这里插入图片描述

链表的构造类似于火车车厢的组合，在客运淡季时车次的车厢数量会相应减少，而在旺季则会额外添加几节车厢。当需要增减某节车厢时，不会对其他车厢造成影响，每节车厢都是独立存在的个体。设想每节车厢的车门都处于锁闭状态，且需要特定的钥匙才能开启，若一次只能携带一把钥匙，该如何从车头走到车尾呢？最简便的方法是让每节车厢内都放置下一节车厢的钥匙。

在链表中，每一个“车厢”有着怎样的形态呢？

在这里插入图片描述

与顺序表不同之处在于，链表内的每一个“车厢”都是独立申请得来的空间，我们将其称作“结点/节点”。节点主要由两部分构成：当前节点需要保存的数据以及用于保存下一个节点地址的指针变量。图中指针变量plist存储的是第一个节点的地址，我们称此时plist“指向”第一个节点，若想要让plist“指向”第二个节点，只需将plist存储的内容修改为对应的地址即可。

为何还需要指针变量来存储下一个节点的位置呢？这是因为链表中每个节点都是独立申请的（即当需要插入数据时才去申请一块节点空间），我们需要通过指针变量来保存下一个节点的位置，从而能够从当前节点找到下一个节点。结合之前所学的结构体知识，我们可以构建出每个节点对应的结构体代码。假设当前要保存的是整型数据，对应的结构体如下：

struct SListNode
{
 int data; // 节点数据 
 struct SListNode* next; // 指针变量用于保存下一个节点的地址 
};

当我们想要保存一个整型数据时，实际上是向操作系统申请一块内存，这块内存不仅要存储整型数据，还要存储下一个节点的地址（当下一个节点不存在时，存储的地址为空）。当我们要从第一个节点遍历到最后一个节点时，只需从前一个节点获取下一个节点的地址（即下一个节点的“钥匙”）即可。那么在给定的链表结构中，如何实现从节点头到节点尾的打印呢？

在这里插入图片描述

2. 单链表的实现

1.定义结点

typedef int SLTDataType;

typedef struct SListNode // s代表single
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

2.打印数据

void SLTPrint(SLTNode* phead)
{
    SLTNode* pcur = phead;
    while (pcur) // pcur != NULL
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

3.申请新节点

SLTNode* SLTBuyNode(SLTDataType x)
{
    SLTNode* newnode =  (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    // 申请成功
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

4.尾插操作

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead); // pphead不能为空，不能对空指针解引用
    // 处理空链表和非空链表情况
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        // 寻找尾节点
        SLTNode* ptail = *pphead;
        while (ptail->next)
        {
            ptail = ptail->next;
        }
        // ptail指向尾节点
        ptail->next = newnode;
    }
}

5.头插操作

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

6.尾删操作

// 尾删
void SLTPopBack(SLTNode** pphead)
{
    // 链表不能为空
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) // ->的优先级高于*，所以要加括号
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        // 寻找尾节点及其前驱节点
        SLTNode* prev = *pphead; // 要删除节点的前驱
        SLTNode* ptail = *pphead; // 要删除的节点
        while (ptail->next)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        // 释放尾节点并更新前驱节点的next指针
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

7.头删操作

void SLTPopFront(SLTNode** pphead)
{
    // 链表不能为空
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next; // 记得加括号
    free(*pphead);
    *pphead = next;
}

8.查找节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* pcur = phead;
    while (pcur) // pcur != NULL
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    // pcur == NULL
    return NULL;
}

9.指定位置前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead && *pphead); // 若*pphead为空，则pos也为空
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    if (pos == *pphead)
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        SLTNode* prev = *pphead; // 寻找pos的前驱节点
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        // 进行节点插入操作
        prev->next = newnode;
        newnode->next = pos;
    }
}

10.指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next; // 注意顺序不能交换
    pos->next = newnode;
}

11.指定位置前删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);
    SLTNode* prev = *pphead; // 寻找pos的前驱节点
    if (pos == *pphead)
    {
        // 执行头删操作
        SLTPopFront(pphead);
    }
    while (prev->next != pos)
    {
        prev = prev->next;
    }
    // 进行节点删除操作
    prev->next = pos->next;
    free(pos);
    pos = NULL;
}

12.指定位置后删除

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = pos->next->next;
    free(del);
    del->next = NULL;
}

13.链表销毁

void SLTDestroy(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* pcur = *pphead;

    while (pcur)
    {
        SLTNode* next = (*pphead)->next;
        free(pcur);
        pcur = next;
    }
    // pcur为空，将头指针置为NULL
    *pphead = NULL;
}

3.程序源码

共分三个文件

SLTist.h 函数的声明

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

// 定义节点结构
// 数据 + 指向下一个节点的指针
typedef int SLTDataType;

typedef struct SListNode // s single
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);
// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
// 尾删
void SLTPopBack(SLTNode** pphead);
// 头删
void SLTPopFront(SLTNode** pphead);

// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在头节点前插入，头节点可能改变
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
// 销毁链表
void SLTDestroy(SLTNode** pphead);

SList.c 函数的实现

“`c

define _CRT_SECURE_NO_WARNINGS

include”SList.h”

void SLTPrint(SLTNode phead)
{
SLTNode pcur = phead;
while (pcur) // pcur != NULL
{
printf(“%d->”, pcur->data);
pcur = pcur->next;
}
printf(“NULL\n”);
}
SLTNode SLTBuyNode(SLTDataType x)
{
SLTNode newnode = (SLTNode)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror(“malloc fail!”);
exit(1);
}
// 申请成功
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 尾插
void SLTPushBack(SLTNode pphead, SLTDataType x)
{
assert(pphead); // pphead不能为空，不能对空指针解引用
// 处理空链表和非空链表情况
SLTNode newnode = SLTBuyNode(x);
if (pphead == NULL)
{
pphead = newnode;
}
else
{
// 寻找尾节点
SLTNode ptail = pphead;
while (ptail->next)
{
ptail = ptail->next;
}
// ptail指向尾节点
ptail->next = newnode;
}
}
void SLTPushFront(SLTNode pphead, SLTDataType x)
{
assert(pphead);
SLTNode newnode = SLTBuyNode(x);
newnode->next = pphead;
*pphead = newnode;
}

// 尾删
void SLTPopBack(SLTNode pphead)
{
// 链表不能为空
assert(pphead && pphead);
if ((pphead)->next == NULL) // ->的优先级高于，所以要加括号
{
free(pphead);
pphead = NULL;
}
else
{
// 寻找尾节点及其前驱节点
SLTNode prev = pphead; // 要删除节点的前驱
SLTNode ptail = *pphead; // 要删除的节点
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
// 释放尾节点并更新前驱节点的next指针
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
// 头删
void SLTPopFront(SLTNode pphead)
{
// 链表不能为空
assert(pphead && pphead);
SLTNode next = (pphead)->next; // 记得加括号
free(pphead);
pphead = next;
}
// 查找
SLTNode SLTFind(SLTNode phead, SLTDataType x)
{
SLTNode pcur = phead;
while (pcur) // pcur != NULL
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
// pcur == NULL
return NULL;
}

void SLTInsert(SLTNode pphead, SLTNode pos, SLTDataType x)
{
assert(pphead && pphead); // 若pphead为空，则pos也为空
assert(pos);
SLTNode newnode = SLTBuyNode(x);
if (pos == pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode prev = *pphead; // 寻找pos的前驱节点
while (prev->next != pos)
{
prev = prev->next;
}
// 进行节点插入操作
prev->next = newnode;
newnode->next = pos;
}
}

void SLTInsertAfter(SLTNode pos, SLTDataType x)
{
assert(pos);
SLTNode newnode = SLTBuyNode(x);
newnode->next = pos->next; // 注意顺序不能交换
pos->next = newnode;
}

void SLTErase(SLTNode pphead, SLTNode pos)
{
assert(pphead && pphead);
SLTNode prev = pphead; // 寻找pos的前驱节点
if (pos == *pphead)
{
// 执行头删操作
SLTPopFront(pphead);
}
while (prev->next != pos)
{
prev = prev->next;
}
// 进行节点删除操作
prev->next = pos->next;
free(pos);
pos = NULL;
}

void SLTEraseAfter(SLTNode pos)
{
assert(pos && pos->next);
SLTNode del = pos->next;
pos->next = pos->next->next;
free(del);
del->next = NULL;
}

© 版权声明
文章版权归作者所有，未经允许请勿转载。
上一篇

没有更多了...

下一篇

没有更多了...

相关文章

数据结构中栈的全面实现揭秘
gsjqwyl
8
2025年最新IDEA激活码永久破解教程 – 支持JetBrains全家桶2099年授权
gsjqwyl
11
JavaScript 解析 URL 查询参数的完整指南
gsjqwyl
50

Java 京东招聘题解
gsjqwyl
7
🚀 2025最新PyCharm永久激活教程｜破解补丁+激活码一键搞定（支持2099年）
gsjqwyl
228
🚀 2025年最新IDEA激活码分享 | 永久破解IDEA终极教程（附破解补丁）
gsjqwyl
13

暂无评论

暂无评论...
添加小工具
点此为“正文侧边栏”添加小工具
Copyright © 2025 AIPRO 陇ICP备2022001249号-4