// vector.h
#pragma once
#include <functional>
// 用于函数指针

using Rank = unsigned int; //秩
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）

template <typename T> class Vector { //向量模板类
protected:
	Rank _size; Rank _capacity;  T* _elem; //规模、容量、数据区
	void copyFrom(T const* A, Rank lo, Rank hi); //复制数组区间A[lo, hi)
	void expand(); //空间不足时扩容
	void shrink(); //装填因子过小时压缩
	bool bubble(Rank lo, Rank hi); //扫描交换
	void bubbleSort(Rank lo, Rank hi); //起泡排序算法
	Rank maxItem(Rank lo, Rank hi); //选取最大元素
	void selectionSort(Rank lo, Rank hi); //选择排序算法
	void merge(Rank lo, Rank mi, Rank hi); //归并算法
	void mergeSort(Rank lo, Rank hi); //归并排序算法
	void heapSort(Rank lo, Rank hi); //堆排序（稍后结合完全堆讲解）
	Rank partition(Rank lo, Rank hi); //轴点构造算法
	void quickSort(Rank lo, Rank hi); //快速排序算法
	void shellSort(Rank lo, Rank hi); //希尔排序算法
public:
	// 构造方法
	Vector(Rank c = DEFAULT_CAPACITY) //容量为c的空向量
	{
		_elem = new T[_capacity = c]; _size = 0;
	}
	Vector(Rank c, Rank s, T v) //容量为c、规模为s、所有元素初始为v；s<=c
	{
		_elem = new T[_capacity = c]; for (_size = 0; _size < s; _elem[_size++] = v);
	}
	Vector(T const* A, Rank n) { copyFrom(A, 0, n); } //数组整体复制
	Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } //区间
	Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); } //向量整体复制
	Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); } //区间
	// 析构方法
	~Vector() { delete[] _elem; } //释放内部空间
	// 只读访问接口
	Rank size() const { return _size; } //规模
	bool empty() const { return !_size; } //判空
	Rank find(T const& e) const { return find(e, 0, _size); } //无序向量整体查找
	Rank find(T const& e, Rank lo, Rank hi) const; //无序向量区间查找
	Rank select(Rank k) { return quickSelect(_elem, _size, k); } //从无序向量中找到第k大的元素
	Rank search(T const& e) const //有序向量整体查找
	{
		return (0 >= _size) ? -1 : search(e, 0, _size);
	}
	Rank search(T const& e, Rank lo, Rank hi) const; //有序向量区间查找
	// 可写访问接口
	T& operator[] (Rank r); //重载下标操作符，可以类似于数组形式引用各元素
	const T& operator[] (Rank r) const; //仅限于做右值的重载版本
	Vector<T>& operator= (Vector<T> const&); //重载赋值操作符，以便直接克隆向量
	T remove(Rank r); //删除秩为r的元素
	Rank remove(Rank lo, Rank hi); //删除秩在区间[lo, hi)之内的元素
	Rank insert(Rank r, T const& e); //插入元素
	Rank insert(T const& e) { return insert(_size, e); } //默认作为末元素插入
	void sort(Rank lo, Rank hi); //对[lo, hi)排序
	void sort() { sort(0, _size); } //整体排序
	void unsort(Rank lo, Rank hi); //对[lo, hi)置乱
	void unsort() { unsort(0, _size); } //整体置乱
	Rank disordered(); // 逆序对个数
	Rank deduplicate(); //无序去重
	Rank uniquify(); //有序去重
	// 遍历
	void traverse(std::function<void(T&)> visit); //遍历（使用函数指针，只读或局部性修改）
	template <typename VST> void traverse(VST&); //遍历（使用函数对象，可全局性修改）
}; //Vector

Vector ( Rank c = DEFAULT_CAPACITY ) //容量为c的空向量
{
    _elem = new T[_capacity = c];
    _size = 0;
}

Vector ( Rank c, Rank s, T v ) //容量为c、规模为s、所有元素初始为v；s<=c
{
    _elem = new T[_capacity = c];
    for ( _size = 0; _size < s; _elem[_size++] = v );
}

Vector ( T const* A, Rank n ) //数组整体复制
{
	copyFrom ( A, 0, n );
}

