一、動態版本順序表

在實作順序表之前，我們要知道順序表按照能不能擴容可以分為兩種版本，靜態版本和動態版本，
靜態版本就是把內容存到陣列中，一旦陣列在記憶體堆疊上開辟了，當資料存滿的時候就不能再繼續存盤了，所以針對這個缺點我們有了動態版本順序表，我們把資料存到堆區中，可以進行自動擴容處理，當資料存滿還能擴容繼續存盤，

二、動態順序表的實作思路

順序表特點：將表中元素一個接一個的存入一組連續的存盤單元中，這種存盤結構是順序結構，針對這種線性結構有以下思路：

所以我們先創建一個順序表結構體型別，結構體型別中有指標，下標，容量，
指標：用來維護在堆上連續的一段空間，
下標：表示資料存放到哪一個位置了，因為資料只能一個接著一個地存放，要有個下標來記錄我資料放到哪一個位置了，
容量：與下標相比較，當下標與容量相等就表示空間存盤滿了，要進行擴容處理，
創建型別如下：

//我們以int型別資料來實作順序表
typedef int DataType; //對int型別重新起個名字叫DataType

//創建一個順序表結構體型別
struct SeqList   
{
	DataType* a; //資料的指標
	int size;    //下標
	int capacity; //記錄開辟空間的最大下標處
};

//對順序表型別struct SeqList型別重新起個名字叫SL
typedef struct SeqList SL;  


//當size 和 capacity相等時要進行擴容處理

這樣我們就可以在主函式main()中創建一個順序表結構體型別的變數，然后我們對資料進行處理，實作順序表的各種介面函式，就是對這個變數進行操作即可，

三、動態順序表記憶體布局圖

在這里插入圖片描述

四、初始化順序表和記憶體釋放

我們最知道區域變數是在堆疊區創建的，初始值為隨機值，我們得對變數sl進行初始化，并且當退出程式的時候要把堆上開辟的空間還給作業系統，要釋放空間，函式如下：

//對變數sl進行初始化函式
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


// 釋放記憶體函式
void SeqListDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

五、順序表介面實作：

1.尾部插入資料

當我們插入資料的時候一定要注意兩點：
1、檢測空間是否滿了，如果滿了就要進行擴容處理，否則就會導致記憶體泄漏
2、插入是否為第一次插入資料，因為初始化函式給的容量是0，就會開辟不了記憶體，所以當第一次插入資料我們容量要給2，以后空間滿了就用二倍來進行擴容處理，

代碼如下：

//增加容量函式
DataType* BuyCapacity(SL* ps)
{
	//第一次插入資料我們容量要給2，以后空間滿了就以二倍來進行擴容處理
	ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;

	DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * ps->capacity);
	if (tmp == NULL)
	{
		perror("erron");
		exit(-1);
	}
	return tmp;

}

//尾部插入資料函式
void SeqListPushBack(SL* ps, DataType x)
{
	if (ps->capacity == ps->size)  //檢測空間是否滿了
	{
		DataType* tmp = BuyCapacity(ps); //增容函式
		ps->a = tmp;
	}
	ps->a[ps->size] = x;   //把資料放到尾部
	ps->size++;  //下標要往后挪動一位
	
}

2.頭部插入資料

頭部插入資料不同于尾部那樣直接在后面放進來即可，我們要把資料先往后挪動一位，再把資料放到頭部，也有兩點要注意：
1、檢測空間是否滿了，如果滿了就要進行擴容處理，否則就會導致記憶體泄漏
2、挪動資料要從尾部往后面挪，如果從頭部往后挪會把資料給覆寫掉，
圖片分析如下：
在這里插入圖片描述

代碼實作如下：

//頭部插入資料函式
void SeqListPushFront(SL* ps,DataType x)
{
	if (ps->capacity == ps->size)
	{
		DataType* tmp = BuyCapacity(ps);
		ps->a = tmp;
	}
	int i = 0;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;   //把資料放到頭部
	ps->size++;    //下標要往后挪動一位
	
}

3.尾部洗掉資料

尾部洗掉資料要注意一點，那就是當我空間沒有資料就不能再洗掉了，所以要洗掉資料時要判斷空間內是否有資料，
代碼如下：

//尾部洗掉資料函式
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0); //判斷空間是否有資料
	ps->size--;   //下標自減一即可
}

4.頭部洗掉資料

頭部的洗掉沒有尾部洗掉那樣簡單，頭刪需要挪動資料，有兩點要注意的地方：
1、要判斷空間內是否有資料，有資料才能洗掉
2、挪動資料要從頭部的第二個元素往前面開始挪動，不能從尾部挪動，因為從尾部往前挪會把資料給覆寫掉，
圖片分析如下：
在這里插入圖片描述

5.顯示資料

顯示資料即把資料列印出來即可，代碼如下：

//顯示資料函式
void SeqListPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

6.查找資料

查找函式就是要找到某一個資料對應的下標，找到了則回傳資料的下標，找不到就回傳 -1，所以我們遍歷一遍陣列即可，代碼如下：

//查找資料函式
int  SeqListFind(SL* ps, DataType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
		   //找到資料就直接回傳下標
			return i;
		}
	}
	
	//找不到就回傳-1
	return -1;
}

