尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
C语言:顺序表详解
C语言顺序表详解SeqList · 连续内存里的线性表 · 从结构定义到动态扩容一次讲透一、什么是顺序表线性表是n个相同类型元素的有序序列。顺序表是线性表最朴素的实现——用一段连续的内存依次存放元素。数组就是最简单的顺序表。但顺序表通常指带容量管理的动态数组能自动扩容、能插入删除。▶ 顺序表三要素连续内存、相同类型、逻辑顺序物理顺序。二、结构定义静态 vs 动态2.1 静态顺序表#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; //定长数组int size; //当前元素个数} SeqListStatic;缺点容量写死。存满了要么拒绝要么溢出——毫无弹性。2.2 动态顺序表推荐typedef struct {int* data; //指向堆上的连续内存int size; //当前元素个数int capacity; //容量最多能存多少个} SeqList;▶ 动态顺序表的核心思想容量不够就 realloc 扩容元素内存由 malloc 管着。三、初始化与销毁void seqlist_init(SeqList* sl, int init_cap) {sl-data (int*)malloc(init_cap * sizeof(int));sl-size 0;sl-capacity init_cap;}void seqlist_destroy(SeqList* sl) {free(sl-data);sl-data NULL;sl-size sl-capacity 0;}▶ 每次 malloc 都有对应的 free。初始化时分配销毁时归还成对出现。四、尾插与尾删最常用的操作void seqlist_push_back(SeqList* sl, int val) {if (sl-size sl-capacity) {seqlist_grow(sl); //扩容}sl-data[sl-size] val;}void seqlist_pop_back(SeqList* sl) {if (sl-size 0) sl-size--;}尾插的时间复杂度 O(1)均摊尾删 O(1)——这是顺序表最擅长的操作。五、动态扩容核心中的核心void seqlist_grow(SeqList* sl) {int new_cap sl-capacity 0 ? 4 : sl-capacity * 2;int* tmp (int*)realloc(sl-data, new_cap * sizeof(int));if (tmp NULL) {perror(realloc failed);exit(1);}sl-data tmp;sl-capacity new_cap;}扩容策略容量×2均摊后每次插入 O(1)最经典的策略固定N每次插入均摊 O(N)性能差realloc 返回值要用临时变量接失败时原指针不丢▶ 扩容量×2 的原因均摊分析。N次插入的总 realloc 成本 O(N)平均每次 O(1)。六、任意位置插入与删除6.1 指定位置插入pos ∈ [0, size]int seqlist_insert(SeqList* sl, int pos, int val) {if (pos 0 || pos sl-size) return 0;if (sl-size sl-capacity) seqlist_grow(sl);//从后往前搬移元素给pos腾位置for (int i sl-size; i pos; i--)sl-data[i] sl-data[i - 1];sl-data[pos] val;sl-size;return 1;}6.2 指定位置删除int seqlist_erase(SeqList* sl, int pos) {if (pos 0 || pos sl-size) return 0;//从前往后搬移覆盖被删位置for (int i pos; i sl-size - 1; i)sl-data[i] sl-data[i 1];sl-size--;return 1;}▶ 插入/删除的平均时间复杂度 O(N)——这是顺序表最贵的操作。频繁中间插入请考虑链表。七、查找与修改int seqlist_find(SeqList* sl, int val) {for (int i 0; i sl-size; i)if (sl-data[i] val) return i;return -1;}//按下标访问O(1)随机访问顺序表的杀手锏int seqlist_at(SeqList* sl, int idx, int* out) {if (idx 0 || idx sl-size) return 0;*out sl-data[idx];return 1;}▶ 按下标访问 O(1) 是顺序表相对链表的绝对优势——数据在内存里连续存放地址直接可算data[i] data i*sizeof(int)。八、顺序表 vs 链表┌──────────┬───────────────┬───────────────┐│ │ 顺序表 │ 链表 │├──────────┼───────────────┼───────────────┤│ 随机访问 │ O(1) ★ │ O(n) ││ 尾插尾删 │ O(1) ★ │ O(1) ││ 中间插入 │ O(n) │ O(1) ★ ││ 缓存友好 │ ★ 好 │ 差 ││ 空间 │ 连续可能浪费│ 分散有指针开销││ 扩容 │ realloc │ 无需动态节点│└──────────┴───────────────┴───────────────┘▶ 结论频繁按下标访问 → 顺序表频繁中间插入删除 → 链表。工程里两者结合才是常态。九、八条常见错误① 忘了检查 pos 越界——插入/删除前不验证下标静默写坏内存② size 和 capacity 混淆——size是元素个数capacity是容量③ 扩容后忘了更新 capacity——下次插入直接溢出④ realloc 返回值直接赋给原指针——失败时空指针丢失原数据⑤ 插入从前往后搬移——应该从后往前否则覆盖还没搬的元素⑥ 删除从后往前搬移——应该从前往后⑦ 销毁后不置 NULL——野指针⑧ 结构体按值传参——复制整个结构修改无效要传指针十、总结▶ 顺序表 连续内存 容量管理。数组是它的静态形态动态数组是它的完全体。▶ 三个状态量size有多少、capacity能存多少、data存在哪。▶ 扩容×2 realloc 临时变量接收是顺序表的两条铁律。▶ 随机访问 O(1) 是它的王牌中间插入 O(n) 是它的软肋。▶ 凡是按下标存取、尾部增删的场合顺序表永远是最优解。The first rule of Fight Club is: you do not talk about Fight Club.—— Tyler Durden, Fight Club—— 顺序表的第一条规则是下标永远从0开始。第二条规则永远不要越界。— END —
RELATED

