什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

静态顺序表

使用定长数组存储元素,只能存储固定的元素个数，存不满导致空间浪费，存满不好增加容量，也容易溢出

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType array[N]; //定长数组
	size_t size;         //有效数据的个数
}SeqList;

动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景,静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小
使用动态开辟的数组存储,我们在堆上开辟空间存放数组

//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array; //指向动态开辟的数组
	size_t size;       //有效数据的位数
	size_t capacity;   //容量空间的大小
}SeqList;

我们将数组存放的元素类型用typedef重定义，这样后续我们要用顺序表存储别的元素，数据更改更加方便
用动态开辟的数组发现容量不够可以随时使用realloc来进行增容

顺序表初始化

一开始将指向数组的指针直接置空，以避免发生野指针访问的问题

void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array = NULL;
	psl->size = psl->capacity = 0;
}

检查容量与增加容量

一般情况下我们是直接按照原容量的两倍进行扩容，因为一次扩多了，存在空间浪费，一次扩少了，频繁扩容，会导致效率下降。所以两倍比较合适

void CheckCapacity(SeqList* psl)
{
	if (psl->capacity == psl->size)
	{
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->array,sizeof(SeqList) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);//直接终止程序
		}

		psl->array = tmp;
		psl->capacity = newcapacity;
	}
}

顺序表增加数据

//在顺序表pos位置插入一个数据x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size >= pos);
	CheckCapacity(psl);
	size_t end = psl->size;
	while (end>pos)
	{
		psl->array[end] = psl->array[end-1];
		end--;
	}
	psl->array[pos] = x;
	psl->size++;
}

顺序表删除数据

//删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(psl->size > pos);

	while (psl->size-1 > pos)
	{
		psl->array[pos] = psl->array[pos + 1];
		pos++;
	}
	psl->size--;
}

顺序表查找数据

//查找，找到了返回下标值，没找到返回-1
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0;i < psl->size;i++)
	{
		if (psl->array[i] == x)
			return i;
	}
	return -1;
}

顺序表修改数据

//修改pos位置的数据为x
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size > pos);

	psl->array[pos] = x;
}

销毁顺序表

我们是动态开辟的数据，在使用完以后最好是将其释放并置空，以免出现内存泄露

//顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}

头文件代码

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//顺序表的静态存储
//#define N 10
//typedef int SLDataType;
//typedef struct SeqList
//{
//	SLDataType array[N]; //定长数组
//	size_t size;         //有效数据的个数
//}SeqList;

//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array; //指向动态开辟的数组
	size_t size;       //有效数据的位数
	size_t capacity;   //容量空间的大小
}SeqList;


// 基本增删查改接口

// 顺序表初始化
void SeqListInit(SeqList* psl);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);

// 顺序表尾删
void SeqListPopBack(SeqList* psl);

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);

// 顺序表头删
void SeqListPopFront(SeqList* psl);

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);

// 顺序表销毁
void SeqListDestory(SeqList* psl);

// 顺序表打印
void SeqListPrint(SeqList* psl);

//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

函数实现代码

#include "SeqList.h"

//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array = NULL;
	psl->size = psl->capacity = 0;
}

//检查容量与增容
void CheckCapacity(SeqList* psl)
{
	if (psl->capacity == psl->size)
	{
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->array,sizeof(SeqList) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);//直接终止程序
		}
		psl->array = tmp;
		psl->capacity = newcapacity;
	}
}

//顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}

//打印顺序表
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	for (int i = 0;i < psl->size;++i)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n");
}

//尾部插入
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	//第一种方法
	//assert(psl);
	//CheckCapacity(psl);
	//psl->array[psl->size] = x;
	//psl->size++;
	
	//第二种方法
	SeqListInsert(psl, psl->size, x);
}

//尾部删除
void SeqListPopBack(SeqList* psl)
{
	//第一种方法
	//assert(psl);
	//assert(psl->size > 0);
	//psl->size--;
	
	//第二种方法
	SeqListErase(psl, psl->size - 1);
}

//头部插入
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	//第一种方法
	//assert(psl);
	//CheckCapacity(psl);
	//int end = psl->size-1;
	//while (end>=0)
	//{
	//	psl->array[end + 1] = psl->array[end];
	//	end--;
	//}
	//psl->array[0] = x;
	//psl->size++;
	
	//第二种方法
	SeqListInsert(psl, 0, x);
}

//头部删除
void SeqListPopFront(SeqList* psl)
{
	//第一种方法
	//assert(psl);
	//assert(psl->size > 0);
	//for (int i = 0;i < psl->size-1;++i)
	//{
	//	psl->array[i] = psl->array[i + 1];
	//}
	//psl->size--;	

	//第二种方法
	//int begin = 0;
	//while (begin < psl->size-1)
	//{
	//	psl->array[begin] = psl->a[begin + 1];
	//	++begin;
	//}
	//psl->size--;
	
	//第三种方法
	SeqListErase(psl, 0);
}

//查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0;i < psl->size;i++)
	{
		if (psl->array[i] == x)
			return i;
	}
	return -1;
}

//在顺序表pos位置插入一个数
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size >= pos);
	CheckCapacity(psl);
	size_t end = psl->size;
	while (end>pos)
	{
		psl->array[end] = psl->array[end-1];
		end--;
	}
	psl->array[pos] = x;
	psl->size++;
}

//删除pos位置的数
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(psl->size > pos);
	//第一种方法
	while (psl->size-1 > pos)
	{
		psl->array[pos] = psl->array[pos + 1];
		pos++;
	}
	psl->size--;

	//第二种方法
	//size_t begin = pos;
	//while (begin < psl->size - 1)
	//{
	//	psl->array[begin] = psl->array[begin + 1];
	//	++begin;
	//}
	//psl->size--;
}

//修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size > pos);

	psl->array[pos] = x;
}

如果发现错误欢迎大佬们指出😸😸