当前位置：首页 > news >正文

线性表的顺序存储和链式存储

news 2025/10/6 12:35:29

线性表：一种逻辑结构，指的是数据元素之间是“一对一”的线性关系。例如：数组、链表、队列、栈等都可以基于线性表实现。

顺序存储和链式存储是实现线性表的两种不同的物理存储结构。

顺序存储，顾名思义，就是用一段地址连续的存储单元依次存储线性表的数据元素。在内存中，它通常表现为数组。

通常会使用一个结构体来管理顺序表，包含三个关键部分：

C语言代码示例：

#define MAXSIZE 100 // 顺序表的最大容量typedef struct {int data[MAXSIZE]; // 用于存储数据元素的数组int length;        // 顺序表的当前长度
} SqList; // Sequence List 的缩写

访问元素：data[i]，时间复杂度为 O(1)。
插入元素：
- 在表尾插入：时间复杂度 O(1)。
- 在表头或中间插入：需要将插入位置及之后的所有元素都向后移动一位，平均时间复杂度为 O(n)。
- 可能触发扩容：如果数组已满，需要申请一个更大的新数组，并进行数据迁移，开销很大。
删除元素：
- 与插入类似，在表头或中间删除需要将后续元素前移，平均时间复杂度为 O(n)。

优点：
1. 随机访问效率高，支持按下标快速存取。
2. 存储密度高，无需为元素间的逻辑关系增加额外的存储空间。
缺点：
1. 预分配空间：需要提前确定最大容量，难以准确估计。
2. 内存要求高：需要一整块连续的存储空间。
3. 插入删除效率低：平均需要移动大量元素。

链式存储，不要求存储空间是连续的。它通过指针（或引用）来表示数据元素之间的逻辑关系。每个数据元素（称为结点）都包含两部分：

C语言代码示例：

typedef struct LNode {int data;           // 数据域struct LNode *next; // 指针域，指向下一个结点
} LNode, *LinkList;

访问元素：需要从头开始遍历，直到找到第 i 个元素，平均时间复杂度为 O(n)。
插入元素：
- 给定一个结点的指针，在其后插入新结点，时间复杂度为 O(1)。
- 给定一个位置 i，需要先遍历找到第 i-1 个结点，然后再插入，查找过程为 O(n)，但插入本身是 O(1)。
删除元素：
- 与插入类似，删除某个已知前驱结点的后继结点，时间复杂度为 O(1)。

优点：
1. 动态分配：无需预先分配空间，内存利用率高。
2. 插入删除效率高：在已知位置后进行操作，时间复杂度为 O(1)。
3. 物理空间灵活：不要求连续的内存空间。
缺点：
1. 存储密度低：需要额外空间存储指针。
2. 不支持随机访问，查找效率低。

选择顺序表，如果：
- 你的程序需要频繁按索引访问元素。
- 已知或可预估数据总量，且变化不大。
- 追求高存储密度和缓存友好性（连续内存对CPU缓存更友好）。
选择链表，如果：
- 你的程序需要频繁在任意位置插入和删除元素。
- 数据总量未知或变化很大，难以预估。
- 内存碎片化严重，难以找到大块连续空间。