《组顺序表矩阵表示》PPT课件.ppt

《《组顺序表矩阵表示》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第5章数组与广义表第5章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.6m元多项式的表示5.7广义表的递归算法5.1数组的定义ADTArray{数据对象：D＝{aj1,j2,...,ji,...jn

2、ji=0,...,bi-1,i=1,2,..,n,称n(>0)为数组的维数，bi为数组第i维的长度，ji为数组元素的第i维下标，aj1,...,jn∈ElemSet}数据关系：R＝{R1,R2,...,Rn},Ri＝{

3、1,...,jN>

4、0≤jk≤bk-1,1≤k≤n且k<>i,0≤ji≤bi-2,aj1,...,ji,...,jn,aj1,...ji+1,...,jn∈D,i=2,...,n}5.1数组的定义基本操作：InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A。DestroyArray(&A)初始条件：数组A已经存在。操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界,则

5、e赋值为所指定的A的元素值,并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。}ADTArray5.2数组的顺序表示和实现由于数组类型不作插入和删除的操作，因此只需要通过"顺序映象"得到它的存储结构，即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。通常有两种映象方法：即“以行(序)为主(序)“row-major的映象方法和”以列(序)为主(序)“column-major的映象方法。将多维数组映射到一

6、维数组的方法representationsofamultidimensionalarray5.2数组的顺序表示和实现以二维数组a[m,n]为例，其在内存中的映像既可以如下排列（行优先）：a00,a01,…,a0,n-1,a10,a11,…,a1,n-1,…am-1,0,…am-1,n-1也可以如下排列（列优先）：a00,a10,…,am-1,0,a01,a11,…,am-1,1,…a0,n-1,…am-1,n-1111213141516212223242526313233343536414243444546111213141516212223242

7、5263132333435364142434445461121314112223242132333431424344415253545162636465.2数组的顺序表示和实现假设二维数组R[m][n]中每个数据元素占L个存储地址，并以LOC(i,j)表示下标为(i,j)的数据元素的存储地址，则该数组中任何一对下标(i,j)对应的数据元素在"以行为主"的顺序映象中的存储地址为：LOC(i,j)=LOC(0,0)+(i*n+j)*L在"以列为主"的顺序映象中的存储地址为：LOC(i,j)=LOC(0,0)+(j*m+i)*L其中LOC(0,0)是二维

8、数组中第一个数据元素（下标为(0,0)）的存储地址，称为数组的"基地址"或"基址"。5.2数组的顺序表示和实现类似地，假设三维数组R[p][m][n]中每个数据元素占L个存储地址，并以LOC(i,j,k)表示下标为(i,j,k)的数据元素的存储地址，则该数组中任何一对下标(i,j,k)对应的数据元素在"以行为主"的顺序映象中的存储地址为：LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L5.2数组的顺序表示和实现templateclassArray1D{friendostream&operator<<(os

9、tream&,constArray1D&);public:Array1D(intsize=0);Array1D(constArray1D&v);//copyconstructor~Array1D(){delete[]element;}T&operator[](inti)const;intSize(){returnsize;}Array1D&operator=(constArray1D&v);Array1Doperator+()const;//unary+Array1Doperator+(constArray1D<

10、T>&v)const;Array1Doperator-()const;//unaryminusArray1Do