一、線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表有兩種物理存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
順序存儲(chǔ)結(jié)構(gòu)
①定義：
用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
②線性表（a1,a2,…,an）的順序存儲(chǔ)如下：
物理上的存儲(chǔ)方式事實(shí)上就是在內(nèi)存中找個(gè)初始地址，然后通過(guò)占位的形式，把一定的內(nèi)存空間給占了，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素依次放在這塊空地中。
③線性表順序存儲(chǔ)結(jié)構(gòu)的結(jié)構(gòu)代碼：
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length; // 線性表當(dāng)前長(zhǎng)度
} SqList;
④順序存儲(chǔ)結(jié)構(gòu)封裝需要三個(gè)屬性：
- 存儲(chǔ)空間的起始位置，數(shù)組data，它的存儲(chǔ)位置就是線性表存儲(chǔ)空間的存儲(chǔ)位置。
- 線性表的最大存儲(chǔ)容量：數(shù)組的長(zhǎng)度MaxSize。
- 線性表的當(dāng)前長(zhǎng)度：length。
注意：數(shù)組的長(zhǎng)度與線性表的當(dāng)前長(zhǎng)度需要區(qū)分一下：數(shù)組的長(zhǎng)度是存放線性表的存儲(chǔ)空間的總長(zhǎng)度，一般初始化后不變。而線性表的當(dāng)前長(zhǎng)度是線性表中元素的個(gè)數(shù)，是會(huì)變化的。
二、地址計(jì)算方法
假設(shè)ElemType占用的是c個(gè)存儲(chǔ)單元（字節(jié)），那么線性表中第i+1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置的關(guān)系是（LOC表示獲得存儲(chǔ)位置的函數(shù)）：LOC(ai+1) = LOC(ai) + c
所以對(duì)于第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置可以由a1推算得出：LOC(ai) = LOC(a1) + (i-1)*c
通過(guò)這個(gè)公式，我們可以隨時(shí)計(jì)算出線性表中任意位置的地址，不管它是第一個(gè)還是最后一個(gè)，都是相同的時(shí)間。那么它的存儲(chǔ)時(shí)間性能就為O(1)，我們通常稱為隨機(jī)存儲(chǔ)結(jié)構(gòu)。
注意：線性表是從1開始計(jì)算的
三、線性表的操作
1.獲得元素
實(shí)現(xiàn)GetElem的具體操作，即將線性表L中的第i個(gè)位置元素值返回。就程序而言非常簡(jiǎn)單了，我們只需要把數(shù)組第i-1下標(biāo)的值返回即可。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
// Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等。
// 初始條件：順序線性表L已存在，1 <= i <= ListLength(L)
// 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。
Status GetElem(SqList L, int i, ElemType *e)
{
if( L.length==0 || i<1 || i>L.length )
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
注：這里返回值類型Status是一個(gè)整型，約定返回1代表OK，返回0代表ERROR。
2.插入操作
線性表的順序存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，時(shí)間復(fù)雜度為O(1)。
實(shí)現(xiàn)ListInsert(*L, i, e)，即在線性表L中的第i個(gè)位置插入新元素e。
插入算法的思路：
- 如果插入位置不合理，拋出異常；
- 如果線性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度，則拋出異?；騽?dòng)態(tài)增加數(shù)組容量；
- 從最后一個(gè)元素開始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置；
- 將要插入元素填入位置i處；
- 線性表長(zhǎng)+1。
代碼：
/* 初始條件：順序線性表L已存在，1<=i<=ListLength(L)。 */
/* 操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L長(zhǎng)度+1。*/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if( L->length == MAXSIZE ) // 順序線性表已經(jīng)滿了
{
return ERROR;
}
if( i<1 || i>L->length+1) // 當(dāng)i不在范圍內(nèi)時(shí)
{
return ERROR;
}
if( i <= L->length ) // 若插入數(shù)據(jù)位置不在表尾
{
/* 將要插入位置后數(shù)據(jù)元素向后移動(dòng)一位 */
for( k=L->length-1; k >= i-1; k-- )
{
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e; // 將新元素插入
L->length++;
return OK;
}
3.刪除操作
算法的思路：
- 如果刪除位置不合理，拋出異常；
- 取出刪除元素；
- 從刪除元素位置開始遍歷到最后一個(gè)元素位置，分別將它們都向前移動(dòng)一個(gè)位置；
- 表長(zhǎng)-1。
實(shí)現(xiàn)代碼：
/* 初始條件：順序線性表L已存在，1<=i<=ListLength(L) */
/* 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度-1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
if( L->length == 0 )
{
return ERROR;
}
if( i<1 || i>L->length )
{
return ERROR;
}
*e = L->data[i-1];
if( i < L->length )
{
for( k=i; k < L->length; k++ )
{
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
插入和刪除的時(shí)間復(fù)雜度：
- 最好的情況：插入和刪除操作剛好要求在最后一個(gè)位置操作，因?yàn)椴恍枰苿?dòng)任何元素，所以此時(shí)的時(shí)間復(fù)雜度為O(1)。
- 最壞的情況：如果要插入和刪除的位置是第一個(gè)元素，那就意味著要移動(dòng)所有的元素向后或者向前，所以這個(gè)時(shí)間復(fù)雜度為O(n)。
- 平均情況，取中間值O((n-1)/2)。平均情況復(fù)雜度簡(jiǎn)化后還是O(n)。
五、線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
線性表的順序存儲(chǔ)結(jié)構(gòu)，在存、讀數(shù)據(jù)時(shí)，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1)。而在插入或刪除時(shí)，時(shí)間復(fù)雜度都是O(n)。
這就說(shuō)明，它比較適合元素個(gè)數(shù)比較穩(wěn)定，不經(jīng)常插入和刪除元素，而更多的操作是存取數(shù)據(jù)的應(yīng)用。
優(yōu)點(diǎn)：
- 無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間。
- 可以快速地存取表中任意位置的元素。
缺點(diǎn)：
- 插入和刪除操作需要移動(dòng)大量元素。
- 當(dāng)線性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量。
- 容易造成存儲(chǔ)空間的“碎片”
