資源簡介

(共11張PPT)
第二章 數組和鏈表
選修一《數據與數據結構》
2.2 鏈表的概念、特性與基本操作
01
Part
什么是鏈表？
鏈表的節點結構
單向鏈表、雙向鏈表和循環鏈表
鏈表在內存當中的存儲
鏈表的特性
鏈表指的是將需要處理的數據對象以節點的形式，通過指針串聯在一起的一種數據結構。
鏈表是什么？
太抽象了，無法理解
貨車
火車
顧客新增加了采購量超出了貨車的承載量？
只能選擇換一個承載量更大的貨車來運輸
鏈表指的是將需要處理的數據對象以節點的形式，通過指針串聯在一起的一種數據結構。
鏈表是什么？
數據對象
節點
指針
鏈表是什么？
1.鏈表的節點結構
數據區域
指針區域
保存數據區域
保存相鄰節點的
存儲地址
head
前驅節點
后繼節點
頭指針（head）的作用
一是鏈表的入口，用戶只有通過頭指針才能進入鏈表
二是為循環鏈表設立一個邊界，便于數據處理時的邊界判斷與處理
A點寶藏
B點地址
B點寶藏
None
鏈表是什么？
2.單向鏈表、雙向鏈表和循環鏈表
None
單向鏈表
None
None
雙向鏈表
循環鏈表
鏈表是什么？
3.鏈表在內存當中的存儲
數組
有16字節的貨物需要存儲
4字節
又新增了4字節的存儲需求
鏈表是什么？
3.鏈表在內存當中的存儲
數組
鏈表
有16字節的貨物需要存儲
又新增了4字節的存儲需求
4字節
鏈表是什么？
3.鏈表在內存當中的存儲
數組
鏈表
鏈表占用的空間不固定
有16字節的貨物需要存儲
又新增了4字節的存儲需求
4字節
鏈表是什么？
4.鏈表的特性
a.鏈表占用的空間不固定
鏈表
鏈表的節點間通過指針相連，相鄰節點存儲時不需要連續空間，充分利用了內存的零散空間，提高了存儲空間利用率。
b.每個鏈表必定有一個頭指針（head），以實現對鏈表的引用和邊界處理
head
循環鏈表
head
c.同一鏈表中每個節點的結構均相同
數據區域
指針區域
數據類型相同
數量和功能相同
一是鏈表的入口，用戶只有通過頭指針才能進入鏈表
二是為循環鏈表設立一個邊界，便于數據處理時的邊界判斷與處理
鏈表要怎么用？
head
小組合作討論：
有關鏈表的創建、訪問、插入和刪除操作要怎么實現呢？

展開更多......

收起↑