数据结构:线性表——2.2 列表
本文最后更新于 762 天前,其中的信息可能已经有所发展或是发生改变。

2.2 列表


2.2.1 从向量到列表


不同数据结构内部的存储与组织方式各异,其操作接口的使用方式及时空性能也不尽相同。引入列表结构的目的在于弥补向量结构在解决某些应用问题时,在功能及性能方面的不足。二者之间的差异,表面上体现于对外的操作方式,但根源则在于其内部存储方式的不同。

从静态到动态

数据结构支持的操作,通常无非静态和动态两类:前者仅从中获取信息,后者则会修改数据结构的局部甚至整体。以基于数组实现的向量结构为例,其 size()get() 等静态操作均可在常数时间内完成,而 insert()remove() 等动态操作却都可能需要线性时间。究其原因,在于"各元素物理地址连续"的约定,此即所谓的"静态存储"策略。

基于上述策略,可在 $\mathcal{O}(1)$ 的时间内由秩确定向量元素的物理地址,但反过来,在添加(删除)元素之前(之后),又不得不移动 $\mathcal{O}(n)$ 个后继元素。可见,尽管如此可使静态操作的效率达到极致,但就动态操作而言,局部的修改可能引起大范围甚至整个数据结构的调整。

列表(list)结构尽管也要求各元素在逻辑上具有线性次序,但对其物理地址却未作任何限制。此即所谓"动态存储"策略。链表(linked list)就是一种典型的动态存储结构。其中的数据,分散为一系列称作节点(node)的单位,节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点, 只需在局部调整少量相关节点之间的指针。这就意味着,采用动态存储策略,至少可以大大降低动态操作的成本。

从秩到位置

改用以上动态存储策略之后,在提高动态操作效率的同时,却又不得不舍弃原静态存储策略中循秩访问的方式,从而造成静态操作性能的下降。

以采用动态存储策略的链表为例。尽管按照逻辑次序,每个数据元素依然具有秩这一指标,但为了访问秩为 r 的元素,我们只能顺着相邻元素之间的指针,从某一端出发。 逐个扫描各元素,经过 r 步选代后才能确定该元素的物理存储位置。这意味着,原先只需 $\mathcal{O}(1)$ 时间的静态操作,此时的复杂度也将线性正比于被访问元素的秩。在最坏情况下等于元素总数 $n$, 即便在各元素被访问概率相等的情况下,平均而言也需要 $\mathcal{O}(n)$ 时间。

对数据结构的访问方式,应与其存储策略相一致。此时,既然继续延用循秩访问的方式已非上策,就应更多地习惯于通过位置,来指代并访问动态存储结构中的数据元素。

与向量中秩的地位与功能类似,列表中的位置也是指代各数据元素的一个标识性指标,借助它可以得到元素的物理存储地址。各元素的位置,通常可表示和实现为联接于元素之间的指针或引用。因此,基于此类结构设计算法时,应更多地借助逻辑上相邻元素之间的位置索引,以实现对目标元素的快速定位和访问,并进而提高算法的整体效率。

列表

与向量一样,列表也是由具有线性逻辑次序的一组元素构成的集合。列表是链表结构的一般化推广,其中的元素称作节点(node),分别由特定的位置或链接指代。与向量一样,在元素之间也可定义前驱、直接前驱,以及后继、直接后继等关系。相对于任意元素,也有定义对应的前缀、后缀等子集。


2.2.2 接口


ADT 接口



ListNode 模板类


#include <iostream>
#include <cstdlib>
using namespace std;

typedef int Rank; //秩
#define ListNodePosi(T) ListNode<T>* //列表节点位置

template<typename T>
struct ListNode{  //列表节点模板类(以双向链表形式实现)
    // 成员
    T data;                //数值
    ListNodePosi(T) pred;  //前驱
    ListNodePosi(T) succ;  //后继
    // 构造函数
    ListNode(){}//针对header和trailer的构造
    ListNode(T e,ListNodePosi(T) p = NULL,ListNodePosi(T) s = NULL)
        :data(e),pred(p),succ(s){}//默认构造器
    // 操作接口
    ListNodePosi(T) insertAsPred(T const &e);//紧靠当前节点之前插入新节点
    ListNodePosi(T) insertAsSucc(T const &e);//紧随当前节点之后插入新节点
};

每个节点都存有数据对象 data。为保证叙述简洁,在不致歧义的前担下,将不再区分节点及其对应的 data 对象。此外,每个节点还设有指针 predsucc,分别指向其前驱和后继。 为了创建一个列表节点对象,只需根据所提供的参数,分别设置节点内部的各个变量。其中前驱、后继节点的位置指针若未子指定,则默认取作 NULL


List 模板类


