跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客我的书AI学习GitHub 精选镜像AI 生图工具UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C算法

数据结构：顺序表详解

数据结构中的顺序表。首先阐述了线性表的逻辑与物理结构区别，引出顺序表的概念及其与数组的关系。内容涵盖静态与动态顺序表的分类，重点讲解了动态顺序表的初始化、销毁、增容机制以及头尾插删操作。随后提供了完整的 C 语言代码实现，包括头文件、源文件和测试文件，展示了顺序表的核心接口如 PushBack、PushFront、Erase、Find 等。最后分析了顺序表的优缺点，指出其插入删除时间复杂度为 O(N)，且增容过程存在空间浪费和性能消耗的问题。

花里胡哨发布于 2026/3/27更新于 2026/9/884 浏览
数据结构：顺序表详解

数据结构：顺序表详解

图片

图片

1. 线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

物理结构上不一定连续，逻辑结构上连续是什么意思呢？我们拿顺序表和链表举例就可以明白

图片

2. 顺序表

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

图片

这看起来不就是数组么？那么顺序表和数组又有什么区别呢？ 实质上：顺序表的底层就是数组，而顺序表对数组进行了封装，可以完成增删查改等操作…… 形象来说数组是苍蝇馆子，而顺序表则是米其林餐厅，同一种原料，但装饰是不同的。

图片

2.1 分类

2.1.1 静态顺序表

图片

使用静态顺序表有个缺陷：

  1. 当数组空间给大时，容易造成浪费(如果开辟了 10000 个空间大小，里面只存了几个数据)；
  2. 或者数组空间给小时又不够用。那么如何解决这个问题呢？ 于是我们提出了使用动态顺序表
2.1.2 动态顺序表

如果我们使用动态顺序表，那么就需要定义一个空间容量，当空间不够时可以动态增容。 重命名 int 为 SLDataType，这样做的好处是如果我们存储的是字符形的顺序表，则只需要在重命名中将 int 形改成 char 形即可，而不需要在每一处涉及整形数组中的地方修改，方便了许多。

图片

图片

2.2 初始化、销毁

初始化时此顺序表并没有插入任何数据，因此需要将 size 和 capacity 都置为 0。

图片

知道了顺序表的初始化，那么相对应的销毁也可以实现。

图片

2.3 头插、尾插

尾插

当要像顺序表的尾部插入数据时，将数据插入 size 中，同时让 size++。

图片

那如果空间不够的时候呢？是否又可以拿数据进行尾插呢？肯定是不可以的，插入的数据会越界。 因此需要增容以继续插入新的数据。

图片

增容

什么情况下进行增容呢？ 当 size == capacity 的时候表示不能再插入数据，这时就要增容。 现在又面临一个问题，增容需要增多少倍合适呢？ 增容过小后面就需要多次增容 (导致性能低下等问题)， 增容过大又容易造成空间的浪费， 较为合适的情况是增加 1 倍或两倍(需从数学角度解释)。

图片

图片

为什么这块新开辟好的空间不直接让 ps->arr 接收呢？ 目的是防止 realloc 失败，成为 NULL 指针。

头插

同样进行头插的时候也可能会面临空间不足的情况，因此我们可以考虑通过调用函数的方法把申请空间 (增容) 封装成一个函数，需要使用到的情况下直接调用这个函数。

图片

图片

图片

顺序表打印

图片

2.4 头删、尾删

