数据结构应用(数组应用基础知识)

数组应用基础知识C++中，数组是一种集合数据类型，它由许多元素组成，每一个元素都有相同的数据类型，在内存中占用相同大小的存储单元，且在内存中连续存放。每一个数组有一个名字，数组中的每一个元素有一个序号（或称下标）表示元素在数组中的位置，我们正是通过下标来识别数组中的每一个元素。数组数组中的元素可以是任何数据类型,因此,通过定义恰当的数据类型(数据结构),我们可以使用数组保存游戏中复杂的信息，比如游戏中的地图相关信息。下面先回顾一下与数组相关的知识：如何定义一个一维数组，如何访问这个数组中的元素如何通过指针动态创建一维数组，然后用指针访问该数组，最后释放该数组如何定义一个二维数组，并访问如何通过指针动态创建二位数组，并访问、释放一维数组和二维数组之间关系如何，如何转换定义和访问一维数组inta[10];for(inti=0;i10;i++){a[i]=i;}int*pa=newint[10];for(inti=0;i10;i++){pa[i]=i*2;}delete[]pa;定义和访问二维数组intb[5][10];for(inti=0;i5;i++){for(intj=0;j10;j++){b[i][j]=i*j;}}int**pb;pb=(int**)newint*[5];for(inti=0;i5;i++){pb[i]=newint[10];}for(inti=0;i5;i++){for(intj=0;j10;j++){pb[i][j]=i*j;}}for(inti=0;i5;i++){delete[]pb[i];}delete[]pb;一维数组和二维数组之间的关系计算机内存是线性排列的（一维），所以二维数组实际上都是由一维数组模拟。两者之间可以如下转化假设要描述一个mXn的二维数组，我们可以先如下定义一个一维数组inta[m*n];访问第i行j列的元素的方式如下：a[i*n+j]同理，如果是下表为k的元素代表的二维数组中的行列计算如下：intnCol=k%n;intnRow=k/n;动态数组数组在定义时需要指定长度,但是在应用时，数组长度往往需要根据需要进行变化，此时需要使用动态数组。在C++里，我们可以定义一个类来描述动态数组，在该类里，可以预先分配一个固定大小的数组空间。数据先存放在该空间里，如果该空间不够用了，则在重新分配两倍原大小的空间，将数据拷贝过来，并删除原来分配的空间。类定义如下classCDynamicArray{public:CDynamicArray();~CDynamicArray();public:voidInsert(intval);int&operator[](intnIndex);voidRemove(intnIndex);intGetSize();private:int*pArray;intnSize;Resize();};STL实际上，我们可以不用自己定义动态数组类，因为STL已经帮我们做好了这样的工作。STL(StandardTemplateLibrary)是C＋＋标准库的一部分，是用C＋＋Template机制来表达泛型的库。示例用一个泛型算法可以处理多种数据结构。而且在获得弹性的同时运行效率上和以前相比没有损失。STL的组成六大组件容器（Container）算法（Algorithm）迭代器（Iterator）仿函数（Functionobject）适配器（Adaptor）空间配制器（allocator）STL的六大组件全都是抽象出来的Concepts容器的概念–用来管理一组元素。Container（容器）容器的分类–序列式容器（Sequencecontainers）每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。vector、deque、list–关联式容器（Associatedcontainers）元素位置取决于特定的排序准则，和插入顺序无关set、multiset、map、multimapVectors–将元素置于一个动态数组中加以管理。–可以随机存取元素（用索引直接存取）。–数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时。序列式容器Vectors示例用vector前，必须包含头文件vector序列式容器Deques–deque，是“double-endedqueue”的缩写。–可以随机存取元素（用索引直接存取）。–数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时。序列式容器Deques示例用deque前，必须包含头文件deque序列式容器