跳到主要内容
极客日志极客日志
首页博客AI提示词GitHub精选代理工具
|注册
博客列表

目录

  1. 数据结构：顺序表
  2. 线性表
  3. 顺序表
  4. 概念与结构
  5. 顺序表和数组区别
  6. 分类
  7. 静态顺序表
  8. 动态顺序表
  9. 动态顺序表模拟实现
  10. 定义动态顺序表结构
  11. 顺序表初始化
  12. 顺序表销毁
  13. 顺序表打印
  14. 顺序表动态扩容
  15. 尾插
  16. 头插
  17. 尾删
  18. 头删
  19. 查找
  20. 指定位置之前插入
  21. 删除 pos 位置的数据
  22. 竞赛中的静态顺序表
  23. 静态申请数组
  24. 封装静态顺序表
  25. 动态顺序表–vector
  26. 创建 vector
  27. size / empty
  28. begin / end
  29. pushback / popback
  30. front / back
  31. resize
  32. clear
  33. insert / erase
C++算法

数据结构：顺序表详解与实现

介绍数据结构中的顺序表，涵盖概念、与数组的区别及分类（静态与动态）。详细展示了动态顺序表的 C++ 模拟实现，包括初始化、销毁、扩容及增删查改操作。同时对比了竞赛中静态数组的应用方式，并介绍了 C++ STL 中 vector 容器的常用接口，如创建、大小查询、迭代器遍历及元素操作，帮助理解顺序表的底层原理与工程实践。

SparkGeek发布于 2026/3/28更新于 2026/4/164 浏览
数据结构：顺序表详解与实现

数据结构：顺序表

线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。 顺序表 逻辑结构：线性 物理结构（存储结构）：线性

顺序表和数组区别

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

数组 ⊆ 线性表

分类

静态顺序表

概念：使用定长数组存储元素

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费 但是在竞赛中经常用静态申请数组的方式，接下来也会说到

动态顺序表

动态顺序表按需申请，不会造成浪费

动态顺序表模拟实现

定义动态顺序表结构

头文件中

// 定义动态顺序表的结构
typedef int SLTDataType;
typedef struct SeqList {
    SLTDataType* arr; // 存储数据
    int size;         // 有效数据个数
    int capacity;     // 空间大小
} SL;
顺序表初始化
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");
}
顺序表动态扩容
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--;
}
查找
// 查找
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--;
}

竞赛中的静态顺序表

静态申请数组

  1. 单个顺序表
// 1·单个顺序表
#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. 多个顺序表

只需要在传入一个参数：对应的数组（传引用节省空间）

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

封装 通过调用 各种各样的接口 已经写好的 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::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
// 5. front / back
// front：返回首元素；
// back：返回尾元素；
// cout << a4.front() << " " << a4.back() << endl;
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;
}
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog

更多推荐文章

查看全部
  • Python 使用 ezdxf 读写 DXF 文件指南
  • IDEA 配置 Tomcat 服务器详细教程
  • PostgreSQL 18 本地安装与配置指南
  • 昇腾平台 Llama-2-7b 大模型深度测评与部署方案
  • Trae AI 编程提升工作效率技巧
  • 集成 Linly-Talker 实现智能客服数字人
  • VR 多相电源架构与选型设计详解
  • TinyWebServer 源码解析：HTTP 机制与高性能设计
  • Verilog 描述半加器结构：FPGA 初学实践
  • 从人类视频到机器人跳舞：BeyondMimic 全流程解析与 rl_sar 部署实践
  • BAAI/bge-m3 环境部署与 WebUI 运行教程
  • RISC-V 开源处理器实战：Verilog RTL 设计与 FPGA 验证
  • 免费 Trae 编辑器体验：i18n 任务排队千名及 AI 编程思考
  • Quartus Prime Lite 23.1 与 ModelSim 18.1 安装及联调仿真教程
  • Linux 下 libwebkit2gtk-4.1-0 安装与配置指南
  • Tauri 架构详解：从 WebView+Rust 到工具链与生态
  • Rust WebAssembly 开发实战：构建高性能前端应用
  • OpenClaw 清理 Skill 实战：基于 Rust+Tauri 构建安全沙箱
  • 融合手术导板与增强现实的椎弓根螺钉置入技术验证
  • RabbitMQ RPC 通信模式详解

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown转HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online

  • JSON 压缩

    通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online