[数据结构与算法]数据结构学习（列表：四（有序列表的唯一化、查找算法））

有序列表

唯一化处理

与有序向量同理，有序列表中重复的元素一定（在逻辑上）紧邻。设置位置指针p和q分别指向相邻的节点，若二者雷同则删除q，否则转向下一对相邻节点如此反复迭代，直至检查所有节点：

template <typename T> int List<T>::uniquify()
{
	if(_size < 2) return 0;  //元素数量小于2，自然无重复。
	int oldSize = _size;  //记录原始规模
	Posi(T) p = first(); Posi(T) q;  //p为各段起点，q为其后继
	while(trailer != (q = p -> succ))  //反复考察紧邻节点对（p，q）
		if(p -> data != q -> data)
			p = q;      //若互异，则转向下一区段
		else
			remove(q);  //若相等，则删除后者
	return oldSize - _size;  //规模变化量，及删除元素总数
}	

复杂度： O(n)

查找

//在有序列表内节点p（可能是trailer）的n个（真）前驱中，找到不大于e的最后者
template <typename T> Posi(T) List<T>::search(T const& e, int n, Posi(T) p)
{
	while(0 < n--)   //对于p的n个前驱，从右向左逐一比较
		if(((p = p -> pred) -> data) <= e) //直至命中、数值越界、范围越界
			break;
	return p;  //返回查找终止的位置
}  //若查找失败，返回区间做左边界的前驱（可能是header）

有序列表的查找算法与无序列表的查找算法几乎一样。它无法有序向量那样，进行减治策略的查找，究其原因在于虽然有序列表中各节点在逻辑上按次序单调排列，但在动态存储策略上，节点的物理地址与逻辑次序毫无关系。

复杂度：O(n)