肚子餓了就要吃 ~ 嗝 ——— 路飛

1.本章重點

2.為什么需要鏈表

引子：順序表的問題及思考

(1)動態順序表

特點：

缺陷：

（2）如何解決：

這就引出了一個新的物理存盤結構 ————> 鏈表

概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，

邏輯結構（想象出來的），如圖：（單鏈表為例）

物理結構（在記憶體中的結構），如圖：（單鏈表為例）

實際中要實作的鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

雖然有這么多的鏈表的結構，但是我們實際中最常用還是兩種結構：

1. 無頭單向非回圈鏈表：

結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，

2. 帶頭雙向回圈鏈表：

結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而簡單了，后面我們代碼實作了就知道了，

注：

plist/phead——>頭指標（一般保持不動）

cur——>當前位置( current簡寫)

找尾巴注意的點：

對比

	//錯誤代碼
    //找到原來的尾巴（進而插尾）
	SLTNode* tail = phead;
	while (tail != NULL)
	{
		tail = tail->next;
	}

	//正確代碼
    //找到原來的尾巴（進而插尾）
	SLTNode* tail = phead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}

解釋：

第一段代碼是錯誤的，因為

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298733.html

標籤：其他