2.2　線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)

2.2.1　線性表的順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)指使用連續(xù)的存儲(chǔ)空間，按照數(shù)據(jù)元素在線性表中的序號(hào)依次存儲(chǔ)數(shù)據(jù)元素。采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表。順序表借助元素在存儲(chǔ)空間中的位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系：邏輯上相鄰的數(shù)據(jù)元素，其物理存儲(chǔ)地址也相鄰。

設(shè)線性表中第一個(gè)元素a0在內(nèi)存中的存儲(chǔ)地址是loc(a0)，每個(gè)元素占用k個(gè)存儲(chǔ)單元，則線性表中任意元素ai在內(nèi)存的存儲(chǔ)地址為：

loc(ai)=loc(a0)+i×k　?。?-1）

由公式（2-1）可知，只要給定loc(a0)和k的值，即可計(jì)算出任意元素在內(nèi)存中的存儲(chǔ)地址，從而進(jìn)行數(shù)據(jù)元素的存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)。

C語言中，一維數(shù)組占用了內(nèi)存中一組連續(xù)的存儲(chǔ)單元，具備隨機(jī)存取的特性，由此可使用一維數(shù)組描述線性表的順序存儲(chǔ)結(jié)構(gòu)。線性表中的數(shù)據(jù)元素（a0,…,ai,…,an?1）在一維數(shù)組的存儲(chǔ)形式如圖2.1所示，圖中maxLength是順序表的最大允許長度。在處理實(shí)際問題時(shí)，所需線性表的長度會(huì)隨具體問題的不同而不同，因此在實(shí)現(xiàn)順序表時(shí)，使用動(dòng)態(tài)分配的一維數(shù)組。

線性表的順序表示定義如下。

圖2.1　順序表示例

在以上定義中，n是順序表的長度，即順序表中數(shù)據(jù)元素的個(gè)數(shù)。maxLength是順序表的最大允許長度。ElemType是自定義類型，它是為了統(tǒng)一描述數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的數(shù)據(jù)類型而設(shè)定的。在實(shí)際使用時(shí)，用戶可以根據(jù)實(shí)際需要將ElemType具體定義為所需的數(shù)據(jù)類型，可以是int、float等基本數(shù)據(jù)類型，也可以是struct結(jié)構(gòu)體類型等。例如typedef int ElemType，將ElemType定義為int型。指針element指示順序表的存儲(chǔ)空間的首地址。SeqList是類型名，可通過它定義相應(yīng)變量，例如

SeqList L;

2.2.2　順序表基本運(yùn)算的實(shí)現(xiàn)

以下討論順序表中幾個(gè)主要運(yùn)算的具體實(shí)現(xiàn)。

1．初始化

順序表的初始化運(yùn)算是使用動(dòng)態(tài)分配數(shù)組空間方式構(gòu)造一個(gè)空的線性表。動(dòng)態(tài)分配數(shù)組空間可以達(dá)到有效利用存儲(chǔ)空間的目的。

【算法步驟】

（1）為順序表L動(dòng)態(tài)分配一維數(shù)組。

（2）若動(dòng)態(tài)分配一維數(shù)組失敗，則返回出錯(cuò)信息；否則返回OK。

程序2.1　順序表的初始化

此處返回值類型Status為整型，返回OK代表1，返回ERROR代表0。之后在代碼中出現(xiàn)將不再贅述。malloc是動(dòng)態(tài)分配內(nèi)存空間的函數(shù)。

2．查找

順序表的查找運(yùn)算是查找表中元素ai的值。順序表具有隨機(jī)存取的特點(diǎn)，因此元素ai的值可以直接通過數(shù)組下標(biāo)定位取得。

【算法步驟】

（1）判斷所要查找的元素下標(biāo)i是否越界，若越界，返回ERROR。

（2）若下標(biāo)i未越界，則取出element[i]的值通過參數(shù)x返回。

程序2.2　順序表的查找

3．插入

