Day26-【13003】短文，什么是順序表？順序表和數組、內存地址的關系？順序表的插入、刪除操作如何實現？操作的時間復雜度是多少？

文章目錄

- 第二節，線性表的順序存儲及實現概覽
- - 什么是順序表和鏈表？順序存儲的叫順序表
  - 順序表和數組還有內存地址的關系？
  - 順序表的基本操作如何實現？
  - - 1、插入操作如何實現？
    - 2、刪除操作如何實現？
    - 3、賦值和查找操作怎樣達成？
    - 這些的操作時間復雜是多少？

第二節，線性表的順序存儲及實現概覽

在這里插入圖片描述

什么是順序表和鏈表？順序存儲的叫順序表

可以使用順序存儲方式和鏈式存儲方式保存線性表，從而分別得到線性表的順序存儲結構和鏈式存儲結構。

順序存儲結構使用數組保存線性表中的各元素

原來數組，不是線性結構的一種，而是線性表的一種實現方式：

來自AI：

線性結構是基礎概念

線性結構是一種數據結構，它具有線性的邏輯關系，即數據元素之間存在著一對一的線性關系。

線性表是典型的線性結構

線性表是最基本、最常用的一種線性結構。它是具有相同數據類型的 n（n≥0）個數據元素的有限序列，通常表示為 (a1, a2, …, an)。

數組是線性表的一種實現方式

從邏輯結構上看，數組可以被看作是一種線性表。例如，一維數組可以看作是一個線性表，數組中的每個元素對應線性表中的一個數據元素，它們在內存中是連續存儲的，元素之間的邏輯順序與物理存儲順序一致，很好地體現了線性表的線性關系。

對于二維數組，可以將其視為線性表的推廣，即線性表中的元素又是一個線性表。

；就是線性表形成一個元素，再組成一個線性表

從存儲結構上看，數組具有隨機訪問的特性，通過下標可以快速地訪問數組中的元素，時間復雜度為 O (1)。這使得數組在很多需要快速定位和訪問元素的場景中非常高效，這也是數組作為線性表實現方式的一個重要優勢。

1、相應的線性表稱為順序表。

使用順序存儲結構保存線性表非常方便，因為可以通過下標來訪問數組元素，所以可以實現對表中元素的隨機訪問。

這是順序存儲結構的優勢。

在順序表中實現插入和刪除時可能需要移動元素，

如果插入和刪除的位置靠近表頭位置，則移動的元素個數偏多。
當有頻繁的插入、刪除操作時，元素的移動也會很頻繁，操作的效率較低。
另外，由于數組的大小是相對固定的，因此，當表的長度有很大變化時，數組空間的利用率也不好控制。
1. 有可能會因為表中元素個數過多而導致數組空間不足，
2. 也可能會因為表中元素個數較少，使得數組中的很多位置是空置的。

這些都是順序存儲結構的不足之處。

針對順序表的這些問題，提出了線性表的另一種存儲方式，即鏈式存儲方式。

鏈式存儲結構使用鏈表保存線性表中的各元素，

2、相應的線性表稱為鏈表。

順序表和數組還有內存地址的關系？

在C語言中，一維數組是順序存儲的連續存儲空間，所以線性表的順序存儲結構就是將線性表中的各數據元素，按照其邏輯次序，依次保存到數組中。

線性表中的一個元素保存在數組的一個單元中。線性表中邏輯上相鄰的兩個元素，保存在數組內相鄰的兩個單元中。

為了保存一個線性表，需要分配一個多大的數組呢?

線性表中的元素個數可以是變化的，這意味著數組的單元數也要變化。

而一旦數組分配完畢，它的個數就不會改變。一般地，需要分配一個足夠大的數組以供線性表使用，這樣既保證能夠保存線性表中當前的全部元素，又為后續的插入操作預留了空間。

在分配數組時，預留的數組空間越大，數組空間占滿的可能性越小，空間利用率越低，即存儲效率越低。

應該根據線性表中可能包含的元素的最大個數來分配數組。

為了表示數組中保存的實際元素個數，通常還需要使用一個整型變量來記錄順序表的當前長度。

在分配數組空間后，將線性表中的n個元素依次保存在數組中，從表頭至表尾的各個元素分別對應從下標0到下標n-1的位置。

數組是內存中一片連續的空間，相鄰的兩個單元在內存中的實際地址也是相鄰的

這表明，線性表中邏輯上相鄰的兩個元素，其存儲地址也是相鄰的。

這是順序表的一個顯著特點。

線性表中的元素可以是有定義的任何類型。

在內存中，保存不同類型的元素時會需要數目不等的存儲單元。

