资源描述：
《2019第五章 数组与广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。对于多维数组，有两种存储方式：一是以行为主
2、序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组Amn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算aij的物理地址的函数为：LOC(aij)=LOC(a11)+((i-1
3、)*n+j-1)*L同理，对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1))*L注意：在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*L5.1数组的定义ADTArray{数据对象D:具有相同类型的数据元素构成的有序集合。数据关系R:对于n维数组，其每一个元素均位于n个向量中，每个元素最多具有n个前驱结点和n个后继结点。基本操作：InitArray(&A,n,index1,…,indexn)新建一个n维数组A，其每维的大小由index1
4、,index2,……,indexn确定。DestroyArray(&A)销毁数组A，收回其占用的空间。Value(A,&x,index1,…,indexn)取出A[index1][index2]……[indexn]数组元素的值存入变量x中。Assign(&A,e,index1,…,indexn)将表达式e的值赋给数组元素A[index1][index2]……[indexn]}ADTArray5.2数组的顺序表示多维数组用一维的存储单元存放需约定次序。PASCAL和C语言是以行序为主序，FORTRAN以列序为主序。给定维数和各维长度，数组的存储空间确定。二维数组中任一元素aij的存储地址:Lo
5、c(i,j)=Loc(0,0)+(b2*i+j)*Ln维数组：教材p93Loc（j1,j2,…,jn)=Loc(0,0,…,0)+∑ciji其中cn=L,ci-1=bi*ci,1#defineMAX_ARRAY_DIM8//数组维数最大值typedefstruct{ElemType*base;//数组元素基址intdim;//数组维数int*bounds;//数组维界基址int*constants;//数组映象函数常量基址}Array;5.3矩阵的压缩存储矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。压缩存储：为多个值相同的元只分配一个存
6、储空间，对零元不分配空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵5.3.1.特殊矩阵对称矩阵：aij=aji1≤i,j≤n压缩存储方法：为每一对对称元分配一个存储空间将下三角的元素，按行存储到一维数组sa中共有n(n+1)/2个存储单元，aij在一维数组中的位置k为：i(i-1)/2+j-1当i>=j否则j(j-1)/2+i-1三角矩阵：上（下）三角中的元均为常数c或0压缩存储方法：同上，只存储上（下）三角元素。下三角：k=i*(i-1)/2+j-1上三角：k=(2n-i)(i-1)/2+j-1(按行)k=j(j-1)/2+
7、i-1（按列）注意：k从零开始，i,j从1开始对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。压缩方法：压缩存储到一维数组sa[]中，三对角矩阵有3n-2个元素。k=2*i+j-35.3.2.稀疏矩阵1.三元组的表示稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。t个非零元，t/(m*n)称为稀疏因子<0.05用三元组(i,j,aij)存储行和列的位置，及非零元数值。（1）稀疏矩阵(SparseM
