小白也爱看的数据结构（顺序表）

好了，我们上篇文章已经了解到衡量一个算法的要素是他的时间复杂度和空间复杂度。我们常说，时间复杂度和空间复杂度只是学习数据结构的开胃小菜，那么我们今天学的顺序表就是另外一道凉菜。

本文的顺序表和链表两者异曲同工，读者在阅读学习的时候可以自己亲身体会一下两者各有什么差距，可能有读者会说，在后续c++的库里面都可以直接用，只要大致了解，但是，实际上，没有数据结构的了解，我们很难真正意义上将这个函数或者代码运用到极致。

话不多说，我们直接开始。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

看到这，你可以狭隘地理解为，差距就是体现在动态数组的创建上，从而引发的一些访问与输出的问题，当然根据我们所知的知识，肯定也会影响我们的时间复杂度和空间复杂度。

下面是标准版的顺序表的格式，这里的格式就会显得非常的呆板。所以我们一般都是用动态顺序表。

#define MAXSIZE 100  // 顺序表的最大容量

typedef struct {
    int data[MAXSIZE];  // 存储数据的数组
    int length;         // 当前表长（元素个数）
} SqList;               // SqList 是结构体类型名

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

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

这里包括上图有一个细节。

typedef int SLDataType;

这行代码定义了一个新的类型 SLDataType，它实际上就是 int 类型。这样做的好处是如果你以后需要改变数据类型，只需要修改这一行即可。

我们学习顺序表，主要是实现基本增删查改接口，熟练实现这四个功能就已经差不多了。

但是基本的插入又分为头插和尾插，删除也分为头删和尾删。基本就汇总为下面

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

本篇文章我们先讲一下初始化和检查。如果你在途中发现有哪里不懂了，一定要及时去弄懂，为什么是这样。代码量很大，请耐心食用。

首先，初始化函数SeqListInit需要为数组分配初始内存，并设置初始大小和容量。然后是CheckCapacity函数，用于在插入元素时检查是否需要扩容，

通常扩容策略是加倍当前容量，这样可以减少频繁扩容的开销。

初始化

// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity) {
    assert(psl);
    psl->array = (SLDataType*)malloc(sizeof(SLDataType) * capacity);
    if (psl->array == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    psl->size = 0;
    psl->capacity = capacity;
}

1.assert 是调试阶段的断言宏，如果 psl 为 NULL，程序会直接终止并报错。用来防止空指针导致的未定义行为

2.再是malloc 申请 capacity 个 SLDataType 类型的连续内存空间。

3.如果 malloc 返回 NULL，表示内存分配失败（如系统内存不足）。
perror 输出错误信息（如 malloc failed: Cannot allocate memory），更好理解，便于调试。
exit(EXIT_FAILURE) 用来终止程序，避免后续操作因空指针崩溃。

4.size = 0：表示当前顺序表中没有有效数据。
5.capacity = capacity：记录分配的初始容量，用于后续扩容判断。

检查

// 检查扩容
void CheckCapacity(SeqList* psl) {
    assert(psl);
    if (psl->size == psl->capacity) {
        size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(psl->array, 
                        sizeof(SLDataType) * newCapacity);
        if (tmp == NULL) {
            perror("realloc failed");
            exit(EXIT_FAILURE);
        }
        psl->array = tmp;
        psl->capacity = newCapacity;
    }
}

这里assert依旧检查是否为空，温柔点的检查是我们用的if（为空)那种，assert是一种非常粗暴强硬的检查，没有就是不行。

这里实现的就是检查空间满了没，满了就扩容，把原来的指针移到新的地址处，所以我们就重点讲一下第一个if分支。

if这里如果当前有效数据个数 psl->size 等于容量 psl->capacity，则需要进行扩容。

再是下一句判断如果当前容量 psl->capacity 为 0（即初始化时没有分配内存），则将新容量设置为 4。否则，将新容量设置为当前容量的两倍。

使用 realloc 动态调整 psl->array 的大小，新的大小为 sizeof(SLDataType) * newCapacity。
(SLDataType*) 将 realloc 返回的 void* 指针强制转换为 SLDataType* 类型。
realloc 会尝试在原有内存块的基础上调整大小，如果无法在原位置调整，则会分配一个新的内存块并将原有数据复制过去，同时释放原有内存块。

这样再进行检查，扩容检查就完成了。

好了，讲到这里前两个点都讲完了，下一篇文章我们就来讲解其他的点，如果你看到了这里，那你真的很棒。如果你觉得对你有帮助，可以点赞关注加收藏，感谢您的阅读，我们下一篇文章再见。

一步步来，总会学会的，首先要懂思路，才能有东西写。