数据结构实战：顺序表原理与 C/C++ 实现

顺序表初始化

初始化时，指针置空，计数归零。

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

顺序表销毁

释放内存后记得把指针置空，避免野指针或重复释放。

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

顺序表动态扩容

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

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 != NULL);
    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;
}

指定位置之前插入

注意断言检查位置合法性，然后从后往前移动数据腾出空间。

// 指定位置之前插入
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) {
    // 1. 先把 [1, n] 的元素统一向后移动一位
    for (int i = n; i >= 1; i--) {
        a[i + 1] = a[i];
    }
    // 2. 把 x 放在表头
    a[1] = x;
    n++; // 元素个数 +1
}

// 在任意位置插入
void insert(int p, int x) {
    // 1. 先把 [p, n] 的元素统一向后移动一位
    for (int i = n; i >= p; i--) {
        a[i + 1] = a[i];
    }
    a[p] = x;
    n++;
}

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

// 头删
void pop_front() {
    // 1. 先把 [2, n] 区间内的所有元素，统一左移一位
    for (int i = 2; i <= n; i++) {
        a[i - 1] = a[i];
    }
    n--;
}

// 任意位置删除
void erase(int p) {
    // 把 [p + 1, n] 的元素，统一左移一位
    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;
}

多个顺序表

只需要传入对应的数组引用即可节省空间。

// 1. 需要多个顺序表，才能解决问题
int a1[N], n1;
int a2[N], n2;
int a3[N], n3;

// 修改上面的代码 例如
// 尾插
void push_back(int a[], int& n, int x) {
    a[++n] = x;
}

// 测试尾插
void test() {
    push_back(a1, n1, 1);
    push_back(a3, n3, 2);
}

封装静态顺序表

使用类或者结构体封装，调用更清晰。

// 使用类或者结构体封装一个静态顺序表
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

// 1. 创建 vector 常用的四种方式
vector<int> a1;                 // 创建了一个名字为 a1 的空的可变长数组，里面都是 int 类型的数据
vector<int> a2(N);              // 创建了一个大小为 10 的可变长数组，里面的值默认都是 0
vector<int> a3(N, 2);           // 创建了一个大小为 10 的可变长数组，里面的值都初始化为 2
vector<int> a4 = {1, 2, 3, 4, 5}; // 初始化列表的创建方式

// <> 里面可以存放任意的数据类型，这就体现了模板的作用，也体现了模板的强大之处
// 这样，vector 里面就可以存放我们见过的所有的数据类型，甚至是 STL 本身
vector<string> a5;      // 存字符串
vector<node> a6;        // 存结构体
vector<vector<int>> a7; // 创建了一个二维的可变长数组

// vector<array<int, 5>> a8; // 二维数组 代替 c 风格数组 需要包含头文件 array
int a10[N];               // 创建了一个大小为 N 的 int 类型数组 数组名叫 a10
vector<int> a9[N];        // 创建了一个大小为 N 的 vector 数组 数组名叫 a9

size / empty

// 2. size / empty
// size 返回实际元素的个数
print(a2);
print(a3);
print(a4);

// empty 返回顺序表是否为空，返回类型是一个 bool 类型的返回值。
// 如果为空返回 true，不空返回 false
if (a2.empty()) cout << "空" << endl;
else cout << "不空" << endl;

if (a1.empty()) cout << "空" << endl;
else cout << "不空" << endl;

begin / end

begin 返回起始位置的迭代器（左闭），end 返回终点位置的下一个位置的迭代器（右开）。利用迭代器可以访问整个 vector，存在迭代器的容器就可以使用范围 for 遍历。迭代器类型 vector<int>::iterator，一般使用 auto 简化。

void test_it() {
    vector<int> a(10, 1);
    // 迭代器的类型是 vector<int>::iterator，但是一般使用 auto 简化
    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

// 4. 尾插以及尾删
for (int i = 0; i < 5; i++) {
    a1.push_back(i);
    print(a1);
}
while (!a1.empty()) {
    a1.pop_back();
    print(a1);
}

front / back

front：返回首元素；back：返回尾元素。

// 5. 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;
}

// 6. resize
void test_resize() {
    vector<int> a(5, 1);
    a.resize(10); // 扩大
    print(a);
    a.resize(3);  // 缩小
    print(a);
    // 扩大成 5，并且多余的修改为 2
    a.resize(5, 2);
    print(a);
}

clear

清空 vector。底层实现的时候，会遍历整个元素，一个一个删除，因此时间复杂度 O(N)。

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

insert / erase

参数为迭代器。

// 8. insert/erase 参数为迭代器
a4.insert(a4.begin() + 2, 0);
print(a4);
a4.erase(a4.begin() + 2);
print(a4);
return 0;
}```