【数据结构入坑指南（二.1）】--《数据结构与算法精讲：从数组到顺序表，如何让数据管理变得强大而优雅？》
🔥@晨非辰Tong：个人主页
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：掌握了复杂度的衡量标尺，现在，让我们用它来审视第一个真正意义上的数据结构——顺序表。本文将亲手实现动态顺序表，并分析其各项操作的效率，为下一篇博客对顺序表的继续分享打通前路。
目录
一、线性表
--线性表是n个有相同特性的数据元素的有限序列，是广泛应用的数据结构。常见的：顺序表、链表、栈、队列、字符串……
--线性表，逻辑上是线性结构（连续的一条线）。物理结构不一定是连续的，线性表在物理上存储，通常以顺序结构、链式结构存储。
二、顺序表
2.1 什么是顺序表？
--定义：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况采用数组存储。（顺序表底层是数组）
那顺序表就是数组？
--不！顺序表是对数组的封装，实现了常用的增删查改等接口。
--形象对比数组与顺序表：
2.2 顺序表类别
2.2.1 静态顺序表
--静态顺序表使用定长数组存储元素。
--不足：可能空间不够用，初始化给多有可能浪费。
--将 int 重新命名为 SLDataType；
--size 指向有效数据的下一位；
2.2.2 动态顺序表
--动态顺序表的空间按需申请
--两种顺序表在不同的应用场景中各有作用。
三、动态顺序表的实现（三文件协同）
--实现动态顺序表，用以下三个文件：
SeqList.h
//SeqList.h头文件 #pragma once #include <stdio.h> #include <stdlib.h> //定义动态顺序表的结构 typedef int SLTDataType; typedef struct SeqList { SLTDataType* arr;//存储数据 int size;//有效数据个数 int capacity;//空间大小 }SL;//SL是对结构体重命名 //定义顺序表初始化函数声明 void SLInit(SL* ps); 不直接int，方便以后进行类型的修改，直接在type地方将int修改对结构体重命名—> typedef struct SeqList SL; 也行
SeqList.c
//SeqList.c文件（配合SeqList.h文件） //定义、实现函数 #define _CRT_SECURE_NO_WARNINGS #include"seqlist.h"//包含头文件 void SLInit(SL* ps)//指针接收地址 { ps->arr = NULL; ps->size = 0; ps->capacity = 0; } test.c（测试文件）
#define _CRT_SECURE_NO_WARNINGS #include"seqlist.h" void test1() { SL s1; SLInit(&s1);//传地址，传址调用 } int main() { test01(); return 0; }--这里要注意，使用的是传址调用：将地址传过去，希望对指向的结构体成员进行初始化（修改指向的内容）；
--如果是传值调用，只是将结构体成员的内容传过去，形参是实参的临时拷贝（二者是独立的个体），改变了形参的值对实参没有影响。（在test.c文件测试会显示使用了未初始化的变量s1，因为是传值，但代码中s1未初始化，无法传值）
--对于上面三文件的相互配合，通过调试来观察之间的数据传递。调试是很好的习惯，尤其是在模块投入复用前，通过调试验证其正确性，就算调试出有错误也能及时修。保证代码质量、提升开发效率、降低后期维护成本的核心必要环节
四、动态顺序表的应用（初）
--经过上面操作，就得到了一个空顺序表，进行应用。
4.1 在尾部插入数据
SeqList.c文件 //尾插 void SLPushBack(SL* ps, SLTDataType x) { //空间不够 if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //增容 SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } //空间足够 ps->arr[ps->size++] = x; } //输出_函数 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); }test.c文件 //实现尾插 void test02() { SL s2;//创建结构体变量 SLInit(&s2);//初始化 SLPushBack(&s2, 1); SLPrint(&s2); SLPushBack(&s2, 2); SLPrint(&s2); SLPushBack(&s2, 3); SLPrint(&s2); SLPushBack(&s2, 4); SLPrint(&s2); } int main() { test02(); return 0; }
--在程序调试时，运行到函数时，F11进入到函数内部观察变量的变化。
对于增容操作：一般进行成倍数增加（而不是插一个数就申请一个）——>最好2倍增容——>有效降低增容次数，虽存在空间浪费，但不会太多——>默认插入的数据越多，并表示将来存储的数据也越多（概率学）。
4.2 在头部插入数据
SeqList.c #include "SeqList.h" //扩容_函数 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //增容 SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } } //头插_函数 void SLPushFront(SL* ps, SLTDataType 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 }--后续会频繁进行空间的判断，所以进行函数封装，直接调用函数。
--其次进行了断言操作，防止传参为空。
test.c文件 #include "SeqList.h" void test02() { SL s2;//创建结构体变量 SLInit(&s2);//初始化 //实现头插 SLPushFront(&s2, 1); SLPrint(&s2); SLPushFront(&s2, 2); SLPrint(&s2); SLPushFront(&s2, 3); SLPrint(&s2); } int main() { test02(); return 0; }
结语：顺序表通过连续的物理空间实现了高效的随机访问，但其插入删除的代价也显而易见。但这只是开始——下篇我们将深入更关键的删除、查找等核心操作，并完成最终的性能评估。敬请期待。
