0.概述

学习了向量，再介绍下列表。先介绍下列表里的概念和语义，这个对理解列表接口还是比较重要的。

1. 从向量到列表

1.1 从静态到动态

1.2 从向量到列表

注意：首末节点描述。

1.3 从秩到位置

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

1.4 列表

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

2. 接口

2.1 列表节点

2.1.1 ADT接口

###

2.1.2 ListNode模板类

using Rank = unsigned int; //秩

template <typename T> struct ListNode;
template <typename T> using ListNodePosi = ListNode<T>*; //列表节点位置

template <typename T> 
struct ListNode { //列表节点模板类（以双向链表形式实现）
// 成员
   T data; ListNodePosi<T> pred, 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 ); //紧随当前节点之后插入新节点
};

2.2 列表

2.2.1 ADT接口

领会下宏观接口，具体接口后面会做介绍。

分别针对有序和无序列表，提供了去重操作的两个版本（deduplicate()和uniquify()），以及查找操作的两
个版本（find()和search()）。与向量一样，有序列表的唯一化，比无序列表效率更高。

由于只能通过位置指针以局部移动的方式访问节点，尽管有序列表中节点在逻辑上始终按照大小次序排列，其查找操作的效率并没有实质改进。

二者的效率完全一致：在最好情况下，均只需O(1)时间；在最坏情况下，均需要O(n)时间；平均而言，二者均需O(n)时间。

2.2.2 List模板类

头尾接口对外不可见，非常重要。

#pragma once

#include "listNode.h" //引入列表节点类

template <typename T> class List { //列表模板类

private:
   Rank _size; ListNodePosi<T> header, trailer; //规模、头哨兵、尾哨兵

protected:
   void init(); //列表创建时的初始化
   Rank clear(); //清除所有节点
   void copyNodes( ListNodePosi<T>, Rank ); //复制列表中自位置p起的n项
   ListNodePosi<T> merge( ListNodePosi<T>, Rank, List<T>&, ListNodePosi<T>, Rank ); //归并
   void mergeSort( ListNodePosi<T>&, Rank ); //对从p开始连续的n个节点归并排序
   void selectionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点选择排序
   void insertionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点插入排序
   void radixSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点基数排序

public:
// 构造函数
   List() { init(); } //默认
   List( List<T> const& L ); //整体复制列表L
   List( List<T> const& L, Rank r, Rank n ); //复制列表L中自第r项起的n项
   List( ListNodePosi<T> p, Rank n ); //复制列表中自位置p起的n项
   // 析构函数
   ~List(); //释放（包含头、尾哨兵在内的）所有节点
// 只读访问接口
   Rank size() const { return _size; } //规模
   bool empty() const { return _size <= 0; } //判空
   ListNodePosi<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, Rank n, ListNodePosi<T> p ) const; //无序区间查找
   ListNodePosi<T> search( T const& e ) const //有序列表查找
   { return search( e, _size, trailer ); }
   ListNodePosi<T> search( T const& e, Rank n, ListNodePosi<T> p ) const; //有序区间查找
   ListNodePosi<T> selectMax( ListNodePosi<T> p, Rank n ); //在p及其n-1个后继中选出最大者
   ListNodePosi<T> selectMax() { return selectMax( header->succ, _size ); } //整体最大者
// 可写访问接口
   ListNodePosi<T> insertAsFirst( T const& e ); //将e当作首节点插入
   ListNodePosi<T> insertAsLast( T const& e ); //将e当作末节点插入
   ListNodePosi<T> insert( ListNodePosi<T> p, T const& e ); //将e当作p的后继插入
   ListNodePosi<T> insert( T const& e, ListNodePosi<T> p ); //将e当作p的前驱插入
   T remove( ListNodePosi<T> p ); //删除合法位置p处的节点,返回被删除节点
   void merge( List<T>& L ) { merge( header->succ, _size, L, L.header->succ, L._size ); } //全列表归并
   void sort( ListNodePosi<T>, Rank ); //列表区间排序
   void sort() { sort( first(), _size ); } //列表整体排序
   Rank dedup(); //无序去重
   Rank uniquify(); //有序去重
   void reverse(); //前后倒置（习题）
// 遍历
   void traverse( void ( * )( T& ) ); //依次实施visit操作（函数指针）
   template <typename VST> void traverse( VST& ); //依次实施visit操作（函数对象）
}; //List

#include "List_implementation.h"

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; //记录规模
}