深入浅出数据结构：手把手实现动态顺序表，从此不再怕数组扩容！

// 静态顺序表
// 定义数组的固定长度（容量）
#define N 7      
typedef struct SeqList 
{
	SLDataType a[N]; // 定长数组，用于存储数据 
	int size;      // 记录顺序表中有效数据个数
}SL;

// 顺序表元素类型（方便修改）
typedef int SLDataType;
// 动态顺序表结构体
typedef struct SeqList
{
	SLDataType* arr; // 指向存储数据的动态数组
	int size;      // 有效元素个数
	int capacity;  // 顺序表容量
}SL;

//顺序表初始化
void SLInit(SL* ps)
{
	assert(ps);
	//避免野指针
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//销毁顺序表
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);//释放堆上的空间
	ps->arr = NULL;//避免野指针
	ps->size = 0;
	ps->capacity = 0;
}

//检查容量，不允许被外部调用 (static 关键字)
static void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//容量不够
	if (ps->capacity == ps->size)
	{
		//计算新容量：容量为0时初始化为4，否则加倍
		int new_capacity = ps->capacity == 0 ? INIT_CAPACITY : 2 * ps->capacity;
		//申请空间：使用realloc来调整内存大小
		//这里一定不能用arr直接接收，因为还有申请失败的可能
		//如果申请失败，不仅得不到新地址，还会将原来的空间也丢掉
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, new_capacity * sizeof(SLDataType));
		//申请失败，退出
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//申请成功后赋值新地址，更新容量
		ps->arr = tmp;
		ps->capacity = new_capacity;
	}
}

//尾插法
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps); // 检查容量并扩容
	ps->arr[ps->size++] = x;//将x放在顺序表最后一个位置，且有效个数加1
}
//尾删法
void SLPopBack(SL* ps)
{
	//有元素才能删除
	assert(ps && ps->size);
	ps->size--; // 逻辑删除，有效元素个数减一
}

//头插法
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	// 将元素从后往前挪，直到索引1位置
	for (int i = ps->size; i > 0; i--)
		ps->arr[i] = ps->arr[i - 1];
	// 插入元素到头部
	ps->arr[0] = x;
	// 元素个数自增
	++ps->size;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	// 将后面的元素往前挪，覆盖掉首元素
	for (int i = 1; i < ps->size; i++)
		ps->arr[i - 1] = ps->arr[i];
	--ps->size;
}

//在指定位置插入元素
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断插入位置是否合法：pos可以等于size，表示尾插
	assert(pos >= 0 && pos <= ps->size);
	//检查容量
	SLCheckCapacity(ps);
	//将pos之后的元素后移
	for (int i = ps->size; i > pos; i--)
		ps->arr[i] = ps->arr[i - 1];
	ps->arr[pos] = x;
	++ps->size;
}
//在指定位置删除元素
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//将pos之后的元素往前挪
	for (int i = pos; i < ps->size; i++)
		ps->arr[i] = ps->arr[i + 1];
	--ps->size;
}

//按值查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	//从头开始遍历查找
	for (int i = 0; i < ps->size; i++)
		if (ps->arr[i] == x)
			return i;//找到返回下标
	return -1;//没找到
}

//清空顺序表
void SLClear(SL* ps)
{
	assert(ps);
	//只把元素有效个数置为0，空间留下，后续继续使用
	ps->size = 0;
}
//获取顺序表长度
int SLGetLength(SL* ps)
{
	assert(ps);
	return ps->size;
}
//判断表空
bool SLIsEmpty(SL* ps)
{
	assert(ps);
	return ps->size == 0;
}
//顺序表反转
void SLReverse(SL* ps)
{
	assert(ps);
	int left = 0, right = ps->size - 1;
	while (left < right)
	{
		// 交换元素
		SLDataType tmp = ps->arr[left];
		ps->arr[left] = ps->arr[right];
		ps->arr[right] = tmp;
		++left; 
		--right;
	}
}
//打印顺序表
void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	puts(" ");
}

// 测试顺序表的基础操作
void TestSeqList1()
{
	SL sl;
	SLInit(&sl); // 初始化
	printf("--- 1. 尾插操作 ---\n");
	SLPushBack(&sl, 10);
	SLPushBack(&sl, 20);
	SLPushBack(&sl, 30);
	SLPushBack(&sl, 40); // 此时触发第一次扩容
	SLPrint(&sl); // 输出: 10 20 30 40 
	printf("Length: %d, Capacity: %d\n", SLGetLength(&sl), sl.capacity); // 4, 4/8
	SLPushBack(&sl, 50); // 触发扩容
	SLPushBack(&sl, 60);
	SLPrint(&sl); // 输出: 10 20 30 40 50 60 
	printf("Length: %d, Capacity: %d\n", SLGetLength(&sl), sl.capacity); // 6, 8
	printf("--- 2. 头插操作 ---\n");
	SLPushFront(&sl, 5);
	SLPushFront(&sl, 1);
	SLPrint(&sl); // 输出: 1 5 10 20 30 40 50 60
	printf("Length: %d, Capacity: %d\n", SLGetLength(&sl), sl.capacity); // 8, 8 (如果初始容量是4，此时会再次扩容到16)
	printf("--- 3. 任意位置插入 (pos=2, 888) ---\n");
	SLInsert(&sl, 2, 888);
	SLPrint(&sl); // 输出: 1 5 888 10 20 30 40 50 60 
	printf("--- 4. 按值查找 (Find 30) ---\n");
	int pos = SLFind(&sl, 30);
	if (pos != -1)
		printf("Element 30 found at index: %d\n", pos); // 5
	printf("--- 5. 尾删和头删 ---\n");
	SLPopBack(&sl); // 删 60
	SLPopFront(&sl); // 删 1
	SLPrint(&sl); // 输出: 5 888 10 20 30 40 50 
	printf("--- 6. 任意位置删除 (pos=1, 删 888) ---\n");
	SLErase(&sl, 1);
	SLPrint(&sl); // 输出: 5 10 20 30 40 50 
	printf("--- 7. 顺序表反转 ---\n");
	SLReverse(&sl);
	SLPrint(&sl); // 输出: 50 40 30 20 10 5 
	printf("--- 8. 清空和销毁 ---\n");
	SLClear(&sl);
	printf("Is Empty: %s\n", SLIsEmpty(&sl) ? "True" : "False");
	SLDestroy(&sl); // 释放内存
}