template <typename T> class List{
private:
    //数据成员
    int _size;               //规模
    ListNodePosi(T) header;  //头哨兵
    ListNodePosi(T) trailer; //尾哨兵
    //头、首、末、尾节点的秩,可分别理解为-1、0、n-1、n

protected:
    //内部函数
    void init();   //列表创建时的初始化
    void copyNodes ( ListNodePosi(T) p, int n );  //复制列表中自p起始的n项
    void merge (ListNodePosi(T) p, int mid, int n);   //内置归并

public:
    //构造函数
    List() { init(); }  //默认构造
    List ( List<T> const& L);                 //整体复制列表L
    List ( List<T> const& L, Rank r, int n);  //复制列表L的自r项起始的n项
    List ( ListNodePosi(T) p,int n);          //复制列表中自p起始的n项

    //析构函数
    ~List();

    //其他接口函数

    //只读函数
    Rank size() const { return _size; }    //规模
    bool empty() const { return !_size; }  //判空
    T &operator[](Rank r) const;  //重载[],支持寻秩访问,效率低
    ListNodePosi(T) first() const { return header -> succ; }  //首节点位置
    ListNodePosi(T) last() const {return trailer -> pred; }   //尾节点位置
    bool valid(ListNodePosi(T) p)  //判断位置p是否合法
    { return p && (trailer != p) && (header != p); }  //将头、尾节点等同于NULL
    ListNodePosi(T) find ( T const& e) const                           
    { return find( e, _size, trailer); }                                //无序查找
    ListNodePosi(T) find( T const& e, int n, ListNodePosi(T) p) const;  //无序区间查找
    ListNodePosi(T) search( T const& e) const
    { return search( e, _size, trailer); }                                //有序查找
    ListNodePosi(T) search( T const& e, int n, ListNodePosi(T) p) const;  //有序区间查找
    ListNodePosi(T) selectMax (ListNodePosi(T) p, int n);                     //区间最大节点
    ListNodePosi(T) selectMax () {return selectMax( header -> succ, _size); }  //整体最大节点

    //可写入接口
    ListNodePosi(T) insertAsFirst (T const& e);               //将e当作首节点插入
    ListNodePosi(T) insertAsLast (T const& e);                //将e当作尾节点插入
    ListNodePosi(T) insertA (ListNodePosi(T) p, T const& e);  //将e当作p的后继插入
    ListNodePosi(T) insertB (ListNodePosi(T) p, T const& e);  //将e当作p的前驱插入
    void clear();  //列表清空
    T remove ( ListNodePosi(T) p );  //删除节点p
    int deduplicate();  //无序去重
    int uniquify();     //有序去重   
    void reverse();  //列表逆置
    void insertionSort (ListNodePosi(T) p, int n);    //插入排序
    void selectionSort ( ListNodePosi(T) p, int n );  //选择排序
    void mergeSort ( ListNodePosi(T)  p, int n );     //归并排序
    void mergeLists(ListNodePosi(T)  p, int n, List<T>& L, ListNodePosi(T) q, int m);               //归并两个链表
    void mergeLists( List<T> & L ) { mergeLists ( header -> succ, _size, L, L.header -> succ, L._size ); } //全列表归并

    //遍历
    void traverse(void (*)(T &)); //使用函数指针操作
    template <typename VST>
    void traverse(VST &); //使用函数对象操作
    template <typename VST>
    void traverse( VST &visit , ListNodePosi(T) r, ListNodePosi(T) l);

};  // List

2.2.3 初始化


头、尾节点


List 对象的内部组成及逻辑结构如图所示:

其中私有的头节点(header)和尾节点(trailer)始终存在,但对外并不可见。对外部可见的数据节点如果存在,则其中的第一个和最后一个节点分别称作首节点(first node)和末节点(last node)。

就内部结构而言,头节点紧邻于首节点之前,尾节点紧邻于末节点之后。这类经封装之后从外部不可见的节点,称作哨兵节点(sentinel node)。List 模板类中的 List::valid() 关于合法节点位置的判别准则可见,此处的两个哨兵节点从外部被等效地视作 NULL。设置哨兵节点之后,对于从外部可见的任一节点而言,其前驱和后继在列表内部都必然存在,故可简化算法的描述与实现。又如,为实现 first()last() 操作,只需直接返回 header -> succtrailer -> pred。此外更重要地,哨兵节点的引入,也使得相关算法不必再对各种边界退化情况做专门的处理,从而避免出错的可能。


默认构造


创建 List 对象时,默认构造方法将调用统一初始化过程 init(),在列表内部创建一对头、尾哨兵节点,并适当地设置其前驱、后继指针构成一个双向链表。

//列表初始化,在创建列表对象时统一调用
template<typename T>
void List<T>::init(){
    header = new ListNode<T>;   //创建头哨兵节点
    trailer = new ListNode<T>;  //创建尾哨兵节点
    header -> succ = trailer; header -> pred = NULL; 
    trailer -> pred = header; trailer -> succ = NULL;
    _size = 0;  //记录规模
}

解释

  • 如图,该链表对外的有效部分初始为空,哨兵节点对外不可见,此后引入新的节点,都将陆续插入到这一对哨兵节点中。

在列表的其它构造方法中,内部变量的初始化过程与此相同,因此都可统一调用 init() 过程。该过程仅涉及常数次基本操作,共需运行常数时间。


由秩到位置的转换


鉴于偶尔可能需要通过秩来指定列表节点,可通过重载操作符 [] 提供一个转换接口:

//重载下标操作符,以通过秩直接访问列表节点(虽方便,效率低,需慎用)
template <typename T>
T& List<T>::operator[] ( Rank r ) const{   //assert: 0 <= r < size
    ListNodePosi(T) p = first(); //从首节点出发
    while ( 0 < r-- ) p = p -> succ; //顺数第r个节点即是
    return p -> data; //目标节点,返回其中所存元素
}

解释

  • 为将任意指定的秩 r 转换为列表中对应的元素,可从首节点出发,顺着后继指针前进 r 步。

只要秩 r 合法, 该算法的正确性即一目了然。其中每步选代仅需常数时间,故该算法的总体运行时间应为 $\mathcal{O}(r + 1)$,线性正比于目标节点的秩。相对于向量同类接口的 $\mathcal{O}(1)$ 复杂度,列表的这一效率十分低下。


2.2.4 查找


无序列表的顺序查找


列表 ADT 针对整体和区间查找,重载了操作接口 find(e)find(e,p,n)。其中,前者作为特例,可以直接调用后者。因此,只需实现后一接口:

//无序区间查找
//在无序列表内节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者
template <typename T> 
ListNodePosi(T) List<T>::find ( T const &e, int n, ListNodePosi(T) p ) const {
    while (0 < n--) //(0 <= n <= rank(p) < _size)对于p的最近的n个前驱,从右向左
        if (e == (p = p -> pred) -> data) return p; //逐个比对,直至命中或范围越界
    return NULL; //p越出左边界意味着区间内不含e,查找失败
} //失败时,返回NULL

以上算法的思路及过程,与无序向量的顺序查找算法 Vector : :find() 相仿,故时间复杂度也应是 $\mathcal{O}(n)$,线性正比于查找区间的宽度。


有序列表的顺序查找


与有序向量可以借助二分查找不同,尽管有序列表中的节点已经在逻辑上单调。但本质上,其动态的存储策略,使得节点的物理地址与其逻辑次序无关,故无法进行有效的查询。

//有序区间查找
//在有序列表内节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者
template <typename T> 
ListNodePosi(T) List<T>::search ( T const &e, int n, ListNodePosi(T) p ) const {
    while (0 < n--) //(0 <= n <= rank(p) < _size)对于p的最近的n个前驱,从右向左
        if (((p = p -> pred) -> data) <= e) break;  //直接找到,或越界
    return p;
} //失败时,返回左边界的前驱,可能是header

