资源描述：
《零基础学数据结构-第7章-数组讲课教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、零基础学数据结构-第7章-数组7.1数组一个m行n列的二维数组可以看成是每个元素由列向量构成的线性表，例如，图7.1所示的二维数组可以表示成A=(p0,p1,…,pr)（其中，r=n-1），每个元素pj(0≤j≤r)又是一个列向量，即pj=(a0,j,a1,j,…,am-1,j)（其中0≤j≤n-1）。7.1数组图7.1所示的二维数组也可以表示成每个元素由行向量构成的线性表，例如，线性表A可以表示成Ｂ＝(q0,q1,…,qs)（其中，s=m-1），qi（0≤j≤m-1）是一个行向量，即qi=(ai,0,ai,1,…,ai,n-1)。如图7.2所示。7.1数组
2、7.1.2数组的抽象数据类型1．数据对象集合数组的数据对象集合为{aj1j2…jnn(>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。数组是一个特殊的线性表。7.1数组2．基本操作集合（1）InitArray(&A,n,bound1,…,boundn)：初始化操作。如果维
3、数和各维的长度合法，则构造数组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)：数组的定位操作。根据数组的元素下标，求出该元素在数组中的相对地址。7.
4、2数组的顺序表示与实现7.2.1数组的顺序存储结构数组的存储方式有两种：一种是以行序为主序（rowmajororder）的存储方式，另一种是以列序为主序（columnmajororder）的存储方式。数组A在计算机中的存储形式如图7.3所示。7.2数组的顺序表示与实现根据数组的维数和各维的长度就能为数组分配存储空间。因为数组中的元素是连续存放得，故任意给定一个数组的下标，就可以求出相应数组元素的存储位置。设每个元素占m个存储单元，则二维数组A中的任何一个元素aij的存储位置可以由以下公式确定。Loc(i,j)=Loc(0,0)+(i×n+j)×m其中，Loc
5、(i,j)表示元素aij的存储地址，Loc(0,0)表示元素a00的存储地址，即二维数组的起始地址（也称为基地址）。7.2数组的顺序表示与实现n维数组中数据元素的存储地址与数组的下标之间的关系：Loc(j1,j2,…,jn)=Loc(0,0,…,0)+(b1b2…bn-1j0+b2b3…bn-1j1+…+bn-1jn-2+jn-1)L其中，bi(1≤i≤n-1)是第i维的长度，ji是数组的第i维下标。数组的顺序存储结构类型定义如下：#defineMaxArraySize3#includetypedefstruct{DataTypebase
6、;/数组元素的基地址/intdim;/数组的维数/intbounds;/数组的每一维之间的界限的地址/intconstants;/数组存储映像常量基地址/}Array;7.2数组的顺序表示与实现数组的存储表示如图7.4所示。7.2数组的顺序表示与实现7.2.2数组的基本运算（1）初始化数组。intInitArray(ArrayA,intdim,...){intelemtotal=1,i;/elemtotal是数组元素总数，初值为1/va_listap;if(dim<1dim>MaxArraySize)/如果维数不合法，返回0/return0;A->dim=d
7、im;A->bounds=(int)malloc(dimsizeof(int));/分配一个dim大小的内存单元/if(!A->bounds)exit(-1);va_start(ap,dim);/dim是一个固定参数，即可变参数的前一个参数/7.2数组的顺序表示与实现for(i=0;ibounds[i]=va_arg(ap,int);/依次取得可变参数，即各维的长度/if(A->bounds[i]<0)return-1;//在math.h中定义为4elemtotal=A->bounds[i];/得到数组中元素总的个数/}va_end
8、(ap);A->base=(DataType)mal
