目录
文章来源地址https://www.toymoban.com/news/detail-829027.html
1.什么是链表?
2.链表的分类
(1)无头单向非循环链表:
(2)带头双向循环链表:
3.单链表的实现
(1)单链表的定义
(2)动态创建节点
(3)单链表打印
(4)单链表尾插
(5)单链表头插
(6)单链表尾删
(7)单链表头删
(8)单链表查找
(9)单链表在pos位置之后插入
(10)单链表在pos位置之前插入
(11)单链表删除pos位置的节点
(12)单链表销毁
4.运行结果
5.结语
1.什么是链表?
可以看出链表有两个变量,一个存放数据,另一个存放指向下一节点的指针;
此外链表还具有以下特征:
(1)链表在逻辑上连续,但在物理上不一定连续;
(2)链表的节点在现实中一般都是在堆上开辟出来的,所以使用结束后需要释放空间;
(3)从堆上申请的空间是按照一定策略分配的,所以物理空间可能连续也可能不连续。
2.链表的分类
链表按单向双向、无头带头、循环非循环可分为多种,这里我们介绍最常用的两种——无头单向非循环链表、带头双向循环链表。本篇文章将详细介绍无头单向非循环链表(简称单链表)的增删查改等的实现。
(1)无头单向非循环链表:
(2)带头双向循环链表:
3.单链表的实现
(1)单链表的定义
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;//存放数据
struct SListNode* next;//存放下一个节点的指针
}SListNode;
结构体定义两个变量,一个是SLDataType类型的数据,另一个时结构体的指针用来存放下一节点指针;
(2)动态创建节点
//申请新的节点,返回指向节点的指针
SListNode* BuySListNode(SLTDateType x)
{
SListNode* buynode = (SListNode*)malloc(sizeof(SListNode));
buynode->data = x;
buynode->next = NULL;
return buynode;
}
(3)单链表打印
// 单链表打印
void SListPrint(SListNode* plist)
{
//assert(plist);//没有节点,指针为空,断言,为空也可打印空指针所以不需要断言
SListNode* psl = plist;//用一个临时变量接收,如果不喜欢也可以不用
while (psl)//利用while循环遍历单链表
{
printf("%d->", psl->data);//打印单链表指向的数据
psl = psl->next;//继续循环
}
printf("%d->NULL\n");//最后一个不要漏了
}
(4)单链表尾插
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);//断言二级指针
SListNode* buy = BuySListNode(x);
assert(buy);//判断节点是否开辟成功
SListNode* psl= *pplist;//创建一个新的变量
if (psl == NULL)//如果是一个节点都没有的情况
{
*pplist = buy;//需要将头指针改变(原本头指针是NULL)所以需要节点指针的指针
return;
}
while (psl->next)//如果已经有节点的情况
{
psl = psl->next;//通过next遍历链表找到最后的节点
}
psl->next = buy;//将最后节点的next改成buy节点的指针,所以需要节点的指针即可,不需要二级指针
}
pplist是指向链表第一个节点指针的指针,是二级指针,所以一定不为空,要用assert断言;
(5)单链表头插
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode* buy = BuySListNode(x);
assert(buy);//判断节点是否开辟成功
SListNode* psl = *pplist;
if (*pplist == NULL)//如果一个节点都没有的情况
{
*pplist = buy;//需要将头指针改变(原本头指针是NULL)所以需要节点指针的指针
return;
}
//有节点的情况
buy->next = psl;//需要通过next连接新节点
*pplist = buy;//通过节点的指针的指针改变节点的指针
}
要注意有两种情况一直是没有一个节点的情况即*pplist = NULL,另一种是有节点的情况;
传二级指针的作用就是为了改变指针plist,所以需要指针的指针pplist;
(6)单链表尾删
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist);
assert(*pplist);//删除节点要判断有没有节点
SListNode* psl = *pplist;
if (psl->next == NULL)//只有一个节点时
{
free(psl);//释放最后一个节点的空间
*pplist = NULL;//尾指针置空
return;
}
while (psl->next->next)//多个节点时找到倒数第二个节点
{
psl = psl->next;
}
free(psl->next);
psl->next = NULL;//尾指针置空
}
单链表尾删同样要注意两种情况;使用free释放指针指向的空间;
(7)单链表头删
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);//删除节点要判断有没有节点
SListNode* psl = *pplist;
if (psl->next == NULL)//只有一个节点时
{
free(psl);
*pplist = NULL;
return;
}
//多个节点时
*pplist = psl->next;//将第二个节点的指针给头指针
free(psl);//释放第一个节点的空间
}
(8)单链表查找
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);//查找节点要判断有没有节点
SListNode* psl = plist;
while (psl)
{
if (psl->data == x)
{
return psl;//找到了返回psl
}
psl = psl->next;
}
return NULL;//没找到返回空指针
}
(9)单链表在pos位置之后插入
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* buy = BuySListNode(x);
assert(buy);//判断节点是否开辟成功
//if (pos->next == NULL)
//{
// pos->next = buy;//将最后节点的next改成buy节点的指针
// return;
//}
buy->next = pos->next;//只有一个节点和多个节点一样
pos->next = buy;
}
思考分析这两行代码可不可以调换一下顺序呢?
buy->next = pos->next;//只有一个节点和多个节点一样
pos->next = buy;
答案是不能,我们看到如果交换顺序,先将buy赋值给pos->next,那么pos->next的值将会被改变,而我们需要在buy->next中保存原来的pos->next,所以不能调换顺序;
如果你想要换也可以通过创建一个临时变量来存储pos->next的方式实现.例如:
SListNode* cur = pos->next;
pos->next = buy;
buy->next = cur;
(10)单链表在pos位置之前插入
// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
//assert(pphead);
assert(pos);
SListNode* buy = BuySListNode(x);
assert(buy);//判断节点是否开辟成功
SListNode* psl = *pphead;
if (psl->next == NULL)//只有一个节点
{
buy->next = pos;
*pphead = buy;
return;
}
while (psl->next != pos)//多个节点
{
psl = psl->next;
}
buy->next = pos;
psl->next = buy;
}
(11)单链表删除pos位置的节点
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pos);
SListNode* psl = *pphead;
if (psl->next == NULL)//只有一个节点,类似于头删
{
free(pos);
pos = NULL;
*pphead = NULL;
return;
}
while (psl->next != pos)//多个节点
{
psl = psl->next;
}
//此时psl->next = pos;
psl->next = pos->next;将pos位置指向的下一个节点指针赋给psl->next
free(pos);
pos = NULL;
}
删除pos位置也要注意有两种情况;
(12)单链表销毁
void SLTDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* psl = *pphead;
SListNode* psll = *pphead;
while (psl != NULL)
{
free(psll);
psl = psl->next;
psll = psl;
}
*pphead = NULL;
}
4.运行结果
5.结语
以上就是今天学习的内容了,单链表的实现关键在于理解它的逻辑结构,包括两个变量,一个是指向数据,另一个则指向下一节点的指针,此外,单链表实现还涉及了二级指针的内容以及动态内存函数的内容,涉及的代码知识更为广泛,但是只要抓住了关键点就会发现每个函数的中心思想都是不变的,好了以上就是今天学习的内容啦,有什么问题欢迎大家在评论区指出或者私信我哦~文章来源:https://www.toymoban.com/news/detail-829027.html
到了这里,关于数据结构——lesson3单链表介绍及实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!