2.2.5 插入和删除


前插入


将新元素 e 作为当前节点的前驱插至列表的过程:

//前插入
template <typename T> //将e紧靠当前节点之前插入于当前节点所属列表(设有哨兵头节点header)
ListNodePosi(T) ListNode<T>::insertAsPred ( T const &e ){
    ListNodePosi(T) x = new ListNode ( e, pred, this ); //创建新节点
    pred -> succ = x; pred = x; //设置正向链接
    return x; //返回新节点的位置
}

解释

  • 插入新节点之前, 列表局部的当前节点及其前驱如图(a)所示。
  • 该算法首先如图(b) 所示创建新节点 new,构造函数同时将其数据项置为 e,并令其后继链接 succ 指向当前节点,令其前驱链接 pred 指向当前节点的前驱节点。
  • 随后如图(c)所示,使 new 成为当前节点前驱节点的后继,使 new 成为当前节点的前驱(次序不能颠倒)。
  • 最终如图(d)所示,经过如此调整,新节点即被顺利地插至列表的这一局部。

注意

  • 列表规模记录的更新由上层调用者负责。
  • 得益于头哨兵节点的存在,即便当前节点为列表的首节点,其前驱也如图(a)所示必然存在,故不必另做特殊处理。

后插入


将新元素 e 作为当前节点的后继插至列表的过程:

//后插入
template <typename T> //将e紧随当前节点之后插入于当前节点所属列表(设有哨兵尾节点trailer)
ListNodePosi(T) ListNode<T>::insertAsSucc ( T const &e ){
    ListNodePosi(T) x = new ListNode ( e, this, succ ); //创建新节点
    succ -> pred = x; succ = x; //设置逆向链接
    return x; //返回新节点的位置
}

插入接口


为将节点插至列表,除了上述两种插入方法,我们可视具体要求的不同,额外提供以下大量接口:

//e当作首节点插入
template <typename T> ListNodePosi(T) List<T>::insertAsFirst ( T const &e )
{ _size ++; return header -> insertAsSucc ( e ); } 

//e当作末节点插入
template <typename T> ListNodePosi(T) List<T>::insertAsLast ( T const &e )
{ _size ++; return trailer -> insertAsPred ( e ); }

//e当作p的后继插入(After)
template <typename T> ListNodePosi(T) List<T>::insertA ( ListNodePosi(T) p, T const &e )
{ _size ++; return p -> insertAsSucc ( e ); } 

//e当作p的前驱插入(Before)
template <typename T> ListNodePosi(T) List<T>::insertB ( ListNodePosi(T) p, T const &e )
{ _size ++; return p -> insertAsPred ( e ); } 

删除


在列表中删除指定节点 p 的算法:

//删除
template <typename T> 
T List<T>::remove ( ListNodePosi(T) p ){
    T e = p -> data; //备份待删除节点的数值(假定T类型可直接赋值)
    p -> pred -> succ = p -> succ; p-> succ -> pred = p -> pred; //后继、前驱
    delete p; 
    _size--; //释放节点,更新规模
    return e; //返回备份的数值
}

解释

  • 删除节点之前,列表在位置p附近的局部如图(a)所示。
  • 为了删除位置 p 处的节点,首先如图(b)所示,令其前驱节点与后继节点相互链接。
  • 然后如图(c)所示, 释放掉已经孤立出来的节点 p,同时相应地更新列表规模计数器 _size
  • 最终如图(d)所示,经过如此调整之后,原节点 p 即被顺利地从列表中摘除。


时间复杂度


由于对链表的插入和删除是直接元素插入位置的地址进行处理,故不需要像向量一样在插入或删除之后移动元素。故所有的插入和删除操作所需的时间复杂度均为 $\mathcal{O}(1)$。在进行频繁的插入删除操作时,列表的效率远远高于向量,可见动态存储策略的优越性。


2.2.6 复制构造和析构


copyNodes()


与向量一样,列表的内部结构也是动态创建的,故利用默认的构造方法并不能真正地完成新列表的复制创建。为此,需要专门编写相应的构造方法,通过复制某一已有列表来构造新列表。

尽管这里提供了多种形式,以允许对原列表的整体或局部复制,但其实质过程均大同小异,都可概括和转化为底层内部方法 copyNodes()。在输入参数合法的前提下,copyNodes() 首先调用 init() 方法,创建头、尾哨兵节点并做相应的初始化处理,然后自 p 所指节点起,从原列表中取出 n 个相邻的节点,并逐一作为末节点插至新列表中。

//copyNodes()
template <typename T> //列表内部方法:复制列表中自位置p起的n项
void List<T>::copyNodes ( ListNodePosi(T) p, int n ){   //p合法,且至少有n-1个真后继节点
    init(); //创建头、尾哨兵节点并做初始化
    while ( n-- ) { insertAsLast ( p -> data ); p = p -> succ; } //将起自p的n项依次作为末节点插入
}

根据此前的分析,init() 操作以及各步适代中的插入操作均只需常数时间,故 copyNodes() 过程总体的运行时间应为 $\mathcal{O}(n + 1)$,线性正比于待复制列表区间的长度 n


基于复制的构造


基于 copyNodes() 我们可以实现多种接口:

//复制列表中自位置p起的n项(assert: p为合法位置,且至少有n-1个后继节点)
template <typename T> 
List<T>::List ( ListNodePosi(T) p, int n ) { copyNodes ( p, n ); }

//整体复制列表L
template <typename T> 
List<T>::List ( List<T> const& L ) { copyNodes ( L.first(), L._size ); }

//复制L中自第r项起的n项(assert: r+n <= L._size)
template <typename T> 
List<T>::List ( List<T> const& L, int r, int n ) { copyNodes ( L[r], n ); }

列表的清空


//清空列表
template <typename T> 
void List<T>::clear(){   
    int oldSize = _size;
    while ( 0 < _size ) remove ( header -> succ ); //反复删除首节点,直至列表变空
}

列表的析构


与所有对象一样,列表对象析构时,将其所占用的资源归还操作系统。

//列表析构器
template <typename T> List<T>::~List()
{ clear(); delete header; delete trailer; }

解释

  • 列表的析构需首先调用 clear() 接口删除并释放所有对外部有效的节点。
  • 然后释放内部的头、尾哨兵节点。

