线性表的基本 *** 作:顺序表、(单) 链表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:合并两个有序表:逐一比较两表当前元素,将正确的元素添加进结果表并移动游标
在做了在做了
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)