Vector ( T const* A, Rank lo, Rank hi ) //数组区间复制
{
	copyFrom ( A, lo, hi );
}

Vector ( Vector<T> const& V )  //向量整体复制
{
    copyFrom ( V._elem, 0, V._size );
}

Vector ( Vector<T> const& V, Rank lo, Rank hi ) //向量区间复制
{
    copyFrom ( V._elem, lo, hi );
}

// vector_copyFrom.h
#pragma once
#include "vector.h"

template <typename T>
void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi)
{
	_elem = new T[_capacity = 2 * (hi - lo)]; // 开辟了两倍的空间 接下来很长一段时间内 不必因为扩容而打断计算过程
	_size = 0; // 先将规模置为0
	while (lo < hi)
		_elem[size++] = A[lo++];
}

// vector_operator_assignment.h
#pragma once
#include "vector.h"

template <typename T>
Vector<T>& Vector<T>::operator= (Vector<T> const& V)
{
	if (_elem) delete[] _elem; // 释放_elem原有内容
	copyFrom(V._elem, 0, V.size());
	return *this;
}

~Vector()
{
	delete [] _elem;
}

// vector_expand.h
#pragma once
#include "vector.h"

template <typename T>
void Vector<T>::expand()
{
	if (_size < _capacity)
		return; // 容量未满的时候无需扩容 否则扩容
	_capacity = max(_capacity, DEFAULT_CAPACITY); // 不低于最小容量

	T* oldElem = _elem;
	_elem = new T[_capacity <<= 1]; // 移位 新开辟一块内粗 容量加倍

	for (int i = 0; i < _size; i++)
		_elem[i] = oldElem[i]; // 逐一复制原来的元素 要求T为基本类型 或者已经重载操作符=
	delete[] oldElem; // 释放原空间
}

// vector_operator_bracket
#pragma once
#include "vector.h"

template <typename T>
T& Vector<T>::operator[](Rank r)
{
	return _elem[r];
}

#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::insert(Rank r, T const& e)
{
	expand(); // 如有必要 扩容
	for (int i = _size; i > r; i--) // 自后向前
		_elem[i] = _elem[i - 1]; // 后继元素顺次后移一个单元

	_elem[r] = e; // 置入新元素
	_size++; // 更新容量
	return r; // 返回秩
}

#pragma once
#include "vector.h"

// 区间删除
template <typename T>
Rank Vector<T>::remove(Rank lo, Rank hi)
{
	if (lo == hi) return 0; // 为了效率单独处理退化情况
	while (hi < _size)
		_elem[lo++] = _elem[hi++]; // 自前向后 [lo,_size)顺次前移hi-lo

	_size = lo; // 更新规模
	shrink(); // 如有必要 缩容
}

// 单元素删除 可以看作区间删除的特例
template <typename T>
T Vector<T>::remove(Rank r)
{
	T e = _elem[r]; // 备份被删除元素
	remove(r, r + 1); // 调用区间删除算法
	return e;
}

// vector_find.h
#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const
{
	while ((lo < hi--) && (e != _elem[hi]));

	return hi;
}

// vector_deduplicate.h
#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::deduplicate()
{
	int oldSize = _size;
	Rank i = 1; // 从_elem[1]开始 而不是_elem[0]
	while (i < _size) // 自前向后逐一遍历
		find(_elem[i], 0, i) ? i++ : remove(i);
		// _elem[i]是否和前缀[0,i)的元素有雷同？ 若无雷同 考察后继 若有雷同 删除_elem[i]这一项
		// 但做完remove(i)之后 现在的_elem[i]就是原来的_elem[i]的后继 不再需要i++

	return oldSize - _size; // 向量规模变化量 即删除元素总数
}

#pragma once
#include "vector.h"
#include <functional>

template <typename T>
void Vector<T>::traverse(std::function<void(T&)> visit) // 使用函数指针 只读或局部性修改
// std::function<void(T&)> func 就是接收T&参数的 返回void类型的 名为func的 函数指针
// 和void(*func)(T&)差不多
{
	for (int i = 0; i < _size; i++)
		visit(_elem[i]);
}

