【数据结构与算法分析】0基础带你学数据结构与算法分析02--表(List)

简介: 笔记

前言


Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.


— Stan Kelly-Bootle


表 (List)


我们将形如 a0,a1,a2,⋯ ,aN−1 组成的有限序列称为 list,这个 list 的大小是 N(N∈N),我们将大小为 0 的表称之为 空表 (empty list)。


除空表外的任何表,我们从 0 开始标记元素,最后一个元素的下标为 N−1 ,那么第 i(i∈N∗)个元素是 ai−1,称 ai 是 ai+1 的 前驱 , ai 是 ai−1 的 后继 。


注意:严蔚敏老师的数据结构中,第 i(i∈N∗) 个元素是 ai


List ADT

template <class T, class Iter>
concept sequence_container =
    requires(T a, const T& b, typename T::const_iterator pos,
             Iter first, Iter last,
             typename T::iterator self_first, typename T::iterator self_last,
             size_type count, const typename T::value_type& value) {
    requires container<T>;
    requires input_iterator<Iter>;
    // iterator
    { a.rbegin() } -> typename T::reverse_iterator;
    { a.rend() } -> typename T::reverse_iterator;
    { b.rbegin() } -> typename T::const_reverse_iterator;
    { b.rend() } -> typename T::const_reverse_iterator;
    { a.crbegin() } -> typename T::const_reverse_iterator;
    { a.crend() } -> typename T::const_reverse_iterator;
    // access
    { a.front() } -> typename T::reference;
    { b.front() } -> typename T::const_reference;
    { a.back() } -> typename T::reference;
    { b.back() } -> typename T::const_reference;
    // capacity
    a.resize(count, value);
    // modifier
    { a.insert(pos, value) } -> typename T::iterator;
    { a.insert(pos, count, value) } -> typename T::iterator;
    { a.insert(pos, first, last) } -> typename T::iterator;
    { a.erase(pos) } -> typename T::iterator;
    { a.erase(self_first, self_last) } -> typename T::iterator;
    a.push_front(value);
    a.pop_front();
    a.push_back(value);
    a.pop_back();
};

19.png

线性表的实现

顺序实现

对表的所有操作都可以使用数组实现。数组是静态分配的,无法扩容,常常使用动态分配一段数组,当容量不够时进行生长。可以生长意味着不需要对表的大小的最大值进行估计。


在生长过程中,需要线性表分配一个全新的数组,并将之前的所有元素复制进新的数组中,复制完毕后将原数组释放。因此如果你的线性表频繁要求生长,那么会导致严重的性能开销,因为每次都需要 Θ(N) 来复制每个元素。如果生长系数过大,比如说 100 倍,但是无法使用那么多时,将造成存储空间的大量浪费。因此生长一般选取 2 倍 或 1.5 倍 比例,保证不会过于频繁生长,并使存储空间由不会浪费太多。


下图就是我们根据数组对线性表的实现:

20.png

现在思考一个问题,在使用 ADT *_back 与 *_front 时,它们两个有没有差别。


*_back 操作时直接将元素在尾端加入或移除,时间复杂度 Θ(1)

*_front 操作时,由于 push 操作导致前端没有位置可以存储元素,而 pop 操作将导致前端产生一个空缺,因此它们都需要将之后的元素集体后移或前移,时间复杂度 Θ(N)

我们尝试给出一个存储结构,如下。这里并没有采用传统的使用整型变量记录当前长度和分配的容量,而是采用三个指针。其中 start 是该 container 的基址, finish 是后随最后一个元素的指针, end 则是后随数组空间的指针。因此在计算当前长度时只需要 finish−start 即可,当finish=start 意味着当前线性表为空,当 finish=end 时意味着当前线性边需要生长。


template <class Element>
struct SequenceList {
  Element* start;
  Element* finish;
  Element* end;
};

这里存储结构中并没有给出迭代器,这是因为这是一个数组结构,我们可以将指针当作迭代器使用,这个迭代器是符合 contiguous_iterator 的。因此在实现该结构时,我们可以为其提供随即访问的接口 – operator[] 和 at ,它们接收一个 size_type 类型参数 n 用以 Θ(1) 时间复杂度访问 start+n 的元素。


