1、頭檔案

我這里主要說的是動態的順序表，當然靜態順序表的操作基本上是一樣的，只是靜態順序表無法進行增容，數量是控制了的，會造成空間的浪費，
靜態順序表

#pragma once //防止頭檔案包含
#include<stdio.h>
#define MaxSize 100
typedef int SLDataType;
//利用typedef給int重命名為SLDataType，為以后改變資料型別提供方便
typedef struct SeqList
{
	SLDataType arr[MaxSize];
	size_t size;//size_t -> unsigned int
}SeqList;

動態順序表

#pragma once //防止頭檔案包含
#include<stdio.h>
#include<stdlib.h>//動態記憶體函式的頭檔案
#include<assert.h>//assert的頭檔案，用于檢查
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;//創建為指標，可以動態的增加空間
	size_t size;//當前資料量
	size_t Capacity;//總容量
}SeqList;

2、初始化

初始化指標a=NULL，當前資料量size=0，總容量Capacity=0

void SeqListInit(SeqList* ps)
{
	assert(ps);//斷言檢查,程式出錯，則報中斷在顯示端，指向哪里出錯
	ps->a = NULL;
	ps->Capacity = 0;
	ps->size = 0;
}

3、銷毀

若指標ps->a不為null，則釋放，在置空

void SeqListDestory(SeqList* ps)
{
	if (ps->a)
	{
		free(ps->a);//防止記憶體泄漏
		ps->a = NULL;//避免成為野指標
	}
	ps->Capacity = 0;//置0
	ps->size = 0;//置0
}

4、列印

回圈遍歷，輸出順序表
時間復雜度：o(n）

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

5、尾插

首先檢查順序表是否滿了，滿了就增容，再在資料的末尾插入值即可，size+1
時間復雜度：o(1)

void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//檢查size是否等于Capacity，等于就擴容
	ps->a[ps->size] = x;
	ps->size++;
}

在這里插入圖片描述

6、尾刪

將size-1即可，就訪問不到最后一個元素了
時間復雜度：o(1)

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

7、頭插

頭插跟尾插一樣需要檢查順序表是否滿員，滿則增容，在將所有的元素往后挪一位，騰出0位置給x，size+1
時間復雜度：o(n)

void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//檢查size是否等于Capacity，等于就擴容
	size_t end = ps->size;
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

在這里插入圖片描述

8、頭刪

洗掉首元素，需要將后面的元素往前挪一位，然后size-1
時間復雜度：o(n)

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	size_t begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

在這里插入圖片描述

9、查找

按照元素x在順序表中查找，遍歷查找即可，找到回傳在順序表中的位置，沒找到回傳 -1
最差時間復雜度：o(n)
最好時間復雜度：o(1)
平均時間復雜度：o(n/2)
時間復雜度：o(n)

int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	size_t begin = 0;
	while (begin < ps->size)
	{
		if (ps->a[begin] == x)
			return begin;
		begin++;
	}
	return -1;
}

10、插入

按照pos的值在順序表中插入值x，需要檢查pos是否在順序表的長度+1的范圍內，在找到pos這個位置，將原來的資料往后移動一位，pos位置插入值x
最差時間復雜度：o(n)
最好時間復雜度：o(1)
平均時間復雜度：o(n/2)
時間復雜度：o(n)

void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
	assert(ps);
	assert(pos <= ps->size && pos >= 0);
	SeqListCheckCapacity(ps);
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

在這里插入圖片描述

11、洗掉

按照pos的值在順序表中查找，首先檢查pos的值是否在順序表長度范圍內，在則將pos位置后的資料往前移動一位，將pos位置的值進行洗掉
最差時間復雜度：o(n)
最好時間復雜度：o(1)
平均時間復雜度：o(n/2)
時間復雜度：o(n)

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	assert(pos < ps->size && pos >= 0);
	size_t begin = pos;
	while (begin < ps->size - 1)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}

在這里插入圖片描述

12、檢查容量

檢查容量的，如果size增加到與Capacity相等了，此時說明順序表滿了，得擴容增加大小，此時就呼叫此函式將Capacity的數值進行增加

void SeqListCheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->Capacity)
	{
		size_t newCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;
		SLDataType*ps1 = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用realloc函式重新開辟一塊空間進行擴容
		if (ps1==NULL)//檢查是否開辟失敗
		{
			perror("realloc");
			return;
		}
		ps->a = ps1;//新空間賦給a
		ps->Capacity = newCapacity;//賦值給Capacity，進行擴容
		
	}
}