向量与列表

2017-11-21 20:17:08来源:CSDN作者:shubao0071人点击

分享

  • 写在前面
    • 线性表
  • 向量
    • 遍历
    • 唯一化

写在前面

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

线性表

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

向量

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

遍历

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

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]);      }}

实例

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>() );}

唯一化

无序向量
算法:自前向后逐一考察各元素,并通过调用find()接口,在其前缀中寻找雷同者,调用remove()接口删除雷同着。

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的后继,以此类推。
这里写图片描述

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;}

待续….

微信扫一扫

第七城市微信公众平台