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

鉴于静态顺序表的局限性，实际开发中重点讲解动态顺序表的实现。

动态顺序表核心实现

结构定义与成员解析

首先定义顺序表的结构体及类型别名。

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

typedef int type;

typedef struct Seqlist {
    type* arr;   // 存储数据的动态数组指针
    int size;    // 当前有效数据个数
    int capacity;// 当前总容量
} SL;

• arr：动态数组指针，管理内存空间。
• size：记录已使用的元素个数，范围 [0, capacity]。
• capacity：记录数组的总容量，当 size == capacity 时需扩容。

1. 初始化

初始化时不分配内存，将指针置空，计数归零。

void SLinit(SL* h) {
    h->arr = NULL;
    h->capacity = h->size = 0;
}

调用时需传址，确保修改实参生效。

2. 扩容机制 (Kuo)

插入操作前需检查容量，若已满则调用扩容函数。

void kuo(SL* h) {
    if (h->capacity == h->size) {
        int newcapacity = h->capacity == 0 ? 4 : 2 * h->capacity;
        type* tmp = (type*)realloc(h->arr, sizeof(type) * newcapacity);
        if (tmp) {
            h->arr = tmp;
            h->capacity = newcapacity;
        } else {
            exit(1); // 内存分配失败
        }
    }
}

设计要点：

• 触发条件：size == capacity。
• 扩容策略：初始为 4，后续翻倍。2 倍扩容能有效降低均摊成本，避免频繁 O(n) 操作导致整体复杂度退化。
• 安全性：使用临时指针 tmp 接收 realloc 返回值，防止分配失败后丢失原内存地址。

3. 尾插 (PushBack)

直接在末尾插入，若空间不足先扩容。

void SLpushback(SL* h, type x) {
    kuo(h);
    h->arr[h->size++] = x;
}

4. 头插 (PushFront)

头部插入需将现有元素整体后移一位，同样需考虑扩容。

void SLpushfront(SL* h, type x) {
    kuo(h);
    int i;
    for (i = h->size; i > 0; i--) {
        h->arr[i] = h->arr[i - 1];
    }
    h->arr[i] = x;
    h->size++;
}

注意：移动必须从后往前，避免覆盖未处理的数据。

5. 尾删 (PopBack)

尾部删除只需减少有效长度，无需释放内存或清零。

void popback(SL* h) {
    assert(h && h->size);
    h->size--;
}

使用 assert 确保指针非空且表不为空。

6. 头删 (PopFront)

头部删除需将后续元素整体前移一位覆盖头部。

void popfront(SL* h) {
    assert(h && h->size);
    int i;
    for (i = 0; i < h->size - 1; i++) {
        h->arr[i] = h->arr[i + 1];
    }
    h->size--;
}

时间复杂度分析

总结：

动态顺序表通过结构体封装数组，实现了灵活的内存管理。相比静态顺序表，它解决了空间固定带来的浪费或不足问题。核心操作的时间复杂度取决于是否涉及元素移动：尾端操作通常为 O(1)，而涉及头部移动的操作则为 O(n)。合理设计扩容策略（如 2 倍增长）可优化性能表现。