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