前言

資料結構中的線性表是資料結構基礎的開始，也是我們在后續學習中需要多次實作的內容，其中的常見介面我們需要熟練掌握，本文將從概念性質、概念圖解、介面代碼等方面來講解線性表中的順序表的知識內容

1.線性表

1.1線性表的概念&理解

定義：線性表是最基本、最簡單、也是最常用的一種資料結構，線性表（linear list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列，

線性表中資料元素之間的關系是一對一的關系，即除了第一個和最后一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部，

個人理解：線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…

PS:線性表在邏輯上是線性結構，有就是說，若果我們用一條線將各個元素連在一起，可以拉成一條直線，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

1.2線性表的圖解

圖解：
1.1線性的感官認識

1.2鏈表的結構展示（邏輯結構）

圖中接頭的存在就是邏輯結構，我們通過箭頭的繪制，使得這些資料直觀的看起來連成一條直線，但實際上，鏈表在記憶體中的存盤形式，可能并非如此整齊，例如下圖

1.3鏈表的結構展示（物理結構）圖中的地址值僅是舉例使用，并非有效真實資料

1.4順序表

2.順序表

2.1順序表的概念&結構

定義：順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

我們面對的順序表常見為兩種情況：
①靜態順序表

②動態順序表：

2.2順序表介面的實作

順序表中的我們需要對其進行一系列介面（函式）的實作，而這些介面在我們后續的鏈表，佇列等地方都需要實作這些介面以及對這些介面的改變，所以介面的實作是至關重要的，

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

首先我們創建順序表結構：

typedef int SQDataType;
typedef struct SeqList
{
	SQDataType * a;//指向動態開辟的陣列空間
	int size;//有效資料個數，當前順序表以及存盤元素個數
	int capacity;//順序表容量空間大小：
}SLT;

2.2.1順序表的初始化

void SeqListInit(SLT* ps1)
{
	assert(ps1 != NULL);//當為假時報錯；
	ps1->a = NULL;
	ps1->size = ps1->capacity = 0;
}

2.2.2順序表判斷空間是否已滿，進行增容

SeqListCheckCapacity(SLT * ps1)//判斷是否需要增容
{
	assert(ps1);

	if (ps1->size == ps1->capacity)
	{
		size_t newcapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;
		//一般增容時，增容為當前存盤能力的兩倍：
		ps1->a = realloc(ps1->a, newcapacity*sizeof(SQDataType));
		ps1->capacity = newcapacity;
	}
}

2.2.3順序表的尾插

void SeqListPushBack(SLT* ps1, SQDataType x)///尾插
{
	assert(ps1);
	SeqListCheckCapacity(ps1);//判斷是否需要增容
	ps1->a[ps1->size] = x;
	ps1->size++;

}

2.2.4順序表的尾刪

void SeqListPopBack(SLT* ps1)//尾刪
{
	assert(ps1);
	//ps1->a[ps1->size - 1] = 0;
	//這一句代碼可以不寫，因為可以只將當前的有效數字記錄減一，這里的資料我們就不看它了，它依然存在；因為如果這里資料不再是int型的資料，而是其他型別的資料不能直接用0覆寫(結構體等)
	ps1->size--;
}

2.2.5順序表的頭插

void SeqListPushFront(SLT* ps1, SQDataType x)//頭插
{
	assert(ps1);

	SeqListCheckCapacity(ps1);//判斷是否需要增容

	int end = ps1->size - 1;//將順序表陣列中的資料后移
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}

	ps1->a[0] = x;//實作頭插
	ps1->size++;

}

2.2.6順序表的查找

int SeqListFind(SLT* ps1, SQDataType x)//查找函式
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)//回圈判斷，不斷后移判斷元素
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

2.2.7順序表在pos位置插入x

void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos <= psl->size && pos >= 0);
	SeqListCheckCapcity(psl);

	size_t end = psl->size;//size_t為無符號資料型別
	while (end > pos)
	{
		psl->a[end] = psl->a[end-1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

2.2.8順序表洗掉pos位置的值

void SeqListErase(SLT*ps1, size_t pos)//指定位置洗掉
{
	assert(ps1);
	assert(pos < ps1->size);

	size_t begin = pos + 1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}

	ps1->size--;
}

2.2.9順序表的銷毀

void SeqListDestory(SLT* ps1)
{
	assert(ps1 != NULL);//當為假時報錯；
	if (ps1->a)
		free(ps1->a);

	ps1->size = ps1->capacity = 0;
}

2.2.10順序表的列印

void SeqListPrint(SLT * ps1)
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

2.3順序表的缺點

①當我們使用動態記憶體函式實作創建順序表時，當判斷當前記憶體不足時，增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入了1個資料，后面沒有資料插入了，那么就浪費了99個資料空間，

②每一次增容需要申請新空間，拷貝資料，釋放舊空間，會造成一定的消耗，

③當我們在執行插入介面時，如果指定的位置是中間或者頭部，那么我們在移動資料時，其時間復雜度為O(N)，

如果我們想要避免這些問題，那么我們可以采用鏈表的形式解決，

總結

①順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

②順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

③鏈表在實作時，會造成記憶體空間浪費 ，時間復雜度較高等一系列缺點，而這些缺點我們可以通過鏈表來解決，

上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】