《从零入门数据结构与算法（二）：线性表详解——从顺序表原理到静态与动态实现》-北京尧图网络

上一篇我们把复杂度这个概念彻底拆了一遍。时间复杂度和空间复杂度各自是什么、怎么算结合一个个经典例子和图像掰开揉碎地讲了个透。我们还把常见的复杂度拉出来做了对比看了各种排序算法的复杂度表格。最后用轮转数组这道力扣题把“算法思路有很多种”这句话落到了实处三种不同的思路从超时到通过再到把时间压到O(n)、空间守到O(1)一趟走下来算法和复杂度的关系算是看明白了。而这一篇我们就要翻开顺序表和链表的新篇章了。初阶的数据结构与算法我们把知识点分成三块。第一块复杂度。第二块顺序表、链表、栈和队列、二叉树。第三块排序。第一块的复杂度已经讲完了。从这篇开始我们正式进入第二块顺序表和链表。目录一、认识线性表二、顺序表线性表的顺序存储结构2.1 顺序表的基本概念2.2 顺序表的两种实现方式2.2.1 静态顺序表2.2.2 动态顺序表2.3 顺序表的结构设计2.3.1 静态顺序表的结构定义2.3.2 动态顺序表的结构定义2.4 动手实现动态顺序表从尾插入手2.4.1 动态顺序表的基本实现①SeqList.h声明顺序表结构与相关接口②SeqList.c实现顺序表功能③test.c编写测试代码验证尾插功能2.5 静态与动态顺序表的完整代码实现2.5.1 静态顺序表的实现①SeqList.h定义静态顺序表结构与接口②SeqList.c实现静态顺序表相关操作③test.c测试静态顺序表2.5.2 动态顺序表的实现①SeqList.h定义动态顺序表结构与接口②SeqList.c实现动态顺序表及尾插操作③test.c测试动态顺序表一、认识线性表线性表Linear List说的是n个具有相同特性的数据元素排成的一个有限序列。这东西在实际开发里太常见了顺序表、链表、栈、队列、字符串全都是线性表家族的成员。线性表在逻辑上是一条连续的直线元素一个挨着一个次序清清楚楚。可到了物理层面就不一定了。它在内存里通常有两种落脚方式一种是数组元素挤在连续的空间里另一种是链式结构元素各住各的靠指针牵线搭桥。所以线性表可以从两个维度来看逻辑结构和物理结构。逻辑结构是人为抽象出来的模型物理结构才是它在内存里的真实存储形态。所谓逻辑结构说白了就是人想象出来的那套秩序而物理结构是数据实打实躺在内存里的样子。二、顺序表线性表的顺序存储结构2.1 顺序表的基本概念顺序表是一段用物理地址连续的存储单元依次把数据元素排进去的线性结构。平时它一般就用数组来存储。那问题来了数组就是顺序表吗顺序表就是数组吗能这么直接划等号吗不能。真要说清楚得这么看顺序表的底层结构是数组它是在数组之上做了一层封装实现了常见的增删查改等接口。换句话说数据结构要干的活儿就是把顺序表那套增删查改的接口函数一个一个实现出来。那数组和顺序表到底啥关系打个比方吧。数组就像街边的苍蝇小馆几口大锅、几张桌子能填饱肚子但没什么讲究。顺序表呢更像米其林五星级餐厅同样的食材人家后厨有一套精细的流程摆盘、上菜、服务样样都有章法。底层都是“吃饭”这件事可一个粗放一个精细体验天差地别。数组给你的是最原始的存储能力而顺序表在它之上把插入、删除、查找、修改这些操作做成了规范、好用的接口。用起来顺手管起来也省心。2.2 顺序表的两种实现方式顺序表分两种静态顺序表和动态顺序表。2.2.1 静态顺序表静态顺序表就是用定长数组来存元素。开篇就定死多大就是多大。它的毛病也很直白空间给少了不够用程序直接趴窝给多了用不完白白浪费。两头不讨好尺寸全靠拍脑袋估。估准了算运气估不准是常态。2.2.2 动态顺序表动态顺序表就不一样了按需申请空间。要多少给多少不够了再扩。空间利用率上去了也不用再为“到底开多大”纠结半天。静态和动态一个把尺寸焊死一个随用随调。各有各的适用场景但真要灵活还得看动态的。2.3 顺序表的结构设计我们分别来看静态顺序表和动态顺序表各自长什么样。2.3.1 静态顺序表的结构定义静态顺序表结构简单到不能再简单一个定长数组加一个记录当前元素个数的变量。2.3.2 动态顺序表的结构定义动态顺序表把定长数组换成了一个指针再配上容量和元素个数两个变量。2.4 动手实现动态顺序表从尾插入手静态顺序表和动态顺序表我们这里只实现动态顺序表。但这并不意味着静态顺序表就没有学习的必要了这一点得先说明白。实现要分成三个文件来做。因为是顺序表名字就叫SeqList。用三个文件实现一个功能这套路我们在扫雷游戏那儿就打过交道了。简单捋一下三个文件各自的分工分别创建三个文件SeqList.h头文件、SeqList.c源文件、test.c测试文件。下面会逐一介绍三个文件怎么写。每个小标题下面的第一段代码就是动态顺序表的代码实现代码后面再抽丝剥茧地展开详解。2.4.1 动态顺序表的基本实现先看三个文件的原貌再一个个拆开讲。代码里藏着几个要命的坑我们边看边说。①SeqList.h声明顺序表结构与相关接口#pragma once #include stdio.h typedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; int capacity; } SL; void SLInit(SL* ps); void SLPushBack(SL* ps, SLDataType x);头文件里SLDataType是类型别名方便以后换成别的数据类型。结构体三个成员arr指向动态数组size记有效数据个数capacity记总容量。②SeqList.c实现顺序表功能#define _CRT_SECURE_NO_WARNINGS 1 #include SeqList.h #include stdlib.h void SLInit(SL* ps) { ps-arr NULL; ps-size ps-capacity 0; } void SLPushBack(SL* ps, SLDataType x) { if (ps-size ps-capacity) { int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity; SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType)); if (tmp NULL) { perror(realloc fail!); exit(1); } ps-arr tmp; ps-capacity newCapacity; } ps-arr[ps-size] x; }③test.c编写测试代码验证尾插功能#define _CRT_SECURE_NO_WARNINGS 1 #include SeqList.h void test01() { SL sl; SLInit(sl); SLPushBack(sl, 1); SLPushBack(sl, 2); SLPushBack(sl, 3); SLPushBack(sl, 4); } int main() { test01(); return 0; }2.5 静态与动态顺序表的完整代码实现这块内容牵扯到结构体的知识。学数据结构对结构体得有足够的认识不然后面全是空中楼阁。先看一段代码#pragma once #define N 100 typedef int SQDataType; struct SeqList { SQDataType a[N]; int size; } // 增删查改等接口函数先说#pragma once这行代码博主在C语言专栏那篇文章里介绍过截图就不重复了。它的功能很单纯避免头文件被重复包含。如果你不想用它也可以写成这样效果完全等价#ifdef __TEST_H__ #define __TEST_H__ #define N 100 typedef int SQDataType; struct SeqList { SQDataType a[N]; int size; } // 增删查改等接口函数 #endif // __TEST_H__一个用编译器的扩展指令一个用预处理宏两条路同一个终点。为什么类型用typedef常量用#define这里有个容易犯迷糊的点。定义数据类型我们一般用typedef定义普通常量才用#define。比如N是个常量100用#define 没问题。这么做的意义在哪假设顺序表的数组长度写死成10struct SeqList { int a[10]; int size; }哪天想改成100或者1000你就得满代码翻一个地方一个地方地改。但换成这样#define N 100 struct SeqList { SQDataType a[N]; int size; }a[]里直接放N想改的时候就在定义处把N动一下其他地方纹丝不动。存储的数据类型也一样。typedef int SLDataType;一写以后想存char就改成char想存double就改成doubletypedef char SLDataType; typedef float SLDataType; typedef double SLDataType;只动一行全局生效。这就是typedef的好处把类型抽象出来改一处通全盘。初始化怎么做初始化可以用循环也可以直接用memset。memset是按字节来初始化的用起来利索。#pragma once #define N 100 typedef int SQDataType; struct SeqList { SQDataType a[N]; int size; } // 增删查改等接口函数 void SeqListInit(struct SeqList sl);我们C语言里写结构体不能直接用结构体名得带上struct关键字。uu们是不是觉得这样太长了那就简写嘛。#ifdef __TEST_H__ #define __TEST_H__ #define N 100 typedef int SQDataType; struct SeqList { SQDataType a[N]; int size; } typedef struct SeqList SL; void SeqListInit(struct SeqList sl); // 增删查改等接口函数 #endif // __TEST_H__当然还有另一种写法很多书、很多老师都这么写#ifdef __TEST_H__ #define __TEST_H__ #define N 100 typedef int SQDataType; typedef struct SeqList { SQDataType a[N]; int size; } SL; void SeqListInit(struct SeqList sl); // 增删查改等接口函数 #endif // __TEST_H__这样就不用再写长长的一截struct SeqList了直接写简写SL#ifdef __TEST_H__ #define __TEST_H__ #define N 100 typedef int SQDataType; typedef struct SeqList { SQDataType a[N]; int size; } SL; void SeqListInit(SL sl); // 增删查改等接口函数 #endif // __TEST_H__是不是简单多了这里再提醒一下uu们敲代码别一股脑全写完再测试。写一个测一个。代码一长一口气写完再运行唰地蹦出几十个错误你盯着屏幕反复调调了一两个小时再一运行又炸出几十个错误人当场就崩了。写一个测一个有问题也只在这几行代码里好找、好改犯不着自己吓自己。顺序表嘛本质就是个数组。uu们可能觉得N这个变量名不好理解那我们就把它写明白#ifdef __TEST_H__ #define __TEST_H__ #define MAX_SIZE 100 typedef int SQDataType; typedef struct SeqList { SQDataType a[MAX_SIZE]; int size; } SL; void SeqListInit(SL s); // 增删查改等接口函数 #endif // __TEST_H__这下是不是一眼就懂MAX_SIZE数组最大容量清清楚楚。初始化写起来也顺#include SeqList.h void SeqListInit(SL s) { memset(sl.a, 0, sizeof(SQDataType) * MAX_SIZE); sl.size 0; // sl.a 说明是按字节初始化 // 初始化多少个字节呢MAX_SIZE 个 // 每个有多大呢sizeof(SQDataType)——SQDataType 这个类型每一个的大小 }到这里定义数组大小为MAX_SIZE的好处就更明显了。想改数组大小只在.h文件里动一下MAX_SIZE所有包含这个头文件的地方全都跟着变。方便得不像话。定义数据类型也一样本质上都是增强程序的可维护性——不用满世界找着改。那我们现在开始写一点测一点。程序要输入输出得包含头文件。不知道memset在哪个头文件查一下嘛cstring或者string.h这俩是一样的。#ifdef __TEST_H__ #define __TEST_H__ #include stdio.h #include string.h // 增强程序可维护性 #define MAX_SIZE 100 typedef int SQDataType; typedef struct SeqList { SQDataType a[MAX_SIZE]; int size; } SL; void SeqListInit(SL s); // 增删查改等接口函数 #endif // __TEST_H__然后来到test.c先写个简单的#include SeqList.h void TestSeqList1() { SL sl; SeqListInit(SL s1); // 调接口进行初始化 } int main() { return 0; }定义完了先跑一跑看看。调试的时候可以结合VS调试技巧F9打断点F5调试程序就停在断点处。不过这里我们就不能这么写了前面那几处得改一改。2.5.1 静态顺序表的实现我们C语言里学过通讯录那个结构跟静态顺序表一个路子定义一个宏尺寸就写死了。①SeqList.h定义静态顺序表结构与接口#ifndef __TEST_H__ #define __TEST_H__ #include stdio.h #include string.h // 增强程序可维护性 #define MAX_SIZE 10 // 100 个、500 个有点太大了先来 10 个 typedef int SQDataType; typedef struct SeqList { SQDataType a[MAX_SIZE]; int size; } SL; // 增删查改等接口函数 void SeqListInit(SL* ps); void SeqListPushBack(SL* ps, SQDataType x); // 尾插 void SeqListPushFront(SL* ps, SQDataType x); // 头插 void SeqListPopBack(SL* ps); // 尾删 void SeqListPopFront(SL* ps); // 头删 #endif这里的命名uu们如果自己有别的习惯也完全可以。博主这里是跟着C STL标准库的命名走的算是比较规范的写法void SeqListPushBack(SL* ps, SQDataType x); // 尾插 void SeqListPushFront(SL* ps, SQDataType x); // 头插 void SeqListPopBack(SL* ps); // 尾删 void SeqListPopFront(SL* ps); // 头删当然接口不止这些。还是老原则写一个测一个。②SeqList.c实现静态顺序表相关操作#include SeqList.h void SeqListInit(SL* ps) { memset(ps-a, 0, sizeof(SQDataType) * MAX_SIZE); ps-size 0; } // 头插、尾插、头删、尾删 void SeqListPushBack(SL* ps, SQDataType x) { if (ps-size MAX_SIZE) { printf(SeqList is Full\n); return; } ps-a[ps-size] x; ps-size; } // 下面几个大致也是这个套路就不一一展开了 void SeqListPushFront(SL* ps, SQDataType x); void SeqListPopBack(SL* ps); void SeqListPopFront(SL* ps);从这里就能看出静态顺序表不是一块好料。你想存1001个数据就得把MAX_SIZE定义成10000白白空着一大片。总结一下它的毛病给少了不够用给多了用不完浪费空间控制不灵活。正因如此我们才转向更灵活的动态顺序表。静态顺序表就介绍到这儿。③test.c测试静态顺序表#include SeqList.h void TestSeqList1() { SL sl; SeqListInit(sl); // 调接口进行初始化 } int main() { TestSeqList1(); return 0; }这里为什么要传指针呢因为形参只是实参的一份临时拷贝形参和实参各有各的空间彼此独立。你在函数里改形参外面那个实参根本不知道。所以得把地址传进去。传了地址函数就能顺着地址找到实参本尊改的就是它了。那为什么传地址就能影响到实参因为地址指向的就是实参所在的那块内存。函数拿到地址后通过指针解引用直接操作的就是实参本身。拷贝的是地址可地址指向的是同一块地方。所以形参改的就是实参。2.5.2 动态顺序表的实现①SeqList.h定义动态顺序表结构与接口#ifdef __SEQLIST__H__ #define __SEQLIST__H__ #include stdio.h #include string.h // 增强程序可维护性 typedef int SLTDataType; typedef struct SeqList { SLTDataType* a; int size; // 有效数据的个数 int capacity; // 容量 } SL; // 增删查改等接口函数 void SeqListInit(SL* ps); void SeqListPrint(SL* ps); void SeqListPushBack(SL* ps, SLTDataType x); // 尾插 void SeqListPushFront(SL* ps, SLTDataType x); // 头插 void SeqListPopBack(SL* ps); // 尾删 void SeqListPopFront(SL* ps); // 头删 #endif②SeqList.c实现动态顺序表及尾插操作#include SeqList.h void SeqListInit(SL* ps) { // 粗暴一点先置为空再改成 0然后 capacity 也改为 0 ps-a NULL; ps-size 0; ps-capacity 0; // 当然我们也可以直接 malloc } // 头插、尾插、头删、尾删 void SeqListPushBack(SL* ps, SLTDataType x) { // 满了就要扩容 if (ps-size ps-capacity) { // 扩容一般扩两倍。一个一个太慢了三倍又太多了C 标准库一般是扩两倍 // 我们有两种思路一种是新开辟一个两倍的空间然后把原来的内容复制过去 // 另一种是 realloc int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2; // 第一次给多少没什么讲究给个 10 也可以只是一开始不要给太大给太大就浪费了 // 动态管理就是开始给小一点不够了慢慢增加 // 最小给个 1 SLTDataType* tmp realloc(ps-a, newcapacity * sizeof(SLTDataType)); // realloc 有可能失败 if (tmp NULL) { printf(realloc fail\n); exit(-1); } else { ps-a tmp; // ps-capacity * 2; // 这里就不是乘两倍了直接等于 newcapacity ps-capacity newcapacity; } } ps-a[ps-size] x; ps-size; } void SeqListPushFront(SL* ps, SLTDataType x); void SeqListPopBack(SL* ps); void SeqListPopFront(SL* ps); void SeqListPrint(SL* ps) { for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } printf(\n); }③test.c测试动态顺序表#include SeqList.h void TestSeqList1() { SL sl; SeqListInit(sl); SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 3); SeqListPushBack(sl, 4); SeqListPushBack(sl, 5); SeqListPushBack(sl, 6); SeqListPushBack(sl, 7); SeqListPushBack(sl, 8); SeqListPushBack(sl, 9); SeqListPushBack(sl, 10); SeqListPushBack(sl, 11); SeqListPrint(sl); } int main() { TestSeqList1(); return 0; }这就是尾插。只要内存够就能一直插下去。它不像静态顺序表那样得提前定死存多少个不够了就扩容可以一直尾插。这就是动态顺序表相较于静态顺序表的优越性。那么uu们可能要问了realloc不是在原来空间的基础上扩容吗如果原来空间是0呢realloc的文档里有一句说明原来空间可以为空。只不过这样一来realloc就等同于malloc如果原来空间为空它直接申请一块新空间跟malloc一模一样。像头插、指定插入、指定删除这些知识点博主会专门整理一篇博客。当然一篇肯定讲不完给主包一点时间整理。或者铸币主包把它们融进顺序表和链表的博客里也是可行的。如果这篇文章对你有帮助别忘了点赞、收藏、关注三连支持。你的每一次反馈都是我继续硬核输出的最大动力。

《从零入门数据结构与算法（二）：线性表详解——从顺序表原理到静态与动态实现》

相关推荐

计算机组成原理课后题：补码、浮点、Cache与微指令解题全攻略

白字配亮色背景肉眼没问题，体检为何仍失败：HarmonyOS 7 动态对比度怎么守住状态切换

Python logging配置全解析：从basicConfig到dictConfig的工程选型与实战

更多资讯

9款AI论文工具实测：专科生开题报告从空白到初稿的完整流程

Unity与Android跨语言回调：AndroidJavaProxy原理、线程安全与避坑指南

DeepSeek聊天记录导出教程：从复制粘贴到自动化归档的完整方案

提示词版本控制实战：用Git管理Prompt的迭代、评测与回滚

Egret弹珠游戏源码解析：碰撞检测与反弹角度实战

Spring @Transactional 事务失效的七大场景与排查修复指南

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？