1. 線性表

????????線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串...線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的， 線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

2. 順序表

2.1 概念與結構

概念：順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。

?順序表和數組的關系是什么？

順序表的底層就是數組，順序表是用數組來實現的，兩種創建數組的方式：

2.2 分類

2.2.1?靜態順序表

概念：使用定長數組存儲元素

2.3 動態順序表的實現

void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}

傳值和傳址操作?

?順序表初始化：

void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}

尾插法

擴容realloc操作：?

//尾插
void SLPushBack(SL* ps, SLTDataType x) {if (ps->size == ps->capacity) { // 空間不夠，擴容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLTDataType* tmp = (SLTDataType *)realloc(ps->arr, sizeof(SLTDataType) * newCapacity);if (tmp == NULL) {perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->size++] = x;
}

利用調試的監視窗口，監視變量的值從而進行調試。按F5調試，按F5+Ctrl，直接運行，按F10一行行調試，但不進入函數內部，按F11進入函數內部。

頭插法：時間復雜度o(n)

// 頭插法
void SLPushFront(SL* ps, SLTDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--) {ps->arr[i] = ps->arr[i-1];}ps->arr[0] = x;ps->size++;
}

?尾刪法：時間復雜度o(1)

// 尾刪法
void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}

頭刪法：o(n)

// 頭刪法
void SLPopFront(SL* ps) {assert(ps && ps->size);//數據整體向前挪動一位for (int i = 0; i < ps->size-1; i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

指定位置之前插入：o(n)

// 指定位置之前插入
void SLInsert(SL* ps, int pos, SLTDataType x) {assert(ps);assert(pos >= 0 && pos < ps->size);SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

刪除pos位置的數據：

// 刪除pos位置的數據
void SLErase(SL* ps, int pos) {assert(ps);assert(0 <= pos && pos < ps->size);for (int i = pos; i < ps->size - 1; i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

銷毀順序表：

void SLDestroy(SL* ps) {if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

相關算法題：

1.?移除元素

27. 移除元素 - 力扣（LeetCode）

2.?刪除有序數組中的重復項

26. 刪除有序數組中的重復項 - 力扣（LeetCode）

3.?合并兩個有序數組

88. 合并兩個有序數組 - 力扣（LeetCode）