最好的做网站公司有哪些,大型网站建设完全教程,网上推广方法,汝州市文明建设门户网站欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 数据结构与算法
先赞后看#xff0c;已成习惯 创作不易#xff0c;多多支持#xff01; 一、链表的概念和结构
1.1 链表的概念
在上一篇文章中#xff0c;我们了解了线性表(linear list)#xff0c;并且学习了其… 欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 数据结构与算法
先赞后看已成习惯 创作不易多多支持 一、链表的概念和结构
1.1 链表的概念
在上一篇文章中我们了解了线性表(linear list)并且学习了其中一种线性表——顺序表(Sequence List)。链表也是线性表的一种那么它是一种什么样的结构呢
链表顾名思义带着链子的表。日常生活中我们知道链子是用来链接两个东西的那么我们可以很容易理解顺序表是基于数组实现的是一个元素一个元素挨着的那链表我们就可以理解为每个元素用链子连接起来这样就形成了链表(Linked List)。
1.2 链表的结构
那么我们得到了两个链表的组成的关键元素一个是每个元素我们管它叫节点(或结点)另一个就是那个链子。而在C语言中我们用结构体来实现节点用指针来充当链连接两个节点。
在生活中链表类似于我们的火车的结构在物理上它是一种存储结构非顺序非连续的结构。 节点的组成主要由两个部分组成一个是数值域用来保存当前节点的数据一个是指针域用来保存下一个节点的地址(指针变量)。 如图所示指针变量plist保存的是第一个节点的地址如果我们想让plist指向第二个节点我们只需要将plist保存的内容修改为0x0012FFD0。
为什么我们需要指针变量来保存下一个节点的位置
因为之前我们说了链表不同于顺序表它在内存中的地址不一定是连续的它是独立申请的(对其插入数据时才申请一个节点)。我们需要通过指针才能从当前节点找到下一个节点。
所以我们可以通过一个结构体来实现一个节点它要有一个节点的数据以及一个指针变量来保存下一个节点的地址代码如下
struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};
当然我们也可以用typedef来进行修改方便我们后续操作。
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data; //节点数据struct SListNode* next; //指针保存下⼀个节点的地址
}SLTNode;
我们如何将链表进行打印呢 首先我们将节点传到打印函数然后我们创建了一个指向头结点的结构体指针利用循环从头遍历到尾每次打印完成令pcur指向pcur的next节点。这里注意的就是结构体成员的访问的问题我们用到了-操作符在前面的博客我们都介绍过。 武器大师——操作符详解下-CSDN博客 代码如下
void SLTPrint(SLTNode* phead){SLTNode *cur phead;while(cur){printf(%d ,cur-data);cur cur-next;}printf(\n);
} 二、单链表的实现
上面我们知道了什么是链表那单链表又是什么呢单链表(Singly Linked List)一般所指的是“不带头单向不循环链表”。
我们实现的功能无非就四个“增、删、查、改”。
2.1 增
2.1.1 尾插
尾插顾名思义在尾部插入俗称后入(bushi)。
首先我们要申请新的节点我们可以写一个申请节点的函数。
SLTNode* BuyNode(SLTDataType x) {SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL) {perror(malloc fail!\n);exit(1);}node-data x;node-next NULL;return node;
}
首先我们用malloc函数动态申请一块内存然后将节点的数据赋进去。
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node BuyNode(x);if (*pphead NULL) {*pphead node;return;}//找尾SLTNode* cur *pphead;while (cur-next) {cur cur-next;}cur-next node;
}
接下来的代码逻辑特别简单首先我们通过buynode函数创建了一个节点然后我们判空如果这个链表是空的我们直接将指针变量pphead赋为node。如果不是空的那我们就需要找到链表的尾部我们可以通过循环来找到尾部首先为了防止原来数据被破坏我们创建一个指向第一个节点的指针变量cur而不是直接遍历pphead。
注意我们如何找尾通过判断该节点的下一个位置是否为空。
这里还有一个细节就是我们传入的是二级指针因为我们要修改一个数据的话需要传地址而那个数据如果是指针的话我们就需要传指针的地址也就是二级指针。
2.1.2 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node BuyNode(x);node-next *pphead;*pphead node;
}
这个代码逻辑也很简单首先我们assert断言防止访问空指针之后buynode函数申请节点然后将结点接到头部也就是*pphead之后别忘了将*pphead再指向node形成新的头。
2.2 删
2.2.1 尾删
尾删也很简单仔细思考我们只需要两步就能完成一个是找尾一个是删除。
首先我们来看找尾我们可以用循环再加上两个指针 //找尾
// SLTNode *cur *pphead;
// SLTNode *prev NULL;
// while(cur-next){
// prev cur;
// cur cur-next;
// }
// prev-next NULL;
// free(cur);
// cur NULL;
首先cur指向头prev指向空cur用来找尾prev用来保存上一个节点的地址。当cur的下一个位置为NULL时循环结束意味着找到最后一个节点了我们将它所指的位置free掉(因为是动态开辟出来的)然后指针置空即可完成删除。
还有一种方法可以用一个指针就解决 SLTNode* tail *pphead;while (tail-next-next) {tail tail-next;}free(tail-next);tail-next NULL; 我们判断条件改成这样实际上我们找的tail是倒数第二个节点所以最后的删除需要改成tail的next为NULL。
2.2.2 头删
头删的逻辑就更加简单了我们只需要创建一个变量来保存原来的头节点方便我们后续删除然后让原头节点移到下一个结点成为新的头结点然后删掉原来的。如果我们不保存我们没有办法找到原来的头结点。
代码如下
void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* first *pphead;*pphead (*pphead)-next;free(first);first NULL;
}
2.3 查
这个实现也很简单就是遍历然后匹配。由于是查找而不是对数据进行修改所以传一级指针即可。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* cur phead;while (cur) {if (cur-data x) {return cur;}cur cur-next;}return NULL;
}
2.4 改
2.4.1 在pos前插入 将图画出来我们就清晰明了了。我们如果想把node插入到pos前我们只需要将node的next指向pos然后将prev的next指向node这样就构成了插入操作。 试想一下1和2的操作可以调换顺序吗答案是不可以这是因为如果我们先做2这个时候我们就找不到pos了也就不能执行1操作了。有人会问我创建两个变量来记录这两个点的位置不可以吗可以但是没必要。
之后我们来看代码部分首先我们要创建一个node节点用buynode函数。正常情况我们需要找pos的前一个节点prev利用循环即可。如果只有一个节点怎么办呢这个时候直接头插就可以了。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);SLTNode* node BuyNode(x);if (*pphead pos) {// node-next pos;// *pphead node;SLTPushFront(pphead, x);return;}//找pos的前一个节点SLTNode* prev *pphead;while (prev-next) {if (prev-next pos) {break;}prev prev-next;}node-next pos;prev-next node;
}
2.4.2 删除pos
其实逻辑也是很简单的要删除pos的话我们需要找到pos前面的节点保存否则就找不到了。
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);if (*pphead pos) {// SLTNode *del *pphead;// *pphead (*pphead)-next;// free(del);// del NULL;SLTPopFront(pphead);return;}//找pos的前一个节点SLTNode* prev *pphead;while (prev-next) {if (prev-next pos) {break;}prev prev-next;}prev-next pos-next;free(pos);// pos NULL;//没有存在的必要
}
并且要注意连接好pos后面的节点后再删除不然也找不到。
2.4.3 在pos后插入
逻辑跟在pos前插入一样也要注意顺序只不过在pos之后插入不需要传链表第一个节点了只需要传pos即可。
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* node BuyNode(x);node-next pos-next;pos-next node;
}
2.4.4 删除pos后的节点
void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos-next);SLTNode *del pos-next;pos-next del-next;free(del);del NULL;
}
其实看到这你就发现对链表的操作无非就是保存节点然后连接同时画图操作也可以对我们学习数据结构有所帮助。
2.5 链表的销毁
我们将链表每个节点通过循环遍历free掉即可唯一比较吃操作的就是创建一个用于保存下一个节点的位置的指针。
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
