【数据结构】顺序表实现超详解（保姆级教程）

//静态循序表
#define CAPACITY 100
typedef struct SeqList
{
	SLDateType data[CAPACITY];//动态开辟指向其地址
	size_t size;//已经使用的数量
}SeqList;

//动态顺序表
typedef struct SeqList
{
	SLDateType* data;//动态开辟指向其地址
	size_t size;//已经使用的数量
	size_t capacity; //开辟空间的总大小（容量）
}SeqList;

//默认开辟大小
#define DEFAULT_SZ 4
//设定默认数据类型
typedef int SLDateType;
//动态顺序表
typedef struct SeqList
{
	SLDateType* data;//动态开辟指向其地址
	size_t size;//已经使用的数量
	size_t capacity; //开辟空间的总大小（容量）
}SeqList;

// 对数据的管理:增删查改 
//初始化
void SeqListInit(SeqList* ps);
//释放
void SeqListDestory(SeqList* ps);
//打印（展示）
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//头插
void SeqListPushFront(SeqList* ps, SLDateType x);
//前删
void SeqListPopFront(SeqList* ps);
//尾删
void SeqListPopBack(SeqList* ps);

// 顺序表查找x的位置
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

//初始化顺序表
void SeqListInit(SeqList* ps)//传入链表地址便于修改
{
	ps->data = NULL;
	ps->capacity = 0;
	ps->size = 0;
	return;
}

//摧毁释放顺序表
void SeqListDestory(SeqList* ps)
{
	free(ps->data);
//记得置空地址
	ps = NULL;
	return;
}

//展示顺序表
void SeqListPrint(SeqList* ps)
{
//暴力断言（ps不为空）
	assert(ps->data);
//使用指针打印结构体内保存的数据
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d\t", ps->data[i]);
	}
	return;
}

//顺序表容量判断
void SeqListCheak(SeqList* ps)
{
	int newcapacity;
//使用完毕时进行判断
	if (ps->size == ps->capacity)
	{
//如果为容量为0,则开辟默认大小的空间；否则扩容为原来的两倍空间
		newcapacity = ps->capacity == 0 ? DEFAULT_SZ : ps->capacity* 2;
//当data为NULL时，realloc的功能和malloc一致（申请开辟空间）
		ps->data = realloc(ps->data, newcapacity);
//判断是否扩容（开辟）空间成功
		if (ps == NULL)
		{
//为开辟（扩容）成功，则打印对应的错误原因，并结束进程
			perror("realloc:");
			exit(1);
		}
	}
//成功则更新记录容量的大小
	ps->capacity = newcapacity;
	return;
}

//顺序表数据尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
//容量检查
	SeqListCheak(ps);
	ps->data[ps->size]=x;
//更新使用数量
	ps->size++;
	printf("顺序表尾插数据成功！\n");
	return;
}

//顺序表头插数据
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	//插入数据考虑扩容
	SeqListCheak(ps);
	for (int i = ps->size - 1; i >= 0; i--)
	{
		//头插从后开始移动数据（避免数据覆盖）
		ps->data[i + 1] = ps->data[i];
	}
	ps->data[0]=x;
	//尾插后更新记录使用数量
	ps->size++;
	printf("顺序表头插数据成功！\n");
	return;
}

//顺序表数据前删
void SeqListPopFront(SeqList* ps)
{
	//暴力断言（也可以选择if判断语句）
	assert(ps->data||ps->size);
	//从前往后移动数据（避免覆盖）
	for (int i = 0; i+1<ps->size; i++)
	{
		ps->data[i] = ps->data[i+1];
	}
	//更新记录使用的数量
	ps->size--;
	printf("顺序表前删数据成功！\n");
	return;
}

//顺序表尾删数据
void SeqListPopBack(SeqList* ps)
{
	assert(ps->data||ps->size);
	ps->size--;
	printf("顺序表尾删数据成功！\n");
	return;
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
//没有数据或者顺序表为空无法查找
	assert(ps->data||ps->size);
//遍历查找，找到则返回下标，否则返回-1
	int pos=-1;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
            pos=i;
			printf("数据查到了，下标是：%d\n", pos);
			return pos;
		}
	}
	printf("链表数据未查到！\n");
	return pos;
}

//顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	SeqListCheak(ps);
	for (int i = ps->size; i >= pos; i++)
	{
		ps->data[i] = ps->data[i - 1];
	}
	printf("请输入要插入的数：");
	scanf("%d", &ps->data[pos]);
	ps->size++;
	printf("链表插入数据成功！\n");
	return;
}

//顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps->data||ps->size);
	for (int i = pos; i+1 <ps->size; i++)
	{
		ps->data[i] = ps->data[i+1];
	}
	ps->size--;
	printf("顺序表删除数据成功！\n");
	return;
}