网站的服务器是什么,如何备份wordpress站点,广州 建网站,甘肃兰州海拔多少米#x1f308;个人主页#xff1a;小新_- #x1f388;个人座右铭#xff1a;“成功者不是从不失败的人#xff0c;而是从不放弃的人#xff01;”#x1f388; #x1f381;欢迎各位→点赞#x1f44d; 收藏⭐️ 留言#x1f4dd; #x1f3c6;所属专栏#xff1… 个人主页小新_- 个人座右铭“成功者不是从不失败的人而是从不放弃的人” 欢迎各位→点赞 收藏⭐️ 留言 所属专栏 数据结构与算法欢迎订阅持续更新中~~~ ✨让小新带着你快乐的学习吧~✨ 目录
1. 链表的概念及结构
2、单链表的实现
准备工作
1、单链表的插入
1头插
2尾插
3指定位置前插
4指定位置后插
2、单链表的删除
1头删
2尾删
3删除指定位置节点
4删除指定位置之后节点
3、单链表的查找
4、单链表的销毁
3、链表的分类
4、 链表经典算法OJ题⽬
3.1 单链表相关经典算法OJ题1移除链表元素(点击进入题目)
3.2 单链表相关经典算法OJ题2反转链表点击进入题目
3.3 单链表相关经典算法OJ题3合并两个有序链表点击进入题目
3.4 单链表相关经典算法OJ题4链表的中间结点点击进入题目
3.5 循环链表经典应⽤-环形链表的约瑟夫问题点击进入题目
3.6 单链表相关经典算法OJ题5分割链表点击进入题目 1. 链表的概念及结构 概念链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 链表的结构跟⽕⻋⻋厢相似淡季时⻋次的⻋厢会相应减少旺季时⻋次的⻋厢会额外增加⼏节。只 需要将⽕⻋⾥的某节⻋厢去掉/加上不会影响其他⻋厢每节⻋厢都是独⽴存在的。 ⻋厢是独⽴存在的且每节⻋厢都有⻋⻔。想象⼀下这样的场景假设每节⻋厢的⻋⻔都是锁上的状 态需要不同的钥匙才能解锁每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾 最简单的做法每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 在链表⾥每节“⻋厢”是什么样的呢 与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点/节点” 节点的组成主要有两个部分当前节点要保存的数据和保存下⼀个节点的地址指针变量。 图中指针变量 plist保存的是第⼀个节点的地址我们称plist此时“指向”第⼀个节点如果我们希 望plist“指向”第⼆个节点时只需要修改plist保存的内容为0x0012FFA0。 为什么还需要指针变量来保存下⼀个节点的位置 链表中每个节点都是独⽴申请的即需要插⼊数据时才去申请⼀块节点的空间我们需要通过指针 变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。 结合前⾯学到的结构体知识我们可以给出每个节点对应的结构体代码 struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};当我们想要保存⼀个整型数据时实际是向操作系统申请了⼀块内存这个内存不仅要保存整型数 据也需要保存下⼀个节点的地址当下⼀个节点为空时保存的地址为空。 当我们想要从第⼀个节点⾛到最后⼀个节点时只需要在前⼀个节点拿上下⼀个节点的地址下⼀个 节点的钥匙就可以了。 补充说明 1、链式机构在逻辑上是连续的在物理结构上不⼀定连续 2、节点⼀般是从堆上申请的 3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续 2、单链表的实现
准备工作
单链表实现前有几个小段代码和问题
1、首先我们来搞懂一个一个概念上的问题就是节点的实参形参问题其实就是考验对指针的理解与掌握 2、申请新的节点
代码比较简单用malloc函数申请新节点的空间让新节点的的data域置为x,next域为空
SLTNode* SLNewNode(SLDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-Data x;newnode-next NULL;return newnode;
}
3、打印当前链表 上代码
void SLPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-Data);pcur pcur-next;}printf(NULL);
}
4、单链表的声明
typedef int SLDataType;
typedef struct SListNode
{SLDataType Data;struct SListNode* next;
}SLTNode;
1、单链表的插入
1头插
分析 尾删思路比较简单我们有头结点的指针phead我们让我们新申请的节点的next指针指向原来的头结点就完成了我们考虑一下特殊情况如果链表为空怎么办那还不简单直接成为新的节点代码就跟不是空表一样so easy!小小头插拿下拿下。
void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode SLNewNode(x);newnode-next *pphead;*pphead newnode;}
2尾插
分析 如图我们想插入一个元素4如何插入呢首先我们得找到原尾节点吧。然后让原尾节点的next指针指向4这个新节点这样我们的4就成为了尾节点再让4的next指针指向NULL。但有一个问题那就是如果链表为空怎么办那就没有尾节点了。直接将这个节点作为我们的新节点。所以大体思路就是先判断链表是否为空如果是就直接作为新的节点如果不是我们就先找到尾节点然后执行插入操作就可以了。
代码如下
void SLPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode SLNewNode(x);//链表为空作为结点if (*pphead NULL){*pphead newnode;return;}//链表不为空寻找尾节点SLTNode* ptail *pphead;//寻找尾节点while (ptail-next){ptail ptail-next;}//ptail就是尾节点ptail newnode;
}
3指定位置前插
分析 我们看到要想在pos(3)之前插入我们就要找到pos之前的节点prevprev的next指向newnodenewnode的next指向pos。考虑特殊情况当pos是头结点时就没有prev怎么办呢我们可以直接调用头插即可。
代码如下
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode SLNewNode(x);//如果pos是头结点if (pos *pphead){SLPushFront(newnode, x);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;
}
4指定位置后插
分析 指定位置后插比指定位置前插较为简单但要注意的是顺序如果先把pos的next给newnode,newnode中的next保存的是pos的下一个节点地址然后再将newnode的next指向下一节点这样导致pos的next不再指向真正的下一节点。而应该先把pos的next赋值给newnode的next,再将pos的next指向newnode.
代码如下 2、单链表的删除
1头删
分析 头删比较简单将原来的第二个节点作为新链表的第一个节点并将原来第一个节点释放掉,并将next赋给pphead
代码如下
void SLPopFront(SLTNode** pphead)//头删
{assert(pphead);//链表不为空assert(*pphead);//-指向第一个节点的地址SLTNode* next (*pphead)-next;free(*pphead);(*pphead) next;
}
2尾删
分析 既然要进行删除操作那么链表至少得有一个节点吧所以得提前判断一下。要进行尾删首先我们要找到尾节点的前一个节点我们就叫他prev吧让prv不再指向尾节点的next域而是NULL然后将尾节点用free函数将尾节点的内存还给操作系统。但只有一个节点的时候呢我们只能将该节点释放掉咯没办法的事无奈
void SLPopBack(SLTNode** pphead)
{assert(pphead);//链表不为空assert(*pphead);//-指向第一个节点的地址while ((*pphead)-nextNULL)//如果只有一个节点{free(*pphead);*pphead NULL;return;}//具有多个节点SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptailptail-next;}//找到prev了prev-next NULL;free(ptail);
ptailNULL//别忘了置空以免疯狗乱咬人狗头 狗头
}
3删除指定位置节点
分析 删除指定位置的节点我们定义一个指针prev让prev找到pos之前的节点寻找prev的循环条件prev-next !pos此时将prev的next指针指向pos的下一个节点再将pos释放掉。注意顺序不能颠倒需要注意的是特殊情况当pos就是头结点。此时没有prev我们可以直接执行头删操作。
代码如下
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos *pphead){SLPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}(prev-next) (pos-next);free(pos);pos NULL;
}
4删除指定位置之后节点
分析 思路比较清晰看图一目了然将pos的next指针指向pos下一个节点的下一个节点
代码如下
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);pos-next pos-next-next;free(pos-next);pos-next NULL;
}
3、单链表的查找
没什么好说的上代码
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-Data x) {return pcur;}pcur pcur-next;}//没有找到return NULL;
}
4、单链表的销毁
上代码
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
完整代码如下
sqlist.c
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid SLPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-Data);pcur pcur-next;}printf(NULL\n);
}
SLTNode* SLNewNode(SLDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-Data x;newnode-next NULL;return newnode;
}
void SLPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode SLNewNode(x);//链表为空作为结点if (*pphead NULL){*pphead newnode;return;}//链表不为空寻找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail就是尾节点ptail newnode;
}
void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode SLNewNode(x);newnode-next *pphead;*pphead newnode;
}
void SLPopBack(SLTNode** pphead)
{assert(pphead);//链表不为空assert(*pphead);//-指向第一个节点的地址while ((*pphead)-nextNULL)//如果只有一个节点{free(*pphead);*pphead NULL;return;}//具有多个节点SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptailptail-next;}//找到prev了prev-next NULL;free(ptail);
}
void SLPopFront(SLTNode** pphead)//头删
{assert(pphead);//链表不为空assert(*pphead);//-指向第一个节点的地址SLTNode* next (*pphead)-next;free(*pphead);(*pphead) next;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode SLNewNode(x);//如果pos是头结点if (pos *pphead){SLPushFront(newnode, x);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;
}
//在指定位置之后插入数据
void SLInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode SLNewNode(x);newnode-next pos-next;pos-next newnode;
}
//删除pos节点
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos *pphead){SLPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}(prev-next) (pos-next);free(pos);pos NULL;
}
//删除pos之后的节点
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);pos-next pos-next-next;free(pos-next);pos-next NULL;
}
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-Data x) {return pcur;}pcur pcur-next;}//没有找到return NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
slist.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int SLDataType;
typedef struct SListNode
{SLDataType Data;struct SListNode* next;
}SLTNode;
void SLPrint(SLTNode* phead);
SLTNode* SLNewNode(SLDataType x);
void SLPushBack(SLTNode** phead, SLDataType x);
void SLPushFront(SLTNode** phead, SLDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode** pphead, SLDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);
测试文件这里就不包含了读者朋友可以自己写代码的时候测试 3、链表的分类 链表的结构⾮常多样以下情况组合起来就有8种2 x 2 x 2链表结构 如下 虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构 单链表 和 双向带头循环链表 1. ⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 2. 带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带 来很多优势实现反⽽简单了后⾯我们代码实现了就知道了。 4、 链表经典算法OJ题⽬ 3.1 单链表相关经典算法OJ题1移除链表元素(点击进入题目) 思路一遍历原链表当遇到等于vul节点的时候就执行删除操作 但有一个问题就是删除操作太麻烦有没有别的更好地方法呢 思路二创建一个新链表遍历原链表当节点值不为val时尾插到新链表尾部 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//定义新链表的头尾巴指针ListNode* newHead,*newTail;newHeadnewTailNULL;ListNode* pcurhead;while(pcur) {ifpcur-val !val//节点值不为val插入链表尾部{if(newHeadNULL)//链表为空{newHeadnewTailpcur;}else//链表不为空插入尾部{newTail-nextpcur;newTailnewTail-next;}}//等于val直接下一个节点pcurpcur-next;}if(newTail){newTail-nextNULL;}return newTail
} 3.2 单链表相关经典算法OJ题2反转链表点击进入题目 思路一创建一个新链表遍历原链表将原链表元素依次头插在新链表当中。 思路二定义三个指针变量分别指向当前节点前驱和后继节点改变节点指向即可。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(headNULL){return head;}ListNode* n1,*n2,*n3;n1NULL,n2head,n3head-next;ListNode* pcur;while(n2){n2-nextn1;n1n2;n2n3;if(n3){n3n3-next;}}return n1;
} 3.3 单链表相关经典算法OJ题3合并两个有序链表点击进入题目 思路建立一个新链表比较俩个链表元素谁小就插入新链表 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1NULL){return list2;}if(list2NULL){return list1;}ListNode* l1,*l2;l1list1,l2list2;ListNode* newHead,*newTail;newHeadnewTail(ListNode*)malloc(sizeof(ListNode));while(l1l2){if(l1-vall2-val){newTail-nextl1;newTailnewTail-next;l1l1-next;}else{newTail-nextl2;newTailnewTail-next;l2l2-next;}}if(l1){newTail-nextl1;}if(l2){newTail-nextl2;}ListNode*ret newHead-next;free(newHead);newHeadNULL;return ret;} 3.4 单链表相关经典算法OJ题4链表的中间结点点击进入题目 思路一遍历统计节点个数当遍历完链表将节点个数除以2可以得到中间节点位置 思路二快慢指针定义一个快指针和一个慢指针快指针一次走俩个元素慢指针一次走一个元素。那当快指针遍历完链表时慢指针就刚好指向中间节点输出该节点即可。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* fast,*slow;fastslowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
} 3.5 循环链表经典应⽤-环形链表的约瑟夫问题点击进入题目 著名的Josephus问题 据说著名犹太 历史学家 Josephus有过以下的故事在罗⻢⼈占领乔塔帕特后39 个犹太⼈与 Josephus及他的朋友躲到⼀个洞中39个犹太⼈决定宁愿死也不要被⼈抓到于是决定了⼀个⾃杀 ⽅式41个⼈排成⼀个圆圈由第1个⼈开始报数每报数到第3⼈该⼈就必须⾃杀然后再由下⼀ 个重新报数直到所有⼈都⾃杀⾝亡为⽌。 然⽽Josephus 和他的朋友并不想遵从Josephus要他的朋友先假装遵从他将朋友与⾃⼰安排在 第16个与第31个位置于是逃过了这场死亡游戏。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
if(headNULL){return head;
}
ListNode* newHeadLess,*newTailLess,*newHeadGreagter,*newTailGreagter;newHeadLessnewTailLess(ListNode*)malloc(sizeof(ListNode));
newHeadGreagternewTailGreagter(ListNode*)malloc(sizeof(ListNode));ListNode* pcurhead;
while(pcur){if(pcur-valx){newTailLess-nextpcur;newTailLessnewTailLess-next;}else{newTailGreagter-nextpcur;newTailGreagternewTailGreagter-next;}pcurpcur-next;
}newTailGreagter-nextNULL;newTailLess-nextnewHeadGreagter-next;ListNode*retnewHeadLess-next;free(newHeadGreagter);free(newHeadLess);return ret;
} 3.6 单链表相关经典算法OJ题5分割链表点击进入题目 思路建立大小链表大于x放大链表小于x放小链表最后连接起来
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
if(headNULL){return head;
}
ListNode* newHeadLess,*newTailLess,*newHeadGreagter,*newTailGreagter;newHeadLessnewTailLess(ListNode*)malloc(sizeof(ListNode));
newHeadGreagternewTailGreagter(ListNode*)malloc(sizeof(ListNode));ListNode* pcurhead;
while(pcur){if(pcur-valx){newTailLess-nextpcur;newTailLessnewTailLess-next;}else{newTailGreagter-nextpcur;newTailGreagternewTailGreagter-next;}pcurpcur-next;
}newTailGreagter-nextNULL;newTailLess-nextnewHeadGreagter-next;ListNode*retnewHeadLess-next;free(newHeadGreagter);free(newHeadLess);return ret;
} 最后感谢大家的观看~~
