🔥个人主页:艾莉丝努力练剑
❄专栏传送门:《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向:C/C++方向
⭐️人生格言:为天地立心,为生民立命,为往圣继绝学,为万世开太平
前言:本篇文章,我们复盘顺序表和链表相关的知识点,在初阶的数据结构与算法阶段,我们把知识点分成三部分,复杂度作为第一部分,顺序表和链表、栈和队列、二叉树为第二部分,排序为第二部分,我们之前已经介绍完了第一部分:算法复杂度,本文我们继续学习第二部分中的顺序表和链表部分内容啦。
半个多月前,博主更新了头插、尾删、头删、随机位置插入、随机位置删除、查找、修改、菜单等内容,本篇文章,我们就来复盘一下动态顺序表的内容,博主会添加很多新内容,希望对大家的顺序表学习有所帮助。
目录
正文
提醒:为什么我们要学那么多的数据结构?这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构,所以数据结构没有谁好谁坏之分,而评估数据结构的好坏要针对场景,如果在一种场景下我们需要频繁地对头部进行插入删除操作,那么这个时候我们用链表;但是如果对尾部进行插入删除操作比较频繁,那我们用顺序表比较好。
因此,不同的场景我们选择不同的数据结构。
三、单链表
(二)实现单链表
3、增删查改
增
(1)尾插
我们要申请新的节点(需要malloc),我们单独封装一个函数。
现在新节点就申请好了,我们要让5和4节点连起来:
这就是为什么我们明明已经有phead这个指针,还要额外再定义一个指针pcur——
这样一来pcur在不断变化,phead保持不变,phead始终保存的是第一个节点的地址。在这里我不想改变phead,phead始终指向第一个节点,方便我们后面遍历完了如果还要再从头开始遍历的时候我们能够找到第一个节点的地址。
我们定义pcur,只要pcur不为空,我们就进入循环,pcur为空我们就跳出循环。
我们这边调用test02:
这是SList.c尾插的代码:
//尾插
void SLTPushBack(SLTNode* phead, SLTDatatype x)
{
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
//链表为空——要特殊处理
if (phead == NULL)
{
phead = newnode;
}
SLTNode* ptail = phead;
while (ptail->next != NULL)
{
ptail = ptail->next;
}
//找到了尾节点 ptail newnode
ptail->next = newnode;
}
这边其实代码还是有问题的,我们先运行一下看看:
尾插:
SList.c:
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
//链表为空——要特殊处理
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
while (ptail->next != NULL)
{
ptail = ptail->next;
}
//找到了尾节点 ptail newnode
ptail->next = newnode;
}
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
尾插的时间复杂度:O(N) 。
(2)头插
头插:
SList.c:
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPrint(plist);
SLTPushFront(&plist, 2);
SLTPrint(plist);
SLTPushFront(&plist, 3);
SLTPrint(plist);
SLTPushFront(&plist, 4);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
头插的时间复杂度:O(1) 。
(3)在指定位置之前插入数据
函数形参中同样需要用二级指针传入链表地址,还要传入指定位置的地址和需要插入的数据。
在函数中,需要先找到指定位置的前一个节点,然后把需要添加的数据插入到这两个节点之间:
SList.c:
void SLTPushBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
//当pos为头节点时 相当于头插
if(*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newNode = SLTBuyNode(x);
//找到pos前一个节点
SLTNode* pre = *pphead;
while(pre->next != pos)
{
pre = pre->next;
}
//把新节点放在pre和pos之间
newNode->next = pre->next;//等价于newNode->next = pos
pre->next = newNode;
}
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 4);
SLTInsert(&plist, pos, 100);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
在指定位置之前插入数据时间复杂度:O(N)。
(4)在指定位置之后插入数据
和类似,我们找到指定位置的后一个节点,把新节点放在这两个节点之间——
4后面插入一个100:
1后面插入一个100:
SList.c:
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
if(pos->next == NULL)
{
//相当于尾插
SLTPushBack(pphead, x);
}
else
{
SLTNode* newNode = SLTBuyNode(x);
newNode->next = pos->next;
pos->next = newNode;
//顺序不能颠倒 否则会先修改pos->next
}
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 1);
//SLTInsert(&plist, pos, 100);
SLTInsertAfter(pos, 100);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
在指定位置之后插入数据时间复杂度:O(1)。
删
(1)尾删
pphead和phead的关系:
本文中的pphead是形参,phead是画图时定义的一个指针。
phead是指向第一个结点的指针;
在程序里面,指向第一个节点的指针在形参里面是*pphead。
函数形参中二级指针存放表头地址。
如果链表只有一个元素需要释放头节点的空间,并把链表指针置为空;
如果有多个元素需要找到倒数第二个节点和最后一个节点,释放最后一个节点,并把倒数第二个节点的next指针置为空。
出问题了:
万一链表只有一个节点,我们要注意这种情况——
尾删:
SList.c:
//尾删
void SLTPopBack(SLTNode** pphead)
{
//链表为空不能删除
assert(pphead && *pphead);
//pphead是*pphead的地址
//pphead是一个二级指针,我们对pphead解引用一次,*pphead就是指向第一个节点的地址
//*pphead为空说明链表为空
//链表只有一个节点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//prev ptail
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
//SLTPushFront(&plist, 1);
//SLTPrint(plist);
//SLTPushFront(&plist, 2);
//SLTPrint(plist);
//SLTPushFront(&plist, 3);
//SLTPrint(plist);
//SLTPushFront(&plist, 4);
//SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
链表为空,如果还要再删一次,程序就会assert(断言)报错:
表达式为假,因为*pphead为空了,在69行断言出现了报错。
如果初始将prev置为*pphead也要讨论:
这样两个指针都指向这个节点,让prev下一个节点置为空——本身它下一个节点就为空,现在把ptail 给 free掉,prev就变成了野指针。
如果只有一个节点,prev->next = NULL;这一行代码就可以不要了,而且ptail和prev都要free。如果不止一个节点的话,那这又是一套逻辑,这种写法会更复杂一些。
博主给出的这种写法会简单一些。
尾删的时间复杂度:O(N) 。
(2)头删
与尾删相似,让头指针指向第二个节点,并释放头节点——
头删:
SList.c:
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
//头删
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
再删一次就会断言报错——
头删的时间复杂度:O(1) 。
(3)删除pos节点
让pos前一个节点指向pos后一个节点——
SList.c:
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos && *pphead);
//pos为头节点
if(pos == *pphead)
{
free(*pphead);
*pphead = NULL;
pos = NULL;
}
else
{
SLTNode* prev = *pphead;
while(prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
SLTErase(&plist, pos);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
(4)删除pos之后的节点
找到pos之后的节点del,连接pos节点和del->next,再释放del——
SList.c:
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos && pos->next && *pphead);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
SLTErase(&plist, pos);
SLTPrint(plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
查
(1)查找
来个不存在的数据测试一下——
查找
SList.c:
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//未找到
return NULL;
}
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 100);
if (pos)
{
printf("找到了!\n");
}
else
{
printf("未找到!\n");
}
}
int main()
{
/*test01();*/
test02();
return 0;
}
改
(1)修改
修改指定位置的数据:直接修改该节点data的值——
SList.c:
void SLTChangeData(SLTNode* pos, SLTDataType x)
{
assert(pos);
pos->data = x;
}
销毁链表
遍历链表,释放每一个节点,由于需要修改指向头节点的指针,因此函数形参中要用二级指针——
(1)销毁链表
SList.c:
void SLTDestroy(SLTNode** pphead)
{
assert(pphead );
SLTNode* pcur = *pphead;
while(pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
这里pos=NULL、pcur=NULL、next=NULL加上置为空是养成好习惯,这里是默认置为空。
test.c:
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
SListDestory(&plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
4、完整代码
(1)SList.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//链表的结构
typedef int SLTDatatype;
typedef struct SListNode
{
SLTDatatype data;
struct SListNode* next;//指向下一个节点的地址
}SLTNode;
//typedef struct SListNode SLTNode;
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//修改
void SLTChangeData(SLTNode* pos, SLTDatatype x);
//销毁链表
void SListDestory(SLTNode** pphead);
(2)SList.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur != NULL)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//后续我们要申请新节点就直接调用SLTBuyNode方法
SLTNode* SLTBuyNode(SLTDatatype x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//malloc不一定申请成功,我们判断一下
if (newnode == NULL)
{
printf("malloc fail!");
exit(1);
}
//初始化一下
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
//链表为空——要特殊处理
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
while (ptail->next != NULL)
{
ptail = ptail->next;
}
//找到了尾节点 ptail newnode
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
//链表为空不能删除
assert(pphead && *pphead);
//pphead是*pphead的地址
//pphead是一个二级指针,我们对pphead解引用一次,*pphead就是指向第一个节点的地址
//*pphead为空说明链表为空
//链表只有一个节点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//prev ptail
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//未找到
return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
//pos指向头节点
if (pos == *pphead)
{
//头插
SLTPushFront(pphead, x);
}
else
{
//找pos前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev newnode pos
prev->next = newnode;
newnode->next = pos;
}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//pos刚好是头节点——头删
if (pos==*pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//pos del del->next
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
//修改
void SLTChangeData(SLTNode* pos, SLTDatatype x)
{
assert(pos);
pos->data = x;
}
//销毁链表
void SListDestory(SLTNode** pphead)
{
//一个一个销毁
assert(pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//*pphead是野指针,要置为空
*pphead = NULL;
}
(3)test.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
int test01()
{
//创建一个链表——实际上是创建一个一个节点,再把节点连起来
SLTNode*node1=(SLTNode*)malloc(sizeof(SLTNode));
SLTNode*node2=(SLTNode*)malloc(sizeof(SLTNode));
SLTNode*node3=(SLTNode*)malloc(sizeof(SLTNode));
SLTNode*node4=(SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
SLTNode* plist = node1;
//打印链表
SLTPrint(plist);
}
void test02()
{
//创建空链表
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
////SLTPushFront(&plist, 1);
//SLTPrint(plist);
//SLTPushFront(&plist, 2);
//SLTPrint(plist);
//SLTPushFront(&plist, 3);
//SLTPrint(plist);
//SLTPushFront(&plist, 4);
//SLTPrint(plist);
////SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
////头删
// SLTPopFront(&plist);
// SLTPrint(plist);
// SLTPopFront(&plist);
// SLTPrint(plist);
// SLTPopFront(&plist);
// SLTPrint(plist);
// SLTPopFront(&plist);
// SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
//if (pos)
//{
// printf("找到了!\n");
//}
//else
//{
// printf("未找到!\n");
//}
//SLTInsert(&plist, pos, 100);
/*SLTInsertAfter(pos, 100);*/
//SLTErase(&plist, pos);
//SLTPrint(plist);
SListDestory(&plist);
}
int main()
{
/*test01();*/
test02();
return 0;
}
结尾
往期回顾:
【数据结构与算法】数据结构初阶:详解顺序表和链表(三)——单链表(上
本期内容需要回顾的C语言知识如下面的截图中所示(指针博主写了6篇,列出来有水字数嫌疑了,就只放指针第六篇的网址,博主在指针(六)把指针部分的前五篇的网址都放在【往期回顾】了,点击【传送门】就可以看了)。
大家如果对前面部分的知识点印象不深,可以去上一篇文章的结尾部分看看,博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了,上一篇文章的链接博主放在下面了:
【数据结构与算法】数据结构初阶:详解顺序表和链表(三)——单链表(上)
结语:本篇文章到这里就结束了,对数据结构的单链表知识感兴趣的友友们可以在评论区留言,博主创作时可能存在笔误,或者知识点不严谨的地方,大家多担待,如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正,再次感谢友友们的关注和支持!