线性表之单链表(C语言)

简介: 线性表之单链表(C语言)

本篇博客只讲:无头单向非循环链表


💨链表的概念及结构

✔概念

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

✔结构

图片.png


✔结构的实现

typedefintSLTDataType;
typedefstructSListNode{
SLTDataTypedata;
structSListNode*next;
}SLTNode;

👇解释

🚩首先我将int类型重命名为SLDataType。虽然看起来名字长了麻烦,但是为了代码的可维护性。比如每一次你存数据都要写一次int,但如果你下次想存字符类型,那你是不是要把所有的int改成char?如果这么写,你只需要把typedef int SLTDataType;里的int改为char就行。

🚩因为是链表,我们看结构图有数据域和指针域,我就定义了一个结构体。数据域就是data,指针域必须是结构体指针,因为你下次链接那个数据肯定和这次一样,还是包括一个数据一个指向下一个节点的指针

🚩struct前加typedef是为了重命名,重新命名的名字写在分号前,这里我重命名为SLTNode。不然每次写SListNode都要带上struct关键字。

🎈next是指针域,存的是下一个节点的地址。


🎈关于结构

逻辑结构:想象出来的

物理结构:实实在在地在内存中如何存储表示他们之间关系的


💨一些接口的实现

💨尾插

voidSListPushBack(SLTNode**pphead,SLTDataTypex) //尾插{
SLTNode*newnode= (SLTNode*)malloc(sizeof(SLTNode));
newnode->data=x;
newnode->next=NULL;
if(*pphead==NULL)
    {
*pphead=newnode;
    }
else    {
SLTNode*tail=*pphead;
while(tail->next!=NULL)
        {
tail=tail->next;
        }
tail->next=newnode;
    }
}

👇解析

🎈为什么要用到结构体二级指针?

🚩因为在主函数中,我们要定义一个结构体指针plist,只有定义了这个指针,我们才能调用结构体里面的两个成员变量。但当我们尾插的时候,一定要把指针的地址传过去,不然传的是形参而非实参。所以要用二级指针接收指针的地址。


①()里面我定义了一个二级指针,和一个int类型的x,就是表示你插入的数据。你会怀疑你这不是写的SLTDataType吗? 别忘记看上面结构的实现里,我把int重命名为SLTDataType。

②下面就是定义一个结构体指针newnode,后面是动态内存开辟的内容,以免造成浪费,用多少内存就造多少内存。

③让此指针指向的链表,数据域为x(即插入的数据),指针域为空

④让二级指针判断是否传过来的结构体指针plist为空,因为你刚开始定义的plist要让他为空,如果为空则把刚开辟的newnode给plist。

⑤如果不为空。就把plist的地址(因为*pphead解引用就代表plist的地址)给新定义的尾指针tail,这样每次在链表尾部插入一个数据的时候,先让他判断尾指针的下一个指向的链表是否为空,不为空则继续判断再下一个链表是否为空。如果下一个为空,就把开辟的newnode给下一个尾指针指向的下一个链表。


💨简化动态内存开辟

如果写接口发现动态内存开辟使用频繁,可以使用函数来简化程序。

具体如下

SLTNode*BuySListNode(SLTDataTypex)
{
SLTNode*newnode= (SLTNode*)malloc(sizeof(SLTNode));
newnode->data=x;
newnode->next=NULL;
returnnewnode;
}

那么上面的代码就可以改为

SLTNode*newnode=BuySListNode(x);

接下来的接口都会这样写动态内存开辟。


💨打印链表

voidSListPrint(SLTNode*phead)  //打印链表{
SLTNode*cur=phead;
while(cur!=NULL)
    {
printf("%d->",cur->data);
cur=cur->next;
    }
printf("NULL\n");
}

🎈在插入等操作完成之后,就直接把指针传过来打印就行,不需要传指针的地址(&plist),因为我们不需要改变原来链表的数值。只是简单的打印。


💨头插

voidSListPushFront(SLTNode**pphead,SLTDataTypex) //头插{
SLTNode*newnode=BuySListNode(x);
newnode->next=*pphead;
*pphead=newnode;
}

这里使用二级指针和尾插同理。

🚩把头指针(plist)的地址给新开辟的结构体指针newnode的指针域,代表头指针已经成为下一个指向的链表的地址

🚩再把新开辟的newnode地址赋给原来的头指针,自然而然我们插入的数据就是从头开始插入的。


💨头删

voidSListPopFront(SLTNode**pphead)  //头删{
SLTNode*next= (*pphead)->next;  //*和=优先级一样,要用()free(*pphead);
*pphead=next;
}

🚩删掉链表中第一个元素,就表示第一个为空了。

所以我们要把头指针的指针域,也就是下一个节点的地址(即原链表中第二个元素地址)赋值给一个结构体指针next。

🚩然后再释放掉头指针的地址(因为我们删的是头元素嘛,所以释放头指针)。

