(纯c)数据结构之------>链表(详解)

news/2024/2/21 10:23:48

目录

一.  链表的定义

        1.链表的结构.

        2.为啥要存在链表及链表的优势.

二. 无头单向链表的常用接口

        1.头插\尾插

        2.头删\尾删

        3.销毁链表/打印链表

        4.在pos位置后插入一个值

        5.消除pos位置后的值

        6.查找链表中的值并且返回它的地址

        7.创建一个动态开辟的结点

三.顺序表与链表的优缺点对比.


        文章开始->:

    一.链表的定义

        首先在学习单链表之前我们已近学过顺序表这一数据结构了,我们知道在使用顺序表的时候,当我们空间不够的时候我们需要扩容,还有在我们进行头插头删的时候我们需要移动元素,这时进行这些操作的时候是非常浪费时间的,并且扩容的时候还有可能浪费一定的空间当然这也是顺序表的缺点,而为了解决这些麻烦我们就弄出来了另外一个数据结构-->(链表)

        链表的定义:在逻辑结构上元素是连续的,但是实际的物理结构上链表是非连续非顺序的存储结构,数据元素的逻辑顺序其实是通过指针来连接的。

        下面就是正常的逻辑结构

 

        所以链表这种结构可以很简单的解决顺序表的问题,他在管理数据的时候并不需要扩容,而是当我们需要空间的时候他会取开辟一块空间然后我们只需要去改变指针的指向就可以将数据给连接起来了,这也省去了移动元素的时间。

        总结单链表的优点:单链表在使用内存空间的时候并不需要想顺序表那样进行扩容,而是我们需要空间的时候会自动去内存中开辟一块空间,也不需要再插入元素的时候移动元素,我们只需要改变指针的指向就可以实现链表逻辑上的顺序管理了。

        链表其实最大的好处就是可以进行头插和头删.

        下图就是我们插入元素时候的操作:->

        

 这样我们就不需要移动元素只需要改变指针的指向就行了。

        

接下来就是我们的重点进入常用接口的详细讲解-->

二.无头单链表的常用接口

      首先我们要理解的就是无头:所谓的无头就是我们并没有先申请一个结点,而是我们的头指针直接指向第一个节点,如果链表是空的那么我们我们的头指针指向的是空指针 。

        首先我们来看一看链表的结构

           在逻辑上-->

        在实际上-->

        

         实际上我们内存当中并没有指针指向的说法,只是我们为了方便理解链表这一数据结构而引入进来的。

链表定义的代码如下:

 typedef int SlistDataType;
    typedef struct Slist
{
    struct Slist* next;
    SlistDataType data;
}ST;

1.销毁链表/打印链表:   在这里我们要注意就是实参与形参的区别不然我们的操作可能会出现问题,打印的话我们直接遍历就行。

        这个接口是必须要有,因为我们在创建链表之前肯定得先有链表这一结构,而销毁链表是为了防止我们程序出现内存泄漏的问题。

        销毁链表:因为我们所申请的空间是在堆区上开辟的空间,而堆区上开辟的空间需要我们自己来释放空间,并且链表所开辟的空间并不是一个连续块的空间,所以我们需要来遍历链表这样保证我们将我们所开辟的空间来进行释放完整,防止内存泄漏。

        

