数据结构详解：顺序表

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

打印

遍历有效数据部分进行输出。

void SLPrint(SL* ps) {
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

动态扩容

当 size 等于 capacity 时，需要扩容。通常策略是初始为 4，之后翻倍。

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        
        // 重新分配内存
        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;
}

头插需要将现有数据整体后移一位，效率较低（O(N)）。

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 SLPopBack(SL* ps) {
    assert(ps && ps->size);
    ps->size--;
}

头删需要将后续数据前移。

void SLPopFront(SL* ps) {
    assert(ps && ps->size);
    
    // 数据整体向前挪动一位
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

查找与插入

按值查找返回下标，未找到返回 -1。

int SLFind(SL* ps, SLTDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            return i;
        }
    }
    return -1;
}

指定位置插入需保证 pos 合法，并将该位置及之后的数据后移。

void SLInsert(SL* ps, int pos, SLTDataType x) {
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    
    SLCheckCapacity(ps);
    
    // pos 及之后数据向后挪动一位
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

删除指定位置数据逻辑类似，将后续数据前移。

void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    
    // pos 后面的数据向前挪动一位
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

竞赛中的静态顺序表

在算法竞赛中，为了追求极致性能，有时会直接使用静态数组模拟顺序表。

静态申请数组

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int a[N]; // 创建足够大的数组模拟顺序表
int n;    // 标记当前元素个数

// 打印
void print() {
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    cout << endl << endl;
}

// 尾插
void push_back(int x) {
    a[++n] = x;
}

// 头插
void push_front(int x) {
    for (int i = n; i >= 1; i--) {
        a[i + 1] = a[i];
    }
    a[1] = x;
    n++;
}

// 任意位置插入
void insert(int p, int x) {
    for (int i = n; i >= p; i--) {
        a[i + 1] = a[i];
    }
    a[p] = x;
    n++;
}

// 尾删
void pop_back() {
    n--;
}

// 头删
void pop_front() {
    for (int i = 2; i <= n; i++) {
        a[i - 1] = a[i];
    }
    n--;
}

// 任意位置删除
void erase(int p) {
    for (int i = p + 1; i <= n; i++) {
        a[i - 1] = a[i];
    }
    n--;
}

// 按值查找
int find(int x) {
    for (int i = 1; i <= n; i++) {
        if (a[i] == x) return i;
    }
    return 0;
}

// 按位查找
int at(int p) {
    return a[p];
}

// 清空
void clear() {
    n = 0;
}

如果需要多个顺序表，只需传入数组引用即可复用逻辑。

封装静态顺序表

利用类或结构体封装，提高代码复用性。

class SqList {
    int a[N];
    int n;
public:
    SqList() { n = 0; }
    
    void push_back(int x) {
        a[++n] = x;
    }
    
    void pop_back() {
        n--;
    }
    
    void print() {
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    SqList s1, s2;
    for (int i = 1; i <= 5; i++) {
        s1.push_back(i);
        s2.push_back(i * 2);
    }
    s1.print();
    s2.print();
    return 0;
}

C++ STL 中的 vector

实际开发中，C++ 标准库提供了 vector 容器，它本质上就是一个自动扩容的动态顺序表。

创建方式

// 四种常用创建方式
vector<int> a1;              // 空数组
vector<int> a2(10);          // 大小为 10，默认值 0
vector<int> a3(10, 2);       // 大小为 10，初始化为 2
vector<int> a4 = {1, 2, 3};  // 初始化列表

// 支持模板，可存任何类型
vector<string> a5;
vector<vector<int>> a7;      // 二维数组

基本操作

• size / empty：获取元素个数或判断是否为空。
• begin / end：获取迭代器，支持范围 for 遍历。
• push_back / pop_back：尾部插入和删除。
• front / back：访问首尾元素。
• resize：调整大小，超出部分补默认值，不足则截断。
• clear：清空内容。
• insert / erase：支持迭代器位置的插入和删除。

void test_resize() {
    vector<int> a(5, 1);
    a.resize(10); // 扩大，多出的补 0
    a.resize(3);  // 缩小，截断多余元素
    a.resize(5, 2); // 扩大并指定新元素值
}

void test_iter() {
    vector<int> a(10, 1);
    // 范围 for 遍历
    for (auto x : a) {
        cout << x << " ";
    }
}

提示：vector 的底层实现已经非常成熟，日常开发建议优先使用，除非有特殊的内存控制需求。