1. 線性表

線性表(lina list)是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串......

線性表在邏輯上是線性結構，也就是說連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

2. 順序表實現

2.1 概念及結構

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

順序表一般可以分為：

1.靜態順序表：使用定長數組存儲。

2.動態順序表：使用動態開辟的數組存儲。

#define N 100
// 靜態順序表
struct SeqList
{int arr[N];int size;	// 有效數據個數
};

typedef int SLDataType;// 動態順序表
typedef struct SeqList
{SLDataType* arr;SLDataType size;	// 有效數據個數SLDataType capacity;	// 空間大小
}SL;

注意：靜態順序表只適用于確定知道需要多少數據的場景。靜態順序表的定長數組導致N定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是使用動態順序表，根據需要動態地分配空間大小，所以下面我們實現動態順序表。

2.2 順序表初始化

// 順序表初始化
void SLInit(SL* ps);

首先，我們需要初始化數組，數組首元素地址 ps->arr 置為NULL；有效數字個數 size 和空間容量capacity 大小都置為0。

// 順序表初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

2.3 順序表銷毀

// 順序表銷毀
void SLDestroy(SL* ps);

我們使用完順序表之后，都需要把順序表進行銷毀，以免造成內存被占用和內存泄漏問題。

首先，需要把開辟的空間 free 掉，再將數組首元素地址 ps->arr 置為NULL；有效數字個數 size 和空間容量 capacity 大小都置為0。

// 順序表銷毀
void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

2.4 順序表打印

// 順序表打印
void SLPrint(SL s);

為了更好地對程序進行調試，我們這里需要寫一個打印程序，以便我們測試每一個接口函數。

// 順序表打印
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}

附：我們完成這些前導工作，接下來我們就可以正式編寫順序表的功能函數。

2.5 順序表尾插

// 順序表尾插
void SLPushBack(SL* ps, SLDataType x);

我們得分兩種情況：

不過在尾插元素之前，我們必須得確保數組空間大小是足夠的，也就是說得有空間插入元素。如果說空間容量不夠的話，我們就得擴容，所以說在尾插之前，我們得判斷空間大小是否足夠，不夠咱就擴容。我們這里得寫一個內存容量檢查函數。

這里我們還得注意一個點：就是我們內存空間不夠的情況下，一般我們是以2倍或者3倍? capacity(容量) * 2 * sizeof(數據類型) 去開辟空間。

// 檢查內存函數
void SLCheckCapacity(SL* ps)
{// 插入數據之前看空間夠不夠if (ps->capacity == ps->size){// 申請空間// 申請之前，要判斷一下capacity是否為0int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;錯誤寫法：這里不要直接這樣寫，要不然申請空間失敗的話，前面的數據會丟失//ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));// 正確寫法SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));// 如果申請失敗if (tmp == NULL){perror("realloc fail!");exit(1);	// 直接退出程序，不再繼續執行}// 空間申請成功ps->arr = tmp;ps->capacity = newCapacity;}
}

檢查開辟完空間后，我們就可以進行下一步，順序表尾插接口函數編寫。

步驟：

① 程序開始前，我們要斷言一下，確保指針是有效的，不是NULL；

② 檢查內存是否足夠；

③ 將我們需要的 x 尾插入下標 ps->size 的位置，插完之后，數組元素總個數 ps->size 得加1。

// 順序表尾插
void SLPushBack(SL* ps, SLDataType x)
{溫柔的解決方式//if (ps == NULL)//	return;assert(ps); // 等價于assert(ps != NULL)// 檢查內存SLCheckCapacity(ps);/*ps->arr[ps->size] = x;++ps->size;*/ps->arr[ps->size++] = x;
}

2.6 順序表頭插

// 順序表頭插
void SLPushFront(SL* ps, SLDataType x);

我們也得分兩種情況：

不過我們在頭插元素之前，我們也得確保數組空間大小是足夠的，所以我們頭插之前也得調用一下內存檢查函數 SLCheckCapacity，保證我們內存容量是足夠的。

步驟：

① 程序開始前，我們要斷言一下，確保指針是有效的，不是NULL；

② 檢查內存是否足夠；

③ 將我們需要的 x 頭插入下標 0?的位置，插完之后，數組元素總個數 ps->size 得加1。

// 順序表頭插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);// 檢查內存SLCheckCapacity(ps);// 先讓順序表中已有的數據整體往后挪動一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0]}ps->arr[0] = x;ps->size++;
}

2.6 順序表尾刪

// 順序表尾刪
void SLPopBack(SL* ps);

我們刪除數據不是說要把這個數據從數組中去除，而是說我們這個所謂的“刪除的數據”不能被訪問，所以我們只需把數組中有效的元素個數 size - 1 即可，并不需要把這個數據變成什么其他的數，這是非常多余的(如果非要更改刪除數據也不是不可)。

步驟：

① 程序開始前，我們要斷言一下，確保指針是有效的，不是NULL；

② 斷言一下，數據有效個數不能為0；

③ 將數據有效個數 size - 1。

// 順序表尾刪
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);	// 順序表有效數字不能為0// 順序表不能為空//ps->arr[ps->size - 1] = -1;	// 這行代碼有點多余ps->size--;
}

附：尾刪還是非常簡單的！

2.7 順序表

// 順序表頭刪
void SLPopFront(SL* ps);

頭刪數據之后，我們還需要每個數據往前一位，最后 size - 1。

步驟：

① 程序開始前，我們要斷言一下，確保指針是有效的，不是NULL；

② 斷言一下，數據有效個數不能為0；

③? 然后將每個數據往前移動一位；

③ 將數據有效個數 size - 1。

// 順序表頭刪
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);	// 順序表有效數字不能為0// 數據整體往前挪動一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1]; // 最后一次，arr[size - 2] = arr[size - 1]}ps->size--;
}