void DestorySlist(STNode* plist)
{assert(plist);//这里我们需要一个一个的删除链表的结点while (plist != NULL){STNode* newplist = plist->next;//存放下一个结点free(plist);plist = newplist;}}

        打印链表:我们只需要遍历到结点为空的情况就行了

        下面是打印的代码:

        

void PrintSlist(STNode* plist)
{assert(plist);while (plist != NULL){printf("%d->", plist->data);plist = plist->next;}printf("NULL\n");
}

     

  2.动态开辟一个结点:在我们进行插入有关操作的时候我们需要申请一块空间来存放要插入的值,所以这一步操作也是不能省略的:

        我们直接上代码:

        

STNode* BuySlistNode(SlistDataType x)
{STNode* newnode = (STNode*)malloc(sizeof(STNode));//判断开辟的空间成功没if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//这样设计可以使得我们最后一个结点不需要在进行单独的设空return newnode;}

 3.尾插\头插:这里我们需要用到二级指针,因为我们知道改变结构体需要结构体指针,而改变结构体指针,我们需要结构体指针的指针,即二级指针来使用。当我们在进行尾插的第一个插入的时候,我们需要改变结构体指针,所以得用二级指针。,而头插每次都需要改变结构体指针

        下面代码:尾插

        

//注意二级指针
void PushBackSlist(STNode** pplist, SlistDataType x)
{STNode* newnode = BuySlistNode(x);if (*pplist == NULL){//插入第一个*pplist = newnode;}else{STNode* tail = *pplist;//我们得先找尾指针while(tail->next!=NULL){ tail = tail->next;}tail->next = newnode;}
}

        尾插的图片:

     

 

  头插代码:在这里我们需要注意的是在进行改变指针的时我们需要先进行将新节点的next指针先指向头,让后在将头改变,如果反了的话我们会使newnode->next指向自身。

        

void PushFrontSlist(STNode** pplist, SlistDataType x)
{STNode* newnode = BuySlistNode(x);newnode->data = x;newnode->next = *pplist;*pplist = newnode;}

        头插图:

4.头删/尾删

        头删:我们首先在删除之前判断链表是否为空,如果为空我们就会报错,如果不为空则会继续进行操作,在这里当链表中只有一个结点的时候,那么我们就需要修改结构体指针了。

        下面是代码:

void PopFrontSlist(STNode** pplist)
{//为空assert(*pplist);//一个结点if ((*pplist)->next == NULL){STNode* del = *pplist;free(del);*pplist = NULL;}//多个结点else{STNode* del = *pplist;STNode* newnode = (*pplist)->next;free(del);*pplist = newnode;}
}

        测试时图片:

        

         尾删:这里也要先判断链表是否为空,然后如果只有一个元素我们需要改变结构体指针,其他的我们则只需要将前面一个的指针指向NULL,就行了。

        尾删代码:

        

void PopBackSlist(STNode** pplist)
{//判断是否为空assert(*pplist);//一个结点if ((*pplist)->next == NULL){STNode* del = *pplist;free(del);*pplist = NULL;}else{STNode* cur = *pplist;//找前一个while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

        尾删测试:

        

         5.链表的查找接口:如果找到了则返回这个值的地址,如果没找到则打印未找到,思路:我们只需要遍历数组即可。

STNode* FindSlist(STNode* plist, SlistDataType x)
{assert(plist);STNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}printf("未找到\n");return NULL;
}

        测试:

        

         6.在pos位置后插入,与消除pos位置后的接口

        插入:首先我们得判断pos是否有意义,如果有则代表有意义,我们就保存pos位置后的结点,然后pos->next=newnode,newnode->next=posafter;

        代码:

void InsertafterSlist( STNode* pos, SlistDataType x)
{assert(pos);STNode* posafter = pos->next;STNode* newnode = BuySlistNode(x);pos->next = newnode;newnode->next = posafter;
}

        测试:

                

      删除pos后面的值:我们先判断pos是否有意义,有意义直接将pos后面的free掉,pos->next=NUll;

        代码:

        

void EraseafterSlist(STNode* pos)
{assert(pos);STNode* posafter = pos->next;pos->next =posafter->next ;free(posafter);}

         测试图:

        

        注意:这后面三个接口通常都是一起使用的。

        到这里我们常用的接口已近讲解完毕了,接下来进行最后一部分的讲解--->

    三:顺序表与链表优缺点对比

        顺序表的优点:顺序表可以随机访问开辟空间的地址,且在内存当中是连续的一块空间,,支持随机访问,缓存利用率比较高。

                       缺点:再进行插入操作的时候需要扩容,而扩容其实底层原理是很麻烦的,这里可以看我前面写过的动态内存开辟的那一张设计realloc扩容,这里就不详细介绍了,且扩容之后还会浪费空间,其次是在进行头删/头插的时候我们需要移动元素,这里会导致很多的空间被持续使用,浪费了大量空间,而且扩容可能扩的非常多,任意插入与删除元素的效率低,时间复杂度为O(n).

        顺序表适合频繁访问的场景。

        链表的优点:再进行任意位置插入与删除的时候,不需要挪动元素时间复杂度为O(1),也不需要扩容操作,只需新增一个结点就行了,然后改变指针的指向就行了。        

        缺点:就是不能随机访问内存。且缓存利用率低

        链表适用于任意位置插入与删除的情况。

        总而言之:数据结构各有各的优点,也各有各的缺点,这些数据结构适合应用的场景不同而已。

                 ~~本章结束,感谢大家的耐心观看,如果你觉得有用的话,可以点个赞哦!

                

 


http://www.ppmy.cn/news/1062432.html

相关文章

网络字节序——TCP接口及其实现简单TCP服务器

网络字节序——TCP接口及其实现简单TCP服务器 文章目录 网络字节序——TCP接口及其实现简单TCP服务器简单TCP服务器的实现1. 单进程版:客户端串行版2. 多进程版:客户端并行版netstat查看网络信息3.多线程版:并行执行log.hpp 守护进程fg、bg s…

13.Oracle中nvl()与nvl2()函数详解

Oracle中nvl()与nvl2()函数详解: 函数nvl(expression1,expression2)根据参数1是否为null返回参数1或参数2的值; 函数nvl2(expression1,expression2,expression3)根据参数1是否为null返回参数2或参数3的值 1.nvl:根据参数1是否为null返回参数…

【安卓】自定义View实现画板涂鸦等功能

一、实现效果 二、代码 1、MainActivity.class package com.lsl.mydrawingboarddemo;import androidx.appcompat.app.AppCompatActivity; import androidx.core.content.ContextCompat;import android.os.Bundle; import android.os.Handler; import android.view.View; impo…

2023年高教社杯数学建模思路 - 复盘:光照强度计算的优化模型

文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米,宽为12米&…

Java性能分析中常用命令和工具

当涉及到 Java 性能分析时,有一系列强大的命令和工具可以帮助开发人员分析应用程序的性能瓶颈、内存使用情况和线程问题。以下是一些常用的 Java 性能分析命令和工具,以及它们的详细说明和示例。 以下是一些常用的性能分析命令和工具汇总: …

c语言中编译过程与预处理

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、c语言的编译与链接1、编译与链接概述2、编译与链接详解 二、c语言预处理1.c语言中内置的预定义符号2、#define定义标识符3、#define定义宏4、#define 替换规…

Arduino驱动四位0.36英寸共阴数码管模块

目录 一、简介二、参数性能三、电路原理图四、使用方法 一、简介 点击图片购买 四位0.36英寸共阴数码管模块由一个12引脚的0.36英寸红色共阴数码管和一个TM1650驱动芯片构成,大大减少了驱动引脚与连线,只需要四根引线IIC即可控制数码管的显示。TM11650是…

如何开发一款唯一艺术平台 区块链 /数字藏品

艺术作品是人类文化的瑰宝,而艺术平台则是连接艺术家与观众的桥梁。如何开发一款独一无二的艺术平台,既要满足专业艺术作品展示的要求,又要提供深度思考的空间,这是我们所面临的挑战。本文将从专业性、思考深度和逻辑性等多个方面…

Python数据分析和爬虫:解析数据的强大工具

引言: 在当今数据爆炸的时代,数据分析和数据提取变得越来越重要。作为一种简洁而强大的编程语言,Python在数据分析和爬虫领域有着广泛的应用。本文将详细介绍Python在数据分析和爬虫中的常用库和技术,并探讨其在实际应用中的优势…

14-模型 - 增删改查

增: # 1. 找到模型类并创建对象 user User() # 2. 给对象的属性赋值 user.username username user.password password user.phone phone # 3. 将user对象添加到session中 (类似缓存) db.session.add(user) # 4. 提交数据 db.session.commit() 删: # 两种删除:# 1. 逻辑删…

USB接口发展历程大全

1996年,由英特尔、微软、ibm等多家公司联合设计的usb标准问世,键盘、鼠标、智能手机以及打印机等等大多使用usb标准来实现供电和数据传输。 usb接口从诞生之初就是为了实现通用这个目的。在usb诞生之前,键盘、鼠标多使用ps二接口&#xff0c…

AcWing算法提高课-5.5.1可见的点

宣传一下 算法提高课整理 CSDN个人主页:更好的阅读体验 原题链接 题目描述 在一个平面直角坐标系的第一象限内,如果一个点 ( x , y ) (x,y) (x,y) 与原点 ( 0 , 0 ) (0,0) (0,0) 的连线中没有通过其他任何点,则称该点在原点处是可见的。…

反射机制-体会反射的动态性案例(尚硅谷Java学习笔记)

// 举例01 public class Reflect{ // 静态性 public Person getInstance(){return new Person(); }// 动态性 public T<T> getInstance(String className) throws Exception{Calss clzz Class.forName(className);Constructor con class.getDeclaredConstructor();con…

P1065 [NOIP2006 提高组] 作业调度方案

[NOIP2006 提高组] 作业调度方案 题目描述 我们现在要利用 m m m 台机器加工 n n n 个工件&#xff0c;每个工件都有 m m m 道工序&#xff0c;每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。 每个工件的每个工序称为一个操作&#xff0c;…

算法:图解前缀和问题

文章目录 实现原理实现思路一维前缀和模板二维前缀和模板 典型例题一维前缀和二维前缀和寻找数组中心下标除自身以外数组的乘积关系矩阵和 总结 实现原理 前缀和问题和二分查找类似&#xff0c;也是有一些固定的模板的&#xff0c;在理解原理的基础上进行实践&#xff0c;就能…

派大星2.2-v8a-正式版

派大星2.2-v8a-正式版.apk (访问密码: 4842)

华为OD机试 - 按索引范围翻转文章片段 - 字符串(Java 2022 Q4 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#…

一名阿里服务端开发工程师的进阶之路

一名阿里服务端开发工程师的进阶之路 一、前言 目前&#xff0c;资讯、社交、游戏、消费、出行等丰富多彩的互联网应用已经渗透到了人们生活和工作的方方面面&#xff0c;正深刻改变着信息时代。随着用户规模的增长和应用复杂度的上升&#xff0c;服务端面临的技术挑战越来越严…

Oracle跨库访问DBLINK

1. DBLINK的介绍 Oracle在进行跨库访问时&#xff0c;可以创建DBLINK实现&#xff0c;比如要将UAT的表数据灌入开发环境&#xff0c;则可以使用UAT库为数据源&#xff0c;通过DBLINK实现将查出的数据灌入开发库。 简而言之就是在当前数据库中访问另一个数据库中的表中的数据 2…

stm32单片机实现电机的PID控制

PID控制应该算是非常古老而且应用非常广泛的控制算法了&#xff0c;小到热水壶温度控制&#xff0c;大到控制无人机的飞行姿态和飞行速度等等。在电机控制中&#xff0c;PID算法用得尤为常见。 一、位置式PID 1.计算公式 在电机控制中&#xff0c;我们给电机输出的是一个PWM占…
最新文章