線性表的定義

線性表(linear-list)是最常用最簡單的一種數據結構。一個線性表是n (n≥0)個相同類型數據元素的有限序列。記為： L= (a1, a2 , … , an )。

其中，L是表名，a1是第一個數據元素（也簡稱為首元素），無前驅，只有一個后繼；an是最后一個數據元素(即第n個數據元素)，只有一個前驅，無后繼。其余的每個數據元素ai (i=2,3, … ,n-1)都只有一個前驅，且只有一個后繼。i (i=1,2, … ,n)稱為表中元素序號。n是數據元素的個數，也稱為表的長度，若n=0，L稱作空表。

線性表的順序表示

線性表的順序存儲方式是指：用一組連續的有限空間依次存儲線性表中的數據元素，簡稱為順序表。

順序表的特點是：

一塊地址連續的空間存放線性表中的數據元素。任意兩個邏輯上相鄰的數據元素在物理上也必然相鄰。

順序表可以隨機訪問。

順序表通常用數組存儲，在C++中，數組有靜態數組和動態數組兩種，在此我們將采用動態數組方式存儲。

順序表插入、刪除算法的復雜度分析

通常順序表的插入和刪除操作都會保持各元素原來的順序不變。

舉例來看順序表上的插入和刪除。

在原來已有7個元素的表的第4個元素前插入數據元素x=24的過程。

線性表的順序存儲方式的缺陷

順序表是用數組方式來存儲的，因數組元素個數固定。當順序表的長度等于數組的元素個數時，順序表就不能再插入新數據元素了。

對于有n個數據元素的順序表，若要保持各數據元素原來的順序不變，則插入和刪除一個數據元素的時間復雜度為O(n)。

順序表要求存儲空間是物理上連續的，這樣即使存儲空間中的存儲單位數超過所需的數目，卻因其不連續，也無法使用。

克服這些缺陷的辦法是：對線性表采用鏈表存儲方式。

在鏈表存儲方式中，用戶通過new函數向系統動態申請所需的存儲空間，把數據元素插入鏈表中合適的位置，而這些在不同時刻向系統動態申請的存儲空間在內存中很可能不連續。

因而，任意兩個在邏輯上相鄰的數據元素在物理上不一定相鄰，數據元素的邏輯次序是通過鏈表中的指針鏈接實現的。

鏈表的表長是動態的、可擴充的，在鏈表中插入和刪除時不需移動元素。

用鏈表存儲方式存儲線性表數據元素的方法是用結點(node)構造鏈。結點通常有一個數據域，另外還有一個或一個以上的指針域。

鏈表存儲主要有單鏈、單循環鏈和雙向鏈等三種。這三種結構中每一種又有帶頭結點結構和不帶頭結點結構兩種。

單鏈表

單鏈表的結構

采用鏈接存儲方式存儲的線性表稱為線性鏈表，又稱單鏈表(linked list)，或簡稱為鏈表。在單鏈表中，每一個數據元素占用一個結點。如圖3-5所示。一個結點由兩個域組成，一個域存放數據元素data，一個域存放指向該鏈表中下一個結點的指針next，它給出下一個結點的開始存儲地址。

在單鏈表的表尾結點中，指針域為空以“?”表示之。設線性表存有某系99級學生的學號如下：(99101，99104，99110，99201，99208)，可用如圖3-6所示的單鏈表表示。

單鏈表結構中又有帶頭結點和不帶頭結點兩種結構。像圖3-6這樣的第一個結點就是數據結點的單鏈表結構，我們稱其為不帶頭結點的單鏈表。

3-7是帶頭結點的單鏈表結構，頭結點是由頭指針所指向的不存放數據元素的結點。我們把頭結點的數據域部分涂上陰影，以明顯表示該結點為頭結點。

單循環鏈表

單循環鏈表，簡稱循環鏈表(circular list), 是線性表的另一種鏈表表示，它的結點結構與單鏈表相同，由一個數據域和一個指針域組成，與單鏈表不同的是鏈表中表尾結點的next域中不是NULL，而是存放了head所指的結點。

在單循環鏈表中判斷當前指針pcurrent是否到達鏈表尾的條件應是pcurrent->next == head。

單循環鏈表也有不帶頭結點和帶頭結點兩種結構，分別如圖3-14，圖3-15所示。

對單循環鏈表，只要知道表中任一結點的地址，就能遍歷表中其他任何結點。循環鏈表的運算與單鏈表類似，不過在鏈頭與鏈尾處理時有所不同。

總結

以上是生活随笔為你收集整理的Java数据结构和算法：线性表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。