7.在某個位置插入資料

在某個位置插入資料有三點要注意：
1、檢測空間是否滿了，如果滿了就要進行擴容處理，否則就會導致記憶體泄漏
2、挪動資料要從尾部開始往后面挪，每一個元素往后面挪動一位
3、要對插入的位置進行判斷，插入的下標要大于或者等于0 并且要小于或者等于陣列的有效位置
圖片分析：
在這里插入圖片描述
代碼如下：

//插入資料函式
void SeqListInsert(SL* ps, DataType x,int pos)
{
	//對插入的位置進行判斷
	assert(pos >= 0 && pos <= ps->size);
	if (ps->capacity == ps->size)
	{
		DataType* tmp = BuyCapacity(ps);
		ps->a = tmp;
	}

	int i = 0;
	//從尾部開始移動
	for (i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;  
	ps->size++;
}

8.在某個位置洗掉資料

這個和頭插類似，也有三點要注意的地方：
1、要判斷空間內是否有資料，有資料才能洗掉
2、挪動資料要從傳過來下標的第二個元素往前面開始挪動，不能從尾部挪動，因為從尾部往前挪會把資料給覆寫掉，
3、要對洗掉的位置進行判斷，洗掉的下標要大于或者等于0 并且要小于陣列的有效位置

圖片分析如下：
在這里插入圖片描述
代碼如下：

//洗掉資料函式
void SeqListErase(SL* ps, int pos)
{
	//要判斷空間內是否有資料
	assert(ps->size != 0); 
	//要對洗掉的位置進行判斷
	assert(pos >= 0 && pos < ps->size);

	//挪動資料
	int i = 0;
	for (i = pos + 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
	ps->size--;
}

六、對頭插尾插頭刪尾刪的改造

頭插、尾插：
大家發現沒有，我們的在某個位置插入資料函式和頭插尾插函式是不是比較類似，其實1、當在某個位置插入資料函式，要插入的下標是0時就是頭插函式了，
2、當在某個位置插入資料函式，要插入的下標是陣列的size時就是尾插函式了
所以我們寫頭插尾插函式時完全什么都不要干，只需要呼叫某個位置插入資料函式，并且把下標傳過去就可以了，
代碼如下：

//尾插函式
void SeqListPushBack(SL* ps, DataType x)
{
    //直接呼叫插入函式，插入的下標是size
	SeqListInsert(ps, x, ps->size);
}

//頭插函式
void SeqListPushFront(SL* ps,DataType x)
{
    //直接呼叫插入函式，插入的下標是0
	SeqListInsert(ps, x, 0);
}

頭刪、尾刪：
某個位置洗掉資料函式和頭刪尾刪函式是不是比較類似，
1、當在某個位置洗掉資料函式，要洗掉的下標是0時就是頭洗掉函式了，
2、當在某個位置洗掉資料函式，要洗掉的下標是陣列的有size時就是尾刪函式了
所以我們寫頭刪、尾刪函式時完全什么都不要干，只需要呼叫某個位置洗掉資料函式，并且把下標傳過去就可以了，
代碼如下：

//尾刪函式
void SeqListPopBack(SL* ps)
{
    //呼叫洗掉函式
	SeqListErase(ps, ps->size - 1);
}

//頭刪函式
void SeqListPopFront(SL* ps)
{
    //呼叫洗掉函式
	SeqListErase(ps, 0);
}

所以我們實作頭插尾插頭刪尾刪可以直接呼叫插入、洗掉函式，

七、總結

總的來說，順序表的實作有幾點要注意：
1、插入的時候要判斷容量是否滿了；
2、洗掉的資料要判斷容量是否為空；
3、插入、洗掉的位置是否在有效范圍內；
4、移動資料要從哪個位置開始移動，
下面附上我的測驗代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void test1()
{
	SL sl;
	SeqListInit(&sl);
	printf("尾插：\n");
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);
	SeqListPushBack(&sl, 6);
	SeqListPrint(&sl);

	printf("頭插：\n");
	SeqListPushFront(&sl, 10);
	SeqListPushFront(&sl, 20);
	SeqListPushFront(&sl, 30);
	SeqListPrint(&sl);

	printf("尾刪：\n");
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPrint(&sl);

	printf("頭刪：\n");
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	printf("中間插入：\n");
	SeqListInsert(&sl, 20, 3);
	SeqListInsert(&sl, 20, 1);
	SeqListInsert(&sl, 20, 2);
	SeqListPrint(&sl);

	printf("中間洗掉：\n");
	SeqListErase(&sl, 5);
	SeqListErase(&sl, 0);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}


int main()
{
	test1();
	return 0;
}

測驗結果：
在這里插入圖片描述
以上就是我的順序表內容了，其中前面我只有把源檔案SeqList.c 和測驗檔案test.c拆開來分析了，如果想要順序表的全部內容，闊以移步到gitee上獲取，

三個源檔案內容鏈接：
https://gitee.com/fait-juyuan/data-structure/tree/master/test_10_14_%E9%A1%BA%E5%BA%8F%E8%A1%A8/test_10_14_%E9%A1%BA%E5%BA%8F%E8%A1%A8