1. 顺序表基本概念
1.1 线性表定义
线性表是n个具有相同特性的数据元素的有序序列
逻辑上呈现为连续的线段结构
1.2 顺序存储结构
顺序表是线性表的顺序存储实现
元素存储在连续的内存空间中，类似于数组
2. 顺序表的实现方式
2.1 静态顺序表
const int N = 1e6 + 10; // 预定义最大容量 int a[N], n; // 静态数组 + 元素个数计数器优缺点：
✅ 优点：代码简单，无动态内存管理开销
❌ 缺点：空间固定，可能浪费或不足
2.2 动态顺序表（vector）
按需动态分配内存
C++ STL中的vector是典型的动态顺序表实现
3. 顺序表基本操作及时间复杂度
3.1 插入操作
操作类型 | 时间复杂度 | 代码示例 |
|---|---|---|
尾插 | O(1) |
|
头插 | O(n) | 所有元素右移一位 |
任意位置插入 | O(n) | 部分元素右移 |
3.2 删除操作
操作类型 | 时间复杂度 | 代码示例 |
|---|---|---|
尾删 | O(1) |
|
头删 | O(n) | 所有元素左移一位 |
任意位置删除 | O(n) | 部分元素左移 |
3.3 查找操作
操作类型 | 时间复杂度 | 代码示例 |
|---|---|---|
按值查找 | O(n) | 遍历整个数组 |
按位查找 | O(1) |
|
3.4 修改操作
时间复杂度：O(1)
代码示例：
a[p] = x
4. Vector（STL动态顺序表）
4.1 创建vector
vector<int> a1; // 空vector vector<int> a2(N); // 大小为N，默认值0 vector<int> a3(N, 2); // 大小为N，初始值2 vector<int> a4 = {1,2,3,4,5}; // 初始化列表 vector<vector<int>> a5; // 二维vector4.2 常用接口及时间复杂度
基本信息
size(): 返回元素个数 - O(1)empty(): 判断是否为空 - O(1)
迭代器
begin(): 起始迭代器end(): 结束迭代器（最后一个元素的下一个位置）
元素访问
front(): 首元素 - O(1)back(): 尾元素 - O(1)operator[]: 随机访问 - O(1)
修改操作
push_back(x): 尾插 - 平均O(1)pop_back(): 尾删 - O(1)resize(new_size): 调整大小 - O(n)clear(): 清空 - O(n)
4.3 遍历方式
// 1. 下标遍历 for(int i = 0; i < a.size(); i++) cout << a[i] << " "; // 2. 迭代器遍历 for(auto it = a.begin(); it != a.end(); it++) cout << *it << " "; // 3. 范围for循环 for(auto x : a) cout << x << " ";5. Vector封装示例
struct SqList { static const int N = 1e6 + 10; int a[N], n; 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; } };6. 算法题应用
6.1 基础应用
询问学号：直接使用vector随机访问特性
寄包柜：使用vector数组模拟二维结构
6.2 双指针技巧
移动零：快慢指针划分数组
颜色分类：三指针划分三种颜色
合并有序数组：从后往前归并避免覆盖
7. 编程模式对比
ACM模式
#include<iostream> #include<vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; // 处理逻辑... return 0; }核心代码模式
class Solution { public: void function(vector<int>& nums) { // 只需实现核心逻辑 } };8. 关键总结
8.1 Vector优势
动态扩容，内存使用更合理
提供丰富的接口，使用方便
支持随机访问，效率高
8.2 使用注意事项
避免频繁的中间插入删除（O(n)操作）
大规模数据时注意扩容开销
多维vector注意内存使用
8.3 适用场景
需要频繁随机访问
数据量变化不大或主要在尾部操作
算法竞赛中空间充足的情况
vector作为C++中最常用的顺序容器，结合了数组的高效访问和动态扩容的灵活性，是解决各类算法问题的利器。
