数据结构初阶之链表的介绍与单链表的实现

server/2024/12/16 14:05:09/

一、引文

从数据结构初阶之顺序表的介绍与动态顺序表的实现-CSDN博客中我们知道了动态顺序表并且实现了动态顺序表,但是对于动态顺序表存在以下几个不足:

(1)中间 / 头部的插入删除操作时间复杂度为 O (N)
(2)扩容需要申请新空间,拷贝旧数据,释放旧空间,这一系列操作会有不小的消耗。(扩容一般是呈 2 倍的增长,这势必会导致一定的空间浪费。比如当前容量为 100,满了以后会扩容到 200,我们再继续插入了 5 个数据,后面没有数据插入了,那么就浪费了 95 个数据空间)

那么该如何解决这些问题呢?接下来我们介绍单链表就很好地解决上述问题,正文启:

二、链表的概念和结构

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

链表逻辑结构一定是线性的,物理结构不一定是线性的。

1、结点

与顺序表不同的是,链表里的每块部分都是独立申请下来的空间,我们称之为 “结点 / 节点”。
结点的组成主要有两个部分:

(1)当前结点要保存的数据;

(2)保存下一个结点的地址(指针变量)。
图中指针变量 plist 保存的是第一个结点的地址,我们称 plist 此时 “指向” 第一个结点,如果我们希望 plist “指向” 第二个结点时,只需要修改 plist 保存的内容为第二个结点的地址即可。
链表中每个结点都是独立申请的(即需要插入数据时才去申请一块结点的空间),我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

2、链表的性质

(1)链式机构在逻辑上是连续的,在物理结构上不一定连续
(2)结点一般是从上申请的空间;
(3)从堆上申请来的空间,是按照一定策略分配出来的,每次申请的空间可能连续,可能不连续

三、单链表的实现

项目创建的时候,要创建一个头文件(.h)SList.h ,两个源文件(.c)SList.ctest.c 。SList.h 用于定义结构体和声明函数;SList.c 用于实现函数;test.c 用于测试函数,每实现一个函数要进行相应的测试。编写代码过程中要勤测试,避免写出大量代码后再测试,如果出现问题,问题无从定位。

1、SList.h:

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

//定义单链表(结点)结构体

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

//声明打印链表的函数
void Print_SList(SLTNode* phead);

//声明创建一个结点的函数
SLTNode* Create_SListNode(SLTDataType x);

//声明尾插一个结点到单链表的函数
void Push_Back_SList(SLTNode** pphead, SLTDataType x);

//声明头插一个结点到单链表的函数
void Push_Front_SList(SLTNode** pphead, SLTDataType x);

//声明尾删单链表的一个结点的函数
void Pop_Back_SList(SLTNode** pphead);

//声明头删单链表的一个结点的函数
void Pop_Front_SList(SLTNode** pphead);

//声明查找指定结点的函数
SLTNode* Find_SList(SLTNode* phead, SLTDataType x);

