1 順序表
1 順序表
核心公式：
程式 = 演算法 + 數據結構
程式設計 = 演算法 + 數據結構 + 編程範式
數據結構 = 結構定義 + 結構操作
1定義
順序表是一種線性表數據結構，即線性結構；它用一段連續的記憶體空間 來存儲一組具有相同類型 的數據。
-
線性表（Linear List）：顧名思義，線性表就是數據排成像一條線一樣的結構。每個線性表上的數據最多只有前和後兩個方向。其中，順序表、鏈表、隊列、棧等都是線性表結構。
-
非線性表：是與線性表相對的概念，如二叉樹、堆、圖等。之所以叫非線性，是因為，在非線性表中，數據之間並不是簡單的前後關係。
2 性質
1. 高效的隨機訪問
-
由於順序表具有連續的記憶體空間和相同類型數據，故支援「隨機訪問」；
-
由於順序表具有連續的記憶體空間，故其下標從「0」開始；定址公式: data[i] = base_address + i * sizeof(data_type), base_address 為存儲空間的首地址。
-
註：隨機訪問 != 查找O(1) ，因為二分查找的複雜度為O(logn)；但是，按照數組索引方式訪問數據，其複雜度為O(1) ；
-
由於要保證物理記憶體的連續性，所以對於順序表的「插入」和「刪除」操作效率非常低，因為需要移動大量的數據元素。
2. 低效的插入與刪除
-
假設順序表的長度為 n，現在，如果我們需要將一個數據插入到順序表中的第 k 個位置。為了 把第 k 個位置騰出來，給新來的數據，我們需要將第 k～n 這部分的元素都順序地往後挪一 位；
-
如果在數組的末尾插入元素，那就不需要移動數據了，這時的時間複雜度為 O(1) ；
-
但如果在數組的開頭插入元素，那所有的數據都需要依次往後移動一位，所以最壞時間複雜度是 O(n) ；
-
因為我們在每個位置插入元素的概率是一樣的，所以平均情況時間複雜度為 (1+2+ …n)/n=O(n) ；
-
跟插入數據類似，如果我們要刪除第 k 個位置的數據，為了記憶體的連續性，也需要將k~n這部分的元素都順序的前移一位；
-
優化方法：建議「插入」和「刪除」操作順序表中的最後一位元素；
1. 插入操作
2. 刪除操作
3. 動態擴容(realloc)
-
因為順序表本身在定義時，需要預先指定空間大小，因為需要分配連續的記憶體空間；當順序表的預定義的存儲空間使用完畢後，此時再「插入」元素時，就需要申請一塊更大的存儲空間，一般建議是預定義空間大小的2倍；
-
註：因為擴容操作涉及記憶體申請和數據搬移，是比較耗時的。所以， 如果事先能確定需要存儲的數據大小，最好在創建 順序表 的時候事先指定數據大小；
3程式碼演示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define GREEN(a) COLOR(a, 32)
#define RED(a) COLOR(a, 31)
typedef struct Vector {
int *data; // 指向一片連續的存儲空間
int size, length; // size：順序表的最大容量，length：當前順序表中數據元素的個數
} Vec;
Vec *init(int); // 初始化，生成一片連續的存儲空間
int insert(Vec *, int, int); // 插入，成功：1，失敗：0
int erase(Vec *, int); // 刪除，成功：1，失敗：0
void clear(Vec *); // 清空
void output(Vec *); // 遍歷
int main() {
#define MAX_N 20
Vec * v = init(1);
srand(time(0));
for (int i = 0; i < MAX_N; i++) {
int op = rand() % 4;
int ind = rand() % (v->length + 3) - 1; // ind 的取值範圍：[-1, v->length + 1]
int val = rand() % 100;
switch (op) {
case 0:
case 1:
case 2: {
printf("insert %d at %d to the Vector = %d\n", val, ind, insert(v, ind, val));
} break;
case 3: {
printf("erase an item at %d from the Vector = %d\n", ind, erase(v, ind));
} break;
}
output(v), printf("\n");
}
#undef MAX_N
clear(v);
return 0;
}
Vec *init(int n) {
Vec *v = (Vec *)malloc(sizeof(Vec));
v->data = (int *)malloc(sizeof(int) * n);
v->size = n;
v->length = 0;
return v;
}
// 動態申請空間的方式：malloc、calloc、realloc
// calloc 相對於 malloc 而言，所申請的空間清零
// realloc 重新申請空間 void *realloc(void *ptr, size_t new_size);
// 1 擴張ptr所指向的已存在記憶體
// 2 分配一個大小為 new_size 位元組的新記憶體塊，並將ptr指向的數據拷貝到新記憶體中，然後釋放ptr指向的數據
// 3 分配失敗（沒有足夠的記憶體），返回NULL，但ptr指向的記憶體並未釋放
int expand(Vec *v) {
// 順序表的動態擴容，一般擴容為原空間的2倍
int extr_size = v->size;
int *p;
// 通過動態的減小extr_size值，來提高擴容的可能性
while (extr_size) {
p = (int *)realloc(v->data, sizeof(int) * (extr_size + v->size));
if (p != NULL) break;
extr_size >>= 1;
}
// 擴容失敗（沒有足夠的記憶體）
if (p == NULL) return 0;
v->size += extr_size;
v->data = p;
return 1;
}
int insert(Vec *v, int ind, int val) {
// 判斷順序表是否存在
if (v == NULL) return 0;
// 1 位置合法性判斷，順序表必須在[0, v->length]的範圍內插入元素
if (ind < 0 || ind > v->length) return 0;
// 2 當前順序表中數據元素是否達到容量上限（size），以此來判斷是否需要擴容處理
if (v->length == v->size) {
if (!expand(v)) {
printf(RED("fail to expand!\n"));
}
printf(GREEN("success to expand! the size = %d\n"), v->size);
}
// 3 將ind後的每一個元素後移（包括ind位置的元素）
for (int i = v->length; i > ind; i--) {
v->data[i] = v->data[i - 1];
}
// 4 在指定位置插入元素，同時順序表中的數據元素個數加一
v->data[ind] = val;
v->length += 1;
return 1;
}
int erase(Vec *v, int ind) {
if (v == NULL) return 0;
// 1 位置合法性判斷，此處必須有等號，因為元素下標是從0開始的
// 2 此處，隱式包含了順序表的判空操作
if (ind < 0 || ind >= v->length) return 0;
// 3 將ind後的每個元素依次向前移動
for (int i = ind + 1; i < v->length; i++) {
v->data[i - 1] = v->data[i];
}
// 4 數據元素的個數減一
v->length -= 1;
return 1;
}
void clear(Vec *v) {
if (v == NULL) return ;
free(v->data);
free(v);
return ;
}
void output(Vec *v) {
if (v == NULL) return ;
printf("[");
for (int i = 0; i < v->length; i++) {
i && printf(", ");
printf("%d", v->data[i]);
}
printf("]\n");
return ;
}
