C算法
C 语言数据结构：顺序表详解与实现
C 语言中的数据结构顺序表。首先解释了数据结构的定义，区分了线性表、顺序表的概念。重点讲解了静态顺序表与动态顺序表的区别，指出动态顺序表通过动态增容解决空间浪费或不足的问题。随后详细实现了动态顺序表的核心功能，包括初始化、销毁、打印、增容、尾插、头插、尾删、头删、随机插入、随机删除、查找和修改操作。提供了完整的 Seqlist.h、Seqlist.c 和 Test.c 代码示例，帮助读者理解顺序表的底层逻辑与内存管理。
C 语言中的数据结构顺序表。首先解释了数据结构的定义，区分了线性表、顺序表的概念。重点讲解了静态顺序表与动态顺序表的区别，指出动态顺序表通过动态增容解决空间浪费或不足的问题。随后详细实现了动态顺序表的核心功能，包括初始化、销毁、打印、增容、尾插、头插、尾删、头删、随机插入、随机删除、查找和修改操作。提供了完整的 Seqlist.h、Seqlist.c 和 Test.c 代码示例，帮助读者理解顺序表的底层逻辑与内存管理。
数据： 数据在生活中随处可见，包括数值（如 1、2、3）、用户信息（姓名/性别/年龄）、网页内容（文字/图片/视频）等所有计算机处理的信息
结构： 通过羊圈管理羊群的比喻说明，无序数据也就是在草原散养羊群，难以管理；而有序结构也就是有编号的羊圈便于查找和操作
所以，数据结构=数据 + 结构，是计算机存储和组织数据的方式，反映数据内部构成和相互关系
线性表（linearlist）是 n 个具有相同特性的数据元素的有限序列，是一种在实际中广泛使 用的数据结构
常⻅的线性表有：顺序表、链表、栈、队列、字符串... 等线性表在逻辑上是线性结构，也就说是连续的一条直线。 但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表本质上是在数组基础上进行维护和封装的数据结构，其底层存储仍然使用数组,在数组的基础上增加了增删查改等方法
顺序表就是线性表的一种，而前面我们说过顺序表的底层存储仍然使用数组，数组在物理结构是连续的 所以，顺序表的物理结构和逻辑结构都是连续的
顺序表可以分为两类，一是静态顺序表，二是动态顺序表
所谓静态，意思是内存是静态的，初始时内存多大就是多大，后续不会再 发生改变
代码演示：（内有注释）
// 静态顺序表
struct Seqlist {
int arr[1000]; // 一个定长数组
int size; // 表示该顺序表当前有效的数据个数
};
在代码中我们可以看到，这就是一个静态顺序表
有一个 arr 定长数组，申请了 1000 个 int 类型，也就是 4000 个字节大小内存
还有一个 size 表示该顺序表当前有效的数据个数
问题： 但是，静态顺序表有一个问题
如果数组空间大小给小了，那么空间将不够用 如果数组空间大小给大了，那么空间将会浪费
而基于这一个问题，就产生了动态顺序表 动态顺序表就可以很好的解决这一个问题
所谓动态，意思是内存是动态的，内存空间大小可以根据需要来进行增大减小
与静态顺序表的区别：
动态顺序表与静态顺序表最大的优势就在于动态顺序表可以进行动态增容，当空间不够用时，会适当的增加一些空间 因此，动态顺序表既不会出现空间不够用的问题，又没有空间浪费的烦恼 所以，在选择顺序表时，优选动态顺序表
代码演示：（内有注释）
// 动态顺序表
struct Seqlist {
int* arr; // 一个数组指针
int size; // 表示该顺序表当前有效的数据个数
int capacity; // 表示当前顺序表的空间大小
};
在代码中我们可以看到，这就是一个动态顺序表
有一个 arr 数组指针
有一个 size 表示该顺序表当前有效的数据个数
还有一个 capacity 表示当前顺序表的空间大小
现在我们知道动态顺序表是优选，但我们该如何来实现一个动态顺序表呢？
之前我们说过，顺序表本质上是在数组基础上在数组的基础上增加了增删查改等方法 现在我们就一一来实现（增加）、（删除）、（查找）、（修改）等操作
本文以创建一个 int 类型的动态顺序表为例
之前在讲解扫雷游戏中我就提到: 在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
如图:
创建了一个 'Seqlist.h' 头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 'Seqlist.c' 源文件
用于用来放函数的定义 (顺序表的主体)
还有一个 'Test.c' 源文件
用于测试顺序表的运行效果
首先我们要定义一个动态顺序表
代码演示：（内有注释）
（在头文件 'Seqlist.h' 中写）
// 重定义，方便修改类型
typedef int SLDataType;
// 定义动态顺序表
typedef struct Seqlist {
SLDataType* arr;
int size;
int capacity;
} SL;
**在定义动态顺序表代码中，有两个需要注意的点：**本文是以
int类型为例，但如果以后要将顺序表修改成char类型或是其他类型一个一个修改就很麻烦 所以我们重定义int类型为SLDataType,并将接下来代码中的int类型全部写成SLDataType这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可****在定义动态顺序表的同时重定义顺序表名为SL方便以后使用
定义完顺序表后，肯定要对顺序表进行初始化，全部置
0 / NULL
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 顺序表的初始化
void SLInit(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 顺序表的初始化
void SLInit(SL* ps) {
assert(ps); // 断言空指针
ps->arr = NULL;
ps->capacity = ps->size = 0; // 全部初始化置 0 / NULL
}
在写动态顺序表代码中，有一个很重要的点： 当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的 故为了我们的代码更加健壮，可以加入
assert 断言来判断是否符合条件，在之后的代码中也都有
在我们的程序运行完毕后，当然要对顺序表进行销毁，以免占用内存
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 顺序表的销毁
void SLDestroy(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 顺序表的销毁
void SLDestroy(SL* ps) {
if (ps->arr != NULL) // 当其不为空时再释放，避免释放空指针
{
assert(ps); // 断言空指针
free(ps->arr); // 释放内存
ps->arr = NULL; // 置 NULL
}
ps->size = ps->capacity = 0; // 置 0
}
顺序表肯定少不了打印啦，直接遍历顺序表进行打印
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 顺序表的打印
void SLshow(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 顺序表的打印
void SLshow(SL* ps) {
assert(ps); // 断言空指针
for (int i = 0; i < ps->size; i++) {
printf("%d ", ps->arr[i]);
}
printf("\n\n");
}
动态顺序表的空间是动态管理的，故当顺序表的空间不足时，可再开辟一些空间使用（动态增容） 但是存在一个问题： 我们到底要开辟多大的空间来使用呢？
1. 若一次性开辟的空间过大，可能会造成空间的浪费 2. 若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适 当原空间为 100 的空间不足时，就增容到 200 空间 （本文选择的是每次增容 2 倍 ）
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 顺序表开辟空间
void SLCheckCapacity(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 顺序表开辟空间
void SLCheckCapacity(SL* ps) {
assert(ps); // 断言空指针
if (ps->size == ps->capacity) // 当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
{
// 先设置新变量，增容后再赋值
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 设置一个三目操作符判断原空间是否为 0
// 当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType)); // 由于是在原空间的基础上给空间增容，故我们这里使用 realloc 函数 增容
// 增容大小为上面的 newcapacity *（类型大小）
if (tmp == NULL) // 加一个 if 语句 防止增容失败
{
perror("realloc fail");
exit(1);
}
// 没有问题后就赋值
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
在做完之前的准备工作后，现在我们可以开始进行操作了 依次写出增删查改等操作
这个很简单，直接用下标进行插入数据
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 x 是要插入的数据，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表尾部插入数据
void SLPushBack(SL* ps, SLDataType x);
在 'Seqlist.c' 源文件中写到：
// 在顺序表尾部插入数据
void SLPushBack(SL* ps, SLDataType x) {
assert(ps); // 断言空指针
SLCheckCapacity(ps); // 用之前写的代码来判断空间是否足够，不够就开辟空间
ps->arr[ps->size++] = x; // 给尾部赋值
}
头插就比尾插想的事情多了 因为当头插时，后面元素的下标都会发生改变，故所有元素都要向后挪动一位给头插腾出空间
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 x 是要插入的数据，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表头部插入数据
void SLPushFront(SL* ps, SLDataType x);
在 'Seqlist.c' 源文件中写到：
// 在顺序表头部插入数据
void SLPushFront(SL* ps, SLDataType x) {
assert(ps); // 断言空指针
SLCheckCapacity(ps); // 用之前写的代码来判断空间是否足够，不够就开辟空间
for (int i = ps->size; i > 0; i--) // 将所有元素向后挪动一位给头插腾出空间
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x; // 赋值
ps->size++; // 元素个数 +1
}
这个很简单，直接用下标进行删除数据
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表尾部删除数据
void SLPopBack(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 在顺序表尾部删除数据
void SLPopBack(SL* ps) {
assert(ps); // 断言空指针
assert(ps->arr != NULL); // 断言顺序表不能为空
ps->size--; // 将元素个数进行 -1 就行
// 这样也不会影响到后面的 增、删、查、改
}
头删就比尾删想的事情多了 因为当头删时，后面元素的下标都会发生改变，故所有元素都要向前挪动一位补齐头删留下的空间，恰恰与头插相反
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表头部删除数据
void SLPopFront(SL* ps);
在 'Seqlist.c' 源文件中写到：
// 在顺序表头部删除数据
void SLPopFront(SL* ps) {
assert(ps); // 断言空指针
assert(ps->arr != NULL); // 断言顺序表不能为空
for (int i = 0; i < ps->size - 1; i++) // 所有元素都要向前挪动一位补齐头删留下的空间
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--; // 将元素个数进行 -1 就行
// 这样不会影响到后面的 增、删、查、改
}
有了头插和尾插，那就还有随机插入了 当随机插入时，与头插同理 , 插入后后面元素的下标都会发生改变，故
pos后面的元素从最后一个元素开始，都要向后挪动一位给要插入的元素腾出空间
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 pos 表示元素下标，下同） （其中 x 是要插入的数据，下同）
在 'Seqlist.h' 头文件中写到：
// 在指定位置（pos）之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
在 'Seqlist.c' 源文件中写到：
// 在指定位置（pos）之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
assert(ps); // 断言空指针
assert(pos >= 0 && pos <= ps->size); // 断言 pos 是否超出顺序表范围
SLCheckCapacity(ps); // 用之前写的代码来判断空间是否足够，不够就开辟空间
for (int i = ps->size; i > pos; i--) // 将 pos 后面的元素从最后一个元素开始
// 向后挪动一位给要插入的元素腾出空间
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x; // 赋值
ps->size++; // 元素个数 +1
}
有了头删和尾删，那就还有随机删除了 当随机删除时，与头删同理 , 删除后后面元素的下标都会发生改变，故
pos后面的元素从第一个元素开始，都要向前挪动一位来补齐删除元素后留下的空间
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 pos 表示要删除数据的下标，下同）
在 'Seqlist.h' 头文件中写到：
// 在指定位置（pos）删除数据
void SLErase(SL* ps, int pos);
在 'Seqlist.c' 源文件中写到：
// 在指定位置（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++) // 将 pos 后面的元素从第一个元素开始
// 向前挪动一位来补齐删除元素后留下的空间
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--; // 将元素个数进行 -1 就行
// 这样不会影响到后面的 增、删、查、改
}
我们还可以实现查找数据 只需通过遍历顺序表就可以判断是否有该数据 并设置返回值：
1. 若找到了就返回下标 2. 若没找到就返回一个负数
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 x 是要查找的数据，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表中查找数据
int SLFind(SL* ps, SLDataType x);
在 'Seqlist.c' 源文件中写到：
// 在顺序表中查找数据
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; // 没找到就返回一个负数
}
修改数据就很简单了 只需要通过下标进行修改
代码演示：（内有注释） （其中 ps 是一个顺序表类型的指针，下同） （其中 pos 是要修改的数据的下标，下同） （其中 x 是修改之后的数据，下同）
在 'Seqlist.h' 头文件中写到：
// 在顺序表中修改数据
void SLAlter(SL* ps, int pos, SLDataType x);
在 'Seqlist.c' 源文件中写到：
// 在顺序表中修改数据
void SLAlter(SL* ps, int pos, SLDataType x) {
assert(ps); // 断言空指针
assert(pos >= 0 && pos <= ps->size); // 断言 pos 是否超出顺序表范围
ps->arr[pos] = x; // 进行修改
}
在 'Seqlist.h' 头文件中写到：
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
// 重定义，方便修改类型
typedef int SLDataType;
// 定义动态顺序表
typedef struct Seqlist {
SLDataType* arr;
int size;
int capacity;
} SL;
// 顺序表的初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SLDestroy(SL* ps);
// 顺序表开辟空间
void SLCheckCapacity(SL* ps);
// 顺序表的打印
void SLshow(SL* ps);
// 在顺序表尾部插入数据
void SLPushBack(SL* ps, SLDataType x);
// 在顺序表头部插入数据
void SLPushFront(SL* ps, SLDataType x);
// 在顺序表尾部删除数据
void SLPopBack(SL* ps);
// 在顺序表头部删除数据
void SLPopFront;
;
;
;
;
在 'Seqlist.c' 源文件中写到：
#include "Seqlist.h"
// 顺序表的初始化
void SLInit(SL* ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->size = 0; // 全部初始化置 0 / NULL
}
// 顺序表的销毁
void SLDestroy(SL* ps) {
assert(ps);
if (ps->arr != NULL) // 当其不为空时再释放，避免释放空指针
{
free(ps->arr); // 释放内存
ps->arr = NULL; // 置 NULL
}
ps->size = ps->capacity = 0; // 置 0
}
// 顺序表的打印
void SLshow(SL* ps) {
assert(ps); // 断言
for (int i = 0; i < ps->size; i++) {
printf("%d ", ps->arr[i]);
}
printf("\n\n");
}
// 顺序表开辟空间
void SLCheckCapacity(SL* ps) {
assert(ps); // 断言
if (ps->size == ps->capacity) // 当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
{
// 先设置新变量，增容后再赋值
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 设置一个三目操作符判断原空间是否为 0
// 当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
SLDataType* tmp = (SLDataType*)(ps->arr, newcapacity * (SLDataType));
(tmp == )
{
perror();
();
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
{
assert(ps);
SLCheckCapacity(ps);
( i = ps->size; i > ; i--)
{
ps->arr[i] = ps->arr[i - ];
}
ps->arr[] = x;
ps->size++;
}
{
assert(ps);
assert(ps->arr != );
ps->size--;
}
{
assert(ps);
assert(ps->arr != );
( i = ; i < ps->size - ; i++)
{
ps->arr[i] = ps->arr[i + ];
}
ps->size--;
}
{
assert(ps);
assert(pos >= && pos <= ps->size);
SLCheckCapacity(ps);
( i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - ];
}
ps->arr[pos] = x;
ps->size++;
}
{
assert(ps);
assert(pos >= && pos <= ps->size);
( i = pos; i < ps->size - ; i++)
{
ps->arr[i] = ps->arr[i + ];
}
ps->size--;
}
{
assert(ps);
( i = ; i < ps->size; i++)
{
(ps->arr[i] == x) {
i;
}
}
;
}
{
assert(ps);
assert(pos >= && pos <= ps->size);
ps->arr[pos] = x;
}
最后，就是 'Test.c' 源文件啦
该文件包含了主函数，大家可以在里面测试自己写的函数
下面是小编自己测试写的代码：
#include "Seqlist.h"
int main() {
SL S1;
SLInit(&S1);
SLPushBack(&S1, 0);
SLPushBack(&S1, 1);
SLPushBack(&S1, 2);
SLPushBack(&S1, 3);
SLPushBack(&S1, 4);
SLPushBack(&S1, 5);
SLPushBack(&S1, 6);
SLPushBack(&S1, 7);
SLPushBack(&S1, 8);
SLshow(&S1);
SLAlter(&S1, 8, 0);
SLshow(&S1);
SLDestroy(&S1);
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