一、线性表

线性表（linear list）：是n个具有相同特性的数据元素的有限序列。
常见的线性表：顺序表、链表、栈、队列、字符串…

🔵特点：
??? 逻辑上：线性结构
??? 物理上：不一定是连续（一般以数组和链式结构的形式存储）

在这里插入图片描述

二、顺序表

??? 2.1 概念和分类

顺序表:是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储

顺序表可以分为两种：

静态顺序表：使用定长数组存储元素
动态顺序表：使用动态开辟的数组存储

??? 2.2 接口实现

动态顺序表是静态顺序表的升级版，这里我们的接口实现考虑动态顺序表：

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

?????? 1.初始化

// 顺序表初始化
void SeqListInit(SeqList* psl)
{
	psl =NULL;
	psl->capicity = 0;
	psl->size = 0;
}

?????? 2.扩容

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
	//新增的空间大小
	//考虑两种情况：①啥也没②有东西但满
	int newcapacity = psl->capicity == 0 ? 4 : psl->capicity * 2;//*2是为了避免不断开辟空间
	//新空间的指针
	SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * newcapacity);
	if (tmp == NULL)
	{
		printf("fail\n");
		exit(-1);
	}
	//新空间指针给旧空间，原始数据迁移旧空间销毁
	psl->array = tmp;
	//容量变成新的数值
	psl->capicity = newcapacity;
}

?????? 3.销毁顺序表

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

?????? 4.打印数据

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

?????? 5.尾插

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	if (psl->capicity == psl->size)
	{
		CheckCapacity(psl);
	}
	psl->array[psl->size] = x;
	psl->size++;
}

?????? 6.尾删

// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	if (psl->size == 0)
	{
		printf("empty!fail!\n");
		exit(-1);
	}
	//暴力点
	//assert(ps->size>0);
	psl->array[psl->size-1] = 0;//这条只是初始化数据实际没啥用可以屏蔽
	//|0 1 2 3 4 5|
	//size=6,要删除最后一个数据需要-1
	psl->size--;
}

?????? 7.头插

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	if (psl->size == psl->capicity)
	{
		CheckCapacity(psl);
	}
	for (int i = psl->size; i > 0; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[0] = x;
	psl->size++;
}

?????? 8.头删

// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
	if (psl->size == 0)
	{
		printf("empty!fail!");
		exit(-1);
	}
	//直接覆盖前一个数据
	for (int i = 1; i < psl->size - 1; i++)
	{
		psl->array[i - 1] = psl->array[i];
	}
	psl->size--;
}

?????? 9.某一位置增

在这里插入图片描述

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	if (psl->size == psl->capicity)
	{
		CheckCapacity(psl);
	}
	for (int i = psl->size; i > pos-1; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[pos-1] = x;
	psl->size++;
}

?????? 10.某一位置删

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	//pos的值有误
	if (pos<-1 || (pos-1)>(psl->size - 1))
	{
		printf("fail！");
		exit(-1);
	}
	//表是空的
	if (psl->size == 0)
	{
		printf("empty!fail!");
		exit(-1);
	}
	for (int i = pos - 1; i < psl->size - 2; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

?????? 11.找

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