C语言数据结构入门：顺序表超详解（从底层原理到代码实现全覆盖）

二、顺序表的结构定义

为了让顺序表具备自动扩容的能力，我们通常采用动态顺序表。我们需要一个指针指向动态开辟的数组，一个变量记录当前存储的数据个数，以及一个变量记录当前的存储容量。

typedef int SLDataType;
typedef struct SeqList {
    SLDataType* a;    // 指向动态数组的指针
    int size;         // 有效数据个数
    int capacity;     // 容量空间大小
} SL;

三、核心操作实现

1. 初始化与销毁

初始化时，我们将指针置空，数量和容量归零。销毁时，切记要释放内存防止内存泄漏。

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

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

2. 检查扩容（关键点）

当 size == capacity 时，说明空间已满。我们使用 realloc 函数按原容量的2倍进行扩容，这是平衡空间浪费和性能开销的经典做法。

3. 插入数据（尾插与随机插入）

插入数据前必须检查空间。在指定位置插入时，需要将该位置之后的数据整体向后移动一位，腾出空间。

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

四、总结

顺序表的优势在于高密度的存储和快速的随机访问，但其缺点是中间插入或删除数据需要搬移大量元素，时间复杂度为O(N)。在实际开发中，我们需要根据业务场景灵活选择数据结构。

—— 掌握顺序表，是通往高级算法工程师的第一步！