lesson2

#2018/10/8 
向量
抽象数据类型 = 数据模型 + 定义在模型上的一组操作
数据结构     = 基于某种特定语言，实现ADT一整套算法
向量各元素与[0,n)内的秩一一对应
typedef int Rank; //秩
#define DEFAULT_CAPACITY 3
template <typename T> class Vector{
   private : Rank _size; int _capacity; T* _elem; //规模、容量、数据区
   protected:
       /* .. 内部函数 */
   public :
       /* ..构造函数 */
       /* ..析构函数 */
       /* ..只读接口 */
       /* ..可读接口 */
       /* ..可写接口 */
       /* ..遍历接口 */
};
构造与析构
Vector(int c = DEFAULT_CAPICITY){
      _elem = new T[_capicity = c];
      size = 0;
}
Vector(T const * A, Rank lo, Rank hi){//数组区间赋值
      copyFrom(A, lo, hi);
}
Vector(Vector<T> const & V, Rank lo, Rank hi){//向量区间赋值
      copyFrom(V._elem, lo, hi);
}
Vector(Vector<T> const& V){           //向量整体赋值
      copyFrom(V._elem, 0, V._size);
}
~Vector(){
      delete [] _elem;  //释放内部空间
}
基于复制的构造
template <typename T> 
void Vector<T> ::copyFrom(T* const A, Rank lo, Rank hi){
    _elem = new T[_capacity = 2*(hi - lo)]; //分配空间
    _size = 0;       //规模清零
    while (lo < hi){  //A[lo,hi)
        _elem[_size++] = A[lo++]; //逐一复制
    }
 --------------------------------------------------
 可扩充向量
 静态空间管理
 _capacity: 总容量
 _size : 当前的实际规模
 若采用静态空间管理,容量_capacity 固定,不足之处:
  1、上溢：_elem[]不足以存放所有元素
  2、下溢：_elem[]中的元素寥寥无几
     装填因子 = _size / _capacity << 0.5
 动态空间管理:
    在即将发生上溢,适当扩大内部数组的容量
    
 扩容算法实现：   
 template<typename T>
 void Vector<T> ::expand(){
     if (_size < _capicity) 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];
     }
     delete [] oldElem;
 }
 容量递增策略
 T* oldElem = _elem;
 _elem = new T[_capacity + = INCREMENT];
 最坏情况：在初始容量0的空向量中,连续插入n = m*I
 不计申请空间操作，每次扩容过程复制原向量的时间成本 ：    
  插入第        1、2、3、4.....  m  次 
  时间成本      0、I、2I、3I....(m-1)I
  O(n^2) 每次扩容的分摊成本O(n)
  
  容量加倍策略
  T* oldElem = _elem;
  _elem = new T[_capacity <<= 1];
  最坏情况：在初始容量1的空向量中,连续插入n = 2^m;
 不计申请空间操作，每次扩容过程复制原向量的时间成本 ：    
  插入第        1、2、3、4..... m  次 
  时间成本      1、2、4、8.... 2^m 
  O(n) 每次扩容的分摊成本O(1)
  
  平均复杂度：
    根据数据结构各种操作出现的概率的分布，将对应的成本加权平均（上述两种复杂度均为O(n)）
  分摊复杂度：
    对数据结构连续的实施足够多次操作，所需总体成本分摊至单次操作
  -------------------------------------------------------------------------------
  无序向量
      元素访问：
         template <typename T>
         T & Vector<T>::operator[](Rank r) const{
               return _elem[r];
         }
         循秩访问
         右值：T x = V[r] + U[s]*W[t];
         左值：V[r] = (T)(x+3);
         (右值只读，左值可读可写) 
      插入：
          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;
          }
       区间删除：
           template<typename T>
           int Vector<T>::remove(Rank lo, Rank hi){
              if (lo == hi) return 0;
              while (hi <_size) _elem[lo++] = _elem[hi++];
              _size = lo; 
              shrink(); // 若有必要，缩容
              return hi-lo;
           }
        查找：
           无序向量：T为可判等的基本类型，或已重载 == 或!=
           有序向量：T为可比较的基本类型，或已重载 < 或 >
           template<typename T>
           int Vector<T>::find(T const & e,Rank lo, Rank hi) const{
               while ((lo < hi--) &&(e ! = _elem[hi]))
                  return hi;
           } //输入敏感
        单元素删除：
           template<typename T>
           int Vector<T>::remove(Rank r){
           T e = _elem[r];
           remove(r,r+1);
           return e;
           }
         唯一化：
            template<typename T>
            int Vector<T>::deduplicate(){
                int oldSize = _size;
                Rank i = 1;
                while (i < _size)
                    (find(_elem[i],0,i) < 0)?
                        i++
                      : remove(i);   
            return oldSize - _size;
            } //
            不变性：在当前元素V[i] 的前缀V[0,i）中，各元素彼此互异
            单调性：随着反复的while 迭代
                   1）当前元素前缀长度非降
                   2）当前元素后缀长度下降
             find() + remove() ==>   O(n^2) 
             遍历：
               利用 函数指针 机制,只读或局部性修改  (*funP)(int) <==> func(int)
               template<typename T>
               void Vector<T>::traverse(void (*vist)(T&)){
                  for (int i = 0; i < _size;i++)
                    visit(_elem[i]);
               }
               //整个函数指针变量的声明格式如同函数myFun的声明处一样，
               // 只不过——我们把myFun改成（*funP）而已，这样就有了一个
               //能指向myFun函数的指针了。
               //example: typedef int (*p)(int); p func;
               利用 函数对象 机制,可全局性修改
               (重载运算符( )实现)
               template<typename T>
               void Vector<T>::traverse(VST& visit){
                  for (int i = 0; i < _size; i++)
                       visit(_elem[i]);
                }
                函数对象实例：
                   template <typename T>
                   struct Increase{
                      virtual void operator()(T & e){e++}
                   };
                   template <typename T>
                   void increase(Vector<T> & V){
                      V.traverse(Increase<T>());
                   }
  -------------------------------------------------------------------
  有序向量：
     template<typename T>
     int Vector<T>::disorder() const{
         int n = 0;
         for (int i =1; i <_size; i++)
            n + =(_elem[i-1] > _elem[i]);
          return n;  
     }
     唯一性：
     低效版
     template<typename T>
     int 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;
     }
     复杂度：
        O(n^2)
        
     高效版： 
     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;
     }
     复杂度：
        O（n）
        
     查找算法  
     约定：在有序向量区间V[lo,hi) 中,确定不大于e的最后一个元素
     (插入时查找的最后一个)
     template<typename T>
     Rank Vector<T>::search(T const & e, Rank lo, Rank hi){       
     return (rand() % 2) ?
         binSearch(_elem, e, lo, hi)
        :fibSearch(_elem, e, lo, hi);
     }
     template<typename T> //减而治之
     Rank Vector<T>::binSearch(T* A, T const & e, Rank lo, Rank hi){       
         while (lo < hi){
           Rank mi = (lo + hi) >> 1;
           if (e < A[mi])
              hi =  mi;
           else if (A[mi] < e)
              lo = mi + 1;
           else
             return mi;
         }
         return -1;
     }   // O(1.5*logn)
     /**满足取到不小于e的最大索引的二分算法,利用数学归纳法证明*/
     template<typename T> void Vector<T>::binSort(T* A, T e,Rank lo, Rank hi){
     while(lo < hi){
        T mid = (lo+hi)>>1;
        e<mid ? hi = mid : lo = mid+1; 
     }
     return --lo;
   } 
     /**起泡排序改进*/
     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;     
     } 
     ----------------------------------------
     归并算法：
       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){
         T* A = _elem + 1o;
         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);){
            if((j < lb) && (lc <=k ||(B[j] <=C[k])))
               A[i++] = B[j++];
            if((k < lc) && (lb <=j || C[k] < B[j])))
               A[i++] = C[k++];
         }
         delete []B;
       }