列表的析构与清空时间复杂度一样,均为 $\mathcal{O}(n)$,线性正比于列表规模。


2.2.7 去重


无序列表的唯一化


旨在剔除无序列表中重复元素的接口 deduplicate(),与算法 Vector: :deduplicate() 类似,这里也是自前向后依次处理各节点 p,一旦通过 find() 接口在 p 的前驱中查到雷同者,则随即调用 remove() 接口将其删除。

//无序列表去重
template <typename T> 
int List<T>::deduplicate() {
    if ( _size < 2 ) return 0; //平凡列表自然无重复
    int oldSize = _size; //记录原规模
    ListNodePosi(T) p = header; Rank r = 0; //p从首节点开始
    while ( trailer != ( p = p -> succ ) ){   //依次直到末节点
        ListNodePosi(T) q = find ( p -> data, r, p ); //在p的r个(真)前驱中查找雷同者
        q ? remove ( q ) : r++; //若的确存在,则删除之;否则秩加一
    } //assert: 循环过程中的任意时刻,p的所有前驱互不相同
    return oldSize - _size; //列表规模变化量,即被删除元素总数
}

解释

  • 向量与列表中元素的逻辑次序一致,故二者的 deduplicate() 算法亦具有类似的不变性和单调性 ,故正确性均可保证。

与无序向量的去重算法一样,该算法总共需做 $\mathcal{O}(n)$ 步迭代。 每一步迭代中 find() 操作所需的时间线性正比于查找区间宽度。列表节点每次 remove() 操作仅需常数时间,但迭代需要的时间为 $\mathcal{O}(n^2)$,故时间复杂度为 $\mathcal{O}(n^2)$。


有序列表的唯一化


与有序向量同理,有序列表中的雷同节点也必然在逻辑上彼此紧邻。利用这一特性,可实现重复节点删除算法。位置指针 pq 分别指向每一对相邻的节点,若二者雷同则删除 q,否则转向下一对相令节点。如此反复迭代,直至检查过所有节点。

//有序列表去重
template <typename T> 
int List<T>::uniquify() {
    if ( _size < 2 ) return 0; //平凡列表自然无重复
    int oldSize = _size; //记录原规模
    ListNodePosi(T) p = first(); ListNodePosi(T) q; //p为各区段起点,q为其后继
    while ( trailer != ( q = p -> succ ) ) //反复考查紧邻的节点对(p, q)
        if ( p -> data != q -> data ) p = q; //若互异,则转向下一区段
        else remove ( q ); //否则(雷同),删除后者
    return oldSize - _size; //列表规模变化量,即被删除元素总数
}

整个过程运行时间为 $\mathcal{O}(n)$,线性正比于列表原先的规模。


2.2.8 遍历


列表也提供支持节点批量式访问的遍历接口,与向量一样,我们在此也提供两种方式:

//方法一://借助函数指针机制遍历
template <typename T>  
void List<T>::traverse ( void ( *visit ) ( T & ) ){   
    for ( ListNodePosi(T) p = header -> succ; p != trailer; p = p -> succ ){ 
        visit ( p -> data );  
    }
}

//方法二://借助函数对象机制遍历
template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse ( VST &visit ){  
    for ( ListNodePosi(T) p = header -> succ; p != trailer; p = p -> succ ){
        visit ( p -> data );  
    }
}

实例

实现遍历输出

//遍历输出从r项开始到l项
template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse ( VST &visit , ListNodePosi(T) r, ListNodePosi(T) l){  
    for ( ListNodePosi(T) p = r -> pred -> succ; p != l -> succ; p = p -> succ ){
        visit ( p -> data );  
    }
}

void show(int e){
    cout << e << " ";
}

2.2.9 逆置和排序


列表逆置


交换节点的前驱和后继的指针,并交换头尾节点:

//列表逆置
template <typename T>
void List<T>::reverse(){
    ListNodePosi(T) p = header;
    for(; p; p = p -> pred){
        std::swap(p -> pred, p -> succ);
    }
    std::swap(header, trailer);     
}

插入排序


插入排序(insertionsort)算法适用于包括向量与列表在内的任何序列结构。

思想

  • 始终将整个序列视作并切分为两部分: 有序的前缀,无序的后缀。通过迭代,反复地将后缀的首元素转移至前缀中。
  • 由此可知:在任何时刻,相对于当前节点 e = S[r],前缀 S[0, r) 总是业已有序。
//插入排序
template <typename T>  //对起始于位置p的n个元素排序
void List<T>::insertionSort ( ListNodePosi(T) p, int n ){   //valid(p) && rank(p) + n <= size
    for (int r = 0; r <= n; r ++){   //逐一为各节点
        insertA ( search( p -> data, r, p ), p -> data ); //查找适当的位置并插入
        p = p -> succ; remove ( p -> pred ); //转向下一节点
    }
}

解释

  • 算法开始时该前缀为空,不变性自然满足。
  • 现假设如图所示前缀 S[0,r) 已经有序,接下来, 借助有序序列的查找算法,可在该前缀中定位到不大于 e 的最大元素。
  • 于是只需将 e 从无序后组中取出,并紧邻于查找返回的位置之后插入,即可使得有序前缀的范围扩大至 S[0,r]

  • 如此,该前缀的范围可不断拓展。当其最终费盖整个序列时,亦即整体有序。

插入排序算法共由 n 步迁代组成,故其运行时间应取决于各步迁代中所执行的查找、删除及插入操作的效率。根据此前的结论,插入操作和删除操作只需 $\mathcal{O}(1)$ 时间,查找操作 search() 所需时间在 $\mathcal{O}(1)$ 至 $\mathcal{O}(n)$ 之间浮动。

若输出序列完全逆序,,则各次 search() 操作所需时间将线性递增。在等概率条件下,平均仍需要 $\mathcal{O}(n^2)$ 时间。


选择排序


选择排序(selectionsort)也适用于向量与列表之类的序列结构。

思想

  • 与插入排序类似,该算法也将序列划分为无序前缀和有序后缀两部分,且要求要求前缀不大于后缀。
  • 如此,每次只需从前缀中选出最大者,并作为最小元素转移至后缀中,即可使有序部分的范围不断扩张,直至整个列表有序。
  • 由此可知:在任何时刻,后缀 S(r, n) 已经有序,且不小于前缀 S[0, r)

