先做一個記錄：這篇博客的開始寫作時間是2021年11月1日22點，明天我就要英語期中考了，一點沒復習的我還在這里搞博客（英語是真的無趣啊），

資料結構簡介

這里參考度娘的話

資料結構是計算機存盤、組織資料的方式，資料結構是指相互之間存在一種或多種特定關系的資料元素的集合，通常情況下，精心選擇的資料結構可以帶來更高的運行或者存盤效率，資料結構往往同高效的檢索演算法和索引技術有關，

好的程式 = 合適的資料結構 + 演算法，學好資料結構對程式員來說是一件重要的事，
資料結構分為線性結構和非線性結構，線性表是線性結構中的一種，之前我們已經學習了C語言，那么接下來我們先用C語言實作我們學習的第一種資料結構：線性表中的順序表，主要內容包括順序表的創建、初始化、增、刪、查、改等，因為本人也是C語言小白，比較理解小白的感受，我盡量詳細的講解！

順序表

線性表簡介

線性表是n個具有相同特性的資料元素的有限序列，線性表在實際中使用廣泛，包括順序表、鏈表、堆疊、佇列、字串……
線性表在邏輯上是線性結構，但在物理上不一定，線性表在物理上的儲存通常以陣列和鏈式結構進行，

順序表簡介

順序表是用一段連續的記憶體空間依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，可分為：

1. 靜態順序表：定長陣列存盤
2. 動態順序表：動態開辟的陣列存盤
   在這里我們一般在結構體中實作，

靜態順序表

11.3號晚，英語考的好爛，不開心，繼續學編程……

幾點簡單的說明

1. 我們把int型重定義為SLDataType，當我們想要修改順序表的資料型別時，只需修改typedef后面的int就行了，后面我們使用的都是SLDataType，就不用修改了
2. size_t其實就是unsigned int
3. 我們知道，在C語言中，我們可以用typedef對一個東西進行重命名，結構體是其中之一，因此我們可以新建一個結構體變數，再對它重命名，或者在創建時就重命名：

   //先創建，再重命名
   struct Student
   {
   	char name[20]; 
   	size_t age; 
   };
   typedef Struct Student St;
   //同時創建和重命名
   typedef struct Student
   {
   	char name[20]; 
   	size_t age; 
   } St;
   

創建一個靜態順序表

#define N 1000
typedef int SLDataType;
typedef struct SeqList
{
SLDataType arr[N]; // 定長陣列
size_t size; // 有效資料的個數
}SL;

這種方法的弊端是十分明顯的，如果我們只需要存盤10個值，而我們開辟的空間過大，或者我們開辟的空間不足，都是非常麻煩的，因此我們基本不使用這種順序表

動態順序表

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

動態順序表的創建

typedef struct SeqList
{
SLDataType* ps; // 指向動態開辟的陣列
size_t size; // 有效資料個數,即當前存盤資料的個數
size_t capicity; // 容量空間的大小
}SL;

動態順序表的初始化

#define MAX_SIZE 4
//我們用函式來實作動態順序表的初始化
void SeqListInit(SL* ps)//把需要初始化的結構體s的指標傳過來，因為我們知道，如果傳過來的是形式引數，我們將無法對原結構體進行修改
{
	ps->ps=NULL;//將指標置為空，后面擴容時再對指標賦值
	ps->size=ps->capicuty=0;//把順序表的當前大小和容量重置為0，這種情況下我們可以用連續賦值（我太懶了）
}

動態順序表的增刪查改

注意：我們后面說的頭插，就是插入到第一個位置，我們所說的pos位置，就是pos下標對應的位置，
我們通過呼叫函式來實作動態順序表的一些操作，這里我們先看一下我們都需要哪些函式，及這些函式實作的功能

