线性表

线性结构的特点

• 线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。
• 通常存储为顺序表（数组）或链表。

顺序表中第 $i$ 个数据元素存储位置的计算

公式： ${\text{LOC}}(a_{i})={\text{LOC}}(a_{1})+(i-1)\times L$

• ${\text{LOC}}(a_{i})$：第 $i$ 个数据元素的存储地址。
• $i$：数据元素在表中的位置。
• $L$：每个元素所占存储单元大小。

该公式体现了顺序存储结构中地址的连续性，计算时间复杂度为 $O(1)$。

顺序表的基本操作

• 取值：根据位置直接通过公式计算地址，时间复杂度为 $O(1)$。
• 查找：按值查找时，需要逐个比较，时间复杂度为 $O(n)$。
• 插入与删除：为保持数据的连续性，需要移动元素，时间复杂度为 $O(n)$。

顺序存储结构的特点

• 逻辑相邻即物理相邻：数据存储为一段连续的内存空间。
• 随机存取：通过公式快速计算元素地址，支持直接访问任意位置。
• 存储密度大：所有存储空间都存储有效数据，密度为 1。

链式存储结构的特点

• 物理位置不一定相邻：数据元素之间通过指针链接，内存分配灵活。
• 顺序存取：必须从头节点开始，逐一访问每个元素。
• 存储密度小于 1：每个节点需要额外存储指针信息。
• 链表：单链表中每个节点包含数据域和指针域。

单链表的操作

单链表的插入操作

在位置 p 之后插入新节点 s：

s->next = p->next;

p->next = s;

1. 将 s 的指针指向 p 的后继。
2. 将 p 的指针指向 s。

单链表的删除操作

删除位置 p 之后的节点 q：

q = p->next;

p->next = q->next;

1. 将 q 定位为 p 的后继节点。
2. 修改 p 的指针，使其跳过 q。

效率

插入和删除只需修改指针，时间复杂度为 $O(1)$，不需要移动数据。