关键词:
在顺序表中我们了解了顺序表的概念与如何创建一个顺序表与它的接口函数完成增删查改的功能。本文将继续介绍线性存储的内容,对单链表的概念进行了相关阐述并且给出了它的接口函数的C语言实现
顺序表的一些缺点:
在顺序表阶段,我们了解到顺序表在内存中是一块连续存储的空间,元素与元素之间紧挨存放。不用经过太多思考,我们就可以发现顺序表在实际应用中的一些缺点:
- 为了能动态的进行存储,那么就需要创建一个动态链表进行数据存储。
- 为了避免频繁扩容,在使用realloc进行申请空间时,往往直接申请当前空间的二倍空间,这就免不了空间浪费。
- 在插入或者删除数据时,需要挪动整个顺序表,效率极低。
- realloc函数在申请内存空间时,有申请失败的风险。
于是有人就考虑用链表的方式来解决上述相关问题。
什么是单链表?
顾名思义,单链表是一种区别于顺序表的一种不需要在内存中连续存储的数据存储类型。各个数据元素可以在内存中分别存储,数据与数据之间通过next指针的方式,相互连接,在结构上如同“铰链”一样形成一个整体。如图所示,可以方便你更加清晰的认识单链表的结构:
单链表仍然以一个结构体作为基本结构。在Data中存放数据,而结构体的next指针中存放下一个数据的地址。只要通过对当前数据的next指针进行解引用操作就可以找到下一个数据元素。单链表总是以一个指向第一个元素的头指针开始,直到最后一个元素的空指针作为结束标志。在上述图中,我们可以发现:由于指针的寻址特性,所以链表不需要连续存储在内存中。
链表的优点:
按需申请空间,不用了就释放空间(更合理的使用了空间)
头部、中间插入数据,不需要挪动数据
链表的缺点:
每一个数据都要一个指针去存链接后面数据的结点
不支持随机访问(用下标访问第i个)
与顺序表不同的是,
链表是以头指针开始的,而不是如顺序表一样单纯的用一个结构体变量的实体化来创建的。单链表是用指针来进行维护的。链表的起始是用一个为NULL的结构体指针开始的,对于指针进行了赋值操作即完成了初始化,固不再额外使用初始化函数对其进行初始化。
注意:要理解好空指针NULL的相关概念,空指针是不能进行解引用操作的,空指针存放的就是0x00000000,它不能解引用访问任何内容,所以一切对空指针的解引用操作都是错误的。但是存放NULL的指针(也就是空指针)是有地址的,尾插传递的就是这个空指针的地址,对空指针的地址的解引用是有效的,得到的是0x00000000这个NULL值。
单链表的实现
链表的每一个节点需要具备的功能有:
1、存放数据
2、访问下一个节点存放的内容
所以对于一个单链表来说,同样采用结构体的方式对其中内容进行定义:
为了方便更换数据类型将我们将int等类型可以类型重定义为SLTDataType
//.h文件
#pragma once
#include<stido.h>
#include<stdlib.h>
typedef int SLTDataType
typedef struct SListNode
SLTDataType data;//存的数据
struct SlistNode* next;//next指针
SLTNode;
//辅助函数用于新节点创建
SLTNode* BuyListNode(SLTDataType x);
//打印函数
void SListPrint(SLTNode* phead);
//尾插
void SListPushBack(SLTNode** pphead,SLDataType x);
//头插
void SListPushFront(SLTNode** pphead,SLDataType x);
//尾删
void SListPopBack (SLNode** pphead);
//头删
void SListPopFront(SLNode** pphead);
//查找函数
void SListFind(SLTNode* phead,SLTNodeType x);
//指定下标插入
void SListInsert(SLTNode* phead,SLTNode *pos,SLTDataType x);
//指定下标之后的一个位置插入
void SListInsertAfter(SLNode* pos,SLTDatatpye x);
//擦除某个特定位置的元素
void SListErase(SLTNode** pphead, STLNode pos,SLTDataType x);
//擦除某个特定未知的之后的元素
void SListEraseAfter(SLTNode* pos);
//销毁链表
void SlistDestory(SLTNode** pphead);
接口函数的具体实现
//.h对应的.c文件
//辅助函数 用于结点创建
SLTNode* BuyListNode(SLTDataType x)
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if(newnode==NULL)
printf("空间不够了");
exit(-1);
else
newnode->data=x;
newnode->next=NULL;
return newnode;
//打印函数
void SListPrint(SLTNode* phead)
SLTNode*cur=phead;
while(cur!=NULL)
printf("%d->",cur->data);
cur=cur->next;
//尾插函数
void SListPushBack(SLTNode** pphead, SLTDataType x)
//切记这个地方要用二级指针来接收 维护链表的phead对其进行传址操作处理
SListNode* newnode=BuyListNode(x);
if(*pphead==NULL)//判断是否phead内存储的是空,即需要判断链表是否开始了
*pphead=newnode;//让头指针指向 这个newnode新节点所维护的struct空间
else//此时说明链表中的有元素,需要寻找尾结点
SLTNode* tail=*pphead;
//尾结点的标志是next为空
//找到尾结点
while(tail->next !=NULL)
tail=tail->next;
tail->next=newnode;
//头插函数
//头插时不需要对头指针判空,只需要申请空间创建节点并赋予头指针即可
void SListPushFront(SLTNode** pphead,SLTDataType x)
SListNode* newnode=BuyListNode(x);
newnode->next=*pphead;
*pphead=newnode;
//尾删
void SListPopBack (SLNode** pphead)
if(*pphead==NULL)//链表为空的时候直接返回0,这里也可以用assert保证链表不为空
return 0;
if((*phead)->next ==NULL)//只有一个节点时
free(*pphead);
*pphead=NULL;
else
SLNode* prev=NULL;
SLNode* tail= *pphead;
while(tail->next!=NULL)
prev=tail;
tail=tail->next;
free(tail);//将最后一个节点的内容free掉
tail=NULL;
//将指向最后节点的tail指针置空,但此时链表中的倒数第二个的next指针并没有被修改为NULL,原因是tail被free掉之后为一个随机值
//所以要对倒数第二个节点的next置NULL完成尾删。
prev->next=NULL;
//通过倒数第三个结构体的next指针访问倒数第二个next指针将其置空,就完成了倒数第二个的next指针置空
/*//也可以用这种方法
SLTNode* tail=*pphead;
while(tail->next->next)
tail=tail->next;
//当调出循环时,tail为倒数第二个节点
//将tail的下一个位置的free掉
free(tail->next);
//tail作为倒数第二个节点需要对其next指针置空
tail->next=NULL;
*/
//头删
void SListPopFront(SLNode** pphead)
if(*pphead==NULL)
return 0;
SLNode* head =*pphead->next;
free(*pphead);
*pphead=head;
//查找函数
STLNode* SListFind(SLTNode* phead,SLTNodeType x)
SLTNode* pf=phead;
/* while(pf->data!=x)
pf=pf->next;
if(pf->data==x)
retrun 1;
else
return -1;
*/
while(pf)
if(of->data==x)
retunn pf;
else
pf=pf->data;
return NULL;
//指定Pos位置插入(前插)
void SListInsert(SLTNode** pphead, STLNode * pos,SLTDataType x)
assert(pphead);
assert(pos);
STLNode* newnode=BuyListNode(x);
//找到pos位置
STLNode* posPrev=*pphead;
while(posPrev->next!=pos)
posPrev=posPre->next;
posPrev->next=newnode;
newnode->next=pos;
//指定位置pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDateType x)
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
//指定位置擦除(从前遍历之后擦除)
void SListErase(SLTNode** pphead, SLTNode* pos)
assert(pphead);
assert(pos);
if (*pphead == pos)
/**pphead = pos->next;
free(pos);*/
SListPopFront(pphead);
else
SLTNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
prev->next = pos->next;
free(pos);//将pos销毁 在立案表中pos维护的空间置为随机值
//pos = NULL;
//指定pos位置删除(pos位置后删除)
void SListEraseAfter(SLTNode* pos)
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;//创建next结构体指针,将pos的下一个位置的结构体交于它维护,目的是找到pos下一个的下一个,以便让pos直接指向下一个的下一个,然后就可以对pos之后的内容进行删除
pos->next = next->next;//用赋值的方式将next结构体指针所维护的空间中的next指针(pos的下一个的下一个)给pos的下一个,对pos的下一个位置进行销毁
free(next);
//next = NULL;
//销毁
void SListDestory(SLTNode** pphead)
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
SLTNode* next = cur->next;
free(cur);
cur = next;
*pphead = NULL;
//.c文件 进行test
void Test_list()
SLTNode* plist = NULL;
//单链表以一个结构体指针开始从而创建出整个链表,所以呼应了上述中需要传递二级指针来修改一级指针的值。
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
//你可以试一试其他接口函数的调用,注意传递的参数类型哦!
int main()
Test_list();
小结
对于一个单链表来说,不需要在内存中连续存储,实现了存储的便捷化,但是也由于这种特性不能通过下标对其进行随机访问。单链表的实体化过程用一个结构体指针来实现,在实现接口函数时,由于头指针为一个一级指针,若想修改一级指针所维护的空间的值,就需要传递一级指针的地址,用二级指针对其进行接收并通过对二级指针解引用操作来修改头指针维护的结构空间。因为单链表的每一个节点通过malloc函数开辟,所以在最后不要忘记对其进行销毁,防止出现野指针等不可预计错误。
数据结构单链表的介绍和基本操作(c语言实现)保姆级别详细教学(代码片段)
...头文件代码完整展示test.cSList.h尾声单链表基本介绍对于数据结构这个模块,我们必须要对C语言中的结构体和指针这两部分的内容有很好的掌握,并且要可以灵活地运用。基本结构链表:链表是一种在物理储存上非连... 查看详情
数据结构--单链表的c语言实现(超详细注释/实验报告)(代码片段)
数据结构–单链表的c语言实现(超详细注释/实验报告)知识小回顾在顺序表中,用一组地址连续的存储单元来一次存放线性表的结点,因此结点的逻辑顺序和物理顺序是一致的。而链表则不然,链表是用一组... 查看详情
新手向超详细的c实现动态顺序表(代码片段)
目录一、各个函数接口的实现1.1不太好‘’李姐‘’的“容量检测函数”1.2在任意位置插入的函数"坑!"1.3在任意位置删除数据的函数1.4其余简单的接口函数初始化函数销毁函数打印函数尾插头插尾删头删通过数据查找... 查看详情
新手向超详细的c实现动态顺序表(代码片段)
目录一、各个函数接口的实现1.1不太好‘’李姐‘’的“容量检测函数”1.2在任意位置插入的函数"坑!"1.3在任意位置删除数据的函数1.4其余简单的接口函数初始化函数销毁函数打印函数尾插头插尾删头删通过数据查找... 查看详情
数据结构与算法线性表的链式表示和实现,超详细c语言版(代码片段)
目录链式存储结构与链式存储有关的术语头指针、头结点和首元结点讨论1.如何表示空表?2.在链表中设置头结点有什么好处?3.头结点的数据域内装的是什么?链表(链式存储结构)的特点链表的优缺点优点... 查看详情
逻辑回归模型logisticregression详细推导(含numpy与pytorch实现)
...告之LR模型介绍符号说明Sigmoid函数LR模型LR模型的优化目标似然函数与损失函数模型参数更新--代数法求梯度 查看详情
《图解数据结构与算法》(java代码实现注释解析算法分析)(代码片段)
文章目录第1章数据结构与算法基础概述1.1数据结构和算法的重要性1.2数据结构概述逻辑结构存储结构1.3算法概述如何理解“大O记法”时间复杂度空间复杂度第2章数组2.1数组概念2.2无序数组2.3有序数组第三章栈3.1栈概念3.2栈的操... 查看详情
数据结构与算法分析(线性表实现)(代码片段)
★线性表是一个序列(线性结构),具有一定的顺序★如果有多个元素,第一个元素没有前驱,最后一个元素没有后继★线性表强调是有限的一.线性表基本存储结构㈠.顺序表——把线性表的结点按逻辑顺序依次存放在一组地... 查看详情
一篇解单链表(0基础看)(c语言)《数据结构与算法》(代码片段)
目录链表1.链表的概念及结构2.链表的分类2.1. 单向或者双向2.2.带头或者不带头2.3.循环或者非循环 2.4.虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构3. 效果展示图4.接口实现4.01. 本文章要实现的接口... 查看详情
单链表(代码片段)
文章目录单链表一.什么是单链表链表的节点头指针,尾指针二单链表的基本操作(C语言代码实现)一.创建一个单链表二.遍历一个单链表三.插入一个元素四.清空链表五.删除节点六.查找节点完整代码如果觉得文章不错,点个关注你就... 查看详情
单链表~增删查改(附代码)~简单实现(代码片段)
目录动态申请一个节点单链表打印单链表的尾删单链表的头删 单链表尾插单链表的头插 单链表的查找单链表在pos位置之后插入x 单链表删除pos位置之后的值 单链表的销毁 所有函数代码链表的概念及结构概念:链表是一... 查看详情
c/c++语言数据结构快速入门(代码解析+内容解析)链表(单链表,双链表,循环链表,静态链表)(代码片段)
一、单链表1、链表(链式存储)相关概念(1)什么是单链表(2)用代码定义一个单链表(3)用代码定义一个单链表头插法建立单链表的算法如下:LinkList*GetElem(LinkListL,inti) LNode*s;intx; L=(LinkL... 查看详情
c/c++语言数据结构快速入门(代码解析+内容解析)链表(单链表,双链表,循环链表,静态链表)(代码片段)
一、单链表1、链表(链式存储)相关概念(1)什么是单链表(2)用代码定义一个单链表(3)用代码定义一个单链表头插法建立单链表的算法如下:LinkList*GetElem(LinkListL,inti) LNode*s;intx; L=(LinkL... 查看详情
基于c语言的队列实现(代码片段)
...插接口,才能达到先进进出的效果。队列逻辑示意图单链表实现,自然要有结点,所以我们要先创建单链表结点的结构体typedefstructNode QDataty 查看详情
6-1单链表逆转(代码片段)
本题要求实现一个函数,将给定的单链表逆转。函数接口定义:ListReverse(ListL);其中List结构定义如下:typedefstructNode*PtrToNode;structNodeElementTypeData;/*存储结点数据*/PtrToNodeNext;/*指向下一个结点的指针*/;typedefPtrToNodeList;/*定义单链表类... 查看详情
单链表c语言实现附加力扣题(代码片段)
...插入排序前言今天我们的主题是实现单向不带头不循环的单链表链表的实现接口的声明ty 查看详情
线性表链式表示(代码片段)
单链表的定义顺序表它虽然可以实现随机存取,但是在初始化时需要申请一大块连续的存储空间,而且它在执行例如插入、删除操作时也需要大量的移动元素,时间复杂度较高。今天讲述线性表的一种新的存储表示方法,也就是... 查看详情
c/c++数据结构:动图演示单链表的结构介绍与实现(代码片段)
文章目录@[toc]链表链表的概念及结构概念理解结构理解链表的分类1、单向或者双向2、带头或者不带头3、循环与非循环单链表定义:结点结构输出:遍历输出链表插入:尾插法插入:头插法删除:尾删法删... 查看详情