网站网站怎么建设,摄影网站模版,女网友叫我一起做优惠券网站,网页设计作品网站 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录1.链表1.1 链表的概念… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录1.链表1.1 链表的概念及结构1.2 顺序表的缺陷1.3 链表的意义2.链表的分类2.1 单向或双向2.2 带头或不带头2.3 循环或非循环3.单链表的实现3.1 工程文件3.2 接口设计3.3 重点接口实现①.创建新节点②.打印单链表③.单链表尾插④.单链表头插⑤.单链表尾删⑥.单链表头删⑦.单链表查找⑧.单链表插入Ⅰ、单链表前插Ⅱ、单链表后插⑨.单链表删除I、删除pos位置的节点II、删除pos位置之后的节点⑩.单链表销毁4.链表实现全部源码4.1 SList.h4.2 SList.c4.3 test.c5.总结1.链表
1.1 链表的概念及结构
链表linked list是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
1.2 顺序表的缺陷
在之前的博客中我们对顺序表有了较深层次的认知同时我们发现顺序表在创建和使用时存在一些问题
当空间不足时顺序表需要进行增容但由于顺序表本质为数组数据在物理上连续存放因此在扩容时要付出较大的空间代价。为避免频繁扩容基本每次都扩容 2 倍当扩容次数增多时就很有可能会造成一定程度的空间浪费。由于顺序表内数据连续存储我们在向顺序表中位置插入或删除数据时就需要挪动大量的数据效率不高。
1.3 链表的意义
人们针对顺序表的这些缺陷设计出了链表这个概念来克服这些不足。 而链表克服这些缺陷的方法是将每一个节点划分为数据与指针两部分数据部分用于存储数据而指针部分用于指向下一节点。这样做的好处是通过指针指向下一节点于是数据的物理存储就可以不必连续于是无论是在扩容还是在插入与删除数据时都能快速、方便的实现并且不会造成很大的空间浪费。
2.链表的分类
2.1 单向或双向 2.2 带头或不带头 2.3 循环或非循环 注虽然有很多种不同的链表结构但是最常用的链表结构主要是两种无头单向非循环链表与带头双向循环链表
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。 带头双向循环链表结构最复杂一般用在单独存储数据。虽然它结构复杂但在实际使用中使用代码实现后会带来很多优势实现反而更加简单。并且在我们的实际中所使用的链表数据结构一般都是带头双向循环链表。
3.单链表的实现
3.1 工程文件
与顺序表的实现方式类似,使用三个文件进行代码书写 SeqList.h存放函数声明、包含其他头文件、定义宏。 SeqList.c书写函数定义书写函数实现。 test.c书写程序整体执行逻辑。 其中我们的接口实现主要研究的是函数实现文件 SeqList.c 中的内容。
单链表和顺序表的结构略有不同单链表的主结构为节点。 一个节点由两部分组成data和next。data为我们存储数据的地方。而next则为下一个节点的地址。
typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;上面我们设计的是不带哨兵位的单链表。这种结构设计相对于带哨兵位的链表的缺点就是设计接口函数时需要考虑链表是否为空的情况。 哨兵位也叫哨兵节点哑节点。该节点并不存储任何数据只是为了方便操作而引入这个节点。起一个站岗放哨的作用。所以形象的叫它哨兵位。如果一个链表有哨兵位那么链表的第一个元素应该是链表第二个节点对应的元素。这时链表永不为空这就可以避免边界问题的处理简化代码与减少代码出错的可能性。 3.2 接口设计
void SLPrint(SLNode* SLHead); //打印单链表
SLNode* BuyListNode(SLDataType x); //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x); //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x); //单链表头插
void SLPopBack(SLNode** pphead); //单链表尾删
void SLPopFront(SLNode** pphead); //单链表头删
void SLFind(SLNode* phead, SLDataType x); //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x); //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x); //单链表后插
void SLErase(SLNode** pphead, SLNode* pos); //单链表删除
void SLEraseAfter(SLNode** pphead, SLNode* pos);//单链表后删除
void SLDestory(SLNode** pphead); //单链表销毁我们发现绝大多数接口的参数都为二级指针这是为什么 我们先了解一下平时单链表的测试用例
void TestList()
{SLTNode* plist NULL;
}链表的一开始是空的。所以我们插入数据时需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针那么要改变plist就要传它的地址plist为二级指针所以也需要用二级指针来接收该参数。
就好比当我们要改变一个int类型的变量时a我们需要传它的地址a那么函数的形参就应该用int* 接收对于指针也是这样一个int* 的指针变量p它也是变量我们需要改变这个值就应该传它的地址p那么函数参数就应该那int* * 接收。
而对于一些接口就不需要传二级指针就拿打印来说吧因为我并不需要改变plist我只需要通过结构体指针访问结构内的next成员并迭代到下一个节点然后打印出数据就可以所以不需要传二级指针。
3.3 重点接口实现
这里是本文的重点即 SeqList.c 文件中的接口具体实现
①.创建新节点
在各项操作前需动态创建新节点再对新创建的节点进行操作。
SLNode* BuyListNode(SLDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(newnode:);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}②.打印单链表
执行操作前无需进行断言原因是循环条件为空指针则条件不满足并停止循环不会出现死循环。 根据指针循环操作打印数据后使指针指向节点内存放下一节点地址的指针 next。
void SListPrint(SLNode* SLHead)
{SLNode* cur SLHead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}③.单链表尾插
如果此时头节点为空指针说明此时单链表内没有节点此时只需要将申请来的新节点作为头节点即可。若头节点不为空则应当首先找到尾节点使尾结点指针指向申请来的新节点后再使新节点指针指向空即可。
void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode BuyListNode(x);if (*pphead NULL){*pphead newnode;}else{//找到尾结点SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}测试接口
④.单链表头插
头插实现非常简单首先申请新节点先使新节点的指针指向原来的头节点再使链表头指向新节点即可。 这里不需要考虑空节点的原因是就算链表内没有内容即首节点为空新节点指针指向空也没有问题申请新节点时原本就指向空。
void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
}测试接口
⑤.单链表尾删
执行操作前需要进行非空判断防止传入空指针。
若链表内只有一个节点则直接释放并置空即可。若有一个以上节点则当执行下面三个步骤 首先寻找尾节点找到后将其释放并置空。但在释放前必须将倒数第二个节点的指针指向空否则将在指向最后一个被释放的节点时变成野指针。单向链表无法回溯于是我们应当定义另一个指针在每次移动尾节点指针前保存当前节点的位置。 void SLPopBack(SLNode** pphead)
{//判断链表是否为空if (*pphead NULL){return;}//若只有一个节点直接释放并置空即可if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//若有多个节点则执行多步尾删else{SLNode* tail *pphead;SLNode* prev NULL;//找到尾节点while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}测试接口
⑥.单链表头删
执行操作前判断指针非空防止对空指针进行操作。 使链表头指向第二个节点接着将第一个节点释放并置空即可。
void SLPopFront(SLNode** pphead)
{if (*pphead NULL){return;}else{SLNode* next (*pphead)-next;free(*pphead);*pphead next;}
}测试接口
⑦.单链表查找
采用遍历思想依次对每一个节点的数据进行判断符合条件即进行打印不符合条件则继续向后遍历直至指向 NULL并且因此无需进行非空判断。
void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur phead;int count 1;while (cur){if (cur-data x){printf(第%d个节点%p - %d\n, count, cur, x);}cur cur-next;}
}测试接口
⑧.单链表插入
单链表在插入新节点时有两种插入方式一种是在目标节点前方插入另一种是在目标节点后方插入因此需要分别进行实现
Ⅰ、单链表前插
前插有两种情况:
在首节点处插入此时即相当于头插操作。在非首节点前插入此时首先申请新节点接着遍历单链表找到插入位置后使新节点指向目标节点后插入其前方。
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod BuyListNode(x);//头插if (*pphead pos){newnod-next *pphead;*pphead newnod;}else{//找到目标节点 pos 的前一个节点SLNode* PostPrev *pphead;while (PostPrev-next ! pos){PostPrev PostPrev-next;}//找到后插入新节点PostPrev-next newnod;newnod-next pos;}
}
测试接口 同下图
Ⅱ、单链表后插
在前插操作时我们需要遍历整个链表来查找插入位置因此效率较为低下于是我们通常使用后插的方式插入新节点。后插直接申请节点插入目标位置后即可。
void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode BuyListNode(x);newnode-next pos-next;pos-next newnode;
}测试接口
⑨.单链表删除
I、删除pos位置的节点
分为两种情况进行处理:
一种情况是整个链表中只有一个节点则删除节点相当于释放整个数组并置空。另一种情况是含有一个以上节点此时只需要让目标节点的前一个节点指针指向后一个节点再释放目标节点并置空即可。
void SLErase(SLNode** pphead, SLNode* pos)
{//头删if (*pphead pos){*pphead pos-next;free(pos);pos NULL;}else{ //找到目标节点 pos 的前一个节点SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}测试接口 同下图
II、删除pos位置之后的节点
和在pos位置之前插入一样我们发现删除pos位置的节点也很麻烦。因为需要找pos的前一个位置所以这种设计也比较麻烦。 所以有时我们会删除pos位置之后的节点这样就很方便了。 既然要删除pos位置之后的节点那么我就需要将pos位置的节点pos位置的 next 的 next 链接起来。那么我们首先用next拷贝记录一下pos-next 然后再将pos-next赋值为next-next也就是pos往后的两个节点。最后释放next位置的节点即可。 注意:pos位置的下一个节点不能是尾结点后面的节点
// 删除指定pos位置后的一个节点
void SLEraseAfter(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos-next);// 删除的不能是尾结点后面的位置SLNode* next pos-next;// 拷贝pos的下一个节点pos-next next-next;// 将pos的next变为下一个节点的nextfree(next);// 释放之前pos的下一个节点next NULL;
}测试接口
⑩.单链表销毁
遍历整个单链表将每一个节点都进行释放并置空即可。 注意:记得把*pphead置空防止野指针问题出现
void SListDestory(SLNode** pphead)
{if (*pphead NULL){return;}SLNode* cur *pphead;while (cur){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
测试接口
4.链表实现全部源码
4.1 SList.h
#pragma once#includestdio.h
#includeassert.h
#includestdlib.h
#includestring.h
typedef int SLDataType;//单链表节点结构
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;void SLPrint(SLNode* SLHead); //打印单链表
SLNode* BuyListNode(SLDataType x); //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x); //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x); //单链表头插
void SLPopBack(SLNode** pphead); //单链表尾删
void SLPopFront(SLNode** pphead); //单链表头删
void SLFind(SLNode* phead, SLDataType x); //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x); //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x); //单链表后插
void SLErase(SLNode** pphead, SLNode* pos); //单链表删除
void SLEraseAfter(SLNode** pphead, SLNode* pos);//单链表后删除
void SLDestory(SLNode** pphead); //单链表销毁4.2 SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
//打印单链表
void SLPrint(SLNode* SLHead)
{SLNode* cur SLHead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//申请节点
SLNode* BuyListNode(SLDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(newnode:);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}//单链表尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode BuyListNode(x);if (*pphead NULL){*pphead newnode;}else{//找到尾结点SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}//单链表头插
void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
}//单链表尾删
void SLPopBack(SLNode** pphead)
{//判断链表是否为空if (*pphead NULL){return;}//若只有一个节点直接释放并置空即可if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//若有多个节点则执行多步尾删else{SLNode* tail *pphead;SLNode* prev NULL;//找到尾节点while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}//单链表头删
void SLPopFront(SLNode** pphead)
{if (*pphead NULL){return;}else{SLNode* next (*pphead)-next;free(*pphead);*pphead next;}
}//单链表查找
void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur phead;int count 1;while (cur){if (cur-data x){printf(第%d个节点%p - %d\n, count, cur, x);}cur cur-next;}
}//单链表前插
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod BuyListNode(x);if (*pphead pos){newnod-next *pphead;*pphead newnod;}else{//找到目标节点 pos 的前一个节点SLNode* PostPrev *pphead;while (PostPrev-next ! pos){PostPrev PostPrev-next;}//找到后插入新节点PostPrev-next newnod;newnod-next pos;}
}//单链表后插
void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode BuyListNode(x);newnode-next pos-next;pos-next newnode;
}//单链表删除
void SLErase(SLNode** pphead, SLNode* pos)
{if (*pphead pos){*pphead pos-next;free(pos);pos NULL;}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
// 删除指定pos位置后的一个节点
void SLEraseAfter(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos-next);// 删除的不能是尾结点后面的位置SLNode* next pos-next;// 拷贝pos的下一个节点pos-next next-next;// 将pos的next变为下一个节点的nextfree(next);// 释放之前pos的下一个节点next NULL;
}
//单链表销毁
void SLDestory(SLNode** pphead)
{if (*pphead NULL){return;}SLNode* cur *pphead;while (cur){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}4.3 test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include SList.h// 测试尾插、带节点的头插
void TestList1()
{SLNode* plist NULL;//SLPushBack(plist, 1);//SLPushBack(plist, 2);//SLPushBack(plist, 3);//SLPushBack(plist, 4);//SLPrint(plist);//SLPushBack(plist, 5);//SLPrint(plist);SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 4);SLPrint(plist);SLPushFront(plist, 5);SLPrint(plist);}// 测试头插、尾删
void TestList2()
{SLNode* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 4);SLPushFront(plist, 5);SLPrint(plist);SLPopBack(plist);SLPopBack(plist);SLPopBack(plist);SLPopBack(plist);SLPrint(plist);SLPopBack(plist);SLPrint(plist);}// 测试头删
void TestList3()
{SLNode* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 4);SLPushFront(plist, 5);SLPrint(plist);SLPopFront(plist);SLPrint(plist);SLPopFront(plist);SLPrint(plist);SLPopFront(plist);SLPrint(plist);SLPopFront(plist);SLPrint(plist);SLPopFront(plist);SLPrint(plist);}void TestList4()
{SLNode* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 2);SLPushFront(plist, 5);SLNode* pos SLFind(plist, 2);int i 1;while (pos){printf(第%d个pos节点%p-%d\n, i, pos, pos-data);pos SLFind(pos-next, 2);}// 修改 3-30pos SLFind(plist, 3);if (pos){pos-data 30;}SLPrint(plist);
}void TestList5()
{SLNode* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 2);SLPushFront(plist, 5);// 3前面插入一个30SLNode* pos SLFind(plist, 3);if (pos){SLInsertFront(plist, pos, 30);}SLPrint(plist);// 5后面插入一个10pos SLFind(plist, 5);if (pos){SLInsertAfter( pos, 10);}SLPrint(plist);
}
void TestList6()
{SLNode* plist NULL;SLPushFront(plist, 1);SLPushFront(plist, 2);SLPushFront(plist, 3);SLPushFront(plist, 2);SLPushFront(plist, 5);SLPrint(plist);// 删除3位置节点SLNode* pos SLFind(plist, 3);if (pos){SLErase(plist, pos);}SLPrint(plist);// 删除4位置之后节点pos SLFind(plist, 5);if (pos){SLEraseAfter(plist, pos);}SLPrint(plist);SLDestory(plist);SLPrint(plist);}int main()
{//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();TestList6();return 0;
}
5.总结
今天我们认识并学习了单向无头链表的相关概念、结构与接口实现并且针对每个常用的功能接口都进行了实现分解并对各个接口的各项注意点都进行了强调说明希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
