数据结构与算法01----线性表

Key 1：线性表是指各数据元素间保持“1对1”关系的数据结构
Key 2：线性表分为顺序表(数组)和链表，分别通过元素相邻和保存指针域的方式来实现“1对1”

查找(定位)元素：按值查找

• 给定长度为 n 的线性表，查找值为 v 的元素
• (最坏)从头到尾遍历 => 时间复杂度O(n)
  

顺序表新增 / 删除元素

• 给定长度为 n 的顺序表，在指定位置 i 插入一个新元素

• 给定长度为 n 的顺序表，删除位置 i 的元素
  

• 需要将位置 i 到位置 n - 1的所有元素都向后或向前挪一格

• 在最坏情况(i = 0)下，需要挪动全部的 n 个元素 => 时间复杂度为O(n)

• 无需利用额外空间 => 空间复杂度为O(1)

(单)链表新增元素

• 给定长度为 n 的顺序表，在第 i 个节点插入一个新元素
  
  
  

• 首先需要从头结点开始逐个向后找 i - 1次 => 时间复杂度为O(n)

• 找到后插入只需要修改第 i - 1个结点和待插入节点的 [后继结点地址] 即可 => O(1)

• 无需利用额外空间 => 空间复杂度为O(1)

(单)链表删除元素

• 给定长度为 n 的单链表，删除第 i 个结点

• 需要移动到第 i 个结点的前驱结点，最坏情况下移动 n - 1次 => 时间复杂度为O(n)

• 修改前驱结点的后继指针 => O(1)

• 无需利用额外空间 => 空间复杂度为O(1)

顺序表更新元素

• 给定长度为 n 的顺序表，更新位置 i 的元素

• 无论 i 的值如何，都可以通过 i 直接访问位置 i 的元素，将其更新为 v’ => 时间复杂度为O(1) => 随机存取

(单)链表更新元素

• 给定长度为 n 的 (单)链表，更新第 i 个结点的值
• 需要从头结点开始按顺序找到第 i 个结点才能访问并更新它 => 顺序存取
• 最坏情况遍历整个链表 => 时间复杂度为 O(n)

Key 1：顺序表中增加和删除一个元素将导致该位置后的元素前移或后移，复杂度为O(n)
Key 2：单链表增加和删除元素虽然不用移动元素，但需先找到其前驱结点，复杂度为O(n)
Key 3：若线性表需要频繁更新元素 -> 选择用顺序表实现（数组）
Key 4：若线性表需要频繁插入删除元素 -> 选择用链式表实现

线性表的集合式合并：只合并不同元素

• 设A表长度为n，B表长度为m
• 对于B表中的每个元素，都需要先判断其是否已经存在A里 => O(mn)
• 如果存在，无需插入，如果不存在，将其插入在A的末尾 => O(1)
• 总时间复杂度为 O(mn)
• 空间复杂度：顺序表 O(m + n) 链表 O(1)

合并两个有序表：本来分别有序，合并结果仍然有序

合并两个有序顺序表

• 设A表长度为n，B表长度为m
• 先预留结果表空间：n + m个元素
• 从表头开始同时逐个访问A表和B表元素，将当前位置上较小者放入结果表并后移一位
• 总时间复杂度为 O(m + n)
• 空间复杂度为 O(m + n)

合并两个有序单链表

注意：

一直重复上图操作

• 设A表长度为n，B表长度为m
• 先创建一个头结点(哑结点dummy)，其数据没有实际意义，只为用它的指针域
• 从表头开始逐个同时遍历A和B，将当前已完成合并的表尾元素的后继结点设置为当前A和B游标中较小的一个，并将该游标向后移动一位
• 时间复杂度为 O(m + n)
• 空间复杂度为 O(1)

Key 1：合并两个有序表：逐一比较两表当前元素，将正确的元素添加进结果表并移动游标

在做了在做了