尾删
  1. 要保证顺序表里面还有顺序才可以删除数据 (因此需要 assert(ps->size)；

让 ps->size–则完成了尾删。

图片

头删

头删的操作其实与头插的操作类似，需要注意的是ps->arr[0]=ps->arr[1], ps->arr[1]=ps->arr[2]……这样的顺序，如果是 ps->arr[ps->size-2]=ps->arr[ps->size-1], ps->arr[ps->size-3]=ps->arr[ps->size-2], 则会把原来数据覆盖掉。

图片

图片

2.5 指定位置插入、删除、查找数据

指定位置插入数据
  1. pos 位置插入数据必须满足 pos 在 [0, ps->size] 之间
  2. 让 pos 后的位置往后挪动一位

插入完成后让 ps->size++

图片

指定位置删除、查找数据

和指定位置插入数据的方法是类似的

删除数据

图片

查找数据

图片

3. 顺序表实现

在项目工程当中，其实并不是在一个源文件中写下所有代码，而是创建测试文件，源文件 (定义)，头文件 (声明) 完成代码功能实现。

图片

图片

图片

图片

SeqList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// 顺序表-->底层就是数组
// 但是提供了很多现成的方法，开箱即用，是很厉害的新的数据结构
// 顺序表是线性表的一种
// 物理结构 逻辑结构
// 顺序表 连续 连续
// 线性表 不一定连续 连续
// 静态顺序表
// struct SeqList
// {
//     int arr[100]; //定长数组
//     int size; //有效数据个数
// };
typedef int SLDataType;

// 动态顺序表
typedef struct SeqList {
    SLDataType* arr;
    int size; //有效数据个数
    int capacity; //空间大小
} SL;

// 顺序表的初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SLDestroy(SL* ps);
// 顺序表的打印
void SLPrint(SL s);
// 头部插入删除/尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
// 尾删
void SLPopBack(SL* ps);
// 头删
void SLPopFront(SL* ps);
// 指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 指定位置删除数据
void SLErase(SL* ps, int pos);
// 查找指定位置的数据
int SLFind(SL* ps, SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

// 顺序表的初始化
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 CheckCapacity(SL* ps) {
    if (ps->capacity == ps->size) {
        // 申请空间
        // malloc calloc realloc int arr[10] -->增容 realloc
        // 三目表达式
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        // 要申请多大空间
        if (tmp == NULL) {
            perror("realloc");
            exit(1); // 退出程序
        }
        // 空间申请成功
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

// 尾插
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    // ps->arr[ps->size] = x;
    // ps->size++;
    // 插入之前先看数据够不够
    CheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

// 头插
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    CheckCapacity(ps);
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

// 顺序表的打印
void SLPrint(SL s) {
    for (int i = 0; i < s.size; i++) {
        printf("%d ", s.arr[i]);
    }
    printf("\n");
}

// 尾删
void SLPopBack(SL* ps) {
    assert(ps);
    assert(ps->size);
    --ps->size;
}

// 头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

// 指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    // 查看空间够不够
    CheckCapacity(ps);
    // 让 pos 后的位置往后挪动一位
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

// 指定位置删除数据
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--;
}

// 查找指定位置的数据
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;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SLTest01() {
    SL sl;
    SLInit(&sl);
    SLPushBack(&sl, 1);
    SLPushBack(&sl, 2);
    SLPushBack(&sl, 3);
    SLPushBack(&sl, 4);
    SLPushBack(&sl, 5);
    SLPushFront(&sl, 6);
    SLPrint(sl);
    SLPopBack(&sl);
    SLPrint(sl);
    SLPopFront(&sl);
    SLPrint(sl);
    SLInsert(&sl, 2, 5);
    SLPrint(sl);
    SLErase(&sl, 2);
    SLPrint(sl);
    int find = SLFind(&sl, 4);
    if (find < 0) {
        printf("没有找到!\n");
    } else {
        printf("找到了！下标为%d\n", find);
    }
    SLDestroy(&sl);
}

int main() {
    SLTest01();
    return 0;
}

4. 思考

其实这个顺序表的实现并不是很完美，它还是有诸多问题需要顾虑

  • 中间/头部的插入删除，时间复杂度为 O(N)
  • 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  • 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。
  • 初始化的时候并没有分配一定空间，刚开始插入数据的时候就要进行增容问题，这个需要用到 C++ 中的缺省参数才能解决。

图片

目录

  1. 数据结构：顺序表详解
  2. 1. 线性表
  3. 2. 顺序表
  4. 2.1 分类
  5. 2.1.1 静态顺序表
  6. 2.1.2 动态顺序表
  7. 2.2 初始化、销毁
  8. 2.3 头插、尾插
  9. 尾插
  10. 增容
  11. 头插
  12. 顺序表打印
  13. 2.4 头删、尾删
  14. 尾删
  15. 头删
  16. 2.5 指定位置插入、删除、查找数据
  17. 指定位置插入数据
  18. 指定位置删除、查找数据
  19. 3. 顺序表实现
  20. 4. 思考

更多推荐文章

查看全部
  • 大语言模型智能体 (LLM Agents) 入门指南
  • 卷积神经网络感受野详解与计算实战
  • 基于 DeepSeek 和 Cursor 构建智能代码审查工具实战
  • 基于腾讯云轻量应用服务器部署 OpenClaw 并接入 QQ 与飞书机器人
  • PyTorch 自定义算子开发：使用 C++ 与 CUDA 扩展
  • Git Worktree 原理、实战与避坑指南
  • Babylon.js 导出器使用指南：构建 Web 3D 场景
  • 无人机 Remote ID Beacon 帧字段详解
  • OpenClaw Session 机制详解：重置、压缩、剪枝与记忆管理
  • 微信公众号文章开源导出工具 wechat-article-exporter 架构剖析
  • Java 开启多个线程，执行完成后再执行主线程
  • 通义万相 vs 可灵AI vs 即梦AI：2026 国产 AI 视频生成器横评
  • 宇树 G1 机器人二次开发：基于 FAST_LIO 的建图与配置实战
  • Spring Boot 消息队列与异步通信
  • Flutter 三方库 dart_webrtc 的鸿蒙化适配指南
  • ToDesk ToClaw AI 科技新闻日报自动化实战
  • Z 字形变换与外观数列算法解析
  • 单链表实战：删除指定节点、反转链表与查找中间节点
  • Llama 3.1 开源模型快速部署实战
  • LeetCode 顺序表练习：移除元素、删除重复项与合并有序数组

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如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