1.1.2 線性表

本節(jié)主要考查線性表的基本概念，以及線性表的順序存儲方式。

1.線性表概述

線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)。

在實際應(yīng)用中，線性表都是以棧、隊列、字符串、數(shù)組等特殊線性表的形式來使用的。由于這些特殊線性表都具有各自的特性，因此，掌握這些特殊線性表的特性，對于數(shù)據(jù)運(yùn)算的可靠性和提高操作效率都是至關(guān)重要的。

線性表是一個線性結(jié)構(gòu)，它是一個含有n（n≥0）個節(jié)點的有限序列，對于其中的節(jié)點，有且僅有一個開始節(jié)點沒有前驅(qū)（前件）節(jié)點但有一個后繼（后件）節(jié)點，有且僅有一個終端節(jié)點沒有后繼節(jié)點但有一個前驅(qū)節(jié)點，其他的節(jié)點都有且僅有一個前驅(qū)節(jié)點和一個后繼節(jié)點。一般來說，一個線性表可以表示成一個線性序列：k1,k2,…,kn，其中k1是開始節(jié)點，kn是終端節(jié)點。

線性結(jié)構(gòu)的基本特征如下：

1）集合中必存在唯一的一個“第一元素”。

2）集合中必存在唯一的一個“最后元素”。

3）除最后一個元素之外，每個元素均有唯一的后繼。

4）除第一個元素之外，每個元素均有唯一的前驅(qū)。

由n（n≥0）個數(shù)據(jù)元素（節(jié)點）a1,a2,…,an組成的有限序列，數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表。常常將非空的線性表（n>0）記作：（a1,a2,…,an）。

2.線性表的順序存儲

線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲又叫作順序表。

（1）線性表的順序存儲基本概念

線性表的順序存儲結(jié)構(gòu)具備以下兩個基本特征：

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

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

假設(shè)線性表的每個元素需要占用k個存儲單元，并且所占的存儲位置ADR（ai+1）和第i個數(shù)據(jù)元素的存儲位置ADR（ai）之間滿足下列關(guān)系：

ADR（ai+1）=ADR（ai）+k

線性表第i個元素ai的存儲位置為：

ADR（ai）=ADR（a1）+（i-1）×k

公式中ADR（a1）是線性表的第一個數(shù)據(jù)元素的存儲位置，通常稱為線性表的起始位置或基址。

在C語言中，通常定義一個一維數(shù)組來表示線性表的順序存儲空間，如圖1-1所示。

在用一維數(shù)組存放線性表時，該一維數(shù)組的長度通常要定義得比線性表的實際長度大一些，以便對線性表進(jìn)行各種運(yùn)算，特別是插入運(yùn)算。

在線性表的順序存儲結(jié)構(gòu)下，可以對線性表做以下運(yùn)算：

1）在線性表的指定位置處加入一個新的元素（即線性表的插入）。

2）在線性表中刪除指定的元素（即線性表的刪除）。

3）在線性表中查找某個（或某些）特定的元素（即線性表的查找）。

4）對線性表中的元素進(jìn)行排序（即線性表的排序）。

5）將一個線性表分解成多個線性表（即線性表的分解）。

6）將多個線性表合并成一個線性表（即線性表的合并）。

7）復(fù)制一個線性表（即線性表的復(fù)制）。

8）逆轉(zhuǎn)一個線性表（即線性表的逆轉(zhuǎn)）。

（2）順序表的基本操作

順序表的基本操作包括插入運(yùn)算和刪除運(yùn)算。

1）順序表的插入運(yùn)算：線性表的插入運(yùn)算是指在表的第i（1≤i≤n+l）個位置上，插入一個新節(jié)點x，使長度為n的線性表（a1,…,ai-1,ai,…,an）變成長度為n+1的線性表（a1,…,ai-1,x,ai,…,an+1）。

現(xiàn)在分析算法的復(fù)雜度。設(shè)它的值為n。該算法的時間主要花費在循環(huán)節(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動節(jié)點的次數(shù)）是n-i+1。由此可看出，所需移動節(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。

當(dāng)i=n+1時，由于循環(huán)變量的終值大于初值，節(jié)點后移語句將不執(zhí)行。這是最好的情況，其時間復(fù)雜度為O（1）。

當(dāng)i=1時，節(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有節(jié)點。這是最壞的情況，其時間復(fù)雜度為O（n）。

綜合以上的情況，得出算法的平均時間復(fù)雜度為O（n）。

2）順序表的刪除運(yùn)算：線性表的刪除運(yùn)算是指將表的第i（1≤i≤n）個節(jié)點刪除，使長度為n的線性表（a1,…,ai-1,ai,ai+1,…,an）變成長度為n-l的線性表（a1,…,ai-1,ai+1,…,an-1）。

該算法的時間分析與插入算法相似，節(jié)點的移動次數(shù)也是由表長n和位置i決定的。

若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動節(jié)點。

若i=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始節(jié)點外的所有節(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O（1）和O（n）。

綜合以上的情況得出，在順序表上做刪除運(yùn)算，平均要移動表中約一半的節(jié)點，平均時間復(fù)雜度也是O（n）。