順序表介紹

順序表是在計算機記憶體中以陣列的形式保存的線性表，線性表的順序存盤是指用一組地址連續的存盤單元依次存盤線性表中的各個元素、使得線性表中在邏輯結構上相鄰的資料元素存盤在相鄰的物理存盤單元中，即通過資料元素物理存盤的相鄰關系來反映資料元素之間邏輯上的相鄰關系，采用順序存盤結構的線性表通常稱為順序表，順序表是將表中的結點依次存放在計算機記憶體中一組地址連續的存盤單元中，

在這里，我們可能會有些迷惑，順序表和普通的陣列有什么區別呢？
順序表和普通陣列的區別主要有以下兩點：

1.順序表的長度可以動態增長，普通陣列的長度是固定的，
2.順序表要求插入的資料在記憶體中是連續的，普通陣列的資料存放可以不連續，

初始化順序表

首先，我們要創建一個順序表型別，該順序表型別包括了順序表的起始位置、記錄順序表內已有元素個數的計數器(size)，以及記錄當前順序表的容量的變數(capacity)，

typedef int SLDataType;//本篇博客以存放整型資料為例

typedef struct SeqList
{
	SLDataType* a;//宣告了一個指向順序表的指標，姑且稱它為“順序表指標”
	int size;//記錄當前順序表內元素個數
	int capacity;//記錄當前順序表的最大容量
}SeqList;

然后，我們需要一個初始化函式，對順序表進行初始化，

//初始化順序表
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;//剛開始時順序表為空，順序表指標為NULL
	ps->size = 0;//起始時元素個數為0
	ps->capacity = 0;//容量為0
}

銷毀順序表

因為順序表所用的記憶體空間是動態開辟在堆區的，所以我們在使用完后需要及時對其進行釋放，避免造成記憶體泄漏，

//銷毀順序表
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);//釋放順序表指標指向的空間
	ps->a = NULL;//及時置空
	ps->size = 0;//元素個數置0
	ps->capacity = 0;//容量置0
}

若需要對資料進行保存，可以使用檔案操作函式將資料保存到一個檔案中，下次使用順序表的時候先讀取檔案資料即可，

列印順序表

列印就比較簡單了，依次回圈列印size個元素即可，

//列印順序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	//回圈列印順序表指標指向的資料
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

增加資料

仔細想想，我們每次需要增加資料的時候，首先都應該先檢查順序表內元素個數是否已達順序表容量上限，若已達上限，那么我們就需要先對順序表進行擴容，然后才能增加資料，

//檢查順序表容量是否已滿，若已滿，則增容
void SeqCheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)//滿了，需要增容
	{
		//判斷順序表容量是否為0，若為0，則先開辟用于存放4個元素的空間大小，若不為0，則擴容為原來容量的兩倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* newA = realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = newA;//開辟成功，將順序表指標更新
		ps->capacity = newcapacity;//容量更新
	}
}

注意：若傳入realloc的指標為空指標(NULL)，則realloc函式的作用相當于malloc函式，

頭插

要想在順序表的表頭插入資料，那么就需要先將順序表原有的資料從后往前依次向后挪動一位，最后再將資料插入表頭，

//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//檢查容量
	int i = 0;
	for (i = ps->size; i > 0; i--)//將資料從后往前依次向后挪
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;//順序表元素個數加一
}

注意：挪動資料的時候應從后向前依次挪動，若從前向后挪動，會導致后一個資料被覆寫，

尾插

尾插相對于頭插就比較簡單了，直接在表尾插入資料即可，

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//檢查容量
	ps->a[ps->size] = x;
	ps->size++;//順序表元素個數加一
}

指定下標位置插入

要做到在指定下標位置插入資料，首先我們需要得到一個下標位置，然后從該下標位置開始（包括該位置），其后的資料從后往前依次向后挪動一位，最后將資料插入到該下標位置，

//指定下標位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//檢查輸入下標的合法性
	SeqCheckCapacity(ps);//檢查容量
	int i = 0;
	for (i = ps->size; i > pos; i--)//從pos下標位置開始，其后的資料從后往前依次向后挪
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;//順序表元素個數加一
}

我們可以發現，頭插和尾插實際上就是在下標為0的位置和下標為ps->size的位置插入資料，也就意味著我們可以統一使用該函式來實作頭插和尾插，

//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	SeqListInsert(ps, 0, x);//在下標為0的位置插入資料
}
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	SeqListInsert(ps, ps->size, x);//在下標為ps->size的位置插入資料
}

洗掉資料

洗掉資料，其實可以理解為：從某個位置開始，資料依次向前覆寫，這樣一來，該位置的資料就相當于洗掉了，

頭刪

要洗掉表頭的資料，我們可以從下標為1的位置開始，依次將資料向前覆寫即可，

//頭刪
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);//保證順序表不為空
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)//將資料從前往后依次向前覆寫
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;//順序表元素個數減一
}

注意：資料覆寫的時候應從前向后依次覆寫，若從后向前覆寫，會導致前一個資料被覆寫，

尾刪

尾刪就更簡單了，直接將順序表的元素個數減一即可，

//尾刪
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);//保證順序表不為空
	ps->size--;//順序表元素個數減一
}

指定下標位置洗掉

要洗掉指定下標位置的資料，我們只需要從下標位置開始，其后的資料從前向后依次覆寫即可，

//指定下標位置洗掉
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);//保證順序表不為空
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)//從pos下標位置開始，其后的資料從前往后依次向前覆寫
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;//順序表元素個數減一
}

同樣的道理，頭刪和尾刪實際上也就是洗掉下標為0的位置和下標為ps->size - 1的位置的資料，也就意味著我們可以統一使用該函式來實作頭刪和尾刪，

//頭刪
void SeqListPopFront(SeqList* ps)
{
	SeqListErase(ps, 0);//洗掉下標為0的位置的資料
}
//尾刪
void SeqListPopBack(SeqList* ps)
{
	SeqListErase(ps, ps->size - 1);//洗掉下標為ps->size - 1的位置的資料
}

查找資料

查找資料也相對簡單，直接遍歷一次順序表即可，若找到了目標資料，則停止遍歷，并回傳該資料的下標，否則回傳-1，

//查找元素，若有，回傳下標，否則回傳-1
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)//遍歷順序表進行查找
	{
		if (ps->a[i] == x)
			return i;//找到該資料，回傳下標
	}
	return -1;//未找到，回傳-1
}

修改資料

修改資料，就直接對該位置的資料進行再次賦值即可，

//修改指定下標位置元素
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//檢查輸入下標的合法性
	ps->a[pos] = x;//修改資料
}