//声明在指定位置之前插入数据的函数
void Insert_Front_SList(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//声明在指定位置之后插入数据的函数
void Insert_Back_SList(SLTNode* pos, SLTDataType x);

//声明删除指定结点的函数
void Del_SList(SLTNode** pphead, SLTNode* pos);

//声明删除pos之后的结点的函数
void Del_Back_SList(SLTNode* pos);

//声明销毁链表的函数
void Destroy_SList(SLTNode** pphead);

2、SList.c:

#include"SList.h"

//实现打印链表的函数
void Print_SList(SLTNode* phead)
{
    SLTNode* pcur = phead;
    while (pcur != NULL)
    {
        printf("%d -> ", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}
//实现创建一个结点的函数
SLTNode* Create_SListNode(SLTDataType x)
{
    //动态申请一个结点的空间
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    //申请失败直接退出
    if (!newnode)
    {
        perror("malloc fail");
        exit(1);
    }
    //申请成功将新节点的data赋值为x,并将next置为NULL
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

//实现尾插一个结点到单链表的函数
void Push_Back_SList(SLTNode** pphead, SLTDataType x)
{
    //pphead不能为NULL,即Push_Back_SList(NULL, x)不被允许
    assert(pphead);

    //先申请一个新的结点
    SLTNode* newnode = Create_SListNode(x);
    //如果链表为空,则新的结点就是头结点
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    //如果链表不为空,就先找到尾结点,再把尾结点和新节点链接起来
    else
    {
        SLTNode* ptail = *pphead;
        while (ptail->next)
        {
            ptail = ptail->next;
        }
        ptail->next = newnode;
    }
}

//实现头插一个结点到单链表的函数
void Push_Front_SList(SLTNode** pphead, SLTDataType x)
{
    //pphead不能为NULL,即Push_Front_SList(NULL, x)不被允许
    assert(pphead);

    //先申请一个新的结点
    SLTNode* newnode = Create_SListNode(x);

    //使新节点的next指向头结点
    newnode->next = *pphead;

    //更新头结点为新的结点
    *pphead = newnode;
}

//实现尾删单链表的一个结点的函数
void Pop_Back_SList(SLTNode** pphead)
{
    //pphead不能为NULL,即Pop_Back_SList(NULL)不被允许;*pphead不能为空,即不能对空链表进行尾删
    assert(pphead && *pphead);

    //尾删的结点正好是头结点
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    
    // 尾删的结点不是头结点
    else
    {
        //定义一个prev指针负责找到尾结点的前驱结点,ptail负责找到尾结点
        SLTNode* prev = NULL;
        SLTNode* ptail = *pphead;
        while (ptail->next)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        prev->next = NULL;
        free(ptail);
        ptail = NULL;
    }
}

//实现头删单链表的一个结点的函数
void Pop_Front_SList(SLTNode** pphead)
{
    //pphead不能为NULL,即Pop_Front_SList(NULL)不被允许;*pphead不能为空,即不能对空链表进行尾删
    assert(pphead && *pphead);

    //pcur来记住头结点的地址
    SLTNode* pcur = *pphead;
    //让头结点移动到下一个节点处
    *pphead = (*pphead)->next;
    
    free(pcur);
    pcur = NULL;
}

//实现查找指定结点的函数
SLTNode* Find_SList(SLTNode* phead, SLTDataType x)
{
    SLTNode* pcur = phead;
    while (pcur)
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

//实现在指定位置之前插入结点的函数
void Insert_Front_SList(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    //pphead不能为NULL,即Insert_Front_SList(NULL, pos,x)不被允许;pos不能为NULL
    assert(pphead && pos);

    //如果pos就是头结点,就是头插
    if (pos == *pphead)
    {
        Push_Front_SList(pphead, x);
    }
    //pos不是头结点
    else
    {        
        //创建一个新节点
        SLTNode* newnode = Create_SListNode(x);

        //ptail找pos的前驱结点
        SLTNode* ptail = *pphead;
        while (ptail->next != pos)
        {
            ptail = ptail->next;
        }
        newnode->next = pos;
        ptail->next = newnode;
    }
}

//实现在指定位置之后插入数据的函数
void Insert_Back_SList(SLTNode* pos, SLTDataType x)
{
    //pphead不能为NULL,即Insert_Back_SList(NULL, pos,x)不被允许;pos不能为NULL
    assert(pos);

    //创建一个新节点
    SLTNode* newnode = Create_SListNode(x);

    //下面两行不能交换位置,如果交换位置 ptail->next = newnode->next; 先使ptail->next指向newnode,再执行 newnode->next = ptail->next; newnode会指向它本身
    newnode->next = pos->next;
    pos->next = newnode;
}

//实现删除指定结点的函数
void Del_SList(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    
    //要删除的pos就是头结点,就是头删
    if (pos == *pphead)
    {
        Pop_Front_SList(pphead);
    }
    //要删除的pos不是头结点
    else
    {
        SLTNode* ptail = *pphead;
        while (ptail->next != pos)
        {
            ptail = ptail->next;
        }
        ptail->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

//实现删除pos之后的结点的函数
void Del_Back_SList(SLTNode* pos)
{
    assert(pos && pos->next);
    
    //tmp用来记住pos之后的结点
    SLTNode* tmp = pos->next;
    pos->next = tmp->next;

    free(tmp);
    tmp = NULL;
}

//实现销毁链表的函数
void Destroy_SList(SLTNode** pphead)
{
    //pphead不能为NULL,并且*pphead不能是空链表
    assert(pphead && *pphead);

    SLTNode* ptail = *pphead;
    SLTNode* pcur = ptail;
    while (ptail)
    {
        ptail = ptail->next;
        free(pcur);
        pcur = ptail;
    }
    *pphead = NULL;
}

test.c自行测试,这里不予提供。

四、回归

我们再回到引文的部分,对于动态顺序表的问题就能很好地解决了,单链表中间 / 头部的插入删除操作时间复杂度为 O (1);单链表不需要扩容,即用即增;链表没有额外的空间浪费

但是我们需要明确的是没有最好的数据结构,只有在特定场景下最适合的数据结构!


http://www.ppmy.cn/server/150647.html

相关文章

netty 知识点 简要介绍

netty简介 netty是一款高性能的网络应用框架&#xff0c;相比较原生的socket编程&#xff0c;它的api更加简单、易用&#xff0c;它对原生的tcp connection进行了包装&#xff0c;提供了channel、channelhandler、编解码器等概念。 线程组 netty中的线程组包括bossgroup和wo…

优化 Vue 3 开发体验:配置 Vite 使用 WebStorm 作为 Vue DevTools 的默认编辑器

优化 Vue 3 开发体验&#xff1a;配置 Vite 使用 WebStorm 替代 VS Code 作为 Vue DevTools 的默认编辑器 在 Vue 3 项目开发中&#xff0c;合理配置开发工具可以大大提升我们的工作效率。本文将介绍如何配置 Vite&#xff0c;使其在使用 Vue DevTools 时将默认编辑器从 VS Co…

单片机:实现流水灯(附带源码)

要详细讲解如何使用单片机实现流水灯&#xff0c;我们可以从以下几个方面深入探讨&#xff1a; 单片机基础概念和工作原理流水灯的硬件实现单片机程序设计及实现流水灯的不同实现方式常见的错误与调试总结与扩展 接下来&#xff0c;我们将从这几个方面逐一深入讲解。 1. 单片…

推荐一种全新的图像修复算法 :PMRF!实现高质量修复图像,降低图像失真还原跟自然逼真度!

PMRF&#xff08;Posterior-Mean Rectified Flow&#xff09; 是一种全新的图像修复算法&#xff0c;旨在实现高质量的图像恢复。 它不仅可以生成自然逼真的修复图像&#xff0c;还能大大降低图像失真&#xff0c;为图像的还原和真实感设立了新的标准。相比于当前的许多图像修…

Coding Caprice - dynamic programming11

1143. 最长公共子序列 class Solution { public:int longestCommonSubsequence(string text1, string text2) {int t1 text1.size();int t2 text2.size();vector<vector<int>> dp(t11, vector<int> (t21, 0));for(int i1; i<t11; i){for(int j1; j<…

mysql常见知识点介绍及解释

以下是一个 MySQL 知识点文档&#xff0c;包含了一些常见的知识点介绍和解释&#xff1a; 一、数据库基础 数据库的概念&#xff1a;数据库是存储数据的仓库&#xff0c;用于管理和组织数据。关系型数据库&#xff1a;MySQL 是一种关系型数据库管理系统&#xff0c;它使用表格…

0002.基于springboot +layui二手物品交易平台

适合初学同学练手项目&#xff0c;部署简单&#xff0c;代码简洁清晰&#xff1b; 注:当前项目架构使用前后端未分离哦&#xff01; 一、系统架构 前端&#xff1a;layui| html 后端&#xff1a;springboot | mybatis-plus 环境&#xff1a;jdk1.8 | mysql | maven 二、代…

CALMM-Drive:首个引入置信度感知的大多模态模型驱动的自动驾驶框架

导读&#xff1a; 本文提出的CALMM-Drive&#xff0c;它是首个引入置信度感知大型多模态模型&#xff08;LMM&#xff09;驱动的自动驾驶框架&#xff0c;通过采用Top-K置信度引导&#xff0c;能够生成多个候选决策及其置信度级别。在nuPlan闭环仿真环境中的评估结果表明&#…