首先要实现定位无序列表中最大的节点的函数 selectMax()

//selectMax()
template <typename T> //从起始于位置p的n个元素中选出最大者
ListNodePosi(T) List<T>::selectMax (ListNodePosi(T) p, int n){
    ListNodePosi(T) max = p; //最大者暂定为首节点p
    for ( ListNodePosi(T) cur = p; 1 < n; n-- ){ //从首节点p出发,将后续节点逐一与max比较
        if ( !lt ( ( cur = cur->succ )->data, max->data ) ) //若当前元素不小于max,则
            max = cur; //更新最大元素位置记录
    }
    return max; //返回最大节点位置
}

选择排序 selectionSort()

//选择排序
template <typename T> //对起始于位置p的n个元素排序
void List<T>::selectionSort ( ListNodePosi(T) p, int n ){   //valid(p) && rank(p) + n <= size
    ListNodePosi(T) head = p -> pred; ListNodePosi(T) tail = p;
    for ( int i = 0; i < n; i ++ ) tail = tail -> succ; //待排序区间为(head, tail)
    while ( 1 < n ){   //在至少还剩两个节点之前,在待排序区间内
        ListNodePosi(T) max = selectMax ( head -> succ, n ); //找出最大者(歧义时后者优先)
        insertB ( tail, remove ( max ) ); //将其移至无序区间末尾(作为有序区间新的首元素)
        tail = tail -> pred; n --;
    }
}

解释

  • 在算法的初始时刻,后缀为空,不变性自然满足。
  • 如图所示,假设不变性己满足。于是,可调用无序序列的查找算法,从前绥中找出最大者 M
  • 接下来,只需将 M 从前绥中取出并作为首元素插入后缀,即可使得后缀的范围扩大,并继续保持有序。

  • 如此,该后缀的范围可不断拓展,当其最终覆盖整个序列时,亦即整体有序。

与插入排序类似地,选择排序亦由 n 步选代组成,故其运行时间取决于各步送代中查找及插入操作的效率 。根据结论可知 insertB()remove() 均只需 $\mathcal{O}(1)$ 时间 。 selectMax() 每次必须遍历整个无序前缀,耗时应线性正比于前缀长度,全程累计耗时 $\mathcal{O}(n^2)$。


归并排序


基于二路归并的向量排序算法,其构思也同样适用于列表结构。实际上,有序列表的二路归并不仅可以实现,而且能够达到与有序向量二路归并同样高的效率。

仿照向量的归并排序算法 mergesort() ,采用分治策略并基于以上有序列表的二路归并算法,实现列表的归并排序算法:

//内置归并
template <typename T>
void List<T>::merge(ListNodePosi(T) p, int mid, int n){
    int lenB = mid;
    int lenC = n - mid;
    ListNodePosi(T) A = p;
    T * B = new T[mid];
    for(int i = 0; i<mid; ++i){
        B[i]= p->data; p = p->succ;  
    }
    ListNodePosi(T) C = p;
    for(int j = 0, k = 0; j < lenB; ){
        if( lenC <= k || B[j] <= C->data ){
            A -> data = B[j ++];  
            A = A -> succ;
        }
        if( k < lenC && C -> data < B[j]){
            A -> data = C -> data;  
            A = A -> succ; C = C -> succ; 
            ++ k;
        }  
    }
    delete [] B;
}

//归并排序
template <typename T>
void List<T>::mergeSort(ListNodePosi(T) p, int n){
    if( n < 2 ) return ;
    ListNodePosi(T) q = p;
    int mid = n >> 1;
    int x = mid; while(x --) q = q -> succ; 
    mergeSort(p, mid); mergeSort(q, n - mid);
    if(q -> pred -> data > q -> data) merge(p, mid, n);  
}

针对两个有序的链表合并,我们提供对外接口:

//合并两个链表
template <typename T>
void List<T>::mergeLists(ListNodePosi(T) p, int n, List<T> &L, ListNodePosi(T) q, int  m){
    List<T> t;
    while(m > 0 && n > 0){
        if(p -> data <= q -> data){
            t.insertAsLast(p -> data);
            p = p -> succ;n --;
        }
        else{
            t.insertAsLast(q -> data);
            q = q -> succ;m --;
        }
    }
    while(n > 0) t.insertAsLast(p -> data), p = p -> succ, n --;
    while(m > 0) t.insertAsLast(q -> data), q = q -> succ, m --;
    this -> clear(), L.clear();
    for(ListNodePosi(T) i = t.first(); i != t.trailer; i = i -> succ){
        this -> insertAsLast(i -> data);
    }
    p = this -> first();
}

2.2.10 列表测试


#include <iostream>
#include <cstdlib>
using namespace std;

typedef int Rank; //秩
#define ListNodePosi(T) ListNode<T>* //列表节点位置

template<typename T>
struct ListNode{  //列表节点模板类(以双向链表形式实现)
    // 成员
    T data;                //数值
    ListNodePosi(T) pred;  //前驱
    ListNodePosi(T) succ;  //后继
    // 构造函数
    ListNode(){}//针对header和trailer的构造
    ListNode(T e,ListNodePosi(T) p = NULL,ListNodePosi(T) s = NULL)
        :data(e),pred(p),succ(s){}//默认构造器
    // 操作接口
    ListNodePosi(T) insertAsPred(T const &e);//紧靠当前节点之前插入新节点
    ListNodePosi(T) insertAsSucc(T const &e);//紧随当前节点之后插入新节点
};

