数据结构-向量

本篇文章整理《数据结构(C++语言版)》关于向量这种线性结构知识点。

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。
线性表有两种存储方式,一种是顺序存储结构,另一种是链式存储结构。即,一种是物理地址与逻辑地址均连续,另一种是只有逻辑地址连续
线性表两种形式

向量

向量结构是一种顺序存储结构,即其物理地址与逻辑地址均连续(数组array是一种无序向量实例)。
向量可以通过寻秩访问进行快速定位向量中某一元素,与此同时,由于其物理地址连续性,向量在删减或添加某个元素时,需对被修改位置之后的所有元素依次向前(后)移动,以保证其物理地址连续性。
向量添加元素示例

遍历

对向量中所有元素实施某种统一操作。
具体有两种采用方式,前一种是借助函数指针*visit()指定某一函数;后者 借助函数对象机制,通过将操作符”()”重载后,使其调用方式可以如同函数一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void Vector<T>::traverse(void (*visit) (T&) ) { //借助函数指针
for(int i = 0; i < _size; i++){
//函数指针调用可以为visit(),也可使用(*visit)(),但前者更合适
visit( _elem[i]);
}
}

template<typename T> template<typename VST>
void Vector<T>::traverse(VST& visit ) { //借助函数对象
for(int i = 0; i < _size; i++){
//函数指针调用可以为visit(),也可使用(*visit)(),但前者更合适
visit( _elem[i]);
}
}

实例

1
2
3
4
5
6
7
8
template <typename T> struct Increase{  //函数对象
virtual void operator() (T& e) {e++;}
}

template <typename T>
void Vector<T>::increase( Vector<T>& V) {
V.traverse( Increase<T>() );
}

唯一化

无序向量
算法:从第二个元素开始,在其前缀中查找相同元素,若存在雷同者,删除当前(最后一个相同元素)。这种算法下,每次最多只有一个相同元素需要去除

1
2
3
4
5
6
7
8
9
10
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;
}

有序向量
算法:对于有序向量,相同元素彼此相邻。设置入选元素_elem[i]与待入选元素_elem[j],比较二者,相同则忽略,不同则将j对应元素赋值i的后继,以此类推。
有序向量唯一化算法示意图

1
2
3
4
5
6
7
8
9
10
template <typename T>
int Vector<T>::uniquify() { //有序向量去重
Rank i = 0, j = 1;
while(j<_size){
(_elem[i] == _elem[j]) ? j++ : _elem[++i] = _elem[j];
}
++i = _size;
shrink(); //截除多余元素
return j - i;
}

查找

无序向量
算法:从后往前,找到该元素对应秩最大者。
代码:略。
有序向量
对有序向量而言,通常采用减而治之的策略。即将所查找的区间分段,分别核实待查元素是落入左区间还是右区间亦或是中点位置,再反复迭代。
为了优化算法。一种方法是增加代价小的一方深度,即将区间点不再设置为中点,转而设置Fibonacci节点,使得左区间包含元素更多(代价小);另一种方法,即将中转点包含入右区间中,使得左右区间代价相等(都只需经过一次判断)。
减而治之
算法:
待续….

本文标题:数据结构-向量

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2019年04月17日 - 20:04

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-向量/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~