在使用顺序实现时,应该注意其支持快速的随机访问能力,在尾部具有高效操作,但中间或头部操作很低效。


单链表实现

为了避免插入和删除的线性开销,我们允许线性表可以不连续存储,以避免修改时的整体移动。这种方式被称之为 链表 (linked list),linked list 由一系列在内存中不必连续的结点组成,每个结点均含有元素域和到指向后继结点的链域。该链的最后一个结点置空 (nullptr 或 NULL) 以避免不必要的麻烦。

21.png

由于这样的 linked list 是单向的,因此我们也称其为单链表。由于结点是单向 Traverse 的,我们无法向前 Traverse,因此单链表 iterator 是一个 forward_iterator 。但这也造成了一点点麻烦,我们失去了随机访问元素的能力,只能以 O(N) 的复杂度进行结点的访问,除非你已经拥有了该结点的迭代器。当你拥有一个结点的迭代器时,可以以 O(1) 的时间复杂度对其进行操作,删除或插入一个结点。

22.png

如何获取到单链表的长度呢?如果增加一个额外的长度域,对于这些结点来说是不必要的,我们只需要一个记录长度的域就好;而在结点中增加域不止造成了内存的浪费,如果用此记录长度,在对结点操作时,我们将丢失正确的长度信息,除非以 O(N)\mathcal{O}(N)O(N) 的代价修改所有结点上的长度域。我们引入一个特殊的头结点,每个线性表实例只需要一个 head 即可。为了快速在尾部进行插入,我们也需要一个指向尾部的域,方便插入操作,移除操作只能由缓慢的 Traverse 找到前驱结点

23.png

最后说明一下 end 迭代器指向 nullptr 的原因,由于我们在遍历时,认为区间是 [first,last) ,因此如果是有 finish field 作为 end 迭代器,那么我们将丢失最后一个结点。


单链表的存储结构


这里的实现使用了 BaseNode ,并在实现 Head 和 Node 时分别继承 BaseNode。由于 BaseNode 只实现关于链表链域的操作,虽然 Head 和 Node 有着不同的操作,但共享其 base class 所提供的链域操作。


struct ForwardListBaseNode { // 单链表基础结点,用于存储并处理链域
  ForwardListBaseNode* next;
};
struct ForwardListHead : ForwardListBaseNode { // 单链表的头结点,用于存储长度与尾结点
  size_t size;
  ForwardListBaseNode* finish;
};
template <class Element>
struct ForwardListNode : ForwardListBaseNode { // 单链表的结点,用于存储真正的数据
  Element value;
};

单链表 BaseNode 的实现


刚刚说了 BaseNode 主要实现对链域的操作,对一个结点,主要有插入、移除结点两种操作。受限于 forward_iterator ,为了运行效率,我们对 ADT 的插入删除进行一些修改。24.png

可以看到修改后,函数主要将该位置 pos 之后的元素进行删除,因此我们可以实现以下四个函数,用以对 insert 与 erase 的支持。但是 erase 与 insert 中都没有实现对边界条件的判定,这应该由具体实现 ForwardList 时完成。


// 将 node 插入到 pos 之后
void insert(ForwardListBaseNode* pos, ForwardListBaseNode* node) {
  node->next = pos->next;
  pos->next = node;
}
// 由实现范围 [first, last) 上迭代器到单链表的构造,接收单链表 [first, last) 并插入
void insert(ForwardListBaseNode* pos,
            ForwardListBaseNode* first, ForwardListBaseNode* last) {
  last->next = pos->next;
  pos->next = first;
}
// 移除 pos 之后一个的元素,并将其返回
ForwardListBaseNode* erase(ForwardListBaseNode* pos) {
  ForwardListBaseNode* erase = pos->next;
  pos->next = erase->next;
  return erase;
}
// 移除 [first + 1, last) 的所有元素,并将其 first + 1 返回
ForwardListBaseNode* erase(ForwardListBaseNode* first, ForwardListBaseNode* last) {
  ForwardListBaseNode* erase = first->next;
  first->next = last;
  return erase;
}


