网站建设中敬请期待,企业网站建设的类型主要有,ui网页设计课程,湖北省和城乡建设厅官方网站目录 1.什么是链表#xff1f;
2.链表的分类
#xff08;1#xff09;无头单向非循环链表#xff1a;
#xff08;2#xff09;带头双向循环链表#xff1a;
3.单链表的实现 #xff08;1#xff09;单链表的定义
#xff08;2#xff09;动态创建节点
#…目录 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位置之后插入xvoid 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-nextfree(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.结语 以上就是今天学习的内容了单链表的实现关键在于理解它的逻辑结构包括两个变量一个是指向数据另一个则指向下一节点的指针此外单链表实现还涉及了二级指针的内容以及动态内存函数的内容涉及的代码知识更为广泛但是只要抓住了关键点就会发现每个函数的中心思想都是不变的好了以上就是今天学习的内容啦有什么问题欢迎大家在评论区指出或者私信我哦~
