当前位置:文档之家› 数据结构应用(数组应用——基础知识)

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


定义和访问一维数组
int a[10];
for(int i=0;i<10;i++) { a[i] = i; } int *pa= new int[10]; for(int i = 0;i<10;i+&# delete []pa;
定义和访问二维数组
int b[5][10];
STL
实际上,我们可以不用自己定义动态数组类, 因为STL已经帮我们做好了这样的工作。
STL(Standard Template Library)是C++标 准库的一部分,是用C++ Template机制来表 达泛型的库。

示例
用一个泛型算法可以处理多种数据结构。 而且在获得弹性的同时运行效率上和 以前相比没有损失。
序列式容器
Vectors

将元素置于一个动态数组中加以管理。
可以随机存取元素(用索引直接存取)。 数组尾部添加或移除元素非常快速。但是在 中部或头部安插元素比较费时。


序列式容器
Vectors 示例
用vector前,必须包含 头文件<vector>
序列式容器
Deques

deque,是“double-ended queue”的缩写。
Container(容器)
– 用来管理一组元素。
容器的分类

序列式容器(Sequence containers) 每个元素都有固定位置--取决于插入时机 和地点,和元素值无关。
vector、deque、list

关联式容器(Associated containers) 元素位置取决于特定的排序准则,和插入顺 序无关 set、multiset、map、multimap
for(int i=0;i<5;i++) { for(int j=0;j<10;j++) {
b[i][j] = i * j;
} }
int **pb;
pb = (int**)new int *[5];
for(int i=0;i<5;i++)
{
{
pb[i] = new int[10]; }
for(int i=0;i<5;i++) for(int j=0;j<10;j++) {
可以随机存取元素(用索引直接存取)。 数组头部和尾部添加或移除元素都非常快速 。但是在中部或头部安插元素比较费时。


序列式容器
Deques 示例
用deque前,必须包 含头文件<deque>
数组应用
基础知识
数组
C++中,数组是一种集合数据类型,它由许多 元素组成,每一个元素都有相同的数据类型, 在内存中占用相同大小的存储单元,且在内存 中连续存放。 每一个数组有一个名字,数组中的每一个元素 有一个序号(或称下标)表示元素在数组中的 位置,我们正是通过下标来识别数组中的每一 个元素。
class CDynamicArray
{
public: CDynamicArray();
~CDynamicArray();
public: void Insert(int val); int &operator[](int nIndex); void Remove(int nIndex); int GetSize(); private: int *pArray; int nSize; Resize();
int a[m * n];
访问 第i行j列的元素的方式如下:
a[i * n + j] 同理,如果是下表为k的元素代表的二维数组 中的行列计算如下: int nCol = k % n;
int nRow = k / n;
动态数组
数组在定义时需要指定长度,但是在应用时, 数组长度往往需要根据需要进行变化,此时需 要使用动态数组。 在C++里,我们可以定义一个类来描述动态数 组, 在该类里,可以预先分配一个固定大小 的数组空间。数据先存放在该空间里,如果该 空间不够用了, 则在重新分配两倍原大小的 空间,将数据拷贝过来, 并删除原来分配的 空间。类定义如下
pb[i][j] = i * j;
} }
for(int i=0;i<5;i++)
{ delete []pb[i]; } delete []pb;
一维数组和二维数组之间的关系
计算机内存是线性排列的(一维),所以二维 数组实际上都是由一维数组模拟。
两者之间可以如下转化 假设要描述一个m X n的二维数组,我们可以 先如下定义一个一维数组
STL的组成

六大组件 容器(Container) 算法(Algorithm) 迭代器(Iterator) 仿函数(Function object) 适配器(Adaptor) 空间配制器(allocator)
STL的六大组件 全都是抽象出 来的Concepts
容器的概念
数组中的元素可以是任何数据类型,因此,通过 定义恰当的数据类型(数据结构),我们可以使 用数组保存游戏中复杂的信息,比如游戏中的 地图相关信息。 下面先回顾一下与数组相关的知识:
如何定义一个一维数组,如何访问这个数组中 的元素 如何通过指针动态创建一维数组,然后用指针 访问该数组,最后释放该数组 如何定义一个二维数组,并访问 如何通过指针动态创建二维数组,并访问、释 放 一维数组和二维数组之间关系如何,如何转换
相关主题