[工学]5数组和广义表.ppt

第五章 数组和广义表 数组 一维数组具有线性表的结构，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素操作 二维数组每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱和两个后继。也可看作是以线性表为数据元素的线性表。 n维数组每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。 因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.1 数组的定义 ADT Array{ 数据对象：ji=0,…,bi-1,i=1,2,…,n, D={aj1j2…jn| n(0)称为数组的维数， bi是数组第i维的长度， ji是数组元素的第i维下标， aj1j2…jn∈ElemSet} 数据关系：R={R1,R2,…,Rn} Ri={aj1…ji…jn,aj1…ji+1…jn| 0≤jk≤bk-1, 1≤k≤n 且k≠i,0≤ji≤bi-2, aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…n} 基本操作： InitArray(A,n,bound1,…,boundn) DestroyArray(A) Value(A,e,index1,…,indexn) Assign(A,e,index1,…,indexn) }ADT Array 5.2 数组的顺序表示 多维数组用一维的存储单元存放需约定次序。PASCAL和C语言是以行序为主序，FORTRAN以列序为主序。 给定维数和各维长度，数组的存储空间确定。 二维数组中任一元素aij的存储地址: Loc(i,j)=Loc(0,0)+(b2*i+j)*L n维数组：教材p89 Loc（j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji 其中 cn=L, ci-1=bi*ci, 1i≤n 5.3 矩阵的压缩存储 矩阵一般可用二维数组实现 特殊矩阵采用压缩存储 压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律 稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵 5.3.1 特殊矩阵 对称矩阵： aij=aji 1≤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+2)(i-1)/2+j-1 (按行) k=j(j-1)/2+i-1 （按列） 注意：k从零开始，i,j从1开始 对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。 压缩方法：压缩存储到一维数组sa[ ]中，三对角矩阵有3n-2个元素。 k=2*i+j-3 5.3.2 稀疏矩阵 1. 三元组的表示 稀疏矩阵可由表示非零元的三元组及其行列数唯一确定 t个非零元，t/(m*n)称为稀疏因子 0.05 用三元组(i,j,aij)存储行和列的位置，及非零元数值 （1）稀疏矩阵 (Sparse Matrix) 用三元组表表示的稀疏矩阵及其转置 （2） 三元组顺序表 #define MAXSIZE 12500 //非零元个数最大值 typedef struct { int i, j; //行下标和列下标 ElemType e; } Triple; typedef struct{ Triple data[MAXSIZE+1]; //非零元三元组表 int mu,nu,tu; //行数、列数、非零元个数 }TSMatrix; TSMatrix a,b; 所需空间：3*tu+3 (3)三元组表稀疏矩阵的转置运算 方法：按照b.data中的三元组的次序，即M的列序，依次在a.data中找到相应的三元组进行转置。 步骤：从k=1开始依次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。 其时间复杂度为 O ( a.nu* a.tu )。 例：若矩阵有200行，200列，10,000个非零元素，总共有2,000,000次处理。 快速转置算法 方法：按a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。 建立辅助数组num和cpot， num[col]表示矩阵第col列中非零元的个数， cpot[col]指示第col