数据结构：线性表顺序存储结构

顺序存储定义

我们可以将线性表看作一个火车车厢，每个车厢代表一个数据元素，所有车厢首尾相接，排列成一列。在线性表的顺序存储结构中，这些车厢在内存中是连续排列的，就像火车停在一个长长的站台上，每节车厢都有一个固定的位置。

在编程中，我们用数组来实现线性表的顺序存储。假设有一个线性表用来存储学生的考试成绩，这个线性表可以用如下的C语言结构体表示：

#define MAXSIZE 100 // 定义线性表的最大容量

typedef struct {
    int data[MAXSIZE]; // 用于存储成绩的数组
    int length; // 当前线性表的长度（存储的成绩数量）
} SqList;

顺序存储方式

顺序存储方式就像把书一本接一本地排在书架上，这些书之间没有空隙，按顺序排列，方便取用。在顺序存储中，每个数据元素（书）都占据一个固定的存储单元（书架位置），并且可以通过数组下标（书的位置）直接访问。例如，访问第3个成绩就像直接找到书架上的第3本书一样方便：

int thirdScore = sqList.data[2]; // 访问线性表中的第3个成绩

这种存储方式有以下优点：

1. 快速访问：可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
2. 连续存储：所有元素存储在连续的内存区域中，有助于提高缓存命中率，访问速度快。

但是，这种方式也有缺点：

1. 空间浪费：需要预先分配一块足够大的连续内存空间，即使存储的元素较少，也会浪费一些存储空间。
2. 插入和删除效率低：在中间位置插入或删除元素时，需要移动大量数据，时间复杂度为O(n)。

数据长度与线性表长度的区别

为了更好地理解数据长度和线性表长度，我们继续以书架和书的类比进行解释：

• 数据长度：就像书架上实际摆放的书的数量。例如，一个书架可以放100本书（最大容量），但当前只放了50本书，那么数据长度就是50。
• 线性表长度：是书架的最大容量，即书架能容纳的最大书本数量。在我们的例子中，书架的容量是100。

SqList sqList;
sqList.length = 50; // 当前线性表中有50个成绩（数据长度）

数据长度是动态变化的，随时可能增加或减少，而线性表长度通常是固定的，一开始就确定了。例如：

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE]; // 数组的最大容量为100
    int length; // 当前存储的元素个数
} SqList;

生动示例

假设我们有一个学生成绩管理系统，系统用一个线性表来存储学生的成绩。这个线性表的最大容量为100，可以容纳100个学生的成绩。

插入操作

某天有一名新生转学过来，我们需要在第5名学生之后插入他的成绩：

int newScore = 85; // 新学生的成绩
int position = 5; // 插入的位置

// 移动后续元素，给新成绩腾出位置
for (int i = sqList.length; i >= position; i--) {
    sqList.data[i] = sqList.data[i-1];
}

// 插入新成绩
sqList.data[position - 1] = newScore;
sqList.length++;

这就像在书架上插入一本新书，需要将后面的书都向后移一格，给新书腾出位置。

删除操作

某天有一名学生毕业了，我们需要删除他的成绩：

int position = 3; // 删除的位置

// 移动后续元素，覆盖要删除的成绩
for (int i = position - 1; i < sqList.length - 1; i++) {
    sqList.data[i] = sqList.data[i+1];
}

sqList.length--;

这就像从书架上取走一本书，需要将后面的书都向前移一格，填补空缺。