数据结构与算法 2. 向量 2021-07-04 浏览量 1295 暂无评论 [TOC] # 2.1 接口与实现 向量与列表都属于线性序列。 1. 这种数据结构怎么实现:接口 2. 这种数据结构对应的有效的算法实现,比如 查找、排序 ## 2.1.1 抽象数据类型(ADT)和数据结构 数据结构是基于某种特定的语言,实现ADT的一整套算法。 ## 2.1.2 从数组到向量 内存中连续,数组中的A[i]的物理地址=A + i * s(s为单个元素占用的空间量),故亦称线性数组。 向量是数组的抽象与泛化,由一组元素按线性次序封装而成。 1. 各元素与[0, n)内的秩一一对应 2. **元素类型不限于基本类型** 接口: ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210421185621188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 2.1.3 Vector模板类 ```cpp typedef int Rank; #define DEFAULT_CAPACITY 3 template class Vector { private: Rank _size; int _capacity; T* _elem; protected: /* ... 内部函数 */ public: /* ... 构造函数 */ /* ... 析构函数 */ /* ... 只读接口 */ /* ... 可写接口 */ /* ... 遍历接口 */ }; ``` **构造与析构** ```cpp Vector(int c = DEFAULT_CAPACITY) { _elem = new T[_capacity = c]; _size = 0; } // 默认 Vector(T const * A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } Vector(Vector const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); } Vector(Vector const& V) { copyFrom(V._elem, 0, V._size); } ~Vector() { delete [] _elem; } ``` **copyFrom** ```cpp template // T为基本类型,或已重载赋值操作符'=' void Vector::copyFrom(T* const A, Rank lo, Rank hi) { _elem = new T[_capacity = 2*(hi - lo)]; _size = 0; while (lo < hi) _elem[_size++] = A[lo++]; } ``` # 2.2 可扩充向量 使用静态空间管理,容量固定,可能发生上溢或下溢 能否根据实际需要动态调整容量呢? **在即将发生上溢时,适当扩大内部数组的容量** ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210424203647629.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp template void Vector::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]; delete [] oldElem; ``` **容量递增的策略:** 为什么每次要翻倍呢?如果扩充固定大小的容量会怎样呢? 考虑在初始容量为0的空向量中,连续插入m = m*I >> 2 即便不计算申请空间操作,总体复制原向量的耗时(算术级数)为: $I*(m-1)*m/2=O(n^2)$,每次扩容的分摊成本为$O(n)$ 而容量加倍策略的总耗时(几何级数)为$O(n)$ **分摊复杂度:** 对数据结构连续地实施足够多次操作,所需总体成本分摊至单次。 # 2.3 无序向量 ## 2.3.1 循秩访问 使用V.get()和V.put(r, e)接口不便捷,没有下标访问好 **重载下标操作符“[ ]”**,因为返回引用,所以既可以作为右值,又可以作为左值 ```cpp template T & Vector::operator[](Rank r) const { return _elem[r]; } ``` ## 2.3.2 插入 ```cpp template Rank Vector::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; } ``` ## 2.3.3 区间删除 ```cpp template int Vector::remove(Rank lo, Rank hi) { if (lo == hi) return 0; while (hi < _size) _elem[lo++] = _elem[hi++]; // 从后往前,不能反 _size = lo; shrink(); // 这里为什么_size = lo?,因为这时候lo已经变成_size-hi+lo return hi - lo; ``` ## 2.3.4 查找 对于无序向量,T为可判等的基本类型,或已重载操作符“==”或“!=”; 对于有序向量,T为可比较的基本类型,或已重载操作符“<”或“>” **输入敏感:** ```cpp template Rank Vector::find(T const & e, Rank lo, Rank hi) const { while ((lo < hi--) && (e != _elem[hi])); // hi == lo怎么办呢 return hi; } ``` 注: ```cpp int main(int argc, char** argv) { int a[] = { 0, 1, 2, 3, 4 }; int hi = 4; while ((0 < hi--) && (a[hi] != -1)) printf("%d\n", hi); printf("End: %d\n", hi); } 3 2 1 0 End: -1 ``` ## 2.3.5 单元素删除 [r] = [r, r+1) ```cpp // O(n-r) template int Vector::remove(Rank lo, Rank hi) { T e = _elem[r]; remove(r, r + 1); return e; ``` 为什么不反过来利用单元素删除实现区间删除呢?效率问题,每个单元素删除都要将后继元素前移。 ## 2.3.6 唯一化 剔除重复元素。 ```cpp // 效率太低 template int Vector::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)中,各元素彼此互异 单调性: 前缀长度单调非降,且迟早增至_size 后缀长度单调下降,且迟早降至0 ## 2.3.7 遍历 遍历向量,统一对各元素分别实施visit操作 如何指定visit操作?将其传到向量内部? 1. 利用函数指针机制,只读或局部性修改,为什么?因为函数已经定义了类型 ```cpp template void Vector::traverse(void (*visit)(T&)) { for (int i = 0; i < _size; i++) visit(_elem[i]); } ``` 2. 利用函数对象(重载()操作符)机制,可全局性修改,通用性更强 ```cpp template template void Vector::traverse(VST& visit) { for (int i = 0; i < _size; i++) visit(_elem[i]); } ``` # 2.4 有序向量 无序:能进行比对操作 有序:能进行比较操作 ## 2.4.1 有序性及其甄别 无序向量经预处理转换为有序向量后,相关算法多可优化 ```cpp template int Vector::disordered() const { int n = 0; for (int i = 1; i < size; i++) n += (_elem[i-1] > _elem[i]); return n; } ``` ## 2.4.2 唯一化 观察:在有序向量中,重复的元素必然相互紧邻构成一个区间 ### 低效版 ```cpp template int Vector::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-1)+O(n-2)+...+O(1)=O(n^2)$ ### 高效版 将每个重复区间作为一个整体,成批删除,不显示删除,直接把唯一的元素放在前面,去掉后面的区间。 ```cpp template int Vector::uniquify() { Rank i = 0, j = 0; while (++j < _size) if (_elem[i] != _elem[j]) _elem[++i] = _elem[j]; _size = ++i; return j - i; ``` 复杂度:$O(n)$ ## 2.5 有序向量二分查找 版本A [lo, hi) ```cpp template static Rank 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; } ``` ## 2.7 查找长度 考察关键码的比较次数 有序向量二分查找约1.50logn ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608220129366.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 3.1 fib查找构思 二分查找可改进的地方: - 转向左右分支前的关键码比较次数不等,而递归深度却相同 改进思路: 通过递归深度的不均衡,对转向成本的不均衡进行补偿。即向左转向时,分配的长度更长,这样左转向需要的递归深度就变深,右转向的深度变浅 实现: 可以用fib数列进行分配。若设$n=fib(k)-1$,则可取$mi=fib(k-1)-1$,于是,前、后子向量的长度分别为$fib(k-1)-1$和$fib(k-2)-1$ # 3.2 fib查找实例 查找长度 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630152239793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 3.3 fib查找实现 ```cpp template static Rank fibSearch(T* A, T const & e, Rank lo, Rank hi) { Fib fib(hi - lo); while (lo < hi) { while (hi - lo < fib.get()) fib.prev()); // 至多迭代几次? Rank mi = lo + fib.get() - 1; if (e < A[mi]) hi = mi; else if (A[mi] < e) lo = mi + 1; else return mi; } return -1; } ``` # 3.4 fib查找最优性 通用策略:对于任何的A[0, n),总是选取$A[\lambda n]作为轴点$, 比如,二分:$\lambda = 0.5$,Fib:$\lambda = 0.618$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630160948316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 4.1 二分查找改进构思 - 二分查找左右转向代价不平衡,那直接让它平衡,减少比较次数 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630162312523.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 实现 ```cpp template static Rank binSearch(T* A, T const & e, Rank lo, Rank hi) { while (1 < hi - lo) { Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi; } return (e == A[lo]) ? lo : -1; } ``` ### 缺陷 无论如何,都要查到1 >= hi - lo,即没有单独考虑直接命中mi的情况,最好的情况更坏,最坏的情况更好,性能稳定。 # 4.2 二分改语义 上述查找算法均未严格地兑现search()接口的语义约定:返回不大于e的最后一个元素。 ```cpp template static Ranik binSearch(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; } ``` # 5.1 冒泡排序构思 **原始版本:** 其实已经使用sorted标志进行改进了,如果上一趟没有交换任何两个元素,那么就说明已经有序,程序结束。 ```cpp void bubblesort(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; } } template void Vector::bubbleSort(Rank lo, Rank hi) { while (!bubble(lo, hi--)); } template bool Vector::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; } ``` **改进版:** 原始版本中,如果前一部分无序,后一部分有序,扫描交换的趟数不会超过无序前缀的长度,但后部分的有序性并没有利用上。 改进思路:记录最右侧逆序对的位置,作为下一趟冒泡的末尾,这样就能利用有序的后缀,减少趟数,比如无序前缀为326,有序后缀为4589,第一趟后,有序后缀变为45689,最右侧逆序对的位置为4,下一趟只需要对2345排序,而不是234568,这样就有效地利用了后缀的有序性。 ```cpp template Rank Vector::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; } ``` **评价:** 输入含重复元素时,算法的稳定性是更为细致的要求,即保持重复元素的前后位置不变。 上述算法满足稳定性,因为只有在逆序时(>)才交换,等于时不变。 # 6.1 归并排序 分治--合并 主算法 ```cpp template void Vector::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); } ``` 二路归并 ```cpp template void Vector::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); ) { 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; } ``` 二路归并改进 ```cpp template void Vector::merge(Rank lo, Rank mi, Rank hi) { T* A = _elem + lo; int lb = mi - lo; T* B = new T[lb + 1]; for (Rank i = 0; i < lb; B[i] = A[i++]); B[lb] = inf; int lc = hi - mi; T* C = new T[lc + 1]; for (Rank i = 0, j = mi; i < lc; C[i] = A[j++]); C[lc] = inf; Rank j = 0, k = 0; for (Rank i = 0; i < hi - lo; i++) { if (B[j] <= C[k]) A[i] = B[j++]; else A[i] = C[k++]; } delete [] B; } ``` 赞赏 微信支付 支付宝支付