顺序表原理与实现：从基础到工程实践

1. 顺序表基础认知：从零开始的线性表之旅

作为数据结构中最基础的存储形式，顺序表本质上就是用一组地址连续的存储单元依次存储数据元素的线性结构。我第一次接触这个概念时，脑海中浮现的是火车站寄存柜的画面——每个柜格大小相同、紧密排列，通过编号就能快速找到对应物品。这种物理结构上的连续性，正是顺序表区别于链表的核心特征。

在实际项目中，顺序表特别适合处理数据量固定或变化不大的场景。比如学生成绩管理系统，每个班级的人数相对稳定，用顺序表存储既节省空间又便于随机访问。它的核心优势在于O(1)时间复杂度的随机访问能力，这得益于元素存储的物理连续性。当我们需要获取第i个元素时，通过首地址加上偏移量就能直接定位，就像根据门牌号找房子一样直接。

关键认知：顺序表在内存中的存储就像整齐排列的集装箱，每个元素占据相同大小的空间，通过下标可直接计算出内存地址。

2. 顺序表的物理实现与内存管理

2.1 静态分配与动态分配的抉择

早期实现顺序表时，我习惯使用静态分配方式：

c复制#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

这种固定大小的数组实现简单，但存在严重缺陷——当数据量超过MAXSIZE时就会溢出。后来改用动态分配方案后，灵活性大幅提升：

c复制typedef struct {
    int *data;    // 动态数组指针
    int length;   // 当前长度
    int capacity; // 总容量
} SeqList;

动态版本的关键在于初始分配和扩容策略。我的经验是：初始容量设为预估数据量的1.5倍，当length达到capacity的80%时触发1.5倍扩容。这种策略在空间效率和扩容频率间取得了较好平衡。

2.2 内存布局的底层视角

从内存角度看，顺序表的元素紧密排列在连续的内存块中。假设存储的是int型数据（4字节），首元素地址为base，则第i个元素的地址为：

code复制address = base + (i-1)*sizeof(int)

这种计算方式使得顺序表的随机访问时间复杂度恒为O(1)。但插入/删除操作需要移动元素，最坏情况下时间