考點3 線性表及其順序存儲結構

1.線性表的基本概念

數據結構中，線性結構又稱為線性表，線性表是最簡單也是最常用的一種數據結構。

線性表是由n（n≥0）個數據元素a1,a2,…,an組成的一個有限序列，表中的第一個元素外，有且只有一個前件，除了最后一個元素外，有且只有一個后件。

線性表或者是個空表，或者可以表示為：

（a1,a2,…,ai,…,an）

其中，ai（i=1,2,…,n）是線性表的數據元素，也稱為線性表的一個節點。

每個數據元素在不同情況下其具體含義各不相同，它可以是一個數或一個字符，也可以是一個具體的事物，甚至是更復雜的信息。但是需要注意的是同一線性表中的數據元素必定具有相同的特性，即屬于同一數據對象。

真考鏈接

考核概率為45%。考生要熟記該知識點屬于了解性內容，主要是線性表的基本概念。

小提示

非空線性表具有以下一些結構特征：

● 只有一個根節點，即頭節點，它無前件；

● 有且只有一個終節點，即尾節點，它無后件；

● 除頭節點與尾節點外，其他所有節點有且只有一個前件，也有且只有一個后件。節點個數n稱為線性表的長度，當n=0時，稱為空表。

2.線性表的順序存儲結構

將線性表中的元素逐個存儲在一片相鄰的存儲區域中。這種順序表示的線性表也稱為順序表。

線性表的順序存儲結構具有以下兩個基本特點。

●元素所占的存儲空間必須是連續的。

●元素在存儲空間的位置是按邏輯順序存放的。

從上述特點也可以看出，線性表是用元素在計算機內物理位置上的相鄰關系來表示元素之間邏輯上的相鄰關系。只要確定了首地址，線性表內任意元素的地址都可以方便地計算出來。

3.線性表的插入運算

線性表的插入運算中，在第i個元素之前插入一個新元素，完成插入操作主要有以下3個步驟。

（1）把原來第n個節點至第i個節點依次往后移一個元素位置。

（2）把新節點放在第i個位置上。

（3）修正線性表的節點個數。

小提示

一般會為線性表開辟一個大于線性表長度的存儲空間，經過多次插入運算，可能出現存儲空間已滿的情況，如果此時仍繼續插入運算，將會產生錯誤，此類錯誤稱為“上溢”。

如果需要在線性表末尾進行插入運算，則只需在表的末尾增加一個元素即可，不需要移動線性表中的元素。

如果在第一個位置插入新的元素，則需要移動表中所有的元素。

4.線性表的刪除運算

在線性表的刪除運算中，刪除第i個位置的元素，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移一個位置，完成刪除運算主要有以下幾個步驟。

（1）把第i個元素之后（不包括第i個元素）的n-i個元素依次前移一個位置。

（2）修正線性表的節點個數。

綜上所述，如果刪除運算在線性表的末尾進行，即刪除第n個元素，則不需要移動線性表中的元素。如果要刪除第1個元素，則需要移動表中所有的數據。

小提示

由線性表的上述性質可以看出，線性表的順序存儲結構適用于小線性表，或者建立之后其中元素不常變動的線性表，而不適用于需要經常進行插入和刪除運算的線性表盒長度較大的線性表。

真題精選

【例1】下列有關順序存儲結構的敘述，不正確的是______。

A）存儲密度大

B）邏輯上相鄰的節點物理上不必鄰接

C）可以通過計算機直接確定第i個節點的存儲地址

D）插入、刪除操作不方便

【答案】B

【解析】順序存儲結構要求邏輯上相鄰的元素物理地址上也相鄰，所以只有選項B敘述錯誤。

【例2】在一個長度為 n 的順序表中，向第 i 個元素（1≤i≤n +1）的位置插入一個新元素，需要從后向前依次移動______個元素。

A）n-i

B）i

C）n-i-1

D）n-i+1

【答案】D

【解析】根據順序表的插入運算的定義知道，在第i個位置上插入x，從ai到an都要向后移動一個位置，所以共需要移動n-i+1個元素。