// 檢查空間，如果滿了，進行增容，因為我們每次呼叫有關增加內容的函式時，都需要檢查空間是否已滿，因此先實作這個函式
void CheckCapacity(SeqList* ps);
// 動態順序表頭插，后面依次后移
void SeqListPushFront(SeqList* psl, SLDataType x);
// 動態順序表頭刪，后面依次前移
void SeqListPopFront(SeqList* ps);
// 動態順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
// 動態順序表尾刪
void SeqListPopBack(SeqList* ps);
// 動態順序表查找
int SeqListFind(SeqList* ps, SLDataType x);
// 動態順序表在pos位置插入x，原pos位及后面的都后移
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
// 動態順序表洗掉pos位置的值，pos位后面的前移
void SeqListErase(SeqList* ps, size_t pos); 
// 動態順序表列印
void SeqListPrint(SeqList* ps);
// 動態順序表銷毀
void SeqListDestory(SeqList* ps);

檢

檢查動態順序表是否已滿，已滿則擴容為原來的二倍，為0則初始化為4：

void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//如果容量已滿
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);//如果是第一次呼叫則容量設為4，否則擴充為原來的二倍
		SLDataType* tmp = (SLDataType*)realloc(ps->ps, newcapacity * sizeof(SLDataType));//realloc指把第一個引數指向的位置擴容到第二個引數表示的大小的位元組數，我們也需要把該函式回傳值強轉為SLDataType*型
		if (tmp == NULL)//開辟空間失敗
		{
			printf("realloc fail\n");
			exit(-1);//退出程式，并且退出代碼為-1，即括號內的引數
		}
		else
		{
			ps->ps = tmp;//把開辟的地址賦給結構體里的陣列指標
			ps->capacity = newcapacity;//擴容
		}
	}
}

增

動態順序表在pos位置插入x：

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);//先確保pos指向的位置未越界，如果括號內運算式不成立，則終止程式執行
	SeqListCheckCapacity(ps);//檢查容量
	int end = ps->size - 1;
	while (end >= pos)//pos及后面的資料后移
	{
		ps->ps[end + 1] = ps->ps[end];
		--end;
	}
	ps->ps[pos] = x;//pos位上賦值
	ps->size++;//順序表大小加一
}

動態順序表頭插：
其實這里我們只用呼叫在pos位置上插入x的函式就可以了(注釋內容為另一種實作方法)：

void SeqListPushFront(SL* ps, SQDataType x)
{
	//SeqListCheckCapacity(ps);

	 1、初始條件
	 2、結束條件
	 3、迭代程序
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->ps[end + 1] = ps->ps[end];
	//	--end;
	//}

	//ps->ps[0] = x;
	//ps->size++;

	SeqListInsert(ps, 0, x);
}

動態順序表尾插（注釋內容為另一種實作方法）：

void SeqListPushBack(SL* ps, SQDataType x)
{
	/*SeqListCheckCapacity(ps);

	ps->ps[ps->size] = x;
	ps->size++;*/

	SeqListInsert(ps, ps->size, x);
}

刪

動態順序表在pos位置洗掉：

void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);
	int start = pos + 1;
	while (start < ps->size)//pos后面的數前移
	{
		ps->ps[start-1] = ps->ps[start];
		++start;
	}
	ps->size--;
}

動態順序表頭刪（注釋內容為另一種實作方法）：

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	
	/*
	int start = 1;
	while (start < ps->size)
	{
		ps->ps[start - 1] = ps->ps[start];
		++start;
	}
	ps->size--;*/
	SeqListErase(ps, 0);
}

動態順序表尾刪（注釋內容為另一種實作方法）：

void SeqListPopBack(SL* ps)
{
	//assert(ps->size > 0);

	ps->ps[ps->size - 1] = 0;
	//ps->size--;
	SeqListErase(ps, ps->size - 1);
}

查

動態順序表遍歷查找，找不到回傳-1，找到回傳下標：

int SeqListFind(SL* ps, SQDataType x)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->ps[i] == x)
		{
			return i;
		}
	}

	return -1;
}

動態順序表的列印：

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

改

動態順序表把pos位置上的數修改為x：

void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);
	ps->ps[pos] = x;
}

到這里，我們就搞定動態順序表的基本功能了，后面我們會通過幾道題進行練習鞏固，