2.2　線性表

從這一節(jié)開始介紹各種常用的數(shù)據(jù)結(jié)構(gòu)。首先要看的便是線性表。線性表是一種典型的線性結(jié)構(gòu)，是最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。

2.2.1　什么是線性表

談到線性表（Linear List），首先應(yīng)該分析其邏輯定義。從邏輯上來看，線性表就是由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，an組成的有限序列。這里需要說明如下幾點(diǎn)：

?數(shù)據(jù)元素的個(gè)數(shù)為n，也稱為表的長度，當(dāng)n=0的時(shí)候稱為空表；

?如果一個(gè)線性表非空，即n>0，則可以簡單地記作（a1，a2，…，an）；

?數(shù)據(jù)元素ai（1≤i≤n）表示了各個(gè)元素，在不同的場合，其含義也不同。

在現(xiàn)實(shí)生活中，可以找到很多線性表的例子。比如英文字母表就是最簡單的線性表，英文字母表（A，B，C，…，Z）中，每個(gè)英文字符就是一個(gè)數(shù)據(jù)元素，也稱為數(shù)據(jù)結(jié)點(diǎn)。另外，表2-1某班級(jí)學(xué)生成績表也是一個(gè)線性表。在這里，數(shù)據(jù)元素就是某個(gè)學(xué)生的記錄，其中包括學(xué)號(hào)、姓名、各個(gè)科目的成績等。

對(duì)于一個(gè)非空的線性表，其邏輯結(jié)構(gòu)特征如下：

?有且僅有一個(gè)開始結(jié)點(diǎn)a1，沒有直接前趨結(jié)點(diǎn)，有且僅有一個(gè)直接后繼結(jié)點(diǎn)a2；

?有且僅有一個(gè)終結(jié)結(jié)點(diǎn)an，沒有直接后繼結(jié)點(diǎn)，有且僅有一個(gè)直接前趨結(jié)點(diǎn)an-1；

?其余的內(nèi)部結(jié)點(diǎn)ai（2≤i≤n-1）都有且僅有一個(gè)直接前趨結(jié)點(diǎn)ai-1和一個(gè)直接后繼結(jié)點(diǎn)ai+1；

?對(duì)于同一線性表，各數(shù)據(jù)元素ai必須具有相同的數(shù)據(jù)類型，即同一線性表中各數(shù)據(jù)元素具有相同的類型，每個(gè)數(shù)據(jù)元素的長度相同。

2.2.2　線性表的基本運(yùn)算

前面介紹的是線性表的邏輯結(jié)構(gòu)，再來分析線性表的基本運(yùn)算。線性表的基本運(yùn)算包括如下內(nèi)容。

1）初始化

初始化表（InitList）即構(gòu)造一個(gè)空的線性表L。

2）計(jì)算表長

計(jì)算表長（ListLength）即計(jì)算線性表L中結(jié)點(diǎn)的個(gè)數(shù)。

3）獲取結(jié)點(diǎn)

獲取結(jié)點(diǎn)（GetNode）即取出線性表L中第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)，這里1≤i≤ListLength（L）。

4）查找結(jié)點(diǎn)

查找結(jié)點(diǎn)（LocateNode）即在線性表L中查找值為x的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在線性表L中的位置。如果在線性表中沒有找到值為x的結(jié)點(diǎn)，則返回一個(gè)錯(cuò)誤標(biāo)志。這里需要注意的是，線性表中有可能含有多個(gè)與x值相同的結(jié)點(diǎn)，那么此時(shí)就返回第一次查找到的結(jié)點(diǎn)。

5）插入結(jié)點(diǎn)

插入結(jié)點(diǎn)（InsertList）即在線性表L的第i個(gè)位置插入一個(gè)新的結(jié)點(diǎn)，使得其后的結(jié)點(diǎn)編號(hào)依次加1。這時(shí)，插入一個(gè)新結(jié)點(diǎn)之后，線性表L的長度將變?yōu)閚+1。

6）刪除結(jié)點(diǎn)

刪除結(jié)點(diǎn)（DeleteList）即刪除線性表L中的第i個(gè)結(jié)點(diǎn)，使得其后的所有結(jié)點(diǎn)編號(hào)依次減1。刪除一個(gè)結(jié)點(diǎn)之后，線性表L的長度將變?yōu)閚-1。

上述內(nèi)容是一個(gè)線性表最基本的運(yùn)算，當(dāng)然讀者根據(jù)需要還可以定義其他一些運(yùn)算。

至此，線性表的邏輯結(jié)構(gòu)和數(shù)據(jù)運(yùn)算討論完畢，線性表的存儲(chǔ)結(jié)構(gòu)還沒有介紹。其實(shí)，在計(jì)算機(jī)中線性表可以采用兩種方法來保存，一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表。順序表和鏈表就是下面要介紹的內(nèi)容。