阅读量:0
线性表顺序存储结构
顺序存储定义
我们可以将线性表看作一个火车车厢，每个车厢代表一个数据元素，所有车厢首尾相接，排列成一列。在线性表的顺序存储结构中，这些车厢在内存中是连续排列的，就像火车停在一个长长的站台上，每节车厢都有一个固定的位置。
在编程中，我们用数组来实现线性表的顺序存储。假设有一个线性表用来存储学生的考试成绩，这个线性表可以用如下的C语言结构体表示：
#define MAXSIZE 100 // 定义线性表的最大容量 typedef struct { int data[MAXSIZE]; // 用于存储成绩的数组 int length; // 当前线性表的长度（存储的成绩数量） } SqList; 顺序存储方式
顺序存储方式就像把书一本接一本地排在书架上，这些书之间没有空隙，按顺序排列，方便取用。在顺序存储中，每个数据元素（书）都占据一个固定的存储单元（书架位置），并且可以通过数组下标（书的位置）直接访问。例如，访问第3个成绩就像直接找到书架上的第3本书一样方便：
int thirdScore = sqList.data[2]; // 访问线性表中的第3个成绩 这种存储方式有以下优点：
- 快速访问：可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
- 连续存储：所有元素存储在连续的内存区域中，有助于提高缓存命中率，访问速度快。
但是，这种方式也有缺点：
- 空间浪费：需要预先分配一块足够大的连续内存空间，即使存储的元素较少，也会浪费一些存储空间。
- 插入和删除效率低：在中间位置插入或删除元素时，需要移动大量数据，时间复杂度为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--; 这就像从书架上取走一本书，需要将后面的书都向前移一格，填补空缺。