template <typename T> template <typename VST>
void Vector<T>::traverse(VST& visit) // 使用函数对象 全局性修改
{
	for (int i = 0; i < _size; i++)
		visit(_elem[i]);
}

template <typename T>
struct Increase
{
	void operator()(T& e)
    {
        e++;
    }
}

template <typename T>
void increase(Vector<T>& v)
{
    v.traverse(Increase<T>());
}

// vector_disordered.h
#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::disordered()
{
	int n = 0; // 计数器
	for (int i = 1; i < _size; i++) // 遍历各对相邻元素
		n += (_elem[i - 1] > _elem[i]); // 逆序就计数
	return n; // n=0 当且仅当向量有序
}

// vector_uniquify.h
#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::uniquify()  // 单元素删除 低效版本
{
	int oldSize = _size;
	int i = 0;
	while (i < _size - 1)
		(_elem[i] == _elem[i + 1]) ? remove(i + 1) : i++;
    return oldSize - _size;
}

Rank i = 1;
while (i < _size)
    find(_elem[i], 0, i) ? i++ : remove(i);

// vector_uniquify.h
#pragma once
#include "vector.h"

template <typename T>
Rank Vector<T>::uniquify() // 区间删除 高效版本
{
	Rank i = 0, j = 0;
	while (++j < _size)
	{
		if (_elem[i] != _elem[j])
			_elem[++i] = _elem[j];
	}
	_size = ++i;
	return j - i; // 向量规模变化量
}

// vector_search.h
template <typename T>
Rank Vector<T>::search(T const& e, Rank lo, Rank hi) const
{
    return (rand() % 2) ?
    binSearch_C(_elem, e, lo, hi) : fibSearch(_elem, e, lo, hi);
    // 各有50%的概率选用二分查找C 或者 Fibonacci查找(略)
    // 为什么是二分查找版本C 原因后面讲
}

// vector_binSearch_A.h
#pragma once
#include "vector.h"

template <typename T>
static Rank binSearch_A(T const& e, Rank lo, Rank hi)
{
	while (lo < hi)
	{
		Rank mi = (lo + hi) >> 1; // 取出lo和hi的中点
		if      (e < A[mi]) hi = mi; // 深入[lo,mi)
		else if (A[mi] < e) lo = mi + 1; // 深入(mi,hi) 都是写的<号 建议总是写<号
		else                return mi; // 那实际上就是A[mi]=e 在mi命中
	}
	return -1; // 查找失败
}

// vector_binSearch_B.h
#pragma once
#include "vector.h"

template <typename T>
static Rank binSearch_B(T* A, T const& e, Rank lo, Rank hi)
{
	while (1 < hi - lo) // 查找区间宽度为1时 算法才会终结
	{
		Rank mi = (lo + hi) >> 1;
		(e < A[mi]) ? hi = mi : lo = mi; // [lo,mi)或[mi,hi)
	}
	return (e == A[0]) ? lo : -1; // 返回命中元素的秩 或者-1(失败)
}

// vector_binSearch_C.h
#pragma once
#include "vector.h"

template <typename T>
static Rank binSearch_C(T* A, T const& e, Rank lo, Rank hi)
{
	while (lo < hi)
	{
		Rank mi = (lo + hi) >> 1;
		(e < A[mi]) ? hi = mi : lo = mi + 1;
	}
	return --lo; // lo-1 即不大于e的元素的秩 符合接口规定
}

void bubbbleSort(int A[], int n)
{
	for(bool sorted = false; sorted=!sorted; n--)
        for(int i=1; i<n; i++)
            if(A[i-1] > A[i]) // 发生逆序
            {
                swap(A[i-1], A[i]); // 交换
                sorted = false;
            }
}

// vector_bubbleSort_B.h 
#pragma once
#include "vector.h"

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi)
{
	while (!bubble(lo, hi--););
	// bubble返回的是有序标志 如果有序就停止循环 及时截断
}

template <typename T>
bool Vector<T>::bubble(Rank lo, Rank hi)
{
	bool sorted = true; // 先认为有序 后面再逐个检查各对相邻元素
	while (++lo < hi)
		if (_elem[lo - 1] > _elem[lo])
		{
			sorted = false; // 整体尚未有序
			swap(_elem[lo - 1], _elem[lo]); // 交换
		}
	return sorted; // 返回有序标志
}

