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

静态顺序表

使用定长数组存储元素

• 参考代码：

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

• 图示：

只适用于确定知道需要存多少数据的场景

局限：静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用

• 动态顺序表：

现实使用时多采用动态顺序表

优势：需要多少用多少

//默认开辟大小
#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;
}

顺序表展示

• 注意：

1. 当顺序表为空时不打印

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

顺序表容量检查

• 注意：

1. 每当要增加数据时，都需要考虑空间是否使用完毕
2. 如果使用完毕则需要考虑增容，增容为原来的两倍（避免频繁扩容）
3. 增容后更新记录容量大小

注：这里我们考虑到有许多地方要检查是否增容，为了方便将它封装成一个函数

• 参考代码:

//顺序表容量判断
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;
}

顺序表数据尾插

• 注意：

1. 插入数据考虑扩容
2. 尾插后更新记录使用数量

• 参考代码：

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

顺序表数据头插

• 注意：

1. 插入数据考虑扩容
2. 头插从后开始移动数据（避免数据覆盖）
3. 尾插后更新记录使用数量

//顺序表头插数据
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;
}

顺序表数据前删

• 注意：

1. 没有数据或者顺序表为空无法删除
2. 前删后从前往后移动数据（避免覆盖）
3. 更新记录使用的数量

• 参考代码：

//顺序表数据前删
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;
}

顺序表数据查找

• 注意：

1. 没有数据或者顺序表为空无法查找
2. 遍历查找，找到则返回下标，否则返回-1

• 参考代码：

// 顺序表查找
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;
}

顺序表指定位置插入数据

• 注意：

1. 检查是否扩容
2. 插入前先移动数据
3. 插入后更新记录使用数量的大小

• 参考代码：

//顺序表在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;
}

顺序表指定位置删除数据

• 注意：

1. 没有数据或者顺序表为空无法删除
2. 覆盖数据达到删除的效果
3. 删除后更新记录使用的数量大小

• 参考代码：

//顺序表删除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;
}

以上基本上就已经讲解顺序表完毕了，别忘了留个三连再走~~