初阶数据结构：顺序表

本文介绍线性结构中的顺序表，这种连续排序的方式在需要频繁访问特定位置元素的应用场景（如矩阵运算、数组查询）中非常高效。

1. 线性表

线性表是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就是说是一条连续的直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念及结构

顺序表是线性表的一种存储方式，它是用一组连续的存储单元依次存储线性表的数据元素。简单来说，就像是把线性表中的元素一个挨着一个地放在数组中进行增删查改工作，就像在一排连续的小格子里存放东西一样。

2.1.1 静态顺序表

typedef int SLDataType; // 静态开辟（不推荐）
#define N 7
typedef struct SeqList {
    SLDataType array[N]; // 指向动态开辟的数组
    int size;            // 数据个数
} SL;

静态顺序表就是创建一个普通的数组，通常数组的长度大小是固定的，所以这种存储方式是不灵活的。静态顺序表的定长数组导致 N 定大了空间开多了浪费，开少了不够用，只适用于确定知道需要存多少数据的场景。

2.1.2 动态顺序表

typedef int SLDataType;
#define INIT_CAPACITY 4
typedef struct SeqList {
    SLDataType* a;       // 指向动态开辟的数组
    int size;            // 数据个数
    int capacity;        // 空间容量
} SL;

动态顺序表是用的最多的顺序表，符合大多数场景下的使用，可以根据场景的需要调整数组的大小，比静态数组更加灵活。

2.2 接口实现

2.2.1 顺序表打印

void SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0; i < ps->size; ++i) {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

因为要访问 ps 指针，所以基本功能的实现都要用断言来预防非法访问，顺序表的打印和数组的打印基本思路一致，这里不过多赘述。

2.2.2 顺序表初始化

void SeqInit(SL* ps) {
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (ps->a == NULL) {
        perror("malloc fail");
        return;
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

对顺序表初始化，这里有个头文件中的宏定义 #define INIT_CAPACITY 4，目的是为了方便修改初始化时的大小，不然每次修改要改多处，定义之后就只需要修改一个地方即可。刚开始 capacity 也要给一定的容量，而不是 0。

2.2.3 顺序表销毁

void SLDestroy(SL* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

这里唯一要注意的点就是，释放完动态数组 a 之后要记得将指针置为空，不然会导致野指针的出现。

2.2.4 顺序表容量检查

void SLCheckCapacity(SL* ps) {
    assert(ps);
    if (ps->size == ps->capacity) {
        SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
    }
    ps->capacity *= 2;
}

size 表示的是当前顺序表存储了多少数据，capacity 表示的是当前顺序表能够存储多少数据，所以当数据存满了之后就需要进行扩容操作，通常我们每次扩容都只扩容两倍，以免空间的浪费。

值得注意的是：realloc 开辟的空间大小不是 ps->capacity * 2，而是 sizeof(SLDataType) * ps->capacity * 2，前者是只考虑了扩大数组元素个数，但是没考虑到每个元素的字节大小，这是需要重点注意的。

2.2.5 顺序表尾插

void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size++] = x;
}
// O(n)

尾插就是在顺序表最后面插入数据，先检查容量是否足够插入数据，然后 ps->a[ps->size++] = x 可以拆分为 ps->a[ps->size] = x 和 ps->size++ 理解，先将下一个数据加入顺序表，然后修改 size 大小。

尾插只需要把 n 个数据依次放到末尾，所以时间复杂度为 O(n)。

2.2.6 顺序表头插

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}
// O(n^2)

还是一样，先检查容量是否足够插入数据，然后用覆盖的方式，将前一个数据覆盖到后一个数据上，即整体数据向右移动，也可以使用 memmove 函数，最后记得修改 size 大小，然后在开头插入数据。

值得注意的是：头插每次插入 n 个数据之前都需要挪动数据，因此时间复杂度为 O(n²)，所以得出结论尾插的效率是高于头插的。

2.2.7 顺序表尾删

void SLPopBack(SL* ps) {
    assert(ps->size > 0);
    ps->a[ps->size - 1] = 0;
    ps->size--;
}

最后一个数据的索引为 size-1，所以将该位置的数据置为 0 即可，但又有人疑问了，需不需要把删除的空间回收了？答案是不需要也没必要，因为通常空间的回收都是整体回收而不是一部分，而且多出来的空间也有可能被使用。

值得注意的是：要考虑顺序表没有数据的情况，如果没有数据了还删除肯定是会造成访问错误的，所以要加断言 assert(ps->size > 0)，头删也是如此。

2.2.8 顺序表头删

void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size > 0);
    int begin = 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

先检查容量是否足够插入数据，然后用覆盖的方式，将后一个数据覆盖到前一个数据上，即整体数据向左移动，也可以使用 memmove 函数，最后记得修改 size 大小。

2.2.9 顺序表在 pos 位置插入 x

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos <= ps->size && pos >= 0);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

在 pos 位置之后将所有数据向左移，然后在 pos 位置插入数据，注意要断言 pos <= ps->size && pos >= 0，避免传入的 pos 地址是个无效地址。

2.2.10 顺序表在 pos 位置删除 x

void SLErase(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos <= ps->size && pos >= 0);
    int begin = pos + 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

定义变量 begin 从要删除元素的下一个位置开始，使用 while 循环将从 pos + 1 位置开始的元素依次向左移动一个位置，覆盖要删除的元素。

值得注意的是：最后一个元素不需要特殊处理。因为顺序表的元素个数是由 size 控制的，当 size 减 1 后，无论原来最后一个元素的值是什么，它都不在有效的元素列表中了，所以不需要对其进行特殊处理，如将其置为某个默认值或进行其他操作。

2.2.11 顺序表查找

int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->a[i] == x) {
            return i;
        }
    }
    return -1;
}

遍历数组，符合则返回索引值，不符合返回 -1。

3. 顺序表的优劣

1. 中间/头部的插入删除，时间复杂度为 O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间

4. 代码展示

4.1 SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;

// 静态开辟（不推荐）
//#define N 7
//typedef struct SeqList
//{
//    SLDataType array[N];
//    int size;
//} SL;

// 动态开辟
#define INIT_CAPACITY 4
typedef struct SeqList {
    SLDataType* a;
    int size;
    int capacity;
} SL;

void SeqInit(SL* s);
void SeqDestory(SL* s);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos, SLDataType x);
int SLFind(SL* ps, SLDataType x);

4.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

// 顺序表打印
void SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0; i < ps->size; ++i) {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

// 顺序表初始化
void SeqInit(SL* ps) {
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (ps->a == NULL) {
        perror("malloc fail");
        return;
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

// 顺序表销毁
void SLDestroy(SL* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

// 检查空间，如果满了，进行增容
void SLCheckCapacity(SL* ps) {
    assert(ps);
    if (ps->size == ps->capacity) {
        SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
    }
    ps->capacity *= 2;
}

// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size++] = x;
}

// 顺序表头插
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

// 顺序表头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size > 0);
    int begin = 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

// 顺序表尾删
void SLPopBack(SL* ps) {
    assert(ps->size > 0);
    ps->a[ps->size - 1] = 0;
    ps->size--;
}

// 顺序表在 pos 位置插入 x
void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos <= ps->size && pos >= 0);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

// 顺序表删除 pos 位置的值
void SLErase(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos <= ps->size && pos >= 0);
    int begin = pos + 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

// 顺序表查找
int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->a[i] == x) {
            return i;
        }
    }
    return -1;
}