当前位置: 首页 > news >正文

初阶数据结构【3】--单链表(比顺序表还好的一种数据结构!!!)

本章概述

  • 前情回顾
  • 单链表
  • 实现单链表
  • 彩蛋时刻!!!

前情回顾

咱们在上一章博客点击:《顺序表》的末尾,提出了一个问题,讲出了顺序表的缺点——有点浪费空间。所以,为了解决这个问题,我们今天就要讲解链表,咱们在讲结构体的时候有提到过链表,链表的最大优点——一点空间也不浪费,用多少就开辟多少在这里插入图片描述

单链表

  • 概念一种在逻辑上成线性结构,在物理空间上不一定成线性结构的数据结构因为链表是线性表的一种,所以在逻辑上成线性结构“ 链 ”字上就能猜到,在逻辑上成线性结构)。我们链表的开辟用的内存函数malloc。知识点忘记的同学自行回顾:点击:《动态内存管理》。因为内存开辟是随机的,所以我们也不知道它会在内存的那一块区域开辟空间,这就导致开辟的空间可能是连续的,也可能不是连续的。所以,在物理空间上不一定成线性结构。在这里插入图片描述
  • 节点每一个个独立,而且还能存放数据的空间被称为节点。数据结构是用来存储数据的,链表自然也是来存储数据的。存储数据就需要有空间,自然有malloc来给我们开辟空间。万事俱备,只欠东风!可是有想过一个问题吗?——malloc开辟的空间东一块,西一块的它不像realloc那样开辟的连续空间(我们可以挨着挨着找到空间),它的空间是散乱的,不连续的。那么,我们该怎样进行数据的存储,而且还能找到一个一个的数据呢我们可以在这个节点内部划分两部分,一部分用来存储我们想要存储的数据,另一部分部分用来存储下一个节点的地址(因为我们的节点空间是用nalloc开辟的,所以每个节点自然就有个地址)这就需要用到结构体了,进行链表的结构展示:
typedef int SLDatatype ;
typedef struct  Sqlist
{SLDatatype data;	//存放数据,这里假设存放整型类型struct Sqlist* next;   //存放下一个节点的地址
}SLND;		  //定义节点类型

这样我们就能通过地址找到下一个节点了,以此类推,我们就能顺次找到各个节点,找到数据了。如图所示:在这里插入图片描述
当我们不想再存储数据时,要给最后一个节点的next指针赋值NULL(下一个节点为NULL,就相当于没有下一个节点),就表示到此结束了。

  • 链表的性质
    • 1、链式机构在逻辑上是连续的,在物理结构上不⼀定连续。
    • 2、结点⼀般是从堆上申请的。
    • 3、从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续。
  • 链表的打印:我们讲过了节点的存储结构了,我们可以通过next指针,找到下一个节点,然后就能打印我们想要的数据了。
  • 直观体验链表:我们先给大家直观感受一下链表,让大家有个感觉,我们就按照上面的结构图进行展示:
#define  _CRT_SECURE_NO_WARNINGS	1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct Sqlist
{SLDatatype data;struct Sqlist* next;
}SLND;void my_printf(SLND* ps)
{assert(ps);while (ps){printf("%d->", ps->data);ps = ps->next;}printf("NULL");
}
void test()
{SLND* plist=NULL;  //创立一个带头指针,用来牵引后面的链表,就像火车头一样SLND* node1 = (SLND*)malloc(sizeof(SLND));   //创立3个节点SLND* node2 = (SLND*)malloc(sizeof(SLND));SLND* node3 = (SLND*)malloc(sizeof(SLND));node1->data = 1;  //分别对3个节点·进行·数据的存储node2->data = 2;node3->data = 3;node1->next = node2;  //每个节点的next的指针指向下一个节点的地址node2->next = node3;node3->next = NULL;plist = node1;my_printf(plist);
}
int main()
{test();return 0;
}

结果运行图:在这里插入图片描述
我们的指针plist就是个牵引的作用,就像高铁一样,没有高铁头车厢照样能跑,就是不美观,没有它也可以正常访问链表。有了它就是逻辑上和美观上要舒服很多。如图所示:在这里插入图片描述

实现单链表

