文档介绍：零基础学数据结构数组
数组
重新认识数组
学过C语言的对数组就不会陌生，数组是一般高级语言都支持的数据类型，下面我们从数据结构的角度来认识下数组。数组（Array）是存储在n个连续内存单元相同类型数据元素的线性结构。从逻辑结构上看，数组可以看作是一般线性表的扩展。一维数组即为线性表，二维数组可以定义为“数据元素为一维数组（线性表）”的线性表。依次类推，即可得到多维数组的定义。
一个形式化的数组描述如下：
一个含有n个元素的一维数组可以表示成线性表A=(a0,a1,…,an-1)。其中，ai(0≤i≤n-1)是表A中的元素，元素个数是n。
第1页/共63页
数组
一个m行n列的二维数组可以看成是每个元素由列向量构成的线性表，例如，=(p0,p1,…,pr)（其中，r=n-1），每个元素pj(0≤j≤r)又是一个列向量，即pj=(a0,j,a1,j,…,am-1,j)（其中0≤j≤n-1）。
第2页/共63页
数组
，例如，线性表A可以表示成Ｂ＝(q0,q1,…,qs)（其中，s=m-1），qi（0≤j≤m-1）是一个行向量，即qi=(ai,0,ai,1,…,ai,n-1)。。
第3页/共63页
数组
数组的抽象数据类型
1．数据对象集合
数组的数据对象集合为{aj1j2…jn|n(>0)称为数组的维数，ji=0,1,…,bi-1，其中，0≤i≤n。bi是数组的第i维长度，ji是数组的第i维下标}。在一个二维数组中，如果把数组看成是由列向量组成的线性表，那么元素aij的前驱元素是ai-1,j，后继元素是ai+1,j；如果把数组看成是由行向量组成的线性表，那么元素aij的前驱元素是ai,j-1，后继元素是ai,j+1。
数组是一个特殊的线性表。
第4页/共63页
数组
2．基本操作集合
（1）InitArray(&A,n,bound1,…,boundn)：初始化操作。如果维数和各维的长度合法，则构造数组A，并返回1，表示成功。
（2）DestroyArray(&A)：销毁数组操作。
（3）GetValue(A,&e,index1,…,indexn)：返回数组的元素操作。如果下标合法，将数组A中对应的元素赋值给e，并返回1，表示成功。
（4）AssignValue(&A,e,index1,…,indexn)：设置数组的元素值操作。如果下标合法，将数组A中由下标index1,…,indexn指定的元素值置为e。
（5）LocateArray(A,ap,&offset)：数组的定位操作。根据数组的元素下标，求出该元素在数组中的相对地址。
第5页/共63页
数组的顺序表示与实现
数组的顺序存储结构
数组的存储方式有两种：一种是以行序为主序（row major order）的存储方式，另一种是以列序为主序（column major order）的存储方式。。
第6页/共63页
数组的顺序表示与实现
根据数组的维数和各维的长度就能为数组分配存储空间。因为数组中的元素是连续存放得，故任意给定一个数组的下标，就可以求出相应数组元素的存储位置。
设每个元素占m个存储单元，则二维数组A中的任何一个元素aij的存储位置可以由以下公式确定。
Loc(i,j)=Loc(0,0)+(i×n+j)×m
其中，Loc(i,j)表示元素aij的存储地址，Loc(0,0)表示元素a00的存储地址，即二维数组的起始地址（也称为基地址）。
第7页/共63页
数组的顺序表示与实现
n维数组中数据元素的存储地址与数组的下标之间的关系：
Loc(j1,j2,…,jn)=Loc(0,0,…,0)+(b1*b2*…*bn-1*j0+b2*b3*…*bn-1*j1+…+bn-1*jn-2+jn-1)*L
其中，bi(1≤i≤n-1)是第i维的长度，ji是数组的第i维下标。
数组的顺序存储结构类型定义如下：
#define MaxArraySize 3
#include<>
typedef struct
{