跳到主要内容数据结构实战:顺序表原理与 C/C++ 实现 | 极客日志C++算法
数据结构实战:顺序表原理与 C/C++ 实现
顺序表作为线性表的顺序存储结构,底层依赖连续内存空间。从概念出发,对比静态与动态顺序表差异,详细拆解动态顺序表的内存管理、扩容机制及增删改查操作实现。同时介绍竞赛中静态数组的应用技巧,并总结 C++ STL 中 vector 容器的常用接口,帮助读者构建扎实的数据结构基础。
BackendPro3 浏览 
线性表
线性表(linear list)是 n 个具有相同特性的数据元素的有限序列。
这是一种在实际中广泛使用的数据结构,常见的线性表包括顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构,也就是连续的一条直线。但在物理结构上并不一定是连续的,通常以数组和链式结构的形式存储。
顺序表
概念与结构
概念:顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。
顺序表和数组区别
顺序表的底层结构是数组,是对数组的封装,实现了常用的增删改查等接口。
数组 ⊆ 线性表
分类
静态顺序表
概念:使用定长数组存储元素

静态顺序表缺陷:空间给少了不够用,给多了造成空间浪费。
不过在竞赛中经常用静态申请数组的方式,接下来也会说到。
动态顺序表
动态顺序表按需申请,不会造成浪费。

动态顺序表模拟实现
这里我们手动模拟一个动态顺序表,重点理解内存管理和边界处理。
定义动态顺序表结构
头文件中定义类型和结构体:
typedef int SLTDataType;
typedef struct SeqList {
SLTDataType* arr;
int size;
capacity;
} SL;
int
顺序表初始化
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--;
}
查找
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);
for (int i = ps->size; i > pos; i--) {
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
删除 pos 位置的数据
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos < ps->size);
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;
}
多个顺序表
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
vector<int> a1;
vector<int> a2(N);
vector<int> a3(N, 2);
vector<int> a4 = {1, 2, 3, 4, 5};
vector<string> a5;
vector<node> a6;
vector<vector<int>> a7;
int a10[N];
vector<int> a9[N];
size / empty
print(a2);
print(a3);
print(a4);
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);
for (auto it = a.begin(); it != a.end(); it++) {
cout << *it << " ";
}
cout << endl << endl;
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);
print(a);
a.resize(3);
print(a);
a.resize(5, 2);
print(a);
}
clear
清空 vector。底层实现的时候,会遍历整个元素,一个一个删除,因此时间复杂度 O(N)。
cout << a.size() << endl;
a.clear();
cout << a.size() << endl;
insert / erase
a4.insert(a4.begin() + 2, 0);
print(a4);
a4.erase(a4.begin() + 2);
print(a4);
return 0;
}```
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,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