template <typename T> class List{
private:
    //数据成员
    int _size;               //规模
    ListNodePosi(T) header;  //头哨兵
    ListNodePosi(T) trailer; //尾哨兵
    //头、首、末、尾节点的秩,可分别理解为-1、0、n-1、n

protected:
    //内部函数
    void init();   //列表创建时的初始化
    void copyNodes ( ListNodePosi(T) p, int n );  //复制列表中自p起始的n项
    void merge (ListNodePosi(T) p, int mid, int n);   //内置归并

public:
    //构造函数
    List() { init(); }  //默认构造
    List ( List<T> const& L);                 //整体复制列表L
    List ( List<T> const& L, Rank r, int n);  //复制列表L的自r项起始的n项
    List ( ListNodePosi(T) p,int n);          //复制列表中自p起始的n项

    //析构函数
    ~List();

    //其他接口函数

    //只读函数
    Rank size() const { return _size; }    //规模
    bool empty() const { return !_size; }  //判空
    T &operator[](Rank r) const;  //重载[],支持寻秩访问,效率低
    ListNodePosi(T) first() const { return header -> succ; }  //首节点位置
    ListNodePosi(T) last() const {return trailer -> pred; }   //尾节点位置
    bool valid(ListNodePosi(T) p)  //判断位置p是否合法
    { return p && (trailer != p) && (header != p); }  //将头、尾节点等同于NULL
    ListNodePosi(T) find ( T const& e) const                           
    { return find( e, _size, trailer); }                                //无序查找
    ListNodePosi(T) find( T const& e, int n, ListNodePosi(T) p) const;  //无序区间查找
    ListNodePosi(T) search( T const& e) const
    { return search( e, _size, trailer); }                                //有序查找
    ListNodePosi(T) search( T const& e, int n, ListNodePosi(T) p) const;  //有序区间查找
    ListNodePosi(T) selectMax (ListNodePosi(T) p, int n);                     //区间最大节点
    ListNodePosi(T) selectMax () {return selectMax( header -> succ, _size); }  //整体最大节点

    //可写入接口
    ListNodePosi(T) insertAsFirst (T const& e);               //将e当作首节点插入
    ListNodePosi(T) insertAsLast (T const& e);                //将e当作尾节点插入
    ListNodePosi(T) insertA (ListNodePosi(T) p, T const& e);  //将e当作p的后继插入
    ListNodePosi(T) insertB (ListNodePosi(T) p, T const& e);  //将e当作p的前驱插入
    void clear();  //列表清空
    T remove ( ListNodePosi(T) p );  //删除节点p
    int deduplicate();  //无序去重
    int uniquify();     //有序去重   
    void reverse();  //列表逆置
    void insertionSort (ListNodePosi(T) p, int n);    //插入排序
    void selectionSort ( ListNodePosi(T) p, int n );  //选择排序
    void mergeSort ( ListNodePosi(T)  p, int n );     //归并排序
    void mergeLists(ListNodePosi(T)  p, int n, List<T>& L, ListNodePosi(T) q, int m);               //归并两个链表
    void mergeLists( List<T> & L ) { mergeLists ( header -> succ, _size, L, L.header -> succ, L._size ); } //全列表归并

    //遍历
    void traverse(void (*)(T &)); //使用函数指针操作
    template <typename VST>
    void traverse(VST &); //使用函数对象操作
    template <typename VST>
    void traverse( VST &visit , ListNodePosi(T) r, ListNodePosi(T) l);

};  // List

//列表初始化,在创建列表对象时统一调用
template<typename T>
void List<T>::init(){
    header = new ListNode<T>;   //创建头哨兵节点
    trailer = new ListNode<T>;  //创建尾哨兵节点
    header -> succ = trailer; header -> pred = NULL; 
    trailer -> pred = header; trailer -> succ = NULL;
    _size = 0;  //记录规模
}

// //重载下标操作符,以通过秩直接访问列表节点(虽方便,效率低,需慎用)
// template <typename T>
// T& List<T>::operator[] ( Rank r ) const{   //assert: 0 <= r < size
//     ListNodePosi(T) p = first(); //从首节点出发
//     while (0 < r--) p = p -> succ; //顺数第r个节点即是
//     return p -> data; //目标节点,返回其中所存元素
// }

//无序区间查找
//在无序列表内节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者
template <typename T> 
ListNodePosi(T) List<T>::find ( T const &e, int n, ListNodePosi(T) p ) const {
    while (0 < n--) //(0 <= n <= rank(p) < _size)对于p的最近的n个前驱,从右向左
        if (e == (p = p -> pred) -> data) return p; //逐个比对,直至命中或范围越界
    return NULL; //p越出左边界意味着区间内不含e,查找失败
} //失败时,返回NULL

//有序区间查找
//在有序列表内节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者
template <typename T> 
ListNodePosi(T) List<T>::search ( T const &e, int n, ListNodePosi(T) p ) const {
    while (0 < n--) //(0 <= n <= rank(p) < _size)对于p的最近的n个前驱,从右向左
        if (((p = p -> pred) -> data) <= e) break;  //直接找到,或越界
    return p;
} //失败时,返回左边界的前驱,可能是header

//前插入
template <typename T> //将e紧靠当前节点之前插入于当前节点所属列表(设有哨兵头节点header)
ListNodePosi(T) ListNode<T>::insertAsPred ( T const &e ){
    ListNodePosi(T) x = new ListNode ( e, pred, this ); //创建新节点
    pred -> succ = x; pred = x; //设置正向链接
    return x; //返回新节点的位置
}

//后插入
template <typename T> //将e紧随当前节点之后插入于当前节点所属列表(设有哨兵尾节点trailer)
ListNodePosi(T) ListNode<T>::insertAsSucc ( T const &e ){
    ListNodePosi(T) x = new ListNode ( e, this, succ ); //创建新节点
    succ -> pred = x; succ = x; //设置逆向链接
    return x; //返回新节点的位置
}

//e当作首节点插入
template <typename T> ListNodePosi(T) List<T>::insertAsFirst ( T const &e )
{ _size ++; return header -> insertAsSucc ( e ); } 

//e当作末节点插入
template <typename T> ListNodePosi(T) List<T>::insertAsLast ( T const &e )
{ _size ++; return trailer -> insertAsPred ( e ); }

//e当作p的后继插入(After)
template <typename T> ListNodePosi(T) List<T>::insertA ( ListNodePosi(T) p, T const &e )
{ _size ++; return p -> insertAsSucc ( e ); } 

//e当作p的前驱插入(Before)
template <typename T> ListNodePosi(T) List<T>::insertB ( ListNodePosi(T) p, T const &e )
{ _size ++; return p -> insertAsPred ( e ); } 

//删除
template <typename T> 
T List<T>::remove ( ListNodePosi(T) p ){
    T e = p -> data; //备份待删除节点的数值(假定T类型可直接赋值)
    p -> pred -> succ = p -> succ; p-> succ -> pred = p -> pred; //后继、前驱
    delete p; 
    _size--; //释放节点,更新规模
    return e; //返回备份的数值
}

