2.3　順序表結(jié)構(gòu)

順序表（Sequential List）就是按照順序存儲方式存儲的線性表，該線性表的結(jié)點按照邏輯次序依次存放在計算機的一組連續(xù)的存儲單元中，如圖2-1所示。

由于順序表是依次存放的，只要知道了該順序表的首地址及每個數(shù)據(jù)元素所占用的存儲長度，那么就很容易計算出任何一個數(shù)據(jù)元素（即數(shù)據(jù)結(jié)點）的位置。

一般的，假設(shè)順序表中所有結(jié)點的類型相同，則每個結(jié)點所占用的存儲空間大小亦相同，每個結(jié)點占用c個存儲單元。其中第一個單元的存儲地址則為該結(jié)點的存儲地址，并設(shè)順序表中開始結(jié)點a1的存儲地址（簡稱為基地址）為LOC（a1），那么結(jié)點ai的存儲地址LOC（ai）可通過下式計算：

LOC（ai）=LOC（a1）+（i-1）*c1≤i≤n

這就是能夠操作順序表進行運算的基本規(guī)則。接下來分析如何在C語言中建立順序表，并完成順序表的基本運算。

2.3.1　準備數(shù)據(jù)

學(xué)習(xí)了前面的理論知識后，下面就開始順序表結(jié)構(gòu)的程序設(shè)計。首先需要準備數(shù)據(jù)，也就是準備在順序表操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。示例代碼如下：

在上述代碼中，定義了順序表的最大長度MAXLEN，順序表數(shù)據(jù)元素的類DATA及順序表的類SLType。在類SLType中，ListLen為順序表已存結(jié)點的數(shù)量，即當前順序表的長度，ListData是一個對象數(shù)組，用來存放各個數(shù)據(jù)結(jié)點。

其實，可以認為該順序表是一個班級學(xué)生的記錄。其中，key為學(xué)號，name為學(xué)生的名稱，age為年齡。

由于Java語言中數(shù)組都是從下標0開始的。在這里，為了講述和理解的方便，從下標1開始記錄數(shù)據(jù)結(jié)點，下標0的位置不使用。

2.3.2　初始化順序表

在使用順序表之前，首先要創(chuàng)建一個空的順序表，即初始化順序表。這里，在程序中只需設(shè)置順序表的結(jié)點數(shù)量ListLen為0即可。這樣，后面需要添加的數(shù)據(jù)元素將從順序表的第一個位置存儲。代碼示例如下：

需要注意的是，這里并沒有清空一個順序表。讀者也可以采用相應(yīng)的程序代碼來清空，只需簡單地將結(jié)點數(shù)量ListLen設(shè)置為0即可，這樣如果順序表中原來已有數(shù)據(jù)，也會被覆蓋，并不影響操作，反而提高了處理的速度。

2.3.3　計算順序表長度

計算順序表長度即計算線性表L中結(jié)點的個數(shù)。由于在類SLType中使用ListLen來表示順序表的結(jié)點數(shù)量，因此程序只要返回該值就可以了。代碼示例如下：

2.3.4　插入結(jié)點

插入結(jié)點就是在線性表L的第i個位置插入一個新的結(jié)點，使得其后的結(jié)點編號依次加1。這時，插入一個新結(jié)點之后，線性表L的長度將變?yōu)閚+1。插入結(jié)點操作的難點在于隨后的每個結(jié)點數(shù)據(jù)都要進行移動，計算量比較大。代碼示例如下：

在上述代碼中，在程序中首先判斷順序表結(jié)點數(shù)量是否已超過最大數(shù)量，以及插入結(jié)點序號是否正確。所有條件都滿足后，然而將順序表中的數(shù)據(jù)向后移動，同時插入結(jié)點，并更新結(jié)點數(shù)量ListLen。

2.3.5　追加結(jié)點

追加結(jié)點并不是一個基本的數(shù)據(jù)結(jié)構(gòu)運算，其可以看作插入結(jié)點的一種特殊形式，相當于在順序表的末尾新增一個數(shù)據(jù)結(jié)點。由于追加結(jié)點的特殊性，其代碼實現(xiàn)相比插入結(jié)點要簡單，因為不必進行大量數(shù)據(jù)的移動，因此這里單獨給出其實現(xiàn)的程序。代碼示例如下：

在上述代碼中，僅簡單判斷這個順序表是否已經(jīng)滿了，然后便追加該結(jié)點，并更新結(jié)點數(shù)量ListLen。

2.3.6　刪除結(jié)點

刪除結(jié)點即刪除線性表L中的第i個結(jié)點，使得其后的所有結(jié)點編號依次減1。刪除一個結(jié)點之后，線性表L的長度將變?yōu)閚-1。刪除結(jié)點和插入結(jié)點類似，都需要進行大量數(shù)據(jù)的移動。代碼示例如下：

在上述代碼中，首先判斷待刪除的結(jié)點序號是否正確，然后開始移動數(shù)據(jù)，并更新結(jié)點數(shù)量ListLen。

2.3.7　查找結(jié)點

查找結(jié)點即在線性表L中查找值為x的結(jié)點，并返回該結(jié)點在線性表L中的位置。如果在線性表中沒有找到值為x的結(jié)點，則返回一個錯誤標志。根據(jù)值x類型的不同，查找結(jié)點可以分為按照序號查找結(jié)點和按照關(guān)鍵字查找結(jié)點兩種方法。

1）按照序號查找結(jié)點

對于一個順序表，序號就是數(shù)據(jù)元素在數(shù)組中的位置，也就是數(shù)組的下標標號。按照序號查找結(jié)點是順序表查找結(jié)點最常用的方法，這是因為順序表的存儲本身就是一個數(shù)組。代碼示例如下：

2）按照關(guān)鍵字查找結(jié)點

另一個比較常用的方法是按照關(guān)鍵字查找結(jié)點。這里，關(guān)鍵字可以是數(shù)據(jù)元素結(jié)構(gòu)中的任意一項。以key關(guān)鍵字為例介紹，由前面知道key可以看作學(xué)生的學(xué)號。代碼示例如下：

2.3.8　顯示所有結(jié)點

顯示所有結(jié)點數(shù)據(jù)并不是一個數(shù)據(jù)結(jié)構(gòu)基本的運算，因為其可以簡單地逐個引用結(jié)點來實現(xiàn)。不過為了方便，還是將其單獨列為一個方法。代碼示例如下：

2.3.9　順序表操作實例

學(xué)習(xí)了前面的順序表的基本運算之后，便可以輕松地完成對順序表的各種操作。下面給出一個完整的例子，來演示順序表的創(chuàng)建、插入結(jié)點、查找結(jié)點等操作。代碼示例如下：

【程序2-1】

在上述代碼中，main（）主方法首先初始化順序表，然后循環(huán)添加數(shù)據(jù)結(jié)點，當輸入全部為0時則退出結(jié)點添加的進程。接下來顯示所有的結(jié)點數(shù)據(jù)，并分別按照序號和關(guān)鍵字來進行結(jié)點的查找。該程序執(zhí)行結(jié)果，如圖2-2所示。