∎∎∎∎ ∎∎∎∎∎∎∎∎∎∎∎∎∎
前缀    后缀

// vector_bubbleSort_C.h
#pragma once
#include "vector.h"

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi)
{
	while (lo < (hi = bubble(lo, hi)));
}

template <typename T>
Rank Vector<T>::bubble(Rank lo, Rank hi)
{
	Rank last = lo; // 记录最右侧逆序对位置
	while (++lo < hi) // 自左向右
		if (_elem[lo - 1] > _elem[lo]) // 若逆序
		{
			last = lo; // 更新最右侧逆序对位置记录
			swap(_elem[lo - 1], _elem[lo]);
		}
	return last; // 返回最右侧逆序对位置 而不再是bool型sorted
}

// vector_mergeSort.h
#pragma once
#include "vector.h"

template <typename T>
void Vector<T>::mergeSort(Rank lo, Rank hi)
{
	if (hi - lo < 2) return; // 单元素区间有序
	int mi = (lo + hi) >> 1; // 以中点为界
	mergeSort(lo, mi); // 对前半段排序
	mergeSort(mi, hi); // 对后半段排序
	merge(lo, mi, hi); // 归并
}

template <typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi)
{
	// A = B + C
	T* A = _elem + lo; // 合并后的向量A[0,hi-lo]=_elem[lo,hi]

	int lb = mi - lo;
	T* B = new T[lb]; // 前子向量B[0,lb)=_elem[lo,mi)
	for (Rank i = 0; i < lb; B[i] = A[i++]);
	// 为B开辟新的内存空间 并将A的前半部分复制到前子向量B

	int lc = hi - mi;
	T* C = _elem + mi; // 后子向量C[0,lc)=_elem[mi,hi)
	// C现在就是A的后半段 只是用了一个新的指针去索引
	// 没有开辟新的内存 也没有复制

	for (Rank i = 0, j = 0, k = 0;(j < lb) || (k < lc);)
								// B[j] C[k]都没了 算法就退出
	{
		if ((j < lb) && (lc <= k) || (B[j] <= C[k]))
		// && 的优先级比 || 更高 就相当于 ( (j < lb) && (lc <= k) ) || (B[j] <= C[k])
		// (B[j]有值 并且 C[k]已经没有了) 或者 C[k]大于等于B[j]
			A[i++] = B[j++]; // 就是取两边相比之下数值更小的 或者只有一边还剩下了元素
			// 这里是B的元素更小 所以取B中的元素放到A里
		if ((k < lc) && (lb <= j) || (c[k] <= B[j]))
		// (C[k]有值 并且 B[j]已经没有了) 或者 B[j]大于等于C[k]
			A[i++] = C[k++];  // 取C中的元素放到A里 
	}
	delete[] B; // 释放临时空间B
}

// vector_mergeSort.h
template <typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi)
{
	T* A = _elem + lo;

	int lb = mi - lo;
	T* B = new T[lb];
	for (Rank i = 0; i < lb; B[i] = A[i++]);

	int lc = hi - mi;
	T* C = _elem + mi;

	for (Rank i = 0, j = 0, k = 0;(j < lb);) // 删除了 || (k < lc) 因为不需要考虑C提前耗尽 只要B提前耗尽 就终止这个算法
	{
        // 两个if语句相较上个版本 交换了位置
        if ((k < lc) && (c[k] <= B[j])) // 进入循环时已经判断了j<lb 则不想需要再考虑j与lb
			A[i++] = C[k++];
		if ((lc <= k) || (B[j] <= C[k]))
			A[i++] = B[j++];
	}
	delete[] B;
}

// list_operator_bracket.h
#pragma once
#include "list.h"

template <typename T>
ListNodePosi<T> List<T>::operator[](Rank r) const
{
	ListNodePosi<T> p = first(); // 从首节点出发
	while (0 < r--) p = p->succ; // 不断沿着succ引用向后行进 结束时p正好处于秩为r的节点
	return p->data;
}