要正確理解“數組中相鄰單元的存儲地址相鄰”這句話的含義。
$假設有線性表 L=(a_0, a_1, a_2, a_3, a_4, a_5)，\\ 每個元素需占用 2 字節，也就是一共占12字節\\ 分配一個含8個元素的數組 A保存 L\\ 則A再內存中的示意圖如圖2-1所示\\ A占據內存從位置M起的連續空間\\ |元素|存儲字節范圍|\\ |a_0|第1 - 2字節|\\ |a_1|第3 - 4字節|\\ |a_2|第5 - 6字節|\\ |a_3|第7 - 8字節|\\ |a_4|第9 - 10字節|\\ |a_5|第11 - 12字節|\\ 線性表L共占 12 字節。\\ 一般每個字節對應內存中的一個存儲單元\\ 計算機編址方式有字編址、字節編址等，編址方式可能不完全一致\\ 所以保存a_0 的首地址與保存 a_1的首地址未必連續，\\ 但這兩地址編號間不會再保存其他元素的地址編號。$

在這里插入圖片描述

數組下標與線性表元素的位置相對應。

線性表元素依次存放的特性，決定了表中位置 i ( i≥0 ) 的元素存儲在數組的下標 i 處。

表頭元素保存在位置0處，；也就是數組的下標0處

這個位置也稱為數組的首地址。

有了這個約定，對表中任意一個元素的訪問將變得非常容易。

只要給出表中元素的序號，就可以根據下標地址計算公式很容易地計算出元素所在的內存位置(實際上是相對于數組首地址的偏移量)，因此可以直接訪問該元素。

順序表中的訪問方式稱為隨機訪問方式，；這是從存儲結構的角度來看，上面AI部分有介紹

其含義是，只要給定數組下標，就能立即計算出相應元素的存儲地址，并據此訪問該元素。

1、下標地址計算公式如下：

$\text{LOC}(a_i)（i \geq 0）表示元素 a的存儲首地址，每個元素需要占用 d 個存儲單元，則有：\\ (2-1):\text{LOC}(a_i)=\text{LOC}(a_{i - 1})+d \quad\\ 進一步地有：\\ (2-2):\text{LOC}(a_i)=\text{LOC}(a_0)+i\times d\quad\\ \text{LOC}(a_0) 即數組的首地址。\\$

用這個公式是怎么算的

2、也可以使用另一種求解方法。

第6個元素占用的最后一個存儲單元，實際上是第7個元素占用的第1個存儲單元的前一個單元。

可以先計算第7個元素的首地址，得到148，再減1，

得到相同的答案。

線性表的插入和刪除是兩個基本操作。

順序表要求表中的相鄰元素存儲在數組的相鄰單元中，

所以當在某個位置插入新元素時，必須先為這個元素找到相應的存儲空間，同時要保證數組中所有元素依然依次相鄰存放。、

在刪除元素時，被刪除元素所占用的位置要由其他元素來填補。

總的來說，在當前位置插入元素或刪除當前位置的元素時，看都會涉及從當前位置開始，一直到表尾的所有元素，即這些元素都需要移動。

當在表尾后插入元素或刪除表尾元素時，操作是容易實現的，因為操作不會引起其他元素的移動。

當插入或刪除操作的位置是其他位置時，移動元素的個數依賴于操作的位置。

例如，當要在表頭插入新元素時，表中當前所有元素都必須向表尾方向移動一個位置以騰出空間。

當要在表中(合理的)位置i插入一個新元素時，這個位置及其到表尾的所有元素都必須向表尾方向移動一個位置。

刪除操作與此類似，只是元素的移動是向表頭方向進行的。

平均來說，插入和刪除操作要移動表中約一半的元素。

設給定一個順序表，初始時含有5個元素:11、5、23、19和6。

在位置2插入元素27，然后刪除位置3的元素，

每步操作后的順序表如圖2-2所示。

在這里插入圖片描述

~~注意，這里是刪除初始順序表中，位置3的元素，而不是插入之后的位置3~~
注意，刪除位置3，其實是刪除第4個位置的元素，也就是說，確實是刪除插入之后的表中的，位置3的元素！
因為位置0，才是第1個元素！

這兩個步驟，實際上就是一個修改操作，把位置3的元素給替換了

1、為了執行“在位置2插入元素27”，需要依次將元素6、19和23向后移動一個位置，注意移動的次序。

先移動6，最后移動23。；也就是先從最后一個開始移

此時，位置3的空間是可用的，將元素27保存在這個位置。、

這個過程如圖2-3所示。

在這里插入圖片描述

2、在執行“刪除位置3的元素”時，需要將23后面的元素(19和6)依次前移一個位置。

移動的次序是,先移動19，再移動6。；注意這里，是從最靠近刪除元素位置的這個19，開始移動

這個過程如圖2-4所示。

在這里插入圖片描述

順序表的基本操作如何實現？

實現基本操作的程序中會用到一些常量，其定義如下。

#define TRUE 1
#define FALSE 0
#define ERROR -1
#ifndef maxSize
#define maxSize 100
#endif

表中每個元素的類型是ELEMType，順序表的定義如下，

typedef int ELEMTYPE;
typedef struct {ELEMTYPE element[maxSize];  //保存元素的數組，最大容量為 maxSizeint n;                      //順序表中的元素個數
} SeqList;
typedef SeqList LinearList;
typedef int Position;

