数据结构入门：动态顺序表的实现与应用

实现具体的逻辑。注意，初始化时需要将指针置为 NULL，避免野指针。

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

// 初始化
void SLInit(SL* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

// 检查容量并增容
static void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

// 尾插
void SLPushBack(SL* ps, SLTDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

// 头插
void SLPushFront(SL* ps, SLTDataType 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 SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

3. 测试文件 (test.c)

通过主函数调用各个接口来验证功能。调试时建议单步进入函数内部观察变量变化，这是排查问题的关键习惯。

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void test1() {
    SL s1;
    SLInit(&s1); // 传址调用，修改实参内容
    SLPrint(&s1);
}

void test2() {
    SL s2;
    SLInit(&s2);
    SLPushBack(&s2, 1);
    SLPushBack(&s2, 2);
    SLPushBack(&s2, 3);
    SLPrint(&s2);
}

void test3() {
    SL s3;
    SLInit(&s3);
    SLPushFront(&s3, 1);
    SLPushFront(&s3, 2);
    SLPushFront(&s3, 3);
    SLPrint(&s3);
}

int main() {
    test1();
    test2();
    test3();
    return 0;
}

核心机制解析

为什么使用传址调用？

在初始化或操作顺序表时，我们需要修改结构体内部的成员（如 arr 指针或 size）。如果采用传值调用，形参只是实参的拷贝，修改形参不会影响外部变量。因此必须传递结构体的地址（指针）。

增容策略

当空间不足时，我们使用 realloc 进行扩容。通常采用 2 倍增长策略。虽然这会导致一定的空间浪费，但从概率学角度看，随着数据量增加，频繁扩容带来的性能损耗远大于空间浪费的成本。成倍增长能有效降低增容次数，平衡时间与空间效率。

头插法的代价

头插法需要将所有已有元素向后移动一位，时间复杂度为 O(N)。相比之下，尾插法只需直接赋值，复杂度为 O(1)。在实际应用中，应根据业务场景选择合适的数据操作方式。

结语

顺序表通过连续的物理空间实现了高效的随机访问，但在头部插入或删除元素时开销较大。理解其底层实现和增容机制，有助于我们在后续学习链表、栈等结构时建立更扎实的基础。