1. 线性表
在讲顺序表之前，我们首先要介绍一个概念，线性表。
C算法
数据结构入门：详解顺序表的实现与操作
顺序表是线性表的顺序存储结构，采用数组连续存储数据元素。分为静态和动态两种，重点讲解动态顺序表的实现。内容包括初始化、销毁、打印、扩容、尾部及头部插入删除、指定位置插入删除、查找元素等操作。同时结合力扣算法题，演示双指针技巧在移除元素、删除有序数组重复项及合并有序数组中的应用。
顺序表是线性表的顺序存储结构，采用数组连续存储数据元素。分为静态和动态两种，重点讲解动态顺序表的实现。内容包括初始化、销毁、打印、扩容、尾部及头部插入删除、指定位置插入删除、查找元素等操作。同时结合力扣算法题，演示双指针技巧在移除元素、删除有序数组重复项及合并有序数组中的应用。
在讲顺序表之前，我们首先要介绍一个概念，线性表。
线性表（Linear List）是数据结构中最基础、最常用的一种结构，它的特点是数据元素之间按线性顺序排列，每个元素最多有一个前驱和一个后继。
线性表有两种实现方式，其一是顺序表，其二是链表。以下我们来为他们做一个简单区分：
| 顺序表（顺序存储） | 链表（链式存储） | |
| 实现方式 | 用数组存储元素，内存连续分配 | 用结点存储元素和指针，内存非连续分配 |
| 特点 |
|
|
| 适用场景 | 元素数量固定、频繁查询、少增删。 | 频繁增删、元素数量变化大。 |
概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
顺序表和数组的区别？
顺序表是数据结构中线性表的一种实现方式，本质是基于数组的封装，通过数组实现元素的连续存储，并添加了对数据操作的逻辑（如插入、删除、扩容等）。
定义与特点
#define SLDataType int // 定义顺序表元素类型为 int（便于后期类型修改）
#define N 7 // 定义顺序表容量为 7（固定大小）
// 静态顺序表结构体定义
typedef struct Seqlist {
// 类型重命名为 SL
SLDataType arr[N]; // 固定大小的数组存储元素
int size; // 记录当前有效元素个数（核心状态标识）
} SL;
定义与特点
malloc 或 new）。// 定义顺序表存储的元素类型为 int
// 使用宏定义方便后续修改元素类型（例如改为 float 或自定义结构体）
#define SLDataType int
// 动态顺序表结构体定义
typedef struct Seqlist {
SLDataType* arr; // 指向动态分配数组的指针（存储元素）
int size; // 当前顺序表中有效元素的数量
int capacity; // 当前顺序表的总容量
} SL;
将静态顺序表和动态数据表做一个对比：
| 特性 | 静态顺序表 | 动态顺序表 |
| 存储方式 | 固定大小数组（栈内存/全局区） | 动态分配数组（堆内存） |
| 容量 | 编译时确定（#define N 7），不可变 | 运行时动态调整（通过malloc/realloc） |
| 内存分配 | 自动分配和释放（无需手动管理） | 需手动管理（malloc/free） |
| 扩容/缩容 | 不支持，大小固定 | 支持，可动态调整（如capacity不足时扩容） |
经过比对，我们发现 静态顺序表简单但僵化，适合确定性的小规模数据。动态顺序表复杂但强大，是现代编程语言中动态数组的基础实现。
本文将以实现动态顺序表为主，详细讲述动态顺序表的扩容，头插，尾插，删除等操作。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList {
SLDataType* arr;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL * ps, SLDataType x);
一个动态顺序表至少应该能够实现以上功能，下面我们来逐一实现。
void SLInit(SL* ps) {
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}
void SLDestroy(SL* ps) {
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}
注意：这里释放空间需要判断指针是否为空，如果是空指针直接释放会报错，同时我们要检查的是 ps->arr，并不是 ps，需要额外注意，不要释放 ps 的空间和将 ps 置空指针
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->capacity == ps->size) {
// 计算新容量：如果当前容量为 0（初始状态）则设为 4，否则扩容 2 倍
int new_capacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
// 尝试重新分配内存
SLDataType* tem = realloc(ps->arr, new_capacity * sizeof(SLDataType));
// 处理内存分配失败的情况
if (tem == NULL) {
perror("realloc"); // 打印错误信息
exit(EXIT_FAILURE); // 终止程序（EXIT_FAILURE 是标准错误退出码）
}
// 更新顺序表结构
ps->arr = tem; // 指向新分配的内存
ps->capacity = new_capacity; // 更新容量值
}
}
关键点说明：扩容时机：当
size == capacity时触发扩容，这是为了防止下一次插入操作导致溢出。扩容策略：初始容量设为 4（常见设计，避免初期频繁扩容）之后每次按 2 倍扩容（标准库常用策略，均摊时间复杂度为 O(1)）。内存管理：使用realloc而不是malloc，可以保留原有数据必须检查返回值是否为 NULL（内存分配可能失败）。错误处理：使用perror输出错误信息（会显示系统级的错误原因）。EXIT_FAILURE是标准库定义的错误退出码（通常值为 1）。安全性：先将 realloc 结果赋给临时变量tem，确认成功后再赋给ps->arr避免直接ps->arr = realloc(...)导致内存泄漏
/**
* @brief 在顺序表尾部插入一个元素
* @param ps 指向顺序表结构的指针（必须非空）
* @param x 要插入的元素值
*/
void SLPushBack(SL* ps, SLDataType x) {
assert(ps); // 确保顺序表指针有效（若 ps 为 NULL 则终止程序）
SLCheckCapacity(ps); // 检查并扩容（若容量不足）
ps->arr[ps->size++] = x; // 在尾部插入元素，并更新 size
}
/**
* @brief 删除顺序表尾部元素（逻辑删除）
* @param ps 指向顺序表结构的指针（必须非空且 arr 有效）
*/
void SLPopBack(SL* ps) {
assert(ps && ps->arr); // 确保顺序表指针和内部数组指针均有效
ps->size--; // 减少 size，忽略最后一个元素（逻辑删除）
}
/**
* @brief 在顺序表头部插入一个元素
* @param ps 指向顺序表结构的指针（必须非空且内部数组已初始化）
* @param x 要插入的元素值
* @note 时间复杂度 O(n)，需要移动所有元素
*/
void SLPushFront(SL* ps, SLDataType x) {
// 1. 参数校验
assert(ps && ps->arr); // 确保顺序表指针和内部数组指针有效
// 2. 容量检查（必要时扩容）
SLCheckCapacity(ps); // 检查并处理容量不足的情况
// 3. 移动元素：从后往前逐个后移
for (int i = ps->size; i > 0; i--) {
ps->arr[i] = ps->arr[i - 1]; // 将元素向后移动一位
}
// 4. 插入新元素到头部
ps->arr[0] = x; // 在数组头部放入新元素
// 5. 更新元素计数
ps->size++; // 顺序表长度 +1
}
/**
* @brief 删除顺序表头部元素
* @param ps 指向顺序表结构的指针（必须非空且顺序表不为空）
* @note 时间复杂度 O(n)，需要移动剩余所有元素
*/
void SLPopFront(SL* ps) {
// 1. 参数校验
assert(ps && ps->size > 0); // 确保顺序表有效且不为空
// 2. 移动元素：从前往后逐个前移
for (int i = 0; i < ps->size - 1; i++) {
ps->arr[i] = ps->arr[i + 1]; // 将元素向前移动一位
}
// 3. 更新元素计数
ps->size--; // 顺序表长度 -1
/* 可选：清零最后一个元素位置的值
ps->arr[ps->size] = 0; // 防止脏数据
*/
}
/**
* @brief 在顺序表指定位置前插入元素
* @param ps 指向顺序表结构的指针（必须非空）
* @param pos 要插入的位置索引（0 ≤ pos ≤ ps->size）
* @param x 要插入的元素值
* @note 时间复杂度 O(n)，需要移动元素
* @note 边界情况：
* - pos=0：相当于头部插入
* - pos=size：相当于尾部追加
*/
void SLInsert1(SL* ps, int pos, SLDataType 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; // 在 pos 位置插入新元素
ps->size++; // 更新元素数量
}
/**
* @brief 在顺序表指定位置后插入元素
* @param ps 指向顺序表结构的指针（必须非空）
* @param pos 参考位置索引（0 ≤ pos < ps->size）
* @param x 要插入的元素值
* @note 时间复杂度 O(n)，需要移动元素
* @note 边界情况：
* - pos=0：在第一个元素后插入
* - pos=size-1：相当于尾部追加
*/
void SLInsert2(SL* ps, int pos, SLDataType x) {
assert(ps); // 确保顺序表指针有效
assert(pos >= 0 && pos < ps->size); // 检查位置合法性
SLCheckCapacity(ps); // 检查并扩容
// 从后往前移动元素，腾出 pos+1 位置
for (int i = ps->size; i > pos + 1; i--) {
ps->arr[i] = ps->arr[i - 1]; // 元素后移
}
ps->arr[pos + 1] = x; // 在 pos+1 位置插入新元素
ps->size++; // 更新元素数量
}
/**
* @brief 删除顺序表指定位置的元素
* @param ps 指向顺序表结构的指针（必须非空且顺序表非空）
* @param pos 要删除的位置索引（0 ≤ pos < ps->size）
* @note 时间复杂度 O(n)，需要移动元素
* @note 边界情况：
* - pos=0：删除头部元素
* - pos=size-1：删除尾部元素
*/
void SLErase(SL* ps, SLDataType pos) {
assert(ps && ps->size > 0); // 确保顺序表有效且非空
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--; // 更新元素数量
/* 可选：清除残留数据（防止脏数据）
ps->arr[ps->size] = 0;
*/
}
/**
* @brief 在顺序表中查找指定元素的位置
* @param ps 指向顺序表结构的指针（必须非空）
* @param x 要查找的元素值
* @return 如果找到，返回元素的索引（0 ≤ index < size）；
* 如果未找到，返回 -1
* @note 时间复杂度 O(n)，需要遍历数组
*/
int SLFind(SL* ps, SLDataType x) {
assert(ps); // 确保顺序表指针有效
// 遍历顺序表查找元素
for (int i = 0; i < ps->size; i++) {
if (ps->arr[i] == x) {
return i; // 找到元素，返回索引
}
}
return -1; // 未找到元素
}
核心思想 使用 双指针技巧：
src（源指针）：遍历原始数组，检查每个元素。dst（目标指针）：记录非val元素的存储位置。 算法步骤 初始化src和dst为 0。 遍历数组：如果nums[src] == val：跳过该元素（src++）。 如果nums[src] != val：将其复制到nums[dst]，然后src++和dst++。 最终dst的值即为新数组的长度。
代码：
int removeElement(int* nums, int numsSize, int val) {
int src = 0, dst = 0;
while(src < numsSize) {
if(nums[src] == val) src++;
else {
nums[dst] = nums[src];
dst++;
src++;
}
}
return dst;
}
核心思想 使用 双指针技巧：
dst（目标指针）：记录唯一元素的存储位置。src（源指针）：遍历数组，寻找与dst不同的元素。 算法步骤 初始化dst = 0（第一个元素必定唯一），src = 1。 遍历数组：如果nums[dst] == nums[src]：跳过重复元素（src++）。 如果nums[dst] != nums[src]：将nums[src]复制到nums[++dst]，然后src++。 最终dst + 1即为新数组的长度（因为索引从 0 开始）。
代码：
int removeDuplicates(int* nums, int numsSize) {
int dst = 0, src = 1;
while(src < numsSize) {
if(nums[dst] == nums[src]) {
src++;
} else {
nums[++dst] = nums[src++];
}
}
return dst + 1;
}
核心思想 使用 逆向双指针法 从后向前合并，避免覆盖
nums1中的未处理元素。 算法步骤 初始化指针：l1 = m - 1：指向nums1的最后一个有效元素。l2 = n - 1：指向nums2的最后一个元素。l3 = m + n - 1：指向nums1的末尾（合并后的位置）。 逆向遍历合并：比较nums1[l1]和nums2[l2]，将较大的值放入nums1[l3]，并移动对应指针。重复直到nums1或nums2遍历完毕。 处理剩余元素：如果nums2有剩余元素（l2 >= 0），直接复制到nums1的前端。
代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;
while(l1 >= 0 && l2 >= 0) {
if(nums1[l1] > nums2[l2]) {
nums1[l3] = nums1[l1];
l3--;
l1--;
} else {
nums1[l3] = nums2[l2];
l2--;
l3--;
}
}
while(l2 >= 0) {
nums1[l3] = nums2[l2];
l2--;
l3--;
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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