第 2 章 线性表

Documentation Index

Fetch the complete documentation index at: https://0907.mintlify.app/llms.txt

Use this file to discover all available pages before exploring further.

​

线性表的定义

​

线性表的表示

​

顺序表

定义与结构图示

核心特征：逻辑顺序与其物理存储顺序完全一致

优缺点对比

主要优点

• 可进行随机访问，按索引查找速度快
• 存储密度高，不需要额外指针空间

主要缺点

• 插入和删除操作效率较低，需要移动大量元素
• 要求分配连续的存储空间，可能产生空间浪费或溢出

基本操作与时间复杂度

• 初始化：静态分配或动态分配
• 插入操作：
  • 最好情况：在尾部插入，$O(1)$
  • 最坏情况：在表头插入，$O(n)$
  • 平均情况：$O(n)$
• 删除操作：
  • 最好情况：删除表尾元素，$O(1)$
  • 最坏情况：删除表头元素，$O(n)$
  • 平均情况：$O(n)$
• 查找操作：
  • 按值查找：$O(n)$
  • 按索引查找：$O(1)$

常见算法题型（参考王道）

• 双指针：如王道 P20 05
• 倒置：如王道 P20 07、10
• Boyer–Moore 投票算法：如王道 P20 12
• 空间换时间：如王道 P21 13

​

链表

定义

数据元素的存储映像称为结点，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域

各类链表及操作复杂度

• 单链表
• 循环链表
• 双向链表
• 静态链表

• 求表长操作：$O(n)$
• 按序号查找节点：$O(n)$
• 按值查找表节点：$O(n)$
• 插入节点操作（含查找）：$O(n)$
• 删除节点操作（含查找）：$O(n)$
• 头插法建立单链表：$O(n)$
• 尾插法建立单链表：$O(n)$

尾结点的指针域指向头结点，形成环状结构适合处理需要反复遍历的场景

每个结点包含两个指针域，分别指向前驱和后继可以双向遍历，在已知结点位置时，插入和删除操作更为高效

借用一维数组来描述线性链表

• 含备用链
• 不含备用链

常见算法题型（参考王道）

• 快慢指针：用于找中点、判环等如王道 P44 15、16、17、20
• 公共节点：求两个链表的交点如王道 P43 05、P45 18
• 空间换时间：如王道 P45 19