新構造的順序表為空表。

空表中所含的元素個數為零，將表清空也意味著表中元素個數為零。

int initList(SeqList *L) 	// 初始化順序表，創建一個空表L
{L->n = 0;return TRUE;
}int clear(SeqList *L) 		// 將表L置空
{L->n = 0;return TRUE;
}

根據順序表中n的值，可以判斷順序表是否為空、是否已滿，

值n也直接代表順序表的長度。

int isEmpty(SeqList *L) {	// 如果表L為空，則返回1，否則返回0if (L->n == 0)return TRUE;elsereturn FALSE;
}int isFull(SeqList *L) {	// 如果表L已滿，則返回1，否則返回0if (L->n == maxSize)return TRUE;elsereturn FALSE;
}int length(SeqList *L) {	// 返回表L的當前長度return L->n;
}

1、插入操作如何實現？

當在不滿的順序表中插入一個元素x時，除了要指明元素的值以外，還要指出插入的位置。

insertList函數帶有3個參數，分別是

順序表、

插入位置

及要插入的值。

位置值pos必須是一個合理的整數值，即pos值介于**0和“L->n”**之間。

合理的位置值有n+1個。

為何加1個，就是空表也能插入

插入在位置0處，意味著插入在表頭位置。

插入在“L->n”處。意味著添加在原表尾的后一個位置。

當確認表不滿且插入位置有效后，從表尾元素開始，到插入位置的元素為止，依次將各元素后移一個位置。

移動完畢，將元素x放到移動后出現的空閑位置中。

之后將元素個數增1，即表長增1。也就是n增加1

插入操作的實現如下。

int insertList(SeqList *L, Position pos, ELEMTYPE x) {	// 在表L的位置pos處插入元素xint i;if (isFull(L) == TRUE) return FALSE;  				// 表已滿if (pos < 0 || pos > L->n) return ERROR; 			// 位置錯誤，與表滿區分開for (i = L->n; i > pos; i--) {L->element[i] = L->element[i - 1];  			// 移動元素}L->element[i] = x;  								// 放置xL->n++;  											// 表長增1return TRUE;
}

對于長度為n的順序表，當在表尾的后一個位置插入元素時，不需要移動任何元素。

如果插入在倒數第一個位置，則需要移動1個元素;

如果插入在倒數第二個位置，則需要移動兩個元素。

依此類推，插入在第一個位置，需要移動n個元素。

總之，當在位置i插入元素時，需要移動n-i個元素。

如果在任何位置進行插入的概率都相等，則插入操作中，移動元素的平均次數N為：
$\frac{\sum_{k = 0}^{n} k}{n + 1} = \frac{n}{2}$

2、刪除操作如何實現？

刪除操作是類似的，函數removeList中需要指明順序表及要刪除的元素所在的位置。

通常，刪除的元素值需要通過一個變量返回給操作調用者，所以removeList函數也帶有三個參數，前兩個參數分別是

順序表

和刪除位置，

刪除的元素值將放到第三個參數中。；這和插入是差不多的三個參數呀

也可以讓removeList函數只帶前兩個參數，

而刪除的元素值通過函數的返回值帶回。；這個才是和插入的區別

也就是形參x是指針元素

在刪除時，需要確認表不為空且位置值pos有效，

這里pos應介于0和“L->n-1”之間。

合理的位置值有n個。

合理的位置值少一個，為什么是0和n-1之間內，為何n要減一個1，n不減行不行

是不是因為插入，可以從空表開始插入，但是刪除，空表沒法刪

注意，刪除的合理位置值比插入的合理位置值少1。

移動表元素時，從被刪除元素的直接后繼開始，一直到表尾結束，各元素依次前移一個位置。

同時，表長減1。也就是n減去1

刪除操作的實現如下。

int removeList(SeqList *L, Position pos, ELEMTYPE *x) {	// 刪除表L中位置pos處的元素并通過x返回  //這個形參x，是指針元素int i;if (isEmpty(L) == TRUE) return FALSE;  				// 表空if (pos < 0 || pos > L->n - 1) return ERROR; 		// 位置錯誤，與表空區分開*x = L->element[pos];  								// 記下被刪除的元素值for (i = pos; i < L->n - 1; i++) {L->element[i] = L->element[i + 1];  			// 前移元素}L->n--;  											// 表長減1return TRUE;
}

來自AI：

在形參列表中，ELEMTYPE *x 這種寫法表明 x 是一個指針。

這里 ELEMTYPE 是自定義的數據類型（在前面代碼中被定義為 int 類型），

* 是指針聲明符，它表示 x 是一個指向 ELEMTYPE 類型數據的指針。

在函數體中，有語句 *x = L->element[pos]; 。
這里使用了 * 操作符（解引用操作符），它的作用是訪問指針 x 所指向的內存空間。
將 L->element[pos] 的值賦值給 *x ，意味著把數組中指定位置的元素值存儲到 x 所指向的內存位置，
這進一步證明了 x 是一個指針。