相关推荐

从“图书管理系统”到“高并发秒杀”:产教融合如何弥合高校Java实训与企业级开发的鸿沟?

从“图书管理系统”到“高并发秒杀”:产教融合如何弥合高校Java实训与企业级开发的鸿沟?

声明: 本文基于越华云图在多家校企合作实训基地的观察数据整理,旨在探讨技术人才的供给侧改革。 作为一名技术出身的人员,我深刻感受到高校Java/大数据专业的实训环节,往往存在 “项目过于Demo化” 的问题。学生虽然会写Spring Bo…

📅 2026/11/14 5:16:28
Ryujinx模拟器:从零到精通的完整Switch游戏PC体验指南

Ryujinx模拟器:从零到精通的完整Switch游戏PC体验指南

Ryujinx模拟器:从零到精通的完整Switch游戏PC体验指南 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx 想在电脑上体验Switch独占游戏却不知如何开始?Ryujinx作为…

📅 2026/10/23 12:19:37
基于ESP32-S3的USB蓝牙双模桌面交互终端开发指南

基于ESP32-S3的USB蓝牙双模桌面交互终端开发指南

在嵌入式开发与桌面交互场景中,经常需要一种能够灵活连接多种设备、支持多种输入方式的小型终端设备。无论是调试物联网设备、快速输入指令,还是作为便携式控制面板,一个集成了USB与蓝牙双模连接、触控交互能力的终端都能极大提升效率。本文将…

📅 2026/10/26 9:03:52
MORE NEWS

更多资讯

📰

工地太忙根本没时间复习考试?北京电工证办理点怎么报名全攻略

工地太忙根本没时间复习考试?北京电工证办理点怎么报名全攻略 工地太忙根本没时间复习考试,你不是一个人。每天早上五点起床赶班车,晚上十点才回宿舍,中间还要抢时间吃口饭、打电话给家里报平安。这种情况下,还要抽时间准备电工证考试,真的太难了。但现…

📰

电工证异地不给复审千万别踩坑 从业者怎么破局

电工证异地不给复审千万别踩坑 从业者怎么破局 你是不是正在为找工作发愁?急需特种作业证才能上岗找工作,偏偏电工证异地不给复审,搞得你到处碰壁?别急,这事儿我见过太多人踩坑了,今天就把实打实的经验告诉你,别再走弯路。…

📰

长春初级电工证在哪考保姆级教程:想上岗必须搞定的电工证全攻略

长春初级电工证在哪考保姆级教程:想上岗必须搞定的电工证全攻略 你还在为找工作发愁吗?是不是听说现在电工证是很多岗位的硬门槛?长春初级电工证在哪考?这个问题,直接关系到你能不能顺利上岗、拿到第一份工资。今天这篇保姆级教程,就帮你把所有问题说透…

📰

电工证3年免复审条件你知道吗?全国通用的政策你别再搞错了

电工证3年免复审条件你知道吗?全国通用的政策你别再搞错了 怕考不过白交培训费?别急,今天就给你讲清楚电工证3年免复审条件到底怎么算,以及怎么选靠谱机构,别再花冤枉钱。 电工证到底有多“硬”?全国通用的它到底值不值?…

📰

电工证异地不给复审,不知道在哪考?三门峡应届生看这篇就够了

电工证异地不给复审,不知道在哪考?三门峡应届生看这篇就够了 你是不是也遇到过这样的情况:手头有个电工证,想换个地方工作,结果一问, 异地不给复审 ?更糟的是,你根本不知道 在哪考 ,生怕被中介坑了一把?别慌,这篇文章就是为你准备的。…

📰

池州电工证在哪办理怎么拿电子证书?急需特种作业证才能上岗找工作

池州电工证在哪办理怎么拿电子证书?急需特种作业证才能上岗找工作 你是不是正为找工作发愁?是不是手里攥着一堆简历却找不到合适的岗位?别急, 池州电工证在哪办理…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