Java 后端2026-05-14 · 1 min

数据结构二

#数据结构

一、线性表的定义与逻辑特征

线性表是由 n (n≥0) 个数据元素组成的有限序列。
数据元素之间存在一对一的逻辑关系。
除第一个元素无前驱、最后一个元素无后继外，其余每个元素有且仅有一个直接前驱和一个直接后继。

二、顺序表（顺序存储结构）

1. 存储特点

物理地址连续：逻辑上相邻的元素在物理存储位置上也一定相邻。
随机存取：知道首地址和元素序号即可直接计算出任一元素的存储地址，时间复杂度为 O(1)，因此顺序表被称为随机存取的数据结构。

2. 地址计算

若首地址为 LOC(a₁)，每个元素占用 k 个存储单元，则第 i 个元素的地址为：

LOC(aᵢ) = LOC(a₁) + (i-1) × k

举例（对应第10题）：
首地址100，元素长度2，则第5个元素地址 = 100 + (5-1)×2 = 108。

3. 插入操作

在长度为 n 的顺序表第 i 个位置（1 ≤ i ≤ n+1）插入新元素时，需要将第 i 到第 n 个元素向后移动。
需移动的元素个数：n - i + 1。
平均移动次数：当插入位置等概率时，平均需移动 n/2 个元素，即表中一半的元素。
时间复杂度：O(n)。

举例（对应第8题）：
向长度为 n 的向量第 i 个元素之前插入，向后移动 n - i + 1 个元素。

4. 删除操作

删除长度为 n 的顺序表第 i 个元素（1 ≤ i ≤ n）时，需要将第 i+1 到第 n 个元素向前移动。
需移动的元素个数：n - i。
平均移动次数：等概率下，平均移动 (n-1)/2 个元素，与表长有关。
时间复杂度：O(n)。

注意区分：插入时移动 n-i+1；删除时移动 n-i（你曾在此误填为 n-1）。

5. 顺序表操作时间复杂度汇总

随机访问（按序号查找）：O(1)
插入、删除：平均 O(n)
按值查找：O(n)

三、链表（链式存储结构）

1. 存储特点

不需要连续的内存空间：用指针将各个结点链接起来，逻辑上相邻的元素物理位置不一定相邻。
每个结点包含两部分：
- 数据域：存放结点值。
- 指针域（链域）：存放直接后继（或前驱）结点的地址。
内存中可用存储单元的地址连续或不连续都可以。

2. 基本性质

链表是采用链式存储结构的线性表。
除首元结点外，任一结点的存储位置由其**直接前驱结点的指针域（链域）**指示。
链表不支持随机存取，访问第 i 个元素需从头遍历，时间复杂度为 O(n)。

3. 删除结点操作的时间复杂度

在单链表中删除已知结点 *p，必须知道其前驱结点的地址才能修改指针，因此需要先遍历找到前驱。
最坏情况下需遍历整个链表，时间复杂度为 O(n)。
若题目中是“删除已知结点的后继”或“已知前驱结点的删除”，则修改指针即可，时间复杂度为 O(1)。

四、时间复杂度通用分析思路（线性表篇）

虽然本试卷未单独出大段程序分析，但时间复杂度思想贯穿始终。对于线性表操作，可直接按以下逻辑判断：

观察操作是否需要“移动元素”或“遍历”：
- 若可通过下标直接计算地址（随机存取），则为 O(1)。
- 若与数据规模 n 成正比（如移动一半元素、遍历整表），则为 O(n)。
平均移动次数的推导（通用解法）：
- 插入：在 n+1 个可能位置等概率插入，第 i 个位置需移动 n-i+1 个元素。
  平均次数 = [∑(n-i+1)] / (n+1) = [(n)+(n-1)+...+1+0] / (n+1) = n(n+1)/2 / (n+1) = n/2。
- 删除：在 n 个元素中等概率删除，删除第 i 个需移动 n-i 个。
  平均次数 = [∑(n-i)] / n = [(n-1)+(n-2)+...+1+0] / n = n(n-1)/2 / n = (n-1)/2 ≈ n/2。
链表遍历与找前驱：
- 单链表找第 i 个结点：需从表头移动 i-1 次指针，时间复杂度 O(n)。
- 删除已知结点 *p 时，由于单链表无法直接获得前驱，必须从表头开始查找，时间 O(n)。

五、易错点自查清单

顺序表物理地址一定连续，链表物理地址不一定连续。
顺序表是随机存取结构，存取时间 O(1)。
插入时移动 n-i+1，删除时移动 n-i，别混淆。
移动元素的个数与表长和插入/删除位置有关。
单链表中，结点存储位置由前驱结点的指针域指示。
删除单链表已知结点 *p 需要前驱，时间复杂度是 O(n)，不是 O(1)。