Chapter 1 向量

1.1 Fabonacci数：线性递归，返回当前计算值，通过引用记录上一计算值

https://blog.csdn.net/qq_43118572/article/details/120139946

1.2 Vector向量支持的操作接口

https://blog.csdn.net/qq_43118572/article/details/120142465

1.3 删除

• 区间删除: remove(lo, hi)
  • 这种方式不是删除一次挪动一次数组，大大减少了时间复杂度

template <typename T> int Vector(T)::remove(Rank lo, Rank hi) {
	if (lo == hi) return 0;
	// 将hi后继元素搬到lo后面来，再更改_size大小，是减少时间复杂度的精髓
	while (hi < _size) _elem[lo++] = _elem[hi++];
	_size = lo;
	shrink(); // 若有必要，则缩容
	return hi - lo;  
}

• 单元素删除remove( r )：通过重载remove接口，删除单元素其实是删除区间的特例。

template <typename T> T Vector<T>::remove(Rank r) {
	T e = _elem[r];
	remove(r, r+1);
	return e;
}

1.4 唯一化 【低效版】

• 算法思想：自前向后考察各元素，若当前元素在前面所有元素出现过，则执行remove操作删除当前元素

template <typename T> int Vector<T>::deduplicate() {
	int oldsize = _size;
	Rank i = 1; // 从_elem[1]开始
	while (i < _size) 
		(find (_elem[i], 0, i) < 0) ? i++ : remove(i);
	return oldsize - _size;
}

1.5 遍历

• ( void ( *visit ) ( T& ) )：从中-右-左顺序读——visit是个指针，指向参数为T& 的函数，返回值类型为void。

  // 方法一：
  template <typename T> void Vector<T>::traverse(void (*visit) (T&))  // 借助函数指针机制 {
  	for (int i=0; i < _size; i++)
  		visit(_elemn[i]);
  }
  
  // 方法二：
  template <typename T>  // 元素类型
  template <typename VST> // 操作器
  void Vector<T>::traverse(VST& visit) // 借助函数对象机制 {
  	for (int i=0; i < _size; i++)
  		visit(_elemn[i]);  // 遍历变量
  }
  

• 实例

  template <typename T> 
  struct Increase // 函数对象：递增一个T类对象
  {
  	virtual void operator() (T& e)  { e++; }
  }
  
  template <typename T>  void increase (Vector<T> &V)
  {
  	V.traverse(Increase<T>());  // 以Increase为基本操作进行遍历
  }
  

1.6 唯一化 【高效版】

• 前提：在向量已经有序的前提下，去除重复元素

• 算法思想：有序向量的重复元素必定是一个序列区间，故只需依次保留各区间的起始元素。使用i,j两个变量分别指向相邻子区间的首元素，将后者移至前者的后继位置。

  template <typename T> 
  int Vector<T>::uniquify() {
  	Rank i = 0, j = 0;
  	while (++j < _size )  
  		if ( _elem[i] != _elem[j] )
  			_elem[++i] = _elem[j];
  	_size = ++i;
  	shrink();
  	return j - i;
  }
  

1.7 二分查找

版本A：三支查找法

• 深入比较[lo, hi) , mi , (mi + 1, hi)

template <typename T> static Rank binSearch(T* A, const & e, Rank lo, Rank hi) {
		while (lo < hi) {
			Rank mi = (lo + hi) >> 2;
			if ( e < A[mi] ) hi = mi;
			else if ( e > A[mi] ) = lo = mi + 1;
			else
				return mi;
		}
		return -1;
	}

• 这种算法的不足在于：在每一步迭代中为确定左、右分支方向，分别需要做1次或2次元素比较。
• 解决办法：1）调整前、后区域的宽度，适当地加长（缩短）前后子向量——Fibonacci查找算法 ； 2）两分支法 【 ( e < A[mi] ) ? hi = mi : lo = mi; 】

版本B：两支查找法，错误仅返回-1

• 深入比较[lo, hi) , [mi , hi)

template <typename T> static Rank binSearch(T* A, const & e, Rank lo, Rank hi) {
	while ( 1 < hi - lo ) { // 每次迭代只需做一次比较判断，有两个分支；成功查找不能提前终止
		Rank mi = (hi - lo) >> 1;
		( e < A[mi] ) ? hi = mi : lo = mi;
	} // 出口是hi - lo = 1，查找区间仅含一个元素A[lo]
	return ( e == A[lo] ) ? lo : -1 ;
} // 有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地返回-1， 而不指示失败的位置

• 成功查找不能提前终止。
• 最好情况的时间复杂度提高，但最坏情况的时间复杂度下降。
• 有多个命中元素时，不能保证返回秩最大者

版本C：两支查找法，失败时能返回失败的位置

• 若在插入新元素e之前通过查找确定适当的插入位置，则希望在查找失败时返回不大（小）于e的最后（前）一个元素，以便将e作为其后继（前驱）插入向量。
• 深入比较[lo, hi) , (mi, hi)

  template <typename T> static Rank binSearch (T* A, T const& e, Rank lo, Rank hi) {
  	while (lo < hi) {
  		Rank mi = ( hi - lo ) >> 2;
  		( e < A[mi] ) ? hi = mi: lo = mi + 1;
  	} // 查找成功不能提前终止
  	return --lo; // 循环终止时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
  } // 有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置。
  

• 循环终止时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩；
• 有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置。