? ? ? ?? ? ? ?

1、線性表定義

線性表是指n個元素的有限序列(n>=0),通常用(a1,a2,a3...,an),來表示。

2、線性表特點

1、存在唯一的一個首元素

2、存在唯一一個尾元素

3、除第首元素外，每個元素只有一個直接前驅。

4、除尾元素外，每個元素只有一個直接后繼。

3、線性表的存儲結構

3.1 線性表的順序存儲

定義：線性表的順序存儲是指用一組連續的存儲單元依次存儲線性表中的數據元素，從而使得邏輯上相鄰的兩個元素在物理存儲位置上也相鄰。這種存儲方式無需占用額外的存儲空間來存儲。

優點：可以隨機讀取 表中的元素。按照序號檢索元素比較快。

缺點：插入、刪除元素都需要移動元素。

3.2 線性表的鏈式存儲

3.2.1 線性表的概念

定義：是節點來存儲數據元素，元素節點的地址可以連續，也可以不連續。因此節點之間的元素的存儲必須有邏輯關系。

元素節點：包含數據域、指針域（存儲該元素的直接前驅、直接后繼的位置信息）

優點：插入和刪除操作不需要移動元素。、

缺點：只能順序的讀取元素，不能隨機讀取。

3.2.2 線性鏈表的分類

單鏈表：最后一個節點指針域為null

循環鏈表：最后一個指針域為指向第一個節點。因此循環鏈表可以從任意節點開始遍歷整個鏈表。

雙向鏈表：每個節點包含兩個指針，分別指明當前元素的直接前驅和直接后繼的存儲信息。可以從兩個方向遍歷鏈表中的元素。

3.3 ?線性表順序存儲和鏈式存儲比較

性能方面	比較內容	順序存儲	鏈式存儲
空間性能	存儲密度	=1 ?更優	<1
	存儲容量	初始化確定	動態分配，更優
	查詢算法	O(n/2)	O(n/2)
	讀取算法	O(1) 更優	O([n+1]/2)，范圍1~n
	插入算法	O([n]/2)，范圍0~n	O(1) 更優
	刪除算法	O([n-1]/2)	O(1) 更優

?

?

IT技術分享社區

個人博客網站：https://programmerblog.xyz

文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識