【数据结构C++邓俊辉】笔记

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的元素的最大秩;
  • 有多个命中元素时,总能保证返回秩最大者;查找失败时,能够返回失败的位置。
上一篇:redis快速入门


下一篇:用requests及BeautifulSoup实现豆瓣电影信息的获取