一、线性表的定义与逻辑结构
1.1 线性表的基本概念
- 定义：线性表是具有相同特性数据元素的一个有限序列，逻辑结构表示为 (a₀, a₁, ..., aᵢ, ..., aₙ₋₁)
- 三大特性：
-
- 所有数据元素类型相同
-
- 元素个数有限
-
- 每个元素有唯一序号（从 0 开始）
- 逻辑序号约定：为方便算法设计，逻辑序号与存储序号统一从 0 开始，n 个元素的序号范围为 0≤i≤n-1
1.2 线性表的抽象数据类型（ADT）
ADT List {
数据对象：D = {aᵢ | 0≤i≤n-1, n≥0, aᵢ为E类型}
数据关系：r = {<aᵢ, aᵢ₊₁> | aᵢ, aᵢ₊₁∈D, i=0,1,...,n-2}
基本运算（11个）：
void CreateList(E[] a); // 由数组创建线性表
void Add(E e); // 末尾添加元素
int size(); // 求表长
void Setsize(int nlen); // 设置表长
E GetElem(int i); // 获取序号i的元素
void SetElem(int i, E e); // 设置序号i的元素
int GetNo(E e); // 查找元素e的序号
void swap(int i, int j); // 交换序号i和j的元素
void Insert(int i, E e); // 在i位置插入元素
void Delete(int i); // 删除i位置的元素
String toString(); // 线性表转字符串
}
二、线性表的顺序存储结构（顺序表）
2.1 顺序表的存储结构
- 物理实现：用数组data存储元素，size记录当前长度，capacity为数组容量
- 核心类定义：
public class SqListClass<E> {
final int initcapacity = 10; // 初始容量
public E[] data; // 存储元素的数组
public int size; // 当前表长
private int capacity; // 数组容量
public SqListClass() { // 构造方法
data = (E[]) new Object[initcapacity];
capacity = initcapacity;
size = 0;
}
// 其他方法...
}
2.2 顺序表基本运算的实现
2.2.1 核心辅助方法：动态扩容
private void updatecapacity(int newcapacity) {
E[] newdata = (E[]) new Object[newcapacity];
for (int i=0; i<size; i++) { // 复制原数组元素
newdata[i] = data[i];
}
data = newdata; // 切换到新数组
capacity = newcapacity; // 更新容量
}
- 作用：当插入导致空间不足时扩容，或删除后空间浪费时缩容
2.2.2 插入操作：Insert (int i, E e)
public void Insert(int i, E e) {
if (i<0 || i>size) { // 检查位置合法性
throw new IllegalArgumentException("插入位置非法");
}
if (size == capacity) { // 空间满时扩容
updatecapacity(2 * size);
}
for (int j=size; j>i; j--) { // 元素后移
data[j] = data[j-1];
}
data[i] = e; // 插入元素
size++; // 表长+1
}
- 时间复杂度：平均 O (n)，最坏情况（i=0）移动 n 次元素
2.2.3 删除操作：Delete (int i)
public void Delete(int i) {
if (i<0 || i>=size) { // 检查位置合法性
throw new IllegalArgumentException("删除位置非法");
}
for (int j=i; j<size-1; j++) { // 元素前移
data[j] = data[j+1];
}
size--; // 表长-1
// 缩容条件：容量>初始容量且长度≤容量/4
if (capacity > initcapacity && size == capacity/4) {
updatecapacity(capacity/2);
}
}
- 时间复杂度：平均 O (n)，最坏情况（i=0）移动 n-1 次元素
2.2.4 其他基本运算
- 末尾添加元素：Add(E e)
public void Add(E e) {
if (size == capacity) {
updatecapacity(2 * size); // 扩容
}
data[size++] = e; // 直接添加到末尾
}
- 获取元素：GetElem(int i)
public E GetElem(int i) {
if (i<0 || i>=size) {
throw new IllegalArgumentException("位置非法");
}
return data[i];
}
三、顺序表的典型应用算法
3.1 元素逆置算法
public static void Reverse(SqListClass<Integer> L) {
int i = 0, j = L.size() - 1; // 双指针指向首尾
while (i < j) {
L.swap(i, j); // 交换元素
i++; j--; // 指针移动
}
}
- 核心思想：双指针从两端向中间移动，交换对称位置元素
- 时间复杂度：O (n)，空间复杂度：O (1)
3.2 删除所有值为 x 的元素（三种解法）
解法 3：区间划分法（最高效）
public static void Deletex3(SqListClass<Integer> L, Integer x) {
int i = -1, j = 0; // i指向非x区间末尾，j遍历全表
while (j < L.size()) {
if (!L.GetElem(j).equals(x)) { // 找到非x元素
i++; // 扩展非x区间
if (i != j) {
L.swap(i, j); // 交换到正确位置
}
}
j++;
}
L.Setsize(i + 1); // 重置表长
}
- 核心思想：将表划分为 "非 x 元素区间" 和 "x 元素区间"，通过交换实现删除
- 时间复杂度：O (n)，仅一次遍历
3.3 两个有序表合并（二路归并）
public static SqListClass<Integer> Merge2(SqListClass<Integer> A, SqListClass<Integer> B) {
SqListClass<Integer> C = new SqListClass<>();
int i = 0, j = 0; // i,j分别遍历A和B
while (i < A.size() && j < B.size()) {
if (A.GetElem(i) < B.GetElem(j)) {
C.Add(A.GetElem(i++)); // 取A中较小元素
} else {
C.Add(B.GetElem(j++)); // 取B中较小元素
}
}
// 处理剩余元素
while (i < A.size()) C.Add(A.GetElem(i++));
while (j < B.size()) C.Add(B.GetElem(j++));
return C;
}
- 时间复杂度：O (n+m)，每个元素仅访问一次
- 比较次数：最好情况 MIN (n,m)，最坏情况 n+m-1
3.4 考研真题：求两个等长有序序列的中位数
public static int findMedian(int[] A, int[] B, int n) {
int i = 0, j = 0, k = 0; // k记录已归并元素个数
while (i < n && j < n) {
k++;
if (A[i] < B[j]) {
if (k == n) return A[i]; // 找到第n个元素（中位数）
i++;
} else {
if (k == n) return B[j];
j++;
}
}
return i < n ? A[i] : B[j]; // 理论上不会执行
}
- 核心思想：归并时只遍历到第 n 个元素，无需合并整个序列
- 时间复杂度：O (n)，空间复杂度：O (1)
四、ArrayList 容器的应用
4.1 ArrayList 常用方法
- 构造方法：
ArrayList<Integer> list1 = new ArrayList<>(); // 初始容量10
ArrayList<Integer> list2 = new ArrayList<>(20); // 指定初始容量
- 核心操作：
list.add(5); // 末尾添加元素
list.add(1, 10); // 在位置1插入元素
int val = list.get(2); // 获取位置2的元素
list.set(3, 15); // 修改位置3的元素
list.remove(4); // 删除位置4的元素
boolean contains = list.contains(20); // 判断是否包含元素
4.2 ArrayList 元素排序
4.2.1 基本类型排序
ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(5, 3, 8, 1, 2));
Collections.sort(nums); // 升序排序：[1,2,3,5,8]
Collections.sort(nums, Collections.reverseOrder()); // 降序排序：[8,5,3,2,1]
4.2.2 对象排序（三种方式）
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() { return name; }
public int getAge() { return age; }
@Override
public String toString() {
return "[" + name + "," + age + "]";
}
// 方式1：实现Comparable接口（按年龄升序）
@Override
public int compareTo(Student o) {
return this.age - o.age;
}
}
public class SortDemo {
public static void main(String[] args) {
ArrayList<Student> students = new ArrayList<>();
students.add(new Student("Tom", 18));
students.add(new Student("Alice", 20));
students.add(new Student("Bob", 18));
// 方式1：直接排序
Collections.sort(students);
System.out.println("按年龄升序: " + students);
// 方式2：自定义Comparator（按姓名升序）
Collections.sort(students, new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
return s1.getName().compareTo(s2.getName());
}
});
System.out.println("按姓名升序: " + students);
// 方式3：Java8 lambda（按姓名降序）
students.sort(Comparator.comparing(Student::getName).reversed());
System.out.println("按姓名降序: " + students);
}
}
五、扩展算法与期末考点
5.1 删除值在 [x,y] 之间的元素
public static void deleteRange(SqListClass<Integer> L, int x, int y) {
int i = -1, j = 0; // i指向非区间元素区，j遍历全表
while (j < L.size()) {
if (!(L.GetElem(j) >= x && L.GetElem(j) <= y)) { // 不在区间内的元素
i++;
if (i != j) {
L.swap(i, j); // 交换到正确位置
}
}
j++;
}
L.Setsize(i + 1); // 重置表长
}
- 时间复杂度：O (n)，空间复杂度：O (1)
5.2 有序表删除重复元素
public static void deleteDuplicates(SqListClass<Integer> L) {
if (L.size() <= 1) return; // 表长小于2时无需处理
int k = 1; // k记录非重复元素个数
for (int i = 1; i < L.size(); i++) {
if (!L.GetElem(i).equals(L.GetElem(k-1))) {
L.SetElem(k++, L.GetElem(i)); // 非重复元素前移
}
}
L.Setsize(k); // 重置表长
}
- 前提条件：表已按升序排列
- 时间复杂度：O(n)
5.3 期末高频考点总结
- 顺序表操作的时间复杂度：
- 插入 / 删除：平均 O (n)，均摊后插入为 O (1)（考虑扩容）
- 查找 / 修改：O (1)
- 核心算法思想：
- 双指针技术（逆置、归并）
- 区间划分法（删除指定元素）
- 二路归并（有序表合并）
- ArrayList 排序要点：
- Comparable接口用于类自身定义排序规则
- Comparator用于外部定制排序逻辑
- 多字段排序使用thenComparing链式调用
算法复杂度对比表
| 操作 | 顺序表时间复杂度 | 说明 |
| 初始化 | O(1) | 分配初始数组 |
| 末尾添加元素 | 均摊 O (1) | 最坏 O (n)（扩容时） |
| 任意位置插入 / 删除 | O(n) | 元素移动导致 |
| 按序号访问元素 | O(1) | 直接数组索引 |
| 按值查找元素 | O(n) | 顺序遍历比较 |
六、线性表典型例题
例题 1：顺序表元素逆置
问题描述
设计算法将顺序表 L 中的元素逆置。例如 L=(1,2,3,4,5)，逆置后为 (5,4,3,2,1)。
代码实现
public static void reverse(SqListClass<Integer> L) {
int i = 0, j = L.size() - 1; // 双指针指向首尾元素
while (i < j) {
L.swap(i, j); // 交换i和j位置的元素
i++; j--; // 指针向中间移动
}
}
例题 2：删除顺序表中所有值为 x 的元素
问题描述
设计算法删除顺序表 L 中所有值为 x 的元素。例如 L=(1,2,1,5,1)，x=1 时，删除后为 (2,5)。
代码实现（区间划分法）
public static void deleteAllX(SqListClass<Integer> L, Integer x) {
int i = -1, j = 0; // i指向非x区间末尾，j遍历全表
while (j < L.size()) {
if (!L.GetElem(j).equals(x)) { // 找到非x元素
i++;
if (i != j) {
L.swap(i, j); // 交换到正确位置
}
}
j++;
}
L.Setsize(i + 1); // 重置表长
}
例题 3：两个有序顺序表合并
问题描述
合并升序表 A=(1,3,5,8) 和 B=(2,3,8,10,11) 为升序表 C。
代码实现
public static SqListClass<Integer> mergeSortedLists(SqListClass<Integer> A, SqListClass<Integer> B) {
SqListClass<Integer> C = new SqListClass<>();
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
if (A.GetElem(i) < B.GetElem(j)) {
C.Add(A.GetElem(i++));
} else {
C.Add(B.GetElem(j++));
}
}
while (i < A.size()) C.Add(A.GetElem(i++));
while (j < B.size()) C.Add(B.GetElem(j++));
return C;
}
例题 4：考研真题 — 求两个有序序列的中位数
问题描述
两个等长升序序列 A 和 B，求合并后序列的中位数。例如 A=(11,13,15,17,19)，B=(2,4,6,8,20)，中位数为 11。
代码实现
public static int findMedian(int[] A, int[] B, int n) {
int i = 0, j = 0, k = 0;
while (i < n && j < n) {
k++;
if (A[i] < B[j]) {
if (k == n) return A[i];
i++;
} else {
if (k == n) return B[j];
j++;
}
}
return i < n ? A[i] : B[j];
}
例题 5：ArrayList 多字段排序
问题描述
对学生类按年龄升序、姓名降序排序。
代码实现
students.sort(Comparator.comparing(Student::getAge)
.thenComparing(Comparator.comparing(Student::getName).reversed()));
