線性表，全名為線性存儲結(jié)構(gòu)。使用線性表存儲數(shù)據(jù)的方式可以這樣理解，即“把所有數(shù)據(jù)用一根線兒串起來，再存儲到物理空間中”。

如圖 1 所示，這是一組具有“一對一”關(guān)系的數(shù)據(jù)，我們接下來采用線性表將其儲存到物理空間中。

首先，用“一根線兒”把它們按照順序“串”起來，如圖 2 所示：

圖 2 中，左側(cè)是“串”起來的數(shù)據(jù)，右側(cè)是空閑的物理空間。把這“一串兒”數(shù)據(jù)放置到物理空間，我們可以選擇以下兩種方式，如圖 3 所示。

圖 3a) 是多數(shù)人想到的存儲方式，而圖 3b) 卻少有人想到。我們知道，數(shù)據(jù)存儲的成功與否，取決于是否能將數(shù)據(jù)完整地復(fù)原成它本來的樣子。如果把圖 3a) 和圖 3b) 線的一頭扯起，你會發(fā)現(xiàn)數(shù)據(jù)的位置依舊沒有發(fā)生改變(和圖 1 一樣)。因此可以認(rèn)定，這兩種存儲方式都是正確的。

將具有“一對一”關(guān)系的數(shù)據(jù)“線性”地存儲到物理空間中，這種存儲結(jié)構(gòu)就稱為線性存儲結(jié)構(gòu)(簡稱線性表)。

使用線性表存儲的數(shù)據(jù)，如同向數(shù)組中存儲數(shù)據(jù)那樣，要求數(shù)據(jù)類型必須一致，也就是說，線性表存儲的數(shù)據(jù)，要么全不都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一組數(shù)據(jù)無法使用線性表存儲。

順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

圖 3 中我們可以看出，線性表存儲數(shù)據(jù)可細(xì)分為以下 2 種：

如圖 3a) 所示，將數(shù)據(jù)依次存儲在連續(xù)的整塊物理空間中，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)(簡稱順序表);

如圖 3b) 所示，數(shù)據(jù)分散的存儲在物理空間中，通過一根線保存著它們之間的邏輯關(guān)系，這種存儲結(jié)構(gòu)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)(簡稱鏈表);

也就是說，線性表存儲結(jié)構(gòu)可細(xì)分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

線性表常用術(shù)語

常用數(shù)據(jù)結(jié)構(gòu)中，一組數(shù)據(jù)中的每個個體被稱為“數(shù)據(jù)元素”(簡稱“元素”)。例如，圖 1 顯示的這組數(shù)據(jù)，其中 1、2、3、4 和 5 都是這組數(shù)據(jù)鐘的一個元素。

另外，對于具有“一對一”邏輯關(guān)系的數(shù)據(jù)，我們一直在用“某一元素的左側(cè)(前邊)或右側(cè)(后邊)”這樣不專業(yè)的詞，其實線性表中有更準(zhǔn)確的術(shù)語：

某一元素的左側(cè)相鄰元素稱為“直接前驅(qū)”，位于此元素左側(cè)的所有元素都統(tǒng)稱為“前驅(qū)元素”;

某一元素的右側(cè)相鄰元素稱為“直接后繼”，位于此元素右側(cè)的所有元素都統(tǒng)稱為“后繼元素”;

以圖 1 數(shù)據(jù)中的元素 3 來說，它的直接前驅(qū)是 2 ，此元素的前驅(qū)元素有 2 個，分別是 1 和 2;同理，此元素的直接后繼是 4 ，后繼元素也有 2 個，分別是 4 和 5。如圖 4 所示：