// listNode.h
#pragma once

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; // 前驱
	ListNodePosi<T> succ; // 后继

	ListNode() {} // 针对header和trailer的构造
	ListNode(T e, ListNodePosi<T> p = NULL, ListNodePosi<T> s = NULL)
		: data, pred(p), succ(s) {} // 默认构造器

	ListNodePosi<T> insertAsPred(T const& e); // 前插入
	ListNodePosi<T> insertAsSucc(T const& e); // 后插入
};

// list.h
#pragma once
#include "listNode.h"

template <typename T>
class List
{
private:
	int _size; // 规模
	ListNodePosi<T> header;
	ListNodePosi<T> 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) { copyNodes(L.first(), L._size); } //整体复制列表L
	List(List<T> const& L, Rank r, Rank n) //复制列表L中自第r项起的n项
	{
		ListNodePosi<T> p = L.first();
		while (0 < r--) p = p->succ;
		copyNodes(p, n);
	}
	List(ListNodePosi<T> p, Rank n) { copyNodes(p, n); } //复制列表中自位置p起的n项
	// 析构方法
	~List() { clear(); delete head; delete tail; } //释放（包含头、尾哨兵在内的）所有节点
	// 只读访问接口
	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) && (head != 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> insertFirst(T const& e); //将e当作首节点插入
	ListNodePosi<T> insertLast(T const& e); //将e当作末节点插入
	ListNodePosi<T> List<T>::insertBefore(ListNodePosi<T> p, T const& 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 deduplicate(); //无序去重
	Rank uniquify(); //有序去重
	// 遍历
	void traverse(void (*)(T&)); //依次实施visit操作（函数指针）
	template <typename VST> void traverse(VST&); //依次实施visit操作（函数对象）
};

// list_init.h
#pragma once
#include "list.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;
}

#pragma once
#include "list.h"

template <typename T>
ListNodePosi<T> List<T>::insertBefore(ListNodePosi<T> p, T const& e)
{
	_size++;
	return p->insertAsPred(e);
}

template <typename T>
ListNodePosi<T> ListNode<T>::insertAsPred(T const& e)
{
	ListNodePosi<T> x = new ListNode(e, pred, this);
    // (b)创建节点 数值为e 新插入节点的前驱是当前的前驱 p->pred 新插入节点的后继是当前节点this 也就是p
	pred->succ = x; // (c)原来的前驱 以新的节点作为后继
	pred = x; // 当前节点 以新的节点作为前驱
	return x;
}

// list_copyNodes.h
#pragma once
#include "list.h"

template <typename T>
void List<T>::copyNodes(ListNodePosi<T> p, Rank n) // 从某一个列表的位置p开始 随后的连续n个节点
{
	init(); // 创建空列表 创建头尾哨兵 并做初始化
	while (n--)
	{
		insertBefore(trailer, p->data); // 把 从位置p开始的n项 依次作为末节点插入
		p = p->succ; // 转向当前节点的后继
	}
}

// list_remove.h
#pragma once
#include "list.h"

template <typename T>
T List<T>::remove(ListNodePosi<T> p) // 删除位置p处的节点 并返回其数值
{
	T e = p->data;

	p->pred->succ = p->data; // 把p现在的后继 当作p现在的前驱的后继
	p->succ->pred = p->pred;

	delete p;
	_size--;

	return e; // 返回数值
}

// list_clear.h
#pragma once
#include "list.h"

template <typename T>
Rank List<T>::clear()
{
	int oldSize = _size;
	while (0 < _size)
		remove(header->succ); // 反复删除首节点 直到列表变空 对外可见的节点有多少个 就删除多少次
	return oldSize;
}

// list_find.h
#pragma once
#include "list.h"

template <typename T>
ListNodePosi<T> List<T>::find(T const& e, Rank n, ListNodePosi<T> p) const
{
	while (0 < n--)
		if (e == (p = p->pred)->data) // 从后往前 取出数据与e比对 直到命中或范围越界
			return p;
	return NULL; // 越出左边界 查找失败
}

// list_deduplicate.h
#pragma once
#include "list.h"