順序表的插入運(yùn)算是在順序表L的元素ai之后插入新元素x。若i=?1，則表示將新元素x插入順序表的最前面。首先需要對(duì)i是否越界、順序表存儲(chǔ)空間是否已滿進(jìn)行判斷。新元素x插入順序表之前，將從n?1到i+1之間的所有元素依次向后移動(dòng)一個(gè)位置。下面以實(shí)例進(jìn)行說明，圖2.2所示為新元素55插入前后線性表的變化。為了將新元素55插入下標(biāo)為2的元素之后，需從下標(biāo)為5的元素開始依次向后移動(dòng)一個(gè)位置，直到下標(biāo)為3的元素。

圖2.2　順序表中插入新元素55

【算法步驟】

（1）判斷元素下標(biāo)i是否越界，若已越界，返回ERROR。

（2）判斷順序表存儲(chǔ)空間是否已滿，若已滿，返回ERROR。

（3）將元素（ai+1,…,an?1）依次向后移動(dòng)一個(gè)位置。

（4）將新元素x放入下標(biāo)i+1的位置。

（5）表長加1。

程序2.3　順序表的元素插入

【算法分析】

順序表的元素插入運(yùn)算過程中，時(shí)間主要消耗在移動(dòng)元素上。對(duì)于長度為n的順序表，在位置i（i=?1,0,1,…,n?1）后插入一個(gè)新元素，需要移動(dòng)n?i?1個(gè)元素。設(shè)Pi是在位置i之后插入一個(gè)新元素的概率，并設(shè)在任意位置處插入元素的概率是相等的，則有Pi=1/(n+1)。設(shè)Ei是在長度為n的順序表中插入一個(gè)新元素時(shí)所需移動(dòng)元素的平均次數(shù)，則

由上述分析可知，順序表插入算法的平均時(shí)間復(fù)雜度為O(n)。

4．刪除

順序表的刪除運(yùn)算的功能是將元素ai刪除。須先對(duì)i是否越界、順序表是否為空進(jìn)行判斷。在順序表中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上也需相鄰，因此不能直接簡單刪除元素ai，而需將從i+1到n?1之間的所有元素依次向前移動(dòng)一個(gè)位置。下面以實(shí)例進(jìn)行說明，圖2.3所示為刪除元素50前后線性表的變化。為了刪除元素50，需從下標(biāo)為3的元素開始依次向前移動(dòng)一個(gè)位置，直到下標(biāo)為5的元素。

圖2.3　刪除順序表中的元素50

【算法步驟】

（1）判斷元素下標(biāo)i是否越界，若不越界，返回ERROR。

（2）判斷順序表是否為空，若為空，返回ERROR。

（3）將元素（ai+1,…,an?1）依次向前移動(dòng)一個(gè)位置。

（4）表長減1。

程序2.4　順序表的元素刪除

順序表的元素刪除運(yùn)算過程中，時(shí)間主要消耗在移動(dòng)元素上。對(duì)于長度為n的順序表，刪除位置i(i=0,1,…,n?1)上的一個(gè)元素，需要移動(dòng)n?i?1個(gè)元素。設(shè)Pi是在位置i刪除一個(gè)元素的概率，并設(shè)在任意位置處刪除元素的概率是相等的，則有Pi=1/n。設(shè)Ed是在長度為n的順序表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)，則

由上述分析可知，順序表刪除算法的平均時(shí)間復(fù)雜度為O(n)。

5．輸出

順序表的輸出運(yùn)算是將順序表的元素依次輸出。

【算法步驟】

（1）判斷順序表是否為空，若為空，返回ERROR。

（2）將元素（a0,…,an?1）依次輸出。

程序2.5　順序表的輸出

6．撤銷

順序表的撤銷運(yùn)算的主要功能是釋放初始化運(yùn)算中動(dòng)態(tài)分配的數(shù)據(jù)元素存儲(chǔ)空間，以防止內(nèi)存泄漏。

程序2.6　順序表的撤銷

7．主函數(shù)main

程序2.7中的主函數(shù)main是為了測試順序表的主要運(yùn)算而設(shè)計(jì)的。

程序2.7　主函數(shù)main