線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列

線性表的數(shù)據(jù)對(duì)象集為{a 1 , a 2 , ……, a n }，每個(gè)數(shù)據(jù)元素的類型相同。其中，除了第一個(gè)元素 a1 之外，每個(gè)元素都有并且只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素 a n之外，每個(gè)元素都有并且只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的。

線性表的訂單存儲(chǔ)結(jié)構(gòu)

線性表的數(shù)據(jù)元素一次存儲(chǔ)在具有連續(xù)地址的存儲(chǔ)單元中

一個(gè)1一個(gè)2......一個(gè)i-1我_......一個(gè)_

順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性：

存儲(chǔ)空間的起始位置：數(shù)據(jù)數(shù)據(jù)，其存儲(chǔ)位置為存儲(chǔ)空間的存儲(chǔ)位置。

直線米最大存儲(chǔ)容量：數(shù)組MaxSize的長(zhǎng)度。

直線米的當(dāng)前長(zhǎng)度：長(zhǎng)度。

內(nèi)存地址計(jì)算方法

用數(shù)組存儲(chǔ)順序表意味著分配固定長(zhǎng)度的數(shù)組空間，因?yàn)榫€性表可以插入或刪除，所以分配的數(shù)組空間應(yīng)該大于等于當(dāng)前線性表的長(zhǎng)度。

記憶中的地址，就像圖書館的座位一樣，都是編號(hào)的。內(nèi)存中的每個(gè)存儲(chǔ)單元都有自己的編號(hào)、地址。因?yàn)槭琼樞蚪Y(jié)構(gòu)，所以當(dāng)?shù)谝粋€(gè)位置確定后，后面的位置就可以計(jì)算出來了。比如，我全班第五，排在我后面的是10，學(xué)生的成績(jī)是6,7,...,15，因?yàn)?+1,5+2,...,5+10。每一個(gè)數(shù)據(jù)元素，無論是整容、真實(shí)還是人物，都需要占用一定的存儲(chǔ)單元空間。假設(shè)占用c個(gè)存儲(chǔ)單元，那么線性表中第二個(gè)i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿足如下關(guān)系：

LOC (a i + 1 ) = LOC (a i ) + c

所以對(duì)于第 i 個(gè)數(shù)據(jù)元素 a i的存儲(chǔ)位置可以有一個(gè)1計(jì)算得到：

LOC (a i ) = LOC (a 1 ) + (i-1) * c

通過這個(gè)公式，可以同時(shí)計(jì)算出線性表中任意位置的地址，任意位置，全部。它的時(shí)間復(fù)雜度是 O(1)。一般將具有這種特性的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)的插入和刪除

1.獲取元素操作碼：

public class ArrayList<E> {
transient Object[] elementData;
public E get(int index) {
Objects.checkIndex(index, this.size);
return this.elementData(index);
}
E elementData(int index) {
return this.elementData[index];
}
}
 Copy code 

2.插入

比如，買春運(yùn)火車票。每個(gè)人都排好隊(duì)。這位是美女，說……對(duì)排隊(duì)的第三個(gè)人，“大哥，請(qǐng)幫幫我，我媽在家病了，趕緊回去看看她，隊(duì)伍這么長(zhǎng)，能不能把我放進(jìn)去在你面前?”你心軟，答應(yīng)了。身后的人都不得不退后一步。這個(gè)例子實(shí)際上已經(jīng)說明了線性表的順序存儲(chǔ)結(jié)構(gòu)，插入數(shù)據(jù)時(shí)的實(shí)現(xiàn)過程。

插入思路：

如果插入位置不合理，拋出異常;

如果線性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度，則拋出異常或動(dòng)態(tài)增加容量;

從最后一個(gè)元素開始，向前遍歷到下一個(gè) i A 地方，將它們分別向后移動(dòng)一個(gè)位置;

填入要插入元素的位置i，Watch長(zhǎng)度加1。

代碼實(shí)現(xiàn)：

public boolean add(E e) {
++this.modCount;
this.add(e, this.elementData, this.size);
return true;
}
public void add(int index, E element) {
this.rangeCheckForAdd(index);
++this.modCount;
int s;
Object[] elementData;
if ((s = this.size) == (elementData = this.elementData).length) {
elementData = this.grow();
}
System.arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
this.size = s + 1;
}
 Copy code 

3.刪除操作

接下來，我們以上面的例子為例。這時(shí)，一名警察出現(xiàn)了，對(duì)美女說道：“跟我去局。” 女人離開了隊(duì)伍。原來，她是個(gè)賣火車票的黃牛，裝窮排隊(duì)買票。然后排隊(duì)的人，都往前邁了一步。這是在線性表的順序存儲(chǔ)結(jié)構(gòu)中刪除元素的過程。

刪除想法：

如果刪除位置不合理，則拋出異常;

移除刪除元素;

從被刪除元素位置遍歷到最后一個(gè)元素位置，分別向前移動(dòng)一個(gè)位置;

手表長(zhǎng)度減 1。

代碼實(shí)現(xiàn)：

public E remove(int index) {
Objects.checkIndex(index, this.size);
Object[] es = this.elementData;
E oldValue = es[index];
this.fastRemove(es, index);
return oldValue;
}
 Copy code 

插入和刪除的時(shí)間復(fù)雜度。

最好的情況，如果要將元素插入到最后一個(gè)位置，或者刪除最后一個(gè)元素，此時(shí)時(shí)間復(fù)雜度為O(1)，因?yàn)椴恍枰苿?dòng)元素。

最壞的情況，如果要插入元素到第一個(gè)位置或者要?jiǎng)h除第一個(gè)元素，此時(shí)時(shí)間復(fù)雜度為O(n)，因?yàn)樗蚝蠡蛳蚯耙苿?dòng)了1個(gè)位置之后的所有元素。

至于一般情況，因?yàn)樵夭迦氲搅说趇個(gè)A地方，或者刪除了第i個(gè)元素，需要移動(dòng)ni個(gè)元素。根據(jù)概率原理，在每個(gè)位置插入或刪除元素的可能性是相同的，也就是說，位置在前面，移動(dòng)更多元素，位置向后，移動(dòng)元素更少。最終平均移動(dòng)次數(shù)等于中間元素的移動(dòng)次數(shù)，乘以(n-1)/2，即O(n)。

分析表明，線性表的順序存儲(chǔ)結(jié)構(gòu)，在存在、讀取數(shù)據(jù)時(shí)，無論在哪里，時(shí)間復(fù)雜度為零O(1);插入或刪除時(shí)，時(shí)間復(fù)雜度為零O(n)。說明它更適合，元素?cái)?shù)量不變，訪問數(shù)據(jù)的應(yīng)用也更多。

線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)勢(shì) ：

無需為表中元素之間的邏輯關(guān)系增加額外的存儲(chǔ)空間

您可以快速檢索表格中任何位置的元素

缺點(diǎn)：

插入和刪除操作需要移動(dòng)大量元素

當(dāng)延米長(zhǎng)度變化較大時(shí)，存儲(chǔ)空間的容量難以確定

創(chuàng)造存儲(chǔ)空間“碎片”

以上就是關(guān)于“線性表的順序存儲(chǔ)結(jié)構(gòu)詳解”的介紹，大家如果對(duì)此比較感興趣，想了解更多相關(guān)知識(shí)，不妨來關(guān)注一下動(dòng)力節(jié)點(diǎn)的Java在線學(xué)習(xí)，里面的課程內(nèi)容從入門到精通，很適合沒有基礎(chǔ)的小伙伴學(xué)習(xí)，希望對(duì)大家能夠有所幫助。