【数据结构】——顺序表
【数据结构】——顺序表
顺序表是数据结构中一种重要的线性表存储结构，它使用一段连续的内存空间来存储数据元素。本文将详细介绍顺序表的基本概念、分类及其基本操作实现，帮助读者深入理解这一数据结构的核心原理和应用场景。
一、顺序表的基本概念与结构（可借助数组进行理解）
在数据结构中，顺序表（Sequential List） 是一种线性表的存储结构，它使用一段连续的内存空间来存储数据元素。顺序表的特点是元素的逻辑顺序与物理存储顺序一致，即元素在内存中是按顺序依次存放的，相信看到这里大家会发现，顺序表的底层结构就是数组！！！顺序表通过指针对数组进行了封装，便于实现增删改查。
二、顺序表的分类
2.1静态顺序表
静态顺序表的内容就和我们常用的数组内容保持一致了，这里以c语言为例。静态顺序表中包含了定长数组，他的有效数字个数是确定的。
typedef struct seqlist
{
sltype arr[9]; //定长数组
int size; //有效数字的个数
}slq;
2.2动态顺序表（很重要）
2.2.1动态顺序表的结构
动态顺序表的结构更加灵活。传统顺序表的容量是固定的，而动态顺序表可以根据实际需求动态扩展或缩减容量。当元素数量超过当前容量时，动态顺序表会自动分配更大的内存空间，并将原有数据复制到新空间中，从而避免溢出问题。他的结构形式是这样的。
typedef struct sldate
{
sltype* arr; //指针指向空间
int size; //有效数字的个数
int capacity; //空间容量
}sl;
它包含了指向特定类型的指针，由size记录数组中有效数字的个数，就如同arr[i]中的i。capacity则记录了总的空间大小。例如，当有效个数为4时size相当于arr[4]，这样方便我们对下一个数据进行保存。当size＝capacity时则空间已满，需通过realloc函数对其进行调整。
2.2.2如何实现动态内存
if (a->size == a->capacity)
{
int newcapacity = a->capacity == 0 ? 4 : 2 * a->capacity;
sltype* b = NULL;
b = (sltype*)realloc(a->arr,sizeof(sltype) * newcapacity);
if (b == NULL)
{
perror("realloc");
return 1;
}
a->arr = b;
a->capacity = newcapacity;
}
当size和capacity相等的时候证明内存已满，通过realloc对指针指向的内存进行调整，为了防止内存调整失败，需先判断realloc所传递的指针是否为空。
2.2.3顺序表的基本功能接口
顺序表和数组类似，其接口实现也与数组类似，主要应用循环等基本知识。
2.2.3.1顺序表的初始化
//初始化
void inint(sl* a)
{
a->arr = NULL;
a->size = 0;
a->capacity = 0;
}
2.2.3.2顺序表的销毁
//销毁
void sldestroy(sl* a)
{
assert(a);
free(a->arr);
a->arr = NULL;
a->size = 0;
a->capacity = 0;
}
2.2.3.3顺序表的打印
//输出
void slprint(sl* a)
{
for (int i = 0; i < a->size; i++)
{
printf("%d ", a->arr[i]);
}
}
2.2.3.4尾端插入
//尾插
void pushback(sl* a, sltype x)
{
assert(a);
//扩容
if (a->size == a->capacity)
{
int newcapacity = a->capacity == 0 ? 4 : 2 * a->capacity;
sltype* b = NULL;
b = (sltype*)realloc(a->arr,sizeof(sltype) * newcapacity);
if (b == NULL)
{
perror("realloc");
return 1;
}
a->arr = b;
a->capacity = newcapacity;
}
a->arr[a->size++] = x;
}
2.2.3.5尾端删除
//尾删
void popback(sl* a)
{
assert(a && a->size);
a->size--;
}
2.2.3.6头端插入
//头插
void pushfront(sl* a, sltype x)
{
assert(a);
if (a->size == a->capacity)
{
int newcapacity = a->capacity == 0 ? 4 : 2 * a->capacity;
sltype* b = NULL;
b = (sltype*)realloc(a->arr, sizeof(sltype) * newcapacity);
if (b == NULL)
{
perror("realloc");
return 1;
}
a->arr = b;
a->capacity = newcapacity;
}
for (int i = a->size; i > 0; i--)
{
a->arr[i] = a->arr[i - 1];
}
a->arr[0] = x;
a->size++;
}
2.2.3.7头端删除
void popfront(sl* a)
{
assert(a);
for (int i = 0; i < a->size-1; i++)
{
a->arr[i] = a->arr[i + 1];
}
a->size--;
}
2.2.3.8任意插入
//任意插入
void insert(sl* a, sltype x, int b )
{
assert(a);
if (a->size == a->capacity)
{
int newcapacity = a->capacity == 0 ? 4 : 2 * a->capacity;
sltype* b = NULL;
b = (sltype*)realloc(a->arr, sizeof(sltype) * newcapacity);
if (b == NULL)
{
perror("realloc");
return 1;
}
a->arr = b;
a->capacity = newcapacity;
}
assert(b > 0 && b < a->capacity);
for (int i = a->size;i > b;i--)
{
a->arr[i] = a->arr[i - 1];
}
a->arr[b] = x;
a->size++;
}
2.2.3.9任意删除
//任意删除
void erase(sl* a, int b)
{
for (int i = b; i < a->size - 1; i++)
{
a->arr[i] = a->arr[i + 1];
}
a->size--;
}
三、顺序表中学习的问题和思考
问题：
1.顺序表的容量是固定的，如何解决容量不足的问题？
2.如何实现动态顺序表？
3.顺序表适用于哪些场景？
4.在实现顺序表时，如何处理边界情况？
思考：
1.使用动态顺序表，在容量不足时动态扩展内存空间。动态扩展通常采用倍增策略。
2.动态顺序表通常使用动态数组来管理内存。
3.适用于需要频繁随机访问元素的场景，例如数组、矩阵、栈、队列等。
4.插入和删除操作时，需要检查索引是否合法（如是否超出范围）。动态扩展时，需要检查内存分配是否成功。