线性表之单链表(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);
    }
}
//如果删除的是头结点,直接调用头删函数。//如果不想用二级指针的话,可以使用带头单链表,不需要改变传过来的指针。

目录
相关文章
|
21天前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
197 6
|
25天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
48 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
90 4
|
2月前
|
存储 缓存 C语言
C语言:链表和数组有什么区别
C语言中,链表和数组是两种常用的数据结构。数组是一种线性结构,元素在内存中连续存储,通过下标访问,适合随机访问且大小固定的情况。链表由一系列不连续的节点组成,每个节点存储数据和指向下一个节点的指针,适用于频繁插入和删除操作的场景,链表的大小可以动态变化。
|
2月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装,包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
29 0
|
2月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装,包括节点的创建、链表的初始化、数据的插入和删除,以及链表的打印等功能。
21 1
|
2月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码,包括创建链表、插入、删除和打印等基本操作。
36 1
|
2月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法,包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除,以及链表的打印等功能。文章通过具体的代码示例,展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除,以及如何清空和销毁链表。
47 0
单链表之无头链表(C语言版)
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
66 0
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
36 0