链表的概念
链表是一种物理存储结构上非联系,非顺序的存储结构,但数据元素的逻辑顺序是通过链表中的指针链接实现的
逻辑结构:
实际物理结构:
每个链表节点都有自己的地址,链表的物理结构实际上是前一个结点保存着下一个结点的地址
所以从上面图中可以看出:
1.链表在逻辑上是连续的,但在物理上不是连续的
2.现实中,每个结点都是从堆中申请的
3.在堆中申请空间,按照一定规则进行分配,所以两次连续的开辟空间可以连续,可能不连续
链表的分类
实际中的链表有多种结构
分别为:
- 带头节点或不带头结点
- 单向或双向
- 循环或不循环
所以链表一共有8种结构
但是常用的只有:不带头节点非循环单链表 和 带头循环双向链表两种
单链表的实现
这里我们介绍的是不带头节点非循环单链表
单链表的结构
一个节点即存放了元素的值,也存放了下一个节点的地址,所以在结构体中,定义一个SLTDataType
类型的data
,以及结构体的自引用:struct SListNode* next
作为指向下一个节点的指针
所以结构体如下:
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
到这里,我们知道了可以通过一个节点找到下一个节点,但是我们如何找到头节点呢?
解决办法就是用一个结构体类型的指针去指向头节点,也解释存放头节点的地址。
所以在接下来的函数中,传这个头指针就可以了
单链表的接口函数
创建节点函数
因为每个节点都需要在堆中开辟,所以可以封装成一个函数,需要调用malloc
去开辟空间
同时,在这个函数中,将data
的值存放到节点中,因为不知道当前下一个节点的地址,所以next
指针赋为NULL
,最后返回这个节点的地址
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
if (new == NULL)
{
perror("malloc fail");
return;
}
new->next = NULL;
new->data = x;
return new;
}
打印函数
从头节点开始,直到NULL
,遍历链表,并且打印出来
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur!= NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾插函数
在实现尾插函数前,如果此时头指针指向的为NULL
,在尾插函数中便会改变头指针的指向,也就是改变头指针的值,如果这个函数是传的一级指针的话,虽然在尾插函数中改变了头指针的指向,但在主函数中,头指针的改变并没有改变
传一级指针的情况图如下
所以这样的情况下,就需要传二级指针,将头节点的二级指针pphead
传过去,让后通过解引用*pphead
去改变头指针的指向
所以在后面的会改变头指针指向的函数中,都需要传二级指针
接下来,实现尾插函数
我们应先创建节点,调用
SLTBuyNode
函数
接下来还有一点要注意的:
如果此时头指针是空,就说明它后面没有任何节点,所以需要把newnode
的节点地址赋值给头指针
如果不为空,找到尾节点,在尾节点的后面插入新节点
这里还需要注意的一个点是:二级指针是头指针的地址,这个地址一定不能为空,如果为空就出问题了,所以在函数开始应用assert
断言判断一下pphead
是否为空
头节点的值可能为NULL
,所以不用断言判断*pphead
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
头插函数
头插函数在头部插入,所以一点会改变头指针的指向,所以仍需传二级指针
然后灵newnode->next
等于*pphead
,然会再将newnode
的值赋给头指针
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
头删函数
头删函数一定会改变头指针指向,所以需要传二级指针
头删,一定必须是链表中有节点,如果没有节点,则头删没有意义,如果链表为空,那么头指针的值就为null
,所以我们可以通过断言判断*pphead
是否为空,同时仍需判断pphead
,所以这个函数的开头需要断言2次
因为节点都是动态开辟出来的,所以要用free
函数释放,如果直接直接free*pphead
,那么后面的节点都找不到了,因为也free
掉了next
的值
所以可以定义一个head
变量指向第一个节点,然后先将head->next
赋给*pphead
,接下来再free掉head
就可以了
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* head = *pphead;
*pphead = head->next;
free(head);
head = NULL;
}
尾删函数
和头删同样,需要传二级指针,以及断言2次
尾删,找到尾节点很简单,但是删除尾节点后还需要把尾节点前一个结点的next
指针赋为NULL
,但是如何找到这个倒数第二个结点是个问题
这里我们有2种放法:
1.利用tail->next->next找,当tail->next->next==NULL时,就找到了新的尾结点
2.定义一个prev指针,让prev一直在tail指针的前面,当tail到达尾时,prev也自然是倒数第二个结点了
起始时:
逐渐向后移动:
最后:
这里我们使用第一种方法,接着我们还会发现一个问题:当只有一个节点时,cur->next
已经为空了。cur->next->next
就错了
所以还需分类运算当只有一个节点的情况
void SLTPophBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
查找函数
遍历链表,如果找到则返回这个节点的地址,否则返回NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pos = phead;
while (pos != NULL)
{
if (pos->data == x)
{
return pos;
}
else
{
pos = pos->next;
}
}
return NULL;
}
pos位置前插入
这个pos是通过SLTFind
寻找返回的节点地址,这个地址不会为空,所以可以断言判断一下
如果想在pos位置前插入,就需要直到pos前一个位置,所以这里就需要遍历寻找pos的前一个结点prev
,然后将prev
,newndoe
和pos
链接在一起
如果这个pos等于*pphead,就是在头节点前插入,也就是头插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos==*pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//想要插入pos前,就要知道pos前的节点,就需要遍历,所以单链表不适合在前面插入
{
prev = prev->next;
}
SLTNode* newnode = SLTBuyNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
因为在pos前插入,所以这个函数是不会做到尾插功能的
下面考虑一个问题:如果只给pos,不给头指针,怎么在pos前插入?
在pos后面插入,再交换pos和pos后面节点中的data值就做到了在pos前面插入
删除pos位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
只给pos,不给头指针,也可以删除pos位置节点:交换pos和pos->next的data值,保存pos->next->next的值为nex,然后删除pos->next,最后链接pos和nex
但是这种方法不适用尾删
pos位置后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
因为在pos后面插入,所以不需要传头指针,同时还需要assert
断言判断pos
是否为空
在pos后面插入,所以这个函数实现不了头插
pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
在pos
后面删除,不仅到断言pos
还需要断言pos->next
其余逻辑很简单
销毁函数
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* del = *pphead;
SLTNode* next = NULL;
while (del != NULL)
{
next = del->next;
free(del);
del = next;
}
*pphead = NULL;
}
因为销毁会改变头指针的指向,所以需要传二级指针
如果链表为空,就不必销毁了,所以需要断言*pphead
销毁链表,是一个一个结点得释放,在释放当前节点前,需要保存下一个节点的地址,然后再销毁当前节点,再删除下一个节点
最后还需要把*pphead
也就是头节点赋值为空*pphead = NULL
单链表的问题
从上面的代码中可以看出,对于单链表想要尾插,就需要找尾,想要尾删就需要找到尾和尾的前一个结点
并且在某个位置插入删除,需要找到这个位置的前一个结点
这些操作都需要遍历链表,效率低文章来源:https://www.toymoban.com/news/detail-738824.html
这也正是单链表的问题,而这些问题放到带头循环双向链表就是小菜一碟了文章来源地址https://www.toymoban.com/news/detail-738824.html
到了这里,关于数据结构——单链表(不带头节点)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!