上次我们数过了代码的脚步，知道了怎么给算法做小体检。接下来终于要正式搬进数据结构的花园啦——第一朵花，是顺序表。它本质上是个穿了小衣服的数组：底层数组没变，但我们为它配好了增删查改的一整套接口，让它用起来优雅多了。

线性表：一条线上排排坐

顺序表是线性表的一种。线性表是 n 个具有相同特性的数据元素的有限序列，常见的还有链表、栈、队列、字符串等等。它们在逻辑上都是一条连续的直线，但物理上存不存得连续就不一定了——顺序表很乖，物理和逻辑都连续，用的是一段数组的土地。

静态还是动态

// 静态顺序表：定长数组
struct SeqList
{
    int arr[100];  // 定长数组
    int size;      // 有效数据个数
};
// 缺陷：空间给少了不够用，给多了又浪费

// 动态顺序表：按需申请
typedef struct SeqList
{
    SLData* arr;   // 指向动态开辟的数组
    int size;      // 有效数据个数
    int capacity;  // 空间大小
}SeqList;

当然是动态的更讨人喜欢啦。还有个小心机：元素类型不写死，用 typedef 起个 SLData 的名字，想存 int、char 还是自定义的联系人结构体，改一行就行。

初始化与告别

void SLInit(SeqList* s)
{
    s->arr = NULL;
    s->size = s->capacity = 0;  // 干干净净地开始
}

void SLDestory(SeqList* ps)
{
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->size = ps->capacity = 0; // 用完也要收拾干净
}

为什么要传指针？因为要修改顺序表本身，就得把它的地址交出来——只传值的话，函数里改的是复印件。

增容的小心机

插入数据之前，先检查空间够不够，不够就增容。这一步尾插头插都要用，干脆单独拎出来：

void SLCheckCapacity(SeqList* ps)
{
    assert(ps);  // 空指针就大声报错
    if (ps->capacity == ps->size)   // 满啦
    {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        // 用临时变量接住，防止申请失败把原指针弄丢
        SLData* temp = (SLData*)realloc(ps->arr,
                            newCapacity * sizeof(SLData));
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(1);   // 申请失败就直接退出
        }
        ps->arr = temp;
        ps->capacity = newCapacity;
    }
}

两个小细节：增容一般成倍地扩，2 倍或 3 倍——扩太小会频繁增容拖慢速度，扩太大又浪费；realloc 的返回值先用临时指针接住，万一申请失败，原数据还安然无恙。有个有趣的冷知识：realloc 可能原地扩容（地址不变），也可能异地扩容（搬新家，旧空间自动释放），可以打印前后地址来验证哦。

尾插头插，尾删头删

void SLPushBack(SeqList* ps, SLData x)   // 尾插
{
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;   // 一行搞定
}

void SLPushFront(SeqList* ps, SLData x)  // 头插
{
    assert(ps);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > 0; i--)  // 全体向后挪一位
        ps->arr[i] = ps->arr[i - 1];
    ps->arr[0] = x;
    ps->size++;
}

void SLDelBack(SeqList* ps)              // 尾删
{
    assert(ps && ps->size);   // 顺便保证表不为空
    --ps->size;               // size 减一，最后一个自然作废
}

void SLDelFront(SeqList* ps)             // 头删
{
    assert(ps && ps->size);
    for (int i = 0; i < ps->size - 1; i++)  // 全体向前挪一位
        ps->arr[i] = ps->arr[i + 1];
    --ps->size;
}

想插哪就插哪

// 在 pos 位置之前插入
void SLInsertFront(SeqList* ps, int pos, SLData x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);  // pos 合法才能动工
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)
        ps->arr[i] = ps->arr[i - 1];
    ps->arr[pos] = x;
    ps->size++;
    // pos == size 时，其实就相当于尾插
}

// 删除 pos 位置的数据
void SLErase(SeqList* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++)
        ps->arr[i] = ps->arr[i + 1];
    ps->size--;
}

有了这两位，尾插尾删其实都是特例——SLInsertFront(ps, ps->size, x) 就是尾插。学会一个通用的，剩下的都通了。

顺手把查找也备好

int SeqListFind(SeqList* ps, SLData x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)   // 一个个比对
            return i;          // 找到就交出下标
    }
    return -1;                 // -1 表示没有找到
}

增删查改的「查」也到齐啦。指定位置插删加上查找，像通讯录这样的小项目，就已经可以顺理成章地在顺序表上盖起来了。

和数组的悄悄话

顺带一提缓存：CPU 读数据时会把它附近的数据一起加载进缓存。顺序表的内存是连续的，缓存命中率高高哒；这是它悄悄加分的隐藏优点。

愿当下的花如你所见般美丽