//copyNodes()
template <typename T> //列表内部方法:复制列表中自位置p起的n项
void List<T>::copyNodes ( ListNodePosi(T) p, int n ){   //p合法,且至少有n-1个真后继节点
    init(); //创建头、尾哨兵节点并做初始化
    while ( n-- ) { insertAsLast ( p -> data ); p = p -> succ; } //将起自p的n项依次作为末节点插入
}

//复制列表中自位置p起的n项(assert: p为合法位置,且至少有n-1个后继节点)
template <typename T> 
List<T>::List ( ListNodePosi(T) p, int n ) { copyNodes ( p, n ); }

//整体复制列表L
template <typename T> 
List<T>::List ( List<T> const& L ) { copyNodes ( L.first(), L._size ); }

//复制L中自第r项起的n项(assert: r+n <= L._size)
template <typename T> 
List<T>::List ( List<T> const& L, int r, int n ) { copyNodes ( L[r], n ); }

//清空列表
template <typename T> 
void List<T>::clear(){   
    int oldSize = _size;
    while ( 0 < _size ) remove ( header -> succ ); //反复删除首节点,直至列表变空
}

//列表析构器
template <typename T> List<T>::~List()
{ clear(); delete header; delete trailer; }

//无序列表去重
template <typename T> 
int List<T>::deduplicate() {
    if ( _size < 2 ) return 0; //平凡列表自然无重复
    int oldSize = _size; //记录原规模
    ListNodePosi(T) p = header; Rank r = 0; //p从首节点开始
    while ( trailer != ( p = p -> succ ) ){   //依次直到末节点
        ListNodePosi(T) q = find ( p -> data, r, p ); //在p的r个(真)前驱中查找雷同者
        q ? remove ( q ) : r++; //若的确存在,则删除之;否则秩加一
    } //assert: 循环过程中的任意时刻,p的所有前驱互不相同
    return oldSize - _size; //列表规模变化量,即被删除元素总数
}

//有序列表去重
template <typename T> 
int List<T>::uniquify() {
    if ( _size < 2 ) return 0; //平凡列表自然无重复
    int oldSize = _size; //记录原规模
    ListNodePosi(T) p = first(); ListNodePosi(T) q; //p为各区段起点,q为其后继
    while ( trailer != ( q = p -> succ ) ) //反复考查紧邻的节点对(p, q)
        if ( p -> data != q -> data ) p = q; //若互异,则转向下一区段
        else remove ( q ); //否则(雷同),删除后者
    return oldSize - _size; //列表规模变化量,即被删除元素总数
}

//方法一://借助函数指针机制遍历
template <typename T>  
void List<T>::traverse ( void ( *visit ) ( T & ) ){   
    for ( ListNodePosi(T) p = header -> succ; p != trailer; p = p -> succ ){ 
        visit ( p -> data );  
    }
}

//方法二://借助函数对象机制遍历
template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse ( VST &visit ){  
    for ( ListNodePosi(T) p = header -> succ; p != trailer; p = p -> succ ){
        visit ( p -> data );  
    }
}

//遍历输出从r项开始到l项
template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse ( VST &visit , ListNodePosi(T) r, ListNodePosi(T) l){  
    for ( ListNodePosi(T) p = r -> pred -> succ; p != l -> succ; p = p -> succ ){
        visit ( p -> data );  
    }
}

void show(int e){
    cout << e << " ";
}

//列表逆置
template <typename T>
void List<T>::reverse(){
    ListNodePosi(T) p = header;
    for(; p; p = p -> pred){
        std::swap(p -> pred, p -> succ);
    }
    std::swap(header, trailer);     
}

//插入排序
template <typename T>  //对起始于位置p的n个元素排序
void List<T>::insertionSort ( ListNodePosi(T) p, int n ){   //valid(p) && rank(p) + n <= size
    for (int r = 0; r <= n; r ++){   //逐一为各节点
        insertA ( search( p -> data, r, p ), p -> data ); //查找适当的位置并插入
        p = p -> succ; remove ( p -> pred ); //转向下一节点
    }
}

//selectMax()
template <typename T> //从起始于位置p的n个元素中选出最大者
ListNodePosi(T) List<T>::selectMax (ListNodePosi(T) p, int n){
    ListNodePosi(T) max = p; //最大者暂定为首节点p
    for ( ListNodePosi(T) cur = p; 1 < n; n-- ){ //从首节点p出发,将后续节点逐一与max比较
        if ( !lt ( ( cur = cur->succ )->data, max->data ) ) //若当前元素不小于max,则
            max = cur; //更新最大元素位置记录
    }
    return max; //返回最大节点位置
}

//选择排序
template <typename T> //对起始于位置p的n个元素排序
void List<T>::selectionSort ( ListNodePosi(T) p, int n ){   //valid(p) && rank(p) + n <= size
    ListNodePosi(T) head = p -> pred; ListNodePosi(T) tail = p;
    for ( int i = 0; i < n; i ++ ) tail = tail -> succ; //待排序区间为(head, tail)
    while ( 1 < n ){   //在至少还剩两个节点之前,在待排序区间内
        ListNodePosi(T) max = selectMax ( head -> succ, n ); //找出最大者(歧义时后者优先)
        insertB ( tail, remove ( max ) ); //将其移至无序区间末尾(作为有序区间新的首元素)
        tail = tail -> pred; n --;
    }
}

//内置归并
template <typename T>
void List<T>::merge(ListNodePosi(T) p, int mid, int n){
    int lenB = mid;
    int lenC = n - mid;
    ListNodePosi(T) A = p;
    T * B = new T[mid];
    for(int i = 0; i<mid; ++i){
        B[i]= p->data; p = p->succ;  
    }
    ListNodePosi(T) C = p;
    for(int j = 0, k = 0; j < lenB; ){
        if( lenC <= k || B[j] <= C->data ){
            A -> data = B[j ++];  
            A = A -> succ;
        }
        if( k < lenC && C -> data < B[j]){
            A -> data = C -> data;  
            A = A -> succ; C = C -> succ; 
            ++ k;
        }  
    }
    delete [] B;
}

//归并排序
template <typename T>
void List<T>::mergeSort(ListNodePosi(T) p, int n){
    if( n < 2 ) return ;
    ListNodePosi(T) q = p;
    int mid = n >> 1;
    int x = mid; while(x --) q = q -> succ; 
    mergeSort(p, mid); mergeSort(q, n - mid);
    if(q -> pred -> data > q -> data) merge(p, mid, n);  
}

