数据结构基础：顺序表详解与动态实现

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

// 初始化顺序表
void SLInit(SL* ps) {
    if (ps == NULL) return;
    ps->arr = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

// 打印顺序表
void SLPrint(SL* ps) {
    if (ps == NULL || ps->arr == NULL) {
        printf("Empty List\n");
        return;
    }
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

// 检查容量并增容
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++;
}

test.c（测试文件）

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void test_basic() {
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1, 1);
    SLPushBack(&s1, 2);
    SLPushBack(&s1, 3);
    SLPrint(&s1);
}

void test_head_insert() {
    SL s2;
    SLInit(&s2);
    SLPushFront(&s2, 1);
    SLPushFront(&s2, 2);
    SLPushFront(&s2, 3);
    SLPrint(&s2);
}

int main() {
    test_basic();
    test_head_insert();
    return 0;
}

调试建议： 编写代码时，养成断点调试的习惯。运行到函数内部时，观察变量 size 和 capacity 的变化，能帮助你更好地理解内存分配过程。

四、关键操作解析

1. 尾插与增容

当 size 等于 capacity 时，需要扩容。通常采用 2 倍扩容策略。虽然会有一定空间浪费，但能显著减少 realloc 调用次数，摊还时间复杂度更优。

2. 头插与移位

头插需要在头部腾出位置，因此需要将现有数据整体后移。这会导致 O(N) 的时间复杂度，但在顺序表中这是不可避免的代价。

五、总结

顺序表通过连续的物理空间实现了高效的随机访问，插入和删除操作则涉及数据移动。理解其底层机制（如增容策略、传址调用）对于掌握数据结构至关重要。在实际开发中，根据数据量是否变化选择静态或动态顺序表，能有效平衡性能与资源。