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

4. 打印功能

遍历有效数据范围输出，方便调试。

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

5. 动态扩容

这是顺序表的核心机制。当 size == capacity 时，需要重新分配更大的内存块。

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        // 初始为 4，否则翻倍
        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;
    }
}

6. 插入操作

尾插

先检查空间，再放入数据，最后更新 size。

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

7. 删除操作

尾删

直接减少有效计数即可。

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

指定位置删除

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

8. 查找

线性遍历，找到返回下标，未找到返回 -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;
}

竞赛中的静态顺序表

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

静态申请数组

#include <iostream>
using namespace std;

const int N = 1e6 + 10; // 根据题目规模设定

int a[N]; // 模拟数组
int n;    // 当前元素个数

// 尾插
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 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;
    }
};

动态顺序表——vector

如果不需要手动管理内存，C++ STL 提供了 vector 容器。它的底层就是一个会自动扩容的顺序表，封装了所有常用接口。

创建方式

vector<int> a1;              // 空向量
vector<int> a2(N);           // 大小为 N，默认值 0
vector<int> a3(N, 2);        // 大小为 N，初始化为 2
vector<int> a4 = {1, 2, 3};  // 初始化列表

常用接口

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

迭代器与遍历

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

在实际开发中，除非是为了学习底层原理或特定场景优化，否则优先使用 vector，既安全又高效。