苏州建筑类网站建设,阿里云做网站需要环境,房地产集团网站建设方案,营销型网站建设的五力原则包括抽象数据类型 数组到向量
C/C 中#xff0c;数组A[]中的元素与[0,n)内的编号一一对应#xff0c;A[0],A[1],...,A[n-1]#xff1b;反之#xff0c;每个元素均由#xff08;非负#xff09;编号唯一指代#xff0c;并可直接访问A[i] 的物理地址 Ai s#xff0c;s 为单…抽象数据类型 数组到向量
C/C 中数组A[]中的元素与[0,n)内的编号一一对应A[0],A[1],...,A[n-1]反之每个元素均由非负编号唯一指代并可直接访问A[i] 的物理地址 Ai × ss 为单个元素占用的空间量所以也叫作线性数组。
向量是数组的抽象与泛化由一组元素按线性次数封装而成。各元素与[0,n)内的秩rank一一对应。 元素的类型不限于基本类型 操作、管理维护更加简化、统一与安全 可更为便捷地参与复杂数据结构的定制与实现
Vector 模板类
using Rank unsigned int; //秩
#define DEFAULT_CAPACITY 3 //默认的初始容量实际应用中可设置为更大
template typename T class Vector { //向量模板类
private:Rank_size;int_capacity;T* _elem;//规模、容量、数据区
protected:/.../
public://构造函数Vector ( Rank c DEFAULT_CAPACITY, Rank s 0, T v 0 ) //容量为c、规模为s、所有元素初始为v{ _elem new T[_capacity c]; for ( _size 0; _size s; _elem[_size] v ); } //scVector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //数组整体复制Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //区间Vector ( VectorT const V ) { copyFrom ( V._elem, 0, V._size ); } //向量整体复制Vector ( VectorT const V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //区间// 析构函数~Vector() { delete [] _elem; } //释放内部空间
}; //Vector可扩充向量
静态空间管理
开辟内部数组_elem[]并使用一段地址连续的物理空间 _capacity 总容量 _size当前的实际规模n
若采用静态空间管理策略容量_capacity固定则有明显的不足 1.上溢( overf1ow ) : _elem[]不足以存放所有元素 尽管此时系统仍有足够的空间 2.下溢( underflow ) : _elem[]中的元素寥寥无几 装填因子(load factor) λ _ s i z e / _ c a p a c i t y 50 % \lambda \_size/\_capacity 50\% λ_size/_capacity50%
更糟糕的是一般的应用环境中难以准确预测空间的需求量。
动态空间管理
在即将发生上溢时适当地扩大内部数组的容量
template typename T
void VectorT::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]; //T为基本类型,或已重载赋值操作符delete [] oldElem; //释放原空间
}得益于向量的封装尽管扩容之后数据区的物理地址有所改变却不致出现野指针。
容量加倍策略在时间复杂度上总体优于容量递增策略。 \space 递增策略倍增策略累计增容时间 O ( n 2 ) \mathcal O(n^2) O(n2) O ( n ) \mathcal O(n) O(n)分摊增容时间 O ( n ) \mathcal O(n) O(n) O ( 1 ) \mathcal O(1) O(1)装填因子 ≈ 100 % ≈100\% ≈100% 50 % 50\% 50%
平均分析 vs 分摊分析
平均复杂度或期望复杂度(average/expected complexity) 根据数据结构各种操作出现概率的分布将对应的成本加权平均 各种可能的操作作为独立事件分别考查 割裂了操作之间的相关性和连贯性 往往不能准确地评判数据结构和算法的真实性能
分摊复杂度(amortized complexity) 对数据结构连续地实施足够多次操作所需总体成本分摊至单次操作 从实际可行的角度对一系列操作做整体的考量 更加忠实地刻画了可能出现的操作序列 可以更为精准地评判数据结构和算法的真实性能
分摊复杂度和平均复杂度的结果并没有必然联系。
无序向量
元素访问
通过V.get(r)和V.put(r)接口可以对元素进行读写。 可以重载下标操作符增加其便捷性
templatetypename T //0 _size
T VectorT::operator[](Rank(r)) const {return _elem[r];}此后对外的V[r]即对应内部的V._elem[r]可以使用下标进行操作
//右值
T x V[r] U[s] W[t];
//左值
V[r] T(2*x 3);插入
template typename T //将e插入至[r]
Rank VectorT::insert ( Rank r, T const e ) { //0 r sizeexpand(); //如必要先扩容for ( Rank i _size; r i; i-- ) //自后向前后继元素_elem[i] _elem[i-1]; //顺次后移一个单元_elem[r] e; _size; //置入新元素并更新容量return r; //返回秩
}区间删除
template typename T int VectorT::remove( Rank lo, Rank hi ) { //0 lo hi nif ( lo hi ) return 0; //出于效率考虑单独处理退化情况while ( hi _size ) _elem[lo] _elem[hi]; //后缀[hi, _size)顺次前移 hi-lo 位_size lo; shrink(); //更新规模lo_size之后的内容无需清零如必要则缩容//若有必要则缩容return hi-lo;//返回被删除元素的数目
}单元素删除
可以视作区间删除的特例[r] [r,r1)
template typename T T VectorT::remove( Rank r ) { //删除向量中秩为r的元素0 r sizeT e _elem[r]; //备份被删除元素remove( r, r 1 ); //调用区间删除算法等效于对区间[r, r 1)的删除return e; //返回被删除元素
}查找
template typename T //在无序向量中顺序查找e成功则返回最靠后的出现位置否则返回lo-1
Rank VectorT::find ( T const e, Rank lo, Rank hi ) const { //0 lo hi _sizewhile ( ( lo hi-- ) ( e ! _elem[hi] ) ); //从后向前顺序查找return hi; //若hi lo则意味着失败否则hi即命中元素的秩
}输入敏感最好 O ( 1 ) \mathcal O(1) O(1) 最差 O ( n ) \mathcal O(n) O(n)
实例去重删除重复元素
template typename T Rank VectorT::dedup() { //删除无序向量中重复元素高效版Rank oldSize _size; //记录原规模for ( Rank i 1; i _size; ) //自前向后逐个考查_elem[1,_size)if ( -1 find(_elem[i], 0, i) ) //在前缀[0,i)中寻找与[i]雷同者至多一个O(i)i; //若无雷同则继续考查其后继elseremove(i); //否则删除[i]O(_size-i)return oldSize - _size; //被删除元素总数
}每轮迭代中 find() 和 remove累计耗费线性时间总体为 O ( n 2 ) \mathcal O(n^2) O(n2)
有序向量唯一化
有序/无序序列中任意/总有一对相邻元素顺序/逆序因此相邻逆序对的数目可用以度量向量的逆序程度。
实例有序向量去重
观察︰在有序向量中重复的元素必然相互紧邻构成一个区间。因此每一区间只需保留单个元素即可
低效算法
template typename T Rank VectorT::uniquify() { //有序向量重复元素剔除算法低效版Rank oldSize _size, i 1; //当前比对元素的秩起始于首元素while ( i _size ) //从前向后逐一比对各对相邻元素_elem[i - 1] _elem[i] ? remove ( i ) : i; //若雷同则删除后者否则转至后一元素return oldSize - _size; //向量规模变化量即被删除元素总数
}效率低运行时间主要取决于 while 循环次数共计_size - 1 n -1 最坏 O ( n 2 ) \mathcal O(n^2) O(n2)
高效算法 反思:低效的根源狂于同一元素可作为被删除元素的后继多次前移 启示︰若能以重复区间为单位成批删除雷同元素性能必将改进
template typename T Rank VectorT::uniquify() { //有序向量重复元素剔除算法高效版Rank i 0, j 0; //各对互异“相邻”元素的秩while ( j _size ) //逐一扫描直至末元素if ( _elem[i] ! _elem[j] ) //跳过雷同者_elem[i] _elem[j]; //发现不同元素时向前移至紧邻于前者右侧_size i; shrink(); //直接截除尾部多余元素return j - i; //向量规模变化量即被删除元素总数
}共计 n - 1 次迭代每次常数时间累计 O ( n ) \mathcal O(n) O(n) 时间。
有序向量二分查找A
//二分查找算法版本A)︰在有序向量的区间[lohi)内查找元素e,0 lo hi _size
template typename T static Rank binSearch( T* S, T const e Rank loRank hi ) {while ( lo hi ) { //每步迭代可能要做两次比较判断有三个分支Rank mi ( lo hi ) 1; //以中点为轴点(区间宽度折半等效于其数值表示的右移一位)if( e s[mi] ) hi mi; //深入前半 段[ 1o mi)继续查找else if ( S[mi] e ) lo mi 1; //深入后半段(mihi)继续查找elsereturn mi; //在mi处命中} //成功查找可以提前终止return -1; //查找失败
} //有多个命中元素时不能保证返回秩最大者;查找失败时简单地返回-1而不能指示失败的位置转向左、右分支前的关键码比较次数不等而递归深度却相同
有序向量Fib 查找
若能通过递归深度的不均衡对转向成本的不均衡进行补偿平均查找长度应能进一步缩短…
#include fibonacci/Fib.h //引入Fib数列类
//Fibonacci查找算法版本A在有序向量的区间[lo, hi)内查找元素e0 lo hi _size
template typename T static Rank fibSearch( T* S, T const e, Rank lo, Rank hi ) {//用O(log_phi(n hi - lo)时间创建Fib数列for ( Fib fib( hi - lo ); lo hi; ) { //Fib制表备查此后每步迭代仅一次比较、两个分支while ( hi - lo fib.get() ) fib.prev(); //自后向前顺序查找分摊O(1)Rank mi lo fib.get() - 1; //确定形如Fib(k)-1的轴点if ( e S[mi] ) hi mi; //深入前半段[lo, mi)继续查找else if ( S[mi] e ) lo mi 1; //深入后半段(mi, hi)继续查找else return mi; //在mi处命中} //一旦找到随即终止return -1; //查找失败
} //有多个命中元素时不能保证返回秩最大者失败时简单地返回-1而不能指示失败的位置通用策略对于任何的 A [ 0 n ) A[0n) A[0n)总是选取 A [ λ n ] A[\lambda n] A[λn] 作为轴点 0 ≤ λ 1 0\leq \lambda1 0≤λ1 在 [ 0 1 ) [01) [01)内 λ \lambda λ 如何取值才能达到最优 ? 设平均查找长度为 α ( λ ) ⋅ l o g 2 n α(\lambda)· log_2n α(λ)⋅log2n何时 α ( λ ) α(\lambda) α(λ) 最小? 二分查找 λ 0.5 \lambda 0.5 λ0.5 Fib 查找 0.6180339... 0.6180339... 0.6180339...
有序向量二分查找B
二分查找中左、右分支转向代价不平衡的问题也可直接解决。将中间点包含在了右边。
//二分查找算法版本B在有序向量的区间[lo, hi)内查找元素e0 lo hi _size
template typename T static Rank binSearch( T* S, T const e, Rank lo, Rank hi ) {while ( 1 hi - lo ) { //每步迭代仅需做一次比较判断有两个分支成功查找不能提前终止Rank mi ( lo hi ) 1; //以中点为轴点区间宽度折半等效于其数值表示的右移一位( e S[mi] ) ? hi mi : lo mi; //经比较后确定深入[lo, mi)或[mi, hi)} //出口时hi lo 1查找区间仅含一个元素A[lo]return e S[lo] ? lo - 1 : lo; //返回位置总是不超过e的最大者
} //有多个命中元素时返回秩最大者查找失败时简单地返回-1而不能指示失败的位置有序向量二分查找C
//二分查找算法版本C在有序向量的区间[lo, hi)内查找元素e0 lo hi _size
template typename T static Rank binSearch( T* S, T const e, Rank lo, Rank hi ) {while ( lo hi ) { //每步迭代仅需做一次比较判断有两个分支Rank mi ( lo hi ) 1; //以中点为轴点区间宽度折半等效于其数值表示的右移一位( e S[mi] ) ? hi mi : lo mi 1; //经比较后确定深入[lo, mi)或(mi, hi)} //成功查找不能提前终止return lo - 1; //至此[lo]为大于e的最小者故[lo-1]即为不大于e的最大者
} //有多个命中元素时返回最靠后者查找失败时返回失败的位置与版本B的差异 1)待查找区间宽度缩短至e而非1时算法才结束 2)转入右侧子向量时左边界取作mi 1而非mi——A[mi]会被遗漏? 3)无论成功与否返回的秩严格符合接口的语义约定…
冒泡排序
向量元素若有序排列计算效率将大大提升
template typename T void vectorT::bubbleSort(Rank loRank h1)
{ while (!bubble(lohi--)); } //逐趟做扫描交换直至全序template typename T bool VectorT::bubble(Rank loRank hi) {bool sorted true; //整体有序标志while (lo hi) //自左向右逐一检查各对相邻元素if (_elem[lo - 1] _elem[lo]) { //若逆序则sorted false;//意味着尚未整体有序并需要swap(_elem[lo - 1],_elem[lo]);//交换}return sorted; l/返回有序标志
}//乱序限于[0√n)时仍需O(n^{3/2})时间——按理O(n)应已足矣改进
template typename T void vector1::bubbleSort(Rank loRank h1)
{ while (lo (hi bubble(lohi)));}//逐趟扫描交换直至全序
template typename T Rank VectorT : :bubble(Rank loRank hi) {Rank last lo;//最右侧的逆序对初始化为[lo - 11o]while (lo hi)//自左向右逐一检查各对相邻元素if(_elem[lo - 1] _elem[lo])//若逆序,则last lo;//更新最右侧逆序对位置记录并swap(_elem[lo - 1]_elem[lo]);//交换}return last;//返回最右侧的逆序对位置
}//前一版本中的逻辑型标志sorted改为秩last三种冒泡排序算法效率相同最好o(n)最坏o(n^2) 在冒泡排序中元素 a 和 b 的相对位置发生变化只有一种可能 1.经分别与其它元素的交换二者相互接近直至相邻 2.在接下来一轮扫描交换中二者因逆序而交换位置
归并排序
分治策略向量与列表通用 序列一分为二 ( O ( 1 ) ) (\mathcal O(1)) (O(1))子序列递归排序 ( 2 × T ( n / 2 ) ) (2 \times T(n/2)) (2×T(n/2))合并有序子序列 ( O ( n ) ) (\mathcal O(n)) (O(n)) 总体复杂度为 ( O ( n log n ) ) (\mathcal O(n\log n)) (O(nlogn))
template typename T //向量归并排序
void VectorT::mergeSort( Rank lo, Rank hi ) { // 0 lo hi sizeif ( hi - lo 2 ) return; //单元素区间自然有序否则...Rank mi ( lo hi ) / 2; //以中点为界mergeSort( lo, mi ); mergeSort( mi, hi ); //前缀、后缀分别排序merge( lo, mi, hi ); //归并
}template typename T //对各自有序的[lo, mi)和[mi, hi)做归并
void VectorT::merge( Rank lo, Rank mi, Rank hi ) { // lo mi hiRank i 0; T* A _elem lo; //合并后的有序向量A[0, hi - lo) _elem[lo, hi)Rank j 0, lb mi - lo; T* B new T[lb]; //前子向量B[0, lb) -- _elem[lo, mi)for ( Rank i 0; i lb; i ) B[i] A[i]; //复制出A的前缀Rank k 0, lc hi - mi; T* C _elem mi; //后缀C[0, lc) _elem[mi, hi)就地while ( ( j lb ) ( k lc ) ) //反复地比较B、C的首元素A[i] ( B[j] C[k] ) ? B[j] : C[k]; //将更小者归入A中while ( j lb ) //若C先耗尽则A[i] B[j]; //将B残余的后缀归入A中——若B先耗尽呢delete[] B; //释放临时空间mergeSort()过程中如何避免此类反复的new/delete
}算法的运行时间主要在于 for 循环merge() 总体迭代不超过 O ( n ) \mathcal O(n) O(n) 次累计只需线性时间。 T ( n ) 2 T ( n / 2 ) O ( n ) T(n) 2T(n/2)\mathcal O(n) T(n)2T(n/2)O(n)
位图
位图Bitmap是一种数据结构用于表示一组位或二进制值的集合。在计算机科学中位图通常用于存储和操作大量的二进制数据其中每个位都表示某种状态或信息。 位图中的每个位或者可以理解为数组的元素代表一个元素是否存在于集合中。当元素存在时对应位的值为1不存在时对应位的值为0。