template <typename T>
Rank List<T>::deduplicate()
{
	if (_size < 2)
		return 0;
	Rank oldSize = _size;
	ListNodePosi<T> p = first(); // p从首节点开始
	Rank r = 1;
	while (trailer != (p = p->succ))
	{
		ListNodePosi<T> q = find(p->data, r, p); // 在p的n个真前驱中 查找重复
		q ? remove(q) : r++; // 若真的存在 删除它 删完之后 r不用增加1 p也归入前缀了 否则秩递增 p就归入前缀了
	}
	return oldSize - _size;
}

// list_uniquify.h
#pragma once
#include "list.h"

template <typename T>
Rank List<T>::uniquify() // 成批剔除重复元素
{
	if (_size < 2) return 0; // 平凡列表自然没有重复
	Rank oldSize = _size;
	ListNodePosi<T> p = first();
	ListNodePosi<T> q;
	while (trailer != ( q = p->succ)) // 反复考察紧邻的节点对(p,q)
	{
		if (p->data != q->data)
			p = q; // 若互异 则转向下一区段
		else
			remove(q); // 若雷同 删除后者
	}
	return oldSize - _size;
}

// list_search.h
#pragma once
#include "list.h"

template <typename T>
ListNodePosi<T> List<T>::search(T const& e, Rank n, ListNodePosi<T> p) const
{
	while (0 <= n--)
		if (((p = p->pred)->data) <= e) // 从后往前 转向p的直接前驱 取出数据与e比较
			break;
	return p;
}

// list_selectionSort.h
#pragma once
#include "list.h"

template <typename T>
void List<T>::selectionSort(ListNodePosi<T> p, Rank n)
{
	ListNodePosi<T> head = p->pred;
	ListNodePosi<T> tail = p;
	// 待排序区间

	for (int i = 0; i < n; i++)
		tail = tail->succ;
	while (1 < n)
	{
		insertBefore(tail, remove(selectMax(head->succ, n))); //找到最大的值 删掉 然后把remove返回的这个值 插入到tail之前
		tail = tail->pred; // tail每次向前移动一个节点 tail是待排列序列的尾部
		n--;
	}
}

// list_selectMax.h
#pragma once
#include "list.h"

template <typename T>
ListNodePosi<T> List<T>::selectMax(ListNodePosi<T> p, Rank n)
{
	ListNode<T> max = p; // 记录当前最大节点
	for (ListNode<T> cur = p; 1 < n; n--) // cur是当前遍历
		if (!lt((cur = cur->succ)->data, max->data))
		// !lt less than 不小于 前者不小于后者 就把max更新为这个不小的
		// 若有重复的 最终它会选取最靠后的 那么max只可能递增 不会下降
		// gt greater than
			max = cur;
	return max;
}

// list_insertSort.h
#pragma once
#include "list.h"

template <typename T>
void List<T>::insertionSort(ListNodePosi<T> p, Rank n)
{
	for (int r = 0; r < n; r++) // r是已经排序的前缀长度
	{
		insertAfter(search(p->data, r, p), p->data); // search返回一个不大于新拿到的牌的最靠后的那张牌
		p = p->succ; // p是未排序的后缀的开头 最新拿到的那张牌 在有哨兵时 p->succ永远是安全的
		remove(p->pred);
	}
}

// stack.h
#pragma once
#include "../vector/vector.h"

template <typename T>
class Stack : public Vector<T> // 使用public就可以直接沿用size() empty()等
{
public:
	void push(T const& e) { insert(e); } // 入栈
	T pop() { return remove(size() - 1); } // 出战
	T& top() { return (*this)[size() - 1]; } // 取栈顶 返回当前向量的末元素
    // 都可以写成this->insert(e) this->size()
};

// stack_convert.h
#include "stack.h"