对于以上的代码进行分析,我们可以得知,一旦位置、端结点确定,从 linked list 中添加或移除任意多的连续结点,其时间复杂度是 O(1) 的。至于构造和析构 [first,last) 上的元素,不再 BaseNode 的讨论范围内,它们不是针对链域的操作。


需要注意的是,我们在实现 erase 的过程中并没有删除 erase 结点指向的 next,也就是说虽然它已经不在链表中,但是通过访问其 next field 依然可以访问曾经的后继。这一操作主要是为了释放结点,erase 移除 (first,last) 后将返回 first 结点的后继,即第一个被移除的结点,我们可以依次对这些结点进行释放,直到准备释放的结点变为 last 为止。当然我们也可以将其设置为 nullptr,只不过判断条件变为了 node!=nullptr ,不过不修改也能完成这样的操作且开销更小。


双链表

单链表如果要删除当前结点,则必须遍历寻找该结点的前驱,才能将其删除。这种方法时间复杂度变成了线性,有什么方法可以让我们更快的查找该结点的前驱吗?既然链表可以指向其后继,那么在其中添加一个前驱域即可,在结点添加进链表时,只需要分别设置结点的前驱与后继即可。这种有两个指针域,一个指向前驱一个指向后继的 linked list 被称之为 双链表。

25.png

对于增加元素与删除元素,与单链表类似。不过需要注意的是,在修改时需要将目标结点的前驱、后继的指针域都加以处理,不然就会出现很多问题。


无论使用单链表还是双链表,我们都可以高效的在序列中进行插入和删除操作,不再需要这些不必要的拷贝,且不存在生长问题。但随之而来的是对数据访问的限制,我们失去了随机访问能力。


边界条件


在双链表的实现过程中需要小心处理边界条件, 请小心 代码 node->next->prev = node->prev 和 node->prev->next = node->next ,如果你释放的是最后一个结点或第一个结点,那么 node->next 或 node->prev 将等于 nullptr,而 nullptr 没有 prev 和 next 域供你使用,更不能被修改!这将直接导致程序发生错误。


这个问题同样可以在单链表中出现。但我们的单链表实现将删除 pos 的后继,实现中我们可以首先判断 pos 是不是最后一个结点,如果是的话将不进入 BaseNode 处理。那双链表可以吗?好像并不可以,因为它删除的是当前结点,如果当前结点为最后一个结点,那我们需要在 BaseNode 中添加额外的代码处理这种情况。


没有办法处理了吗?当然是有的,我们的链表实现中还有 head 供第一个结点缓冲;因此只有最后一个结点有问题,那我们为最后一个结点添加一个后随结点就好了!后随结点永远不会被删除,且可以为最后一个结点提供缓冲,防止其修改 nullptr 引发程序错误。那这个后随结点从那里产生呢,还记得我们的 Head 结点吗?它继承了 BaseNode,完全可以当作一个结点使用,这时候 Head 就不再需要其中的 finish 域了。

26.png

这样首尾相接的链表被称为之 循环链表 。左边是一个 size=7 的循环链表;右边是一个 size=0 时的循环链表,这个空表所有迭代器都指向 haed,当 traverse 时循环条件 begin≠end 或rbegin≠rend 都不会成功,traverse 直接结束,因此对循环链表的遍历并不会产生任何问题。


双链表的存储结构


双链表的存储结构相比于单链表,只需要给 BaseNode 中添加另一个指针域,并删除 Head 中的无用 finish 即可。

struct BidirectionalListBaseNode {
  BidirectionalListBaseNode* prev;
  BidirectionalListBaseNode* next;
};
struct ForwardListHead : BidirectionalListBaseNode { size_t size; };
template <class Element>
struct BidirectionalListNode : BidirectionalListBaseNode { Element value; };

双链表的 BaseNode 实现


我们可以 O(1) 的访问结点的前驱,因此按照 ADT 的要求来实现相关的插入与移除。同样地,我们在 BaseNode 中仅处理最核心的链域的修改。