//合并两个链表
template <typename T>
void List<T>::mergeLists(ListNodePosi(T) p, int n, List<T> &L, ListNodePosi(T) q, int  m){
    List<T> t;
    while(m > 0 && n > 0){
        if(p -> data <= q -> data){
            t.insertAsLast(p -> data);
            p = p -> succ;n --;
        }
        else{
            t.insertAsLast(q -> data);
            q = q -> succ;m --;
        }
    }
    while(n > 0) t.insertAsLast(p -> data), p = p -> succ, n --;
    while(m > 0) t.insertAsLast(q -> data), q = q -> succ, m --;
    this -> clear(), L.clear();
    for(ListNodePosi(T) i = t.first(); i != t.trailer; i = i -> succ){
        this -> insertAsLast(i -> data);
    }
    p = this -> first();
}

int num[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  //有序数组num

void test_01(){

    cout << "##### test_01() begin #####" << endl << endl;

    cout << "Test List Init :" << endl; 
    List<int> a;
    List<double> b;
    List<List<int>> c;

    cout << "RIGHT!" << endl << endl;

    cout << "Test List copyNodes():" << endl;

    List<int> e;

    for(int i = 0; i < 10; i ++) e.insertAsLast(num[i]);

    cout << "e = ";
    e.traverse(show, e.first(), e.last());
    cout << endl;

    List<int> f(e);
    cout << "f = ";
    f.traverse(show, f.first(), f.last());
    cout << endl;

    List<int> g(e.first(), 4);
    cout << "g = ";
    g.traverse(show, g.first(), g.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "##### test_01() over #####" << endl;

}

void test_02(){

    cout << "##### test_02() begin #####" << endl << endl;

    cout << "Test find() :" << endl;

    List<int> a;

    for(int i = 0; i < 10; i ++){
        int x = rand() % 20;
        a.insertAsLast(x);
    }    

    cout << "a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    bool vis_1[101] = {0};

    for(int i = 0; i < 10; i ++){
        int x = rand() % 20;
        if(!vis_1[x]) cout << "find(" << x << ") = " << a.find(x) << endl; 
        vis_1[x] = 1;
    }

    cout << "RIGHT!" << endl << endl;

    cout << "Test search() :" << endl;

    List<int> b;

    for(int i = 0; i < 10; i ++) b.insertAsLast(num[i]);

    cout << "b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    int vis_2[101]={0};

    for(int i = 0; i < 10; i ++){
        int x = rand() % 20;
        if(!vis_2[x]){
            cout << "search(" << x << ") = " << b.search(x);
            if(b.search(x) == b.last() && b.last() -> data != x) cout << " Not Found!";
            cout << endl;
        }
        vis_2[x] = 1;
    }

    cout << "RIGHT!" << endl << endl;

    cout << "##### test_02() over #####" << endl;

}

void test_03(){

    cout << "##### test_03() begin #####" << endl << endl;

    cout << "Test remove() :" << endl;

    List<int> a;

    for(int i = 0; i < 10; i ++) a.insertAsLast(num[i]);

    cout << "a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    cout << "remove(4)" << endl;
    cout << "remove(7)" << endl;

    a.remove(a.first() -> succ -> succ -> succ);
    a.remove(a.last() -> pred -> pred -> pred);

    cout << "removed a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;
    cout << "size(a) = " << a.size() << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "Test clear() : " << endl;

    List<int> b(a);

    cout << "b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    b.clear();

    cout << "b.clear(), size(b) = " << b.size() << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "##### test_03() over #####" << endl;

}

void test_04(){

    cout << "##### test_04() begin #####" << endl << endl;

    cout << "Test deduplicate() :" << endl;

    List<int> a;

    for(int i = 0; i < 20; i ++){
        int x = rand() % 20;
        a.insertAsLast(x);
    }  

    cout << "a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    a.deduplicate();

    cout << "deduplicated a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "Test uniquify() :" << endl;

    List<int> b;

    for(int i = 1; i <= 5; i ++){
        for(int j = 0; j < i; j ++){
            b.insertAsLast(i);
        }
    }

    cout << "b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    b.uniquify();

    cout << "uniquifyed b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "##### test_04() over #####" << endl;

}

void test_05(){

    cout << "##### test_05() begin #####" << endl << endl;

    cout << "Test reverse() :" << endl;

    List<int> a;

    for(int i = 1; i <= 10; i ++) a.insertAsLast(i);

    cout << "a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    a.reverse();

    cout << "reversed a = ";
    a.traverse(show, a.first(), a.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "Test sort() :" << endl;

    List<int> b;

    for(int i = 0; i < 20; i ++){
        int x = rand() % 100;
        b.insertAsLast(x);
    } 

    cout << "b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    // b.insertionSort(b.first(), b.size());
    // b.insertionSort(b.first(), b.size());
    b.mergeSort(b.first(), b.size());

    cout << "sorted b = ";
    b.traverse(show, b.first(), b.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "Test mergeLists() :" << endl;

    List<int> e,f;

    for(int i = 1; i < 20; i += 2) e.insertAsLast(i);
    for(int i = 2; i <= 20; i += 2) f.insertAsLast(i);

    cout << "e = ";
    e.traverse(show, e.first(), e.last());
    cout << endl;

    cout << "f = ";
    f.traverse(show, f.first(), f.last());
    cout << endl;

    e.mergeLists(f);

    cout << "e = ";
    e.traverse(show, e.first(), e.last());
    cout << endl;

    cout << "RIGHT!" << endl << endl;

    cout << "##### test_05() over #####" << endl;

}

int main(){

    cout << "###########################" << endl;
    test_01();
    cout << "###########################" << endl;
    cout << endl;

    cout << "###########################" << endl;
    test_02();
    cout << "###########################" << endl;
    cout << endl;

    cout << "###########################" << endl;
    test_03();
    cout << "###########################" << endl;
    cout << endl;

    cout << "###########################" << endl;
    test_04();
    cout << "###########################" << endl;
    cout << endl;

    cout << "###########################" << endl;
    test_05();
    cout << "###########################" << endl;
    cout << endl;

    return 0;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