前言
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(); };
线性表的实现
顺序实现
对表的所有操作都可以使用数组实现。数组是静态分配的,无法扩容,常常使用动态分配一段数组,当容量不够时进行生长。可以生长意味着不需要对表的大小的最大值进行估计。
在生长过程中,需要线性表分配一个全新的数组,并将之前的所有元素复制进新的数组中,复制完毕后将原数组释放。因此如果你的线性表频繁要求生长,那么会导致严重的性能开销,因为每次都需要 Θ(N) 来复制每个元素。如果生长系数过大,比如说 100 倍,但是无法使用那么多时,将造成存储空间的大量浪费。因此生长一般选取 2 倍 或 1.5 倍 比例,保证不会过于频繁生长,并使存储空间由不会浪费太多。
下图就是我们根据数组对线性表的实现:
现在思考一个问题,在使用 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) 以避免不必要的麻烦。
由于这样的 linked list 是单向的,因此我们也称其为单链表。由于结点是单向 Traverse 的,我们无法向前 Traverse,因此单链表 iterator 是一个 forward_iterator 。但这也造成了一点点麻烦,我们失去了随机访问元素的能力,只能以 O(N) 的复杂度进行结点的访问,除非你已经拥有了该结点的迭代器。当你拥有一个结点的迭代器时,可以以 O(1) 的时间复杂度对其进行操作,删除或插入一个结点。
如何获取到单链表的长度呢?如果增加一个额外的长度域,对于这些结点来说是不必要的,我们只需要一个记录长度的域就好;而在结点中增加域不止造成了内存的浪费,如果用此记录长度,在对结点操作时,我们将丢失正确的长度信息,除非以 O(N)\mathcal{O}(N)O(N) 的代价修改所有结点上的长度域。我们引入一个特殊的头结点,每个线性表实例只需要一个 head 即可。为了快速在尾部进行插入,我们也需要一个指向尾部的域,方便插入操作,移除操作只能由缓慢的 Traverse 找到前驱结点
最后说明一下 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 的插入删除进行一些修改。
可以看到修改后,函数主要将该位置 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 被称之为 双链表。
对于增加元素与删除元素,与单链表类似。不过需要注意的是,在修改时需要将目标结点的前驱、后继的指针域都加以处理,不然就会出现很多问题。
无论使用单链表还是双链表,我们都可以高效的在序列中进行插入和删除操作,不再需要这些不必要的拷贝,且不存在生长问题。但随之而来的是对数据访问的限制,我们失去了随机访问能力。
边界条件
在双链表的实现过程中需要小心处理边界条件, 请小心 代码 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 域了。
这样首尾相接的链表被称为之 循环链表 。左边是一个 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; }