void convert(Stack<char>& S, __int64 n, int base)
{
    static char digit[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
    while (n > 0)
    {
        S.push(digit[n % base]); // 余数入栈
        n /= base; // n更新为其对base的除商
    }
}

int main()
{
	Stack<char> S;
	__int64 n = 89;
	int base = 2;
	convert(S, n, base); // 用栈记录转换得到的各数位
	while (!S.empty())
		printf("%c", S.pop()); // 逆序输出
}

// stack_paren.cpp
#include "stack.h"

bool paren(const char exp[], int lo, int hi)
{
	Stack<char> S; // 使用栈记录已发现但尚未匹配的左括号
	for (int i = lo; i < hi; i++) // 逐一检查当前字符
	{
		if ('(' == exp[i]) // 是左括号
			S.push(exp[i]); // 左括号入栈
		else if (!S.empty()) // 否则就是右括号
			S.pop(); // 否则就是右括号 遇右括号时 如果栈非空 弹出栈顶的左括号
		else
			return false; // 否则栈为空 即遇到右括号时 栈为空 必然不匹配
	}
	return S.empty(); // 栈空当且仅当匹配 若非空 必定是有左括号 但没有右括号和它配对
}

// stack_evaluate.cpp
#include "stack.h"
#include <cctype>

float evaluate(char* S, char*& RPN)
{
	Stack<float> opnd; // 运算数栈
	Stack<char> optr; // 运算符栈
	optr.push('\0'); // 结束标志首先推入操作符栈
	while (!optr.empty()) // 逐渐处理各字符 直至运算符空
	{
		if (isdigit(*S)) // 当前字符如果是数字
			readNumber(S, opnd); // 读入数字 放入运算符栈 可能多位要完整读入 具体实现暂略
		else // 当前字符是运算符
			switch (orderBetween(optr.top(), *S))
			{
				// 查要看其与栈顶运算符之间优先级的高低
				// 暂略
			}
	}
	return opnd.pop();
}

#define N_OPTR 9 // 定义运算符的数量，用于优先级矩阵的维度

const char pri[N_OPTR][N_OPTR] = // 运算符优先级[栈顶][当前]
{
	'>', '>', '<', '<', '<', '<', '<', '>', '>',
	'>', '>', '<', '<', '<', '<', '<', '>', '>',
	'>', '>', '>', '>', '<', '<', '<', '>', '>',
	'>', '>', '>', '>', '<', '<', '<', '>', '>',
	'>', '>', '>', '>', '>', '<', '<', '>', '>',
	'>', '>', '>', '>', '>', '>', ' ', '>', '>',
	'<', '<', '<', '<', '<', '<', '<', '=', ' ',
	' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
	'<', '<', '<', '<', '<', '<', '<', ' ', '='
};

switch (orderBetween(optr.top(), *S))
{
	// 查要看其与栈顶运算符之间优先级的高低
	case '<': // 栈顶运算符优先级更低 比如栈顶加号 又来了个乘号
		optr.push(*S); S++; break; // 计算推迟 当前运算符进栈 目光转向表达式的下一个字符
	case '=': // 优先级相等 只有可能是栈顶为'(' 当前为')' 或者栈顶为'/0' 当前为'/0'
		// 1 栈顶'(' 当前')'
		// 这样一对括号彼此相逢 只可能是括号内的运算符都算完了
		// 括号里只可能有数字 不会有运算符
		// 它们直接消失就好了 栈顶'('也弹出 当前')'忽略 注意力转向表达式的下一个字符
		// 2 栈顶'\0' 当前'\0'
		// 最开始时 我们往栈底推入了一个'\0' 遇到了当前作为整个表达式结束标志的'\0'
		// 将栈顶'\0'弹出 即栈清空 并将注意力跳过当前的\0字符
		optr.pop(); S++; break;
	case '>': // 栈顶运算符优先级更高 可以计算了 结果入栈 比如栈顶乘号 又来了个加号
		char op = optr.pop(); // 弹出目前的栈顶操作符
		if ('!' == op) // 阶乘 一元操作符
			opnd.push(calcu(op, opnd.pop())); // 弹出操作数栈的栈顶 用这个操作符计算 计算结果推回到操作数栈 
		else
		{
			float pOpnd2 = opnd.pop (), pOpnd1 = opnd.pop(); // pOpnd2是后进先出
			opnd.push(calcu(pOpnd1, op, pOpnd2)); // 这两个操作数用操作符计算
			// 如果栈顶是3 第二靠近栈顶的是2 那么pOpnd2就是3 pOpnd1就是2 op是'\' 那就是计算2\3
			// 不直接使用opnd.push(calcu(opnd.pop(),op,opnd.pop()))
			// 因为这两个pop的求值顺序是未定义行为 具体怎样完全取决于编译器
		}
		break;
}