自己电脑上做网站怎么使用源码,深圳广告公司集中在哪里,wordpress 页面列表,同步编辑wordpress【C语言】链表带环问题分析及顺序表链表对比分析 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;C语言学习之路 文章目录 【C语言】链表带环问题分析及顺序表链表对比分析前言一.顺序表和链表对比1.1顺序表和链表的区别1.2缓存利用率#…【C语言】链表带环问题分析及顺序表链表对比分析 个人主页大白的编程日记
专栏C语言学习之路 文章目录 【C语言】链表带环问题分析及顺序表链表对比分析前言一.顺序表和链表对比1.1顺序表和链表的区别1.2缓存利用率缓存命中率 二.链表的带环问题2.1快慢指针2.2证明快慢指针相遇问题2.3快指针的步长2.4环的入口 后言 前言 哈喽各位小伙伴大家好由于考试周很久没有更新博客了。今天给大家带来的是链表的带环问题和顺序表链表的对比分析。话不多说进入正题。向大厂冲锋 一.顺序表和链表对比
1.1顺序表和链表的区别 顺序表和链表是两种不同的数据结构。他们各有各的优劣。我们就来对比分析一下他们的区别。我们这里用带头双向循环链表和顺序表做对比。 存储空间 顺序表物理上是连续的。 链表因为链表是由节点组成每个节点由指针连接。 所以在逻辑上是连续的但每个节点都是malloc动态开辟的在物理空间上不一定连续。 随机访问 顺序表顺序表可以通过下标来进行随机访问。 链表链表不支持随机访问只能从头节点开始遍历寻找节点。 任意位置插入删除 顺序表如果不是尾插尾删需要挪动数据。 链表链表由节点组成插入或删除只需要修改前后节点的指针指向即可。 扩容 顺序表空间不够需要扩容。 扩容realloc本身会有消耗且异地扩容消耗不小2倍扩容可能存在空间浪费。 链表按需申请释放需要一个申请一个不存在扩容不会浪费空间。
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
int main()
{int* p (int*)malloc(4);printf(%p\n, p);int* p1 (int*)realloc(p, 40);printf(%p, p1);
}异地扩容 只要空间大一点基本都是异地扩容。 原地扩容
应用场景 顺序表和链表的优劣是互补的。 顺序表适合随机访问不适合中间位置的插入删除。 链表适合任意位置的插入删除但无法随机访问。 所以如果经常随机访问但只需要尾插尾删就选择顺序表。 如果不经常随机访问在中间位置插入删除就选择链表。 具体根据他们的优劣进行选择。 1.2缓存利用率缓存命中率 顺序表和链表的区别还有一个就是 顺序表的缓存命中率高。 链表的缓存命中率低。 为什么呢?什么是缓存命中率呢?
内存和硬盘
这是我们计算机的内部的存储结构。 主存也就是我们的内存和硬盘的区别就是 内存的存储空间更小通常为8G和16G,但速度快。需要带电存储 硬盘存储空间更大速度慢但不需要带电存储。 他们的本质是带不带电。 例如 如果我正在写一份ppt因为硬盘的速度慢所以是存在内存中的如果我这时电脑突然没电关机。重新开机后我的ppt就不见了。因为我没有另存到硬盘中。 只用当我们另存到硬盘中才存在。 寄存器和三级缓存 那既然已经有内存内存的速度也还行为什么还有寄存器和三级缓存呢
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
int main()
{int i 0;int ret i;
}以这段代码为例 i存在内存中也就是main函数的栈帧里。i的执行过程是这样的 先把i放在eax寄存器中 对eax, 把eax寄存器放i的内存位置 那为什么要这样做呢 因为CPU和内存不同频CPU跑的太快了。 如果直接访问内存数据进行,因为内存太慢了。 他宁愿把内存中数据加载到寄存器中CPU在寄存器执行指令再把运行结果返回内存。
一般来说CPU不会直接访问内存 寄存器 如果数据比较小(4或8字节)就会把数据加载到寄存器。 缓存 如果数据比较大就加载到缓存中。 缓存命中如果要访问的数据在缓存叫缓存命中直接访问。 缓存不命中如果要访问的数据不在缓存叫缓存不命中先把数据加载到缓存中再访问。 缓存的加载 如果你要加载4个字节到缓存通常会加载一长段空间到缓存中。而不只是4个字节。为什么呢
把内存看作学校缓存看作大巴CPU看作度假村。 现在学校安排大巴把学生(数据)送到度假村去。
所以顺序表的缓存命中率高 链表的缓存命中率低而且会造成缓存污染。 如果大家想多了解缓存的话可以看这篇文章 与程序员相关的CPU缓存知识
二.链表的带环问题 链表带环是链表中的经典问题值得我们深入学习。解决带环问题通常使用快慢指针相遇解决。但是你如何证明快慢指针一定相遇以及快指针的步长不同会怎样呢接下来小编带大家一一探讨。 2.1快慢指针
题目 环形链表 思路 创建一个快指针和一个慢指针快指针一次走两步慢指针一次走一步。 如果是链表带环快慢指针最终会相遇。不带环则快指针走到尾。代码实现 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{ListNode*slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;//慢指针走一步fastfast-next-next;//快指针走两步if(fastslow)//快慢指针相遇{return true;}}return false;//不带环
}2.2证明快慢指针相遇问题
那如何证明题目一定会相遇呢 当慢指针入环时快指针与慢指针相差N个节点。 由于快指针每次走两步慢指针走一步。 每次移动快指针都会与慢指针的距离缩小一个节点。 当他们的距离节点缩小为0时就会相遇。 所以快慢指针一定能够相遇。
2.3快指针的步长
那快指针是不是只能走一步呢如果快指针走345…N步还一定能相遇吗
步长为3时 证明结果如下
我们用快慢指针步长的关系列出等式反推证明N为奇数和C为偶数的情况不会出现从而得出结论步长为3时一定能相遇。 验证 步长为345…N 这些情况和前面的推导证明过程相似大家有兴趣可以自己深入探究。
2.4环的入口 题目 环形链表二 思路 创建一个快指针和一个慢指针快指针一次走两步慢指针一次走一步。 如果是链表带环快慢指针最终会相遇。 一个指针相遇点开始走一个指针从头节点开始走每次两个指针都走一步。 当两个指针相遇时相遇节点就是入环节点。 不带环则快指针走到尾。 代码实现 typedef struct ListNode ListNode ;
struct ListNode *detectCycle(struct ListNode *head)
{ListNode*slow,*fast;slowfasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast){ListNode* pcurslow;while(pcur!head){pcurpcur-next;headhead-next;}return pcur;}}return NULL;
}证明
具体证明过程如下 验证 -
所以根据推导我们得出只要再相遇后一个head指针从头节点出发一个pcur节点从相遇点出发等他们相遇时相遇点就是入环点。
后言 这就是链表的带环问题和顺序表链表的对比。这些都是我们数据结构学习时的重要内容。大家一定要好好掌握。今天就分享到这里咱们下期见拜拜~
