順序表定義

1，前言

線性表的順序存儲又稱為順序表。它是用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。其最大的特點就是：元素的邏輯順序與其物理順序相同?。

線性表的順序存儲結(jié)構(gòu)中任一元素都可以隨機存取，并且注意?：線性表中元素的位序是從1 開始的，而數(shù)組中元素的下標(biāo)是從0 開始的。假定線性表的元素類型為 EleType ，則線性表的順序存儲類型可以描述為：

2，動態(tài)實現(xiàn)

1，結(jié)構(gòu)定義：

2，初始化順序表：

3，增加動態(tài)數(shù)組的長度：

順序表上的基本操作

1，插入操作（Listsert(&L,i,e)

在表L 中的第i 個位置上插入指定元素e 。以下采用的是“靜態(tài)分配的方式實現(xiàn)。

以下給出實現(xiàn)的主要代碼部分，便于我們閱讀理解：

插入操作的時間復(fù)雜度分析：

通過觀察以上代碼，我們分析時間復(fù)雜度時只需要關(guān)注最深層循環(huán)語句的執(zhí)行次數(shù)與問題規(guī)模n 的關(guān)系。即語句“L.data[j]=L.data[j-1];”?即可：

（1）最好情況：新元素插入到表位，不需要移動元素，i=n+1，循環(huán)0次；最好的時間復(fù)雜度為O(1)

（2）最壞情況：新元素插入到表頭，需要將原有的n 個元素全都向后移動，i =1，循環(huán)n 次；最壞的時間復(fù)雜度為O(n);

（3）平均情況：假設(shè)新元素插入到任何一個位置的概率相同，概率為P=1/(n+1)。i=1，循環(huán)n 次；i =2 時，循環(huán)n-1次；i =3 ，循環(huán)n-2 次 ..... i =n+1 時，循環(huán)0 次。平均循環(huán)次數(shù) =np+(n-1)p+(n-2)p+.....+1.p= n/2。即得平均時間復(fù)雜度= O(n)

提示：如果以上的分析i 的值和循環(huán)次數(shù)n 的關(guān)系不是太清楚，要回想下開頭提到的線性表中元素的位序是從1 開始的，而數(shù)組中元素的下標(biāo)是從0 開始的。

2，刪除操作（ListDelete(SqList &L,int i,int &e)）

刪除順序表L 中的第i （1<=i<=L.length)個位置的元素，用引用變量e 返回。若輸入的i 不合法，則返回false ；否則，將被刪元素賦給引用變量e ，并將第i+1 個元素及其后的所有元素一次往前移動一個位置，返回true 。

下面給出部分代碼，輔助我們理解閱讀：

刪除操作的是時間復(fù)雜度分析：

通過觀察以上代碼，我們分析時間復(fù)雜度時只需要關(guān)注最深層循環(huán)語句的執(zhí)行次數(shù)與問題規(guī)模n 的關(guān)系。即語句“L.data[j-1]=L.data[j];”?即可：

（1）最好情況：刪除元素，不需要移動其他元素，i=n，循環(huán)0次；最好的時間復(fù)雜度為O(1)

（2）最壞情況：刪除表頭元素，需要將后續(xù)的n-1個元素全都向前移動。i=1，循環(huán)n-1次；最壞時間復(fù)雜度= O(n)

（3）平均情況：假設(shè)刪除任何一個元素的概率相同，及p=1/n，i=1，循環(huán)n-1次；i=2，循環(huán)n-2 次..... i=n 時，循環(huán)0次，故平均循環(huán)次數(shù)=(n-1)p+(n-2)p+.....+1.p=(n-1)/2.則時間復(fù)雜度為O(n)

3，按位查找（GetElem(L,i)）

獲取表L 中第i 個位置的元素的值。下面給出一段簡單的代碼示例：

由于順序表的各個元素在內(nèi)存中連續(xù)存放，因此可以根據(jù)起始地址和數(shù)據(jù)元素大小立即找到第i 個元素，這也就是隨機存取?特性的體現(xiàn)。因此其時間復(fù)雜度可得為 O(1)。

4，按值查找（LocateElem( L, e) ）

在表L 中查找具有給定關(guān)鍵字的元素。如下給出在順序表L 中查找第一個元素值等于e 的元素，并返回其位序：

對于時間復(fù)雜度的分析：

通過觀察以上代碼，我們分析時間復(fù)雜度時只需要關(guān)注最深層循環(huán)語句的執(zhí)行次數(shù)與問題規(guī)模n 的關(guān)系。即語句“ if(L.data[i]==e ”?即可：

（1）最好情況：目標(biāo)元素在表頭，循環(huán)1次；最好時間復(fù)雜度為O(1)

（2）最壞情況：目標(biāo)元素在表尾，循環(huán)n 次；最壞時間復(fù)雜度為O(n);

（3）平均情況：假設(shè)目標(biāo)元素出現(xiàn)在任何一個位置的概率相同，都是1/n，目標(biāo)元素在第一位，循環(huán)1次；第2位，循環(huán)2次；....... 在第n 為，循環(huán)n 次，則平均循環(huán)次數(shù) =1\n+2.1/n+....+n.1/n=(n+1)/2；則平均時間復(fù)雜度為O(n)。

關(guān)于順序表的一些知識先就說這么多，共勉！

寫在最后：對于準(zhǔn)備學(xué)習(xí)C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

微信公眾號：C語言編程學(xué)習(xí)基地

C語言零基礎(chǔ)入門教程（83集全）

整理分享（多年學(xué)習(xí)的源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！

編程學(xué)習(xí)書籍分享：

學(xué)習(xí)資料領(lǐng)取：