【数据结构与算法分析】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;
}
相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
26 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
20 0
数据结构与算法学习十四:常用排序算法总结和对比
|
1月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
30 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
20 0
|
17天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
91 9
|
8天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
16 1
|
10天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。