数据结构：顺序表
C算法
数据结构：顺序表概念与实现
顺序表是线性表的顺序存储结构，采用物理地址连续的存储单元依次存储数据元素。分为静态顺序表和动态顺序表，前者空间固定易浪费，后者支持动态扩容。核心操作包括初始化、销毁、增删改查及扩容逻辑。C++ STL 提供 vector 容器作为动态顺序表的高效封装，简化开发流程。
顺序表是线性表的顺序存储结构，采用物理地址连续的存储单元依次存储数据元素。分为静态顺序表和动态顺序表，前者空间固定易浪费，后者支持动态扩容。核心操作包括初始化、销毁、增删改查及扩容逻辑。C++ STL 提供 vector 容器作为动态顺序表的高效封装，简化开发流程。
线性表（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 位置的数据
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 的底层就是一个会自动扩容的顺序表， 其中创建以及增删查改等等的逻辑已经实现好了，并且也完成了封装
// 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; // 创建了一个二维的可变长数组
int a10[N]; // 创建了一个大小为 N 的 int 类型数组 数组名叫 a10
vector<int> a9[N]; // 创建了一个大小为 N 的 vector 数组 数组名叫 a9
// 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 返回终点位置的下一个位置的迭代器（右开） 利用迭代器可以访问整个 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;
}
// 4. 尾插以及尾删
for (int i = 0; i < 5; i++) {
a1.push_back(i);
print(a1);
}
while (!a1.empty()) {
a1.pop_back();
print(a1);
}
// 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;
}
如果大于原始的大小，多出来的位置会补上默认值，一般是 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);
}
清空 vector
// 底层实现的时候，会遍历整个元素，一个一个删除，因此时间复杂度 O(N)
cout << a.size() << endl;
a.clear();
cout << a.size() << endl;
// 8. insert/erase 参数为迭代器
a4.insert(a4.begin() + 2, 0);
print(a4);
a4.erase(a4.begin() + 2);
print(a4);
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online