【C語言】鏈表帶環問題分析及順序表鏈表對比分析

🔥個人主頁：大白的編程日記

🔥專欄：C語言學習之路

---

前言

哈嘍，各位小伙伴大家好！由于考試周很久沒有更新博客了。今天給大家帶來的是鏈表的帶環問題和順序表鏈表的對比分析。話不多說，進入正題。向大廠沖鋒！

一.順序表和鏈表對比

1.1順序表和鏈表的區別

順序表和鏈表是兩種不同的數據結構。他們各有各的優劣。我們就來對比分析一下他們的區別。我們這里用帶頭雙向循環鏈表和順序表做對比。

• 存儲空間
  順序表：物理上是連續的。
  鏈表：因為鏈表是由節點組成，每個節點由指針連接。 所以在邏輯上是連續的，但每個節點都是malloc動態開辟的，在物理空間上不一定連續。
  
• 隨機訪問
  順序表：順序表可以通過下標來進行隨機訪問。
  鏈表：鏈表不支持隨機訪問，只能從頭節點開始遍歷尋找節點。
  
• 任意位置插入刪除
  順序表：如果不是尾插尾刪，需要挪動數據。
  鏈表：鏈表由節點組成，插入或刪除只需要修改前后節點的指針指向即可。
  
• 擴容
  順序表：空間不夠需要擴容。
  擴容realloc本身會有消耗且異地擴容消耗不小，2倍擴容可能存在空間浪費。
  鏈表：按需申請釋放，需要一個申請一個，不存在擴容，不會浪費空間。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.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
#include<stdio.h>
#include<stdlib.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;slow=fast=head;while(fast&&fast->next){slow=slow->next;//慢指針走一步fast=fast->next->next;//快指針走兩步if(fast==slow)//快慢指針相遇{return true;}}return false;//不帶環
}

2.2證明快慢指針相遇問題

那如何證明題目一定會相遇呢？

當慢指針入環時，快指針與慢指針相差N個節點。
由于快指針每次走兩步，慢指針走一步。
每次移動快指針都會與慢指針的距離縮小一個節點。
當他們的距離節點縮小為0時，就會相遇。
所以快慢指針一定能夠相遇。

2.3快指針的步長

那快指針是不是只能走一步呢？如果快指針走3，4，5…N步還一定能相遇嗎？

• 步長為3時
  證明結果如下
  

我們用快慢指針步長的關系列出等式，反推證明N為奇數和C為偶數的情況不會出現，從而得出結論步長為3時一定能相遇。

• 驗證
  

• 步長為3，4，5…N
  這些情況和前面的推導證明過程相似，大家有興趣可以自己深入探究。

2.4環的入口

• 題目
  環形鏈表二

• 思路
  創建一個快指針和一個慢指針，快指針一次走兩步，慢指針一次走一步。
  如果是鏈表帶環，快慢指針最終會相遇。
  一個指針相遇點開始走，一個指針從頭節點開始走，每次兩個指針都走一步。
  當兩個指針相遇時，相遇節點就是入環節點。
  不帶環，則快指針走到尾。

• 代碼實現

 typedef struct ListNode ListNode ;
struct ListNode *detectCycle(struct ListNode *head) 
{ListNode*slow,*fast;slow=fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){ListNode* pcur=slow;while(pcur!=head){pcur=pcur->next;head=head->next;}return pcur;}}return NULL;
}

• 證明

具體證明過程如下：

• 驗證
  -

所以根據推導我們得出只要再相遇后，一個head指針從頭節點出發，一個pcur節點從相遇點出發，等他們相遇時，相遇點就是入環點。

后言

這就是鏈表的帶環問題和順序表鏈表的對比。這些都是我們數據結構學習時的重要內容。大家一定要好好掌握。今天就分享到這里，咱們下期見！拜拜~