数据结构之——向量

(1).智能指针——Vector（STL）

        在总结本章向量之前，先了解一个重要的模板类vector. 它类似于string，在使用之前需要用 #include **的**头文件来调用。实际上他可以很好地代替动态的数组，因为它可以在末尾附加新数据，还可以在中间插入新的数据。“实际上，vector类确实使用new和delete来管理内存，但这种工作是自动完成的。”

具体介绍： <p align="center"> </p>

•   vector的模板类一般定义如下：（包含大小size，物理容量capacity，数据区_elem）

• vector与构造与析构的一些代码：（一次构造，一次复制构造，两次析构）

• 关于vector中的push_back的描述：（vector有很多接口）

• vector内部基于复制的构造

   不仅要了解如何使用vector和其他类或接口的协同合作，也要搞清楚vector内部是如何实现一些简单的复制的构造接口功能的

（2）可扩充的向量

首先来比较 静态空间管理 和 动态空间管理 <p align="center"> </p>

• 静态空间管理

容量capacity如果是固定的话，那明显随着元素的增加，到一定程度的时候是明显不足够的,也可能开始的容量过大，造成下溢 1.上溢（overflow）:_elem[]不足以存放元素 2.下溢（underflow）:_elem[]中的元素太少（具体又填装因子多少来决定） 填装因子：（load factor）： x = _size / _capacity «50%

• 动态空间管理

动态空间管理有两种办法：①容量加倍策略      ②容量递增策略 这里只写了一个加倍的策略，递增的代码大家可以自己动手去写。: ) 加倍策略实现部分：

另外：在看邓俊辉的教学视频的时候，里面讲到 平均分析 和 分摊分析。主页菌概念也有点模糊，大家各自查资料理解下

• 平均分析:各种操作出现概率的分布，将对应的成本加权平均
• 分摊平均:连续地实施足够多的操作，所需成本分摊至单次操作

（3）无序向量

•  元素的访问

因为数组的访问效率高于逐个的访问 template T & vector ::operator[](Rank r)const {return _elem[r];} **访问哪个编号的元素就输入秩，则返回元素**

•   区间删除

整体的操作过程如下所示，要将lo->hi区间这一段删除，除了达到这个要求，还需要将后面的部分填充上来。

•   插入元素

向一个无序向量里面插入一个元素 操作过程如下图所示，将后面的部分依次往后移动一个单位，用_elem[i] = _elem[i-1];//本来i是没有元素的，整个区段从  0->i-1才有元素 <p align="center"> </p>

• 查找元素（遍历并找到匹配的）

实现方式：从hi一直往前搜索 <p align="center"> </p>

•    剔除重复

当然，除了必须学会的增删改查之外，还有一些比较好用并且需要运用到现实的接口功能，比如剔除重复。 实现：里面核心的地方运用了一个很高明的方法。三目运算符，判断有无重复，调用find,选择删还是不删除，调用remove函数。运用一个三目运算符和两个接口共同组合成剔除重复的核心部分

（4）有序向量

• 逆序数计算（很巧妙简洁的方法）

只需要一条语句 ：  n+=（_elem[i-1] >_elem[i]）//元素i从1开始

• 有序向量剔除重复元素的  低效算法 和  高效算法 的比对

低效算法 在一段有序向量之中，重复元素是成对或者连续存在的，所以入手就比较简单了。

• 有序向量的查找

这其中介绍两种查找方式  二分查找算法 和 Fibonacci查找算法 先写查找的接口：

• 二分法查找的长度

由代码可知  向左 消耗1次  向右  消耗两次

元素一共有4个  总共的情况相加2+3+3+4=12  则平摊下俩 12/4 = 3   刚好这个复杂度是  1.5log(3+1)//这里3+1是约定俗称，一般约为最近的2的平方数 所以  一般的二分法的系数 1.5     O（1.5logn）的复杂度

•  fib查找的构思

二分法的系数是1.5 ，但是这个系数是可以改进的 。 在二分法里面  我们平分的是“深度”  但是转向的次数是不平均的，能不能有一种方法 可以将转向+1（左边）的次数更多的结构呢，如下图。这就要用到fib的数据结构方法来查找了。

这里面有个通用的策略 就是使用黄金分割法  x=0.618…….

• 改进2 可一部改变深度  改变次数  用个三木运算符 将两边的区段改变 包含Mi就可以  详细参考  数据结构

（5）排序—merge and two way merge

在排序算法里面有一个很切实的复杂度区段    一个可接受的复杂度的范围 BubbleSort…..     : O(n^2) ….. ….. ….. C.B.ASort…….     : O(nlogn) 所以在这之中的复杂度产生的排序方法都是可能的

•                             MergeSort

1.将序列一分为2   O（1） 2.子序列递归排序    2*T（n/2） 3.合并有序子序列    O（n） T( n )  = 2 T (n/2) + O(n) = O( nlogn ) 演算：   【在stack overflow上找到的归纳法】

•                             Two Way Mergesort

如图所示，分为两组，比较两组中小的数，取出

** 4. 数据结构 （严蔚敏） 5.DataStructure and Alogrithms in C++ (Adam Drozdek) 6.重点感谢学堂在线课程 数据结构（邓俊辉老师！） 写了一天了，该去歇歇了！技术帝养成之路哇！

2015年7月24日21:17:53