和顺序表一样,我们也是创建3个文件: Sqlist .h , Sqlist.ctest .c文件。具体的原因个顺序表一样的。接下来我直接给大家展示代码,我会在注释中详细讲解的。

  • Sqlist.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SListDatatype;
typedef struct SListNode
{SListDatatype data;struct SListNode* next;
}SLND;SLND* SListFind(SLND* phead, SListDatatype x);//找对应的节点
SLND* SLTButnode(SListDatatype x);//申请新的节点
void my_printf(SLND* phead); //·打印链表信息void SListpushback(SLND** pphead, SListDatatype x); //尾插
void SListpopback(SLND** pphead);//尾删void SListpushFront(SLND** pphead, SListDatatype x); //头插
void SListpopFront(SLND** pphead);//头删void SListrdFrontpush(SLND** pphead, SLND* find, SListDatatype x);//在任意节点之前插入数据
void SListrdBackpush(SLND* find, SListDatatype x);//在任意节点之后插入数据void SListposePop(SLND* phead, SLND* pose); //删除指定节点
void SListDestry(SLND** pphead); //销毁链表
  • Sqlist.c:
#include "SList.h"
//打印链表信息
void my_printf(SLND* phead)   //打印信息,便于我们看信息的输出
{SLND* pcur = phead;while (pcur){printf("%d-> ",pcur->data);pcur = pcur->next;}printf("NULL\n"); //第N+1个为空====没有链表
}
SLND * SLTButnode(SListDatatype x)	//申请新空间,返回新空间地址,便于咱们找到新空间插入数据
{SLND* newnode = (SLND*)malloc(sizeof(SLND));if (newnode == NULL){perror("malloc fail!");exit(1);		//若开辟失败就直接退出程序,也可以写成 return 1;}else{newnode->data = x;  	//走到这里就开辟成功,进行初始化newnode->next = NULL;}return newnode;
}
void SListpushback(SLND** pphead, SListDatatype x) //尾插数据
{assert(pphead);  //检查传递的指针是否为空指针SLND* newnode = SLTButnode(x);if (*pphead==NULL)  {*pphead = newnode;	//如果起始没有节点,先创立个节点}else{SLND* ptail = *pphead;while (ptail->next)      //遍历节点,找到最后一个节点的next为空的情况,跳出循环{ptail = ptail->next;  }ptail->next = newnode;  //走到这里说明找到了最后一个节点,在此之后插入新的节点}
}
void SListpopback(SLND** pphead) //尾删数据
{assert(pphead&&*pphead);  //检查传递的指针是否为空指针   SLND* ptail = *pphead;  //我们把起始节点的地址给ptail,用ptail进行遍历数据,去寻找最后的尾节点SLND* prev = NULL;   //prev是用来记录尾节点前一个节点,不记录的话,就会随着我们删除最后一个节点而丢失信息while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);  //找到最后一个节点,进行空间释放ptail = NULL;  //释放后要置空,防止产生野指针
}
void SListpushFront(SLND**pphead,SListDatatype x) //头插数据
{assert(pphead);  //判断传递的地址是否为空指针SLND* newnode = SLTButnode(x);newnode->next = *pphead;*pphead = newnode;
}
void SListpopFront(SLND**pphead)//头删
{assert(pphead&&*pphead);	//判断传递的地址是否为空指针SLND*next = (*pphead)->next;free(*pphead);  //释放头节点*pphead = next;  //释放头节点后,要使得plist指向第二个节点
}
SLND* SListFind(SLND*phead,SListDatatype x) //找对应的节点
{assert(phead); 	//判断传递的地址是否为空指针while (phead){if (phead->data == x)return phead;    //找到目标节点,就返回目标节点的地址phead = phead->next;}return NULL;  //没找到就返回空指针
}
void SListrdFrontpush(SLND**pphead,SLND*find,SListDatatype x)//在任意节点之前插入数据
{assert(pphead&&*pphead);		//判断传递的地址是否为空指针if (*pphead == find)    //任意位置刚好是头节点时,相当于头插数据SListpushFront(pphead, x); //头插数据else {SLND*newnode= SLTButnode(x);//申请新的节点SLND* prev = NULL;SLND* ptail = *pphead;while (ptail!= find){prev = ptail;ptail = ptail->next;}prev->next = newnode;  //指定位置之前的节点的next指针指向要插入的新节点newnode->next = ptail;		//这个新节点的next指针指向下一个节点}
}
void SListrdBackpush( SLND* find, SListDatatype x)//在任意节点之后插入数据
{assert(find);		//判断传递的地址是否为空指针SLND* newnode = SLTButnode(x);newnode->next = find->next;  //新节点的next指针指向下一个节点find->next = newnode;		//新节点之前的节点next指针指向这个新节点
}
void SListposePop(SLND**pphead, SLND* pose) //删除指定节点
{assert(*pphead&&pose);		//判断传递的地址是否为空指针if(pose==*pphead)		//当删除的节点是头节点时,就相当于头删SListpopFront(pphead);//头删else{SLND* prev = NULL;	SLND* ptail = *pphead;while (ptail != pose)		//遍历节点,找到目标节点{prev = ptail;ptail = ptail->next;}SLND* next = ptail->next;	prev->next = next;free(ptail);  //删除指定的节点ptail = NULL;    //置空指针,防止发生野指针}
}//链表的销毁和顺序表不一样
void SListDestry(SLND**pphead) //链表的销毁不像顺序表那样直接释放内存就欧克,因为每个
{							//节点都是独立的,所以我们需要去遍历每个节点去销毁assert(*pphead);		//判断传递的地址是否为空指针SLND* prev = NULL;SLND* ptail = *pphead;while (ptail->next) //一直遍历到最后一个节点才结束{prev = ptail;ptail = ptail->next;free(prev); //每遍历一个节点就释放prev = NULL;  //置空指针防止产生野指针}ptail = NULL;		//置空指针防止产生野指针*pphead = NULL;	//置空指针防止产生野指针
}
  • test.h
#define  _CRT_SECURE_NO_WARNINGS	1
#include "SList.h"
void test()
{		//这里给大家演示一下尾插数据,其它功能大家可以自行尝试一下SLND* plist = NULL;SListpushback(&plist,1);//尾插SListpushback(&plist,2);//尾插SListpushback(&plist,3);//尾插SListpushback(&plist,4);//尾插my_printf(plist);
}int main()
{test();return 0;
}

结果运行图:在这里插入图片描述

彩蛋时刻!!!

歌曲:《All Falls Down》听会儿歌曲放松一下呗!!!
在这里插入图片描述
每章一句道路是曲折的,前途是光明的!感谢你能看到这里,点赞+关注+收藏+转发是对我最大的鼓励,咱们下期见!!!

http://www.lryc.cn/news/466269.html

相关文章:

  • mysql迁移到达梦的修改点
  • Go小技巧易错点100例(十八)
  • 【python】极简教程8-字符串
  • UEFI EDK2框架学习 (四)——UEFI图形化
  • 【C++】— 一篇文章让你认识STL
  • mysql--索引
  • 【linux】线程 (三)
  • c++日常积累
  • 字节流写入文件
  • Torch模型导入
  • 博弈论:博弈类型空间集合;三层博弈拓展式;
  • 数据库表的关联、集合操作
  • word怎么清除格式,Word一键清除所有格式教程
  • ShardingProxy服务端分库分表
  • 开源的 FOC(Field-Oriented Control) 项目
  • 高等数学 5.5 反常积分的审敛法 Γ函数
  • 宝塔安装ffmpeg的方法
  • 案例分享-优秀蓝色系UI界面赏析
  • 陪诊小程序之uniapp(从入门到精通)
  • 深度学习(一)基础:神经网络、训练过程与激活函数(1/10)
  • 源代码加密技术的一大新方向!
  • SVN——常见问题
  • JavaCV 图像灰度化处理
  • 基于Multisim三极管B放大系数放大倍数测量电路设计(含仿真和报告)
  • Molmo模型实战
  • 免费开源的微信开发框架
  • 波形的变化和信号的产生1+multisim仿真
  • 【FAQ】HarmonyOS SDK 闭源开放能力 —Map Kit(3)
  • 电脑微信多开方法,保姆级教学,超简单!
  • 【Mysql】-锁,行级锁