🚩再把原来第二个节点的地址给头指针。现在他就是第一个元素了,不再是第二个了。


💨尾删

voidSListPopBack(SLTNode**pphead)  //尾删{
//如果链表为空,直接returnif(*pphead==NULL)
    {
return;
    }
elseif((*pphead)->next==NULL)  //只有一个节点    {
free(*pphead);
*pphead=NULL;
    }
else    {
SLTNode*prve=NULL;
SLTNode*tail=*pphead;
while (tail->next!=NULL)
        {
prve=tail;
tail=tail->next;
        }
free(tail);
prve->next=NULL;
    }
}

尾删的时候就要考虑一下,是否为空链表的情况,以及只有一个结点的情况。

🚩先定义两个结构体指针,tail判断下一个结点是否为空,而prve就作为tail的前一个指针。

🚩如果tail的指针域tail->next不为空(即下一个结点不为空)。则把tail赋值给prve,自己进入下一个结点。

🚩只有当tail的指针域为空了,就代表这个结点是最后一个结点,那就释放tail,然后prve的指针域指向空,这样prve现在指向的结点就是链表的最后一个结点了。

🍳详细点说就是,比如链表总共三个结点,tail指向第三个结点,那么prve就指向第二个节点,你删掉第三个结点,那原来的第二个结点自然称为链表的最后一个结点。


如果我们想在某个位置前插入一个数据,那么我们需要先找到那个数据才能进行插入。

💨查找某个元素

SLTNode*SListFind(SLTNode*phead,SLTDataTypex) //查找{
SLTNode*cur=phead;
while (cur)
    {
if(cur->data==x)
        {
returncur;
        }
cur=cur->next;
    }
returnNULL;
}

🚩参数就是,在添加完链表之后,把链表头指针以形参的形式传过来,因为不改变链表元素数值,所以传值而不是传址,用一级指针接收。再把要查找的元素数值传过来。

🚩while循环表达的意思就是如果数据域等于我们要找的数值,就返回指针的地址。找不到就继续往下找,直到找到或者找完整个链表都没找到。


💨在某个位置插入

1.voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDataTypex) //在pos前插入x{
if (pos==*pphead)
    {
SListPushFront(pphead, x);
    }
else    {
SLTNode*newnode=BuySListNode(x);
SLTNode*prev=*pphead;
while (prev->next!=pos)
        {
prev=prev->next;
        }
prev->next=newnode;
newnode->next=pos;
    }
}

🚩要考虑到一种情况,如果要在第一个结点之前插入,不就成头插了吗,直接调用头插函数。

pos哪来的? pos是插入的位置,在主函数中要写上以下内容

SLTNode*pos=SListFind(plist,3);
if(pos)
    {
SListInsert(&plist,pos,30);
    }

比如你在3前面插入一个30,那么你就先找到3,上面查找函数不是返回了cur的地址了吗?地址就给了pos,然后调用插入函数,比较然后插入即可。


💨删除某个位置的值

1.voidSListErase(SLTNode**pphead,SLTNode*pos) //删除pos位置的值{
if(pos==*pphead) //删除的是头结点    {
SListPopFront(pphead);
    }
else    {
SLTNode*prve=*pphead;
while (prve->next!=pos)
        {
prve=prve->next;
        }
prve->next=pos->next;
free(pos);
    }
}
//如果删除的是头结点,直接调用头删函数。//如果不想用二级指针的话,可以使用带头单链表,不需要改变传过来的指针。

目录
相关文章
|
22天前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
|
1月前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
24 0
|
15天前
|
存储 数据管理 C语言
C语言实战 | 使用链表完成“贪吃蛇”游戏
【7月更文挑战第1天】整体思维,即系统思维,强调以整体视角理解事物。在编程中,结构体体现这种思想,将相关变量打包处理。示例展示了如何用链表而非数组实现“贪吃蛇”游戏,链表提供了更灵活的动态数据管理。一系列代码图片详细描绘了链表结构体在游戏中的应用,包括节点定义、移动、碰撞检测等,凸显了使用链表的优势和代码的清晰组织。
18 0
C语言实战 | 使用链表完成“贪吃蛇”游戏
|
1月前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
17 2
|
1月前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
24 2
|
2月前
|
存储 C语言 Python
|
2月前
|
存储 C语言
C语言链表详解 & 两类重要链表的实现
本文详细介绍了链表数据结构,包括链表的非连续、非顺序的物理存储和逻辑顺序通过指针链接的概念。文章以C语言实现链表,并计划更新两种链表(无头单向非循环链表和带头双向循环链表)的代码实现。目前提供了链表的逻辑和物理结构图解,帮助读者理解链表的工作原理,强调了画图在学习数据结构中的重要性。此外,文章指出链表的分类有多种组合形式,并预告将对常用类型的链表进行代码实现。
43 3
|
1月前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
13 0
|
1月前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
39 0
|
1月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
17 0