数据结构：顺序表原理与实现

销毁

销毁时需要释放动态分配的内存，并重置状态，避免重复释放。

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

打印

用于调试和查看当前顺序表内容。

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

动态扩容

当有效数据个数等于容量时，需要扩容。通常采用倍增策略，初始为 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;
}

头插

头插需要将现有数据整体向后移动一位，腾出位置给新元素。

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++;
}

删除 pos 位置的数据

删除后，pos 后面的数据需向前覆盖。

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 change(int p, int x) {
    a[p] = x;
}

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

多个顺序表

如果需要管理多个顺序表，可以将数组作为引用参数传入。

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

// 测试
void test() {
    int a1[N], n1 = 0;
    int a2[N], n2 = 0;
    push_back(a1, n1, 1);
    push_back(a2, n2, 2);
}

封装静态顺序表

通过类或结构体封装，可以像调用 STL 接口一样使用。

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 一样方便。

动态顺序表 – vector

如果不需要自己实现，C++ 的 STL 提供了 vector 容器，底层就是自动扩容的顺序表。

创建 vector

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

// 模板特性：可存放任意类型
vector<string> a5;              // 存字符串
vector<node> a6;                // 存结构体
vector<vector<int>> a7;         // 二维可变长数组

// 数组与 Vector 混合
int a10[N];                     // C 风格数组
vector<int> a9[N];              // Vector 数组

size / empty

// size 返回实际元素个数
// empty 判断是否为空，返回 bool
if (a2.empty()) cout << "空" << endl;
else cout << "不空" << endl;

begin / end

迭代器指向起始位置（左闭），end 指向终点下一个位置（右开）。支持范围 for 遍历。

void test_it() {
    vector<int> a(10, 1);
    
    // 传统迭代器遍历
    for (auto it = a.begin(); it != a.end(); it++) {
        cout << *it << " ";
    }
    cout << endl << endl;
    
    // 范围 for 遍历
    for (auto x : a) {
        cout << x << " ";
    }
    cout << endl << endl;
}

push_back / pop_back

for (int i = 0; i < 5; i++) {
    a1.push_back(i);
    print(a1);
}
while (!a1.empty()) {
    a1.pop_back();
    print(a1);
}

front / back

获取首元素和尾元素。

void test_fb() {
    vector<int> a(5);
    for (int i = 0; i < 5; i++) {
        a[i] = i + 1;
    }
    cout << a.front() << " " << a.back() << endl;
}

resize

调整大小。大于原大小时补默认值（通常为 0），小于原大小时截断尾部元素。

void print(vector<int>& a) {
    for (auto x : a) {
        cout << x << " ";
    }
    cout << endl;
}

void test_resize() {
    vector<int> a(5, 1);
    a.resize(10);       // 扩大，补 0
    print(a);
    a.resize(3);        // 缩小
    print(a);
    a.resize(5, 2);     // 扩大成 5，多余部分填 2
    print(a);
}

clear

清空容器，时间复杂度 O(N)。

cout << a.size() << endl;
a.clear();
cout << a.size() << endl;

insert / erase

基于迭代器进行插入和删除操作。

// 在 begin+2 处插入 0
a4.insert(a4.begin() + 2, 0);
print(a4);

// 删除 begin+2 处的元素
a4.erase(a4.begin() + 2);
print(a4);

总结

顺序表的核心在于连续内存存储带来的随机访问优势，以及动态扩容时的内存管理策略。手动实现有助于深入理解底层机制，而在实际开发中，合理使用 STL 的 vector 能显著提升开发效率和安全性。