1.3　線性表及其順序存儲結構

考點1　線性表的基本概念

（1）線性表是一種最常見最簡單的數(shù)據(jù)結構，由一組數(shù)據(jù)元素構成。數(shù)據(jù)元素在線性表中的位置值只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是線性的。

（2）非空線性表的結構特征：

①有且只有一個根結點a₁，它無前件；

②有且只有一個終端結點a_n，它無后件；

③除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。

線性表中結點的個數(shù)n稱為線性表的長度。當n＝0時，稱為空表。

【真題演練】

下列敘述中正確的是（　　）。[2014年9月真題]

A．結點中具有兩個指針域的鏈表一定是二叉鏈表

B．結點中具有兩個指針域的鏈表可以是線性結構，也可以是非線性結構

C．二叉樹只能采用鏈式存儲結構

D．循環(huán)鏈表是非線性結構

【答案】B

【解析】A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表；B項正確，如雙向鏈表是線性結構，二叉樹為非線性結構，兩者結點中均有兩個指針域；C項錯誤，二叉樹通常采用鏈式存儲結構，也可采用其他結構；D項錯誤，循環(huán)鏈表是線性結構，邏輯概念線性非線性與實際存儲結構無關。答案選擇B選項。

考點2　線性表的順序存儲結構

（1）概述

順序存儲是一種最簡單的在計算機中存放線性表的方法，也稱順序分配。

（2）特點

①線性表中所有元素所占的存儲空間是連續(xù)的；

②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。

（3）運算

在線性表的順序存儲結構下，可對線性表進行以下運算：

①插入：在線性表的指定位置處加入一個新的元素；

②刪除：在線性表中刪除指定的元素；

③查找：在線性表中查找某個（或某些）特定的元素；

④排序：對線性表中的元素進行整序；

⑤分解：按要求將一個線性表分解成多個線性表；

⑥合并：按要求將多個線性表合并成一個線性表；

⑦復制：復制一個線性表；

⑧逆轉：逆轉一個線性表等。

【真題演練】

在線性表的順序存儲結構中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)（　　）。[2014年3月真題]

A．相同，元素的存儲順序與邏輯順序一致

B．相同，但其元素的存儲順序可以與邏輯順序不一致

C．不同，但元素的存儲順序與邏輯順序一致

D．不同，且其元素的存儲順序可以與邏輯順序不一致

【答案】A

【解析】在順序表中，每個元素占有相同的存儲單元。順序表具有特征：①線性表中所有元素所占的存儲空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。答案選擇A選項。

考點3　順序表的插入運算

假設線性表的存儲空間為V（1：m），線性表的長度為n（n≤m），插入的位置為i（表示在第i個位置插入元素），則順序表插入新元素過程如下：

（1）首先處理以下三種異常情況：

①當存儲空間已滿（即n＝m）時為“上溢”錯誤，不能進行插入，算法結束；

②當i＞n時，認為在最后一個元素之后（即第n＋1個元素之前）插入；

③當i＜1時，認為在第1個元素之前插入。

（2）從最后一個元素開始，直到第i個元素，其中每一個元素均往后移動一個位置。

（3）最后將新元素插入到第i個位置，并且將線性表的長度增加1。

考點4　順序表的刪除運算

假設線性表的存儲空間為V（1：m），線性表的長度為n（n≤m），刪除的位置為i（表示刪除第i個元素），則順序表刪除元素的過程如下：

（1）首先處理以下兩種異常情況：

①當線性表為空（即n＝0）時為“上溢”錯誤，不能進行插入，算法結束；

②當i＜1或i＞n時，認為在最后一個元素之后（即第n＋1個元素之前）插入。

（2）然后從第i＋1個元素開始，直到最后一個元素，其中每一個元素均依次往前移動一個位置。

（3）最后將線性表的長度減小1。