// 将 node 插入到 pos 之前
void insert(BidirectionalListBaseNode* pos, BidirectionalListBaseNode* node) {
  node->prev = pos->prev;
  node->next = pos;
  node->prev->next = node->next->prev = node;
}
// 将 [first, last) 插入到 pos 之前,并将 first - 1 与 last 重新连接
void insert(BidirectionalListBaseNode* pos,
            BidirectionalListBaseNode* first, BidirectionalListBaseNode* last) {
  BidirectionalListBaseNode* first_prev = first->prev;
  first->prev->next = last;
  last->prev->next = pos;
  pos->prev->next = first;
  first->prev = pos->prev;
  pos->prev = last->prev;
  last->prev = first_prev;
}
// 移除 pos 并将 pos 的后继返回
BidirectionalListBaseNode* erase(BidirectionalListBaseNode* pos) {
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  return pos->next;
}
// 移除 [first, last) 的所有元素
void erase(ForwardListBaseNode* first, ForwardListBaseNode* last) {
  first->prev->next = last;
  last->prev = first->prev;
}


一些关于表的算法

为了屏蔽一些不必要的实现细节,因此我们约定,使用 iterator 进行 traverse,且 iterator 可以通过 handle 取得底层的链表结点。而函数参数中的引用类型 T& 则表示着对该形式参数的修改将会修改实际参数。


合并两个已排序链表

现在假设两个链表都已按照从小到大排列,将两个链表 a 与 b 合并到 c,且合并后的链表也按照从小到大进行排列。


void __transfer(iterator& pos, iterator& c) {
  iterator it = pos++;
  insert(c.handle(), it.handle(), pos.handle());
}
void merge(iterator a_begin, iterator a_end, iterator b_begin, iterator b_end, iterator& c) {
  while (a_begin != a_end && b_begin != b_end) {
    __transfer(*a_begin < *b_begin ? a_begin : b_begin, c);
  }
  if (a_begin != a_end) {
    insert(c.handle(), a_begin.handle(), a_end.handle());
  }
  if (b_begin != b_end) {
    insert(c.handle(), b_begin.handle(), b_end.handle());
  }
}


引入了 __transfer 函数将找到的 a、b 当前最小的元素插入 c 中,并使其迭代器向前步进一。在 a 或 b 结束之后,我们将 a 或 b 剩余的元素全部添加到 c 的后面,这些元素是最大的一批。分析该算法的时间复杂度得 O(sizea+sizeb−1) 。


反转

反转链表是一个很有意思的操作,尤其是针对没有前驱结点的单链表来说。


void reverse(ForwardListBaseNode* head) {
  ForwardListBaseNode* curr = head->next;
  head = nullptr;
  while (curr != nullptr) {
    ListNode* next = curr->next;
    curr->next = head;
    head = curr;
    curr = next;
  }
}

这个方法直接使用到了 ForwardListHead ,利用 head 指向当前结点的前驱,当 traverse 完成后,head 也顺利指向最终结果。其时间复杂度 O(N) 。我们可以将其改为递归方式,时间复杂度不变:


ForwardListBaseNode* __recursion(ForwardListBaseNode* node, ForwardListBaseNode* head) {
  if (!node) {
    return nullptr;
  }
  if (node->next == nullptr) {
    head->next = node;
    return nullptr;
  }
  ForwardListBaseNode* tmp = __recursion(node->next);
  node->next->next = node;
  node->next = nullptr;
  return tmp;
}
void reverse(ForwardListBaseNode* head) {
  __recursion(head->next, head);
}


双链表的操作也很精彩!由于实现是循环的,因此我们只需要将每个结点的前驱后继按顺序调换位置即可。其时间复杂度同样是 O(N)

void reverse(BidirectionalListBaseNode* head) {
  BidirectionalListBaseNode* curr = head->next,* temp;
  while (curr != head) {
    temp = curr->next;
    curr->next = curr->prev;
    curr = curr->prev = temp;
  }
  temp = head->next;
  head->next = head->prev;
  head->prev = temp;
}
相关文章
|
22天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
59 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
26天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
19 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
19天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
30 4
|
26天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
17 0
数据结构与算法学习十四:常用排序算法总结和对比
|
26天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
26 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
25天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
26天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
3天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
50 9
|
2天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
21 4
|
26天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器