邓俊辉 c++数据结构第二章 向量_数据结构 邓俊辉

        数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为：线性结构、线性结构和非线性结构。

        线性结构根据逻辑次序和物理次序的关系，分为向量和列表。向量的逻辑次序和物理位置是对应的；列表的逻辑次序和物理位置无关，逻辑上相邻的向量物理位置不一定相邻。

        本章重点是向量的抽象类型接口规范和对应的算法，尤其是高效维护动态向量的技巧。

2.1 从数组到向量

2.1.1 数组

        数组：各元素具有一个线性次序，可将他们存放于物理位置连续的一段存储空间，并统称为数组。假设A表示n个元素的数组，那么A中的每个元素都有唯一的下标编号，在多数的计算机语言中，一般都是从0开始编号，依次是0、1、2、3、4、...、n-1。记作

A={A[0],A[1],A[2],...,A[n-1]}.

    A[i-1]称为A[i]的前驱，A[i+1]称为A[i]的后继。A[i]的物理地址是A + i * s,s表示每个元素占用的空间。

        按照面向对象的数据抽象原则，可以对以上的数据结构做一般性的推广，使得其以上特性具有更普遍性的。向量就是数组的一种推广。

2.1.2 向量

2.2 接口

2.2.1 ADT接口

     作为一种抽象数据类型，向量对象应该支持如下操作接口。

        以下对每个接口进行描述：        

size（）:返回向量的规模——元素个数。

get(r)：返回秩为r的元素.

put(r,e)：将向量的秩为r的元素置为e。

intert（r,e）：在位置r处插入元素e，原来元素依次后移。

disordered():返回向量的逆序数的和。（逆序数：左边元素大于右边元素称为一个逆序数）

sort():将原来向量按照升序排列。

2.2.3 Vector模版类

   按照2.2.1确定的向量ADT接口，可定义Vector模板类如代码2.1所示。