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

真考鏈接

在選擇題中，考核概率為45%。該知識點屬于了解性內容，考生需了解線性表的基本概念。

1.線性表的基本概念

在數據結構中，通常將線性結構習慣上稱為線性表，線性表是最簡單也是最常用的一種數據結構。

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

線性表要么是一個空表，要么可以表示為：

（a1，a2，…，ai，…，an）

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

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

小提示

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

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

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

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

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

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

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

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

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

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

3.線性表的插入運算

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

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

（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個元素。