《数组和广义表 》PPT课件.ppt

第五章第五章 数组和广义表数组和广义表 数组和广义表可看成是一种特殊的线数组和广义表可看成是一种特殊的线性表，其特殊在于性表，其特殊在于:表中的数据元素本表中的数据元素本身也是一种线性表身也是一种线性表 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单多维数组是向量的推广例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn Amn= 可以看成是可以看成是m m由个行向量组成的向量，也由个行向量组成的向量，也可以看成是可以看成是n n个列向量组成的向量个列向量组成的向量 数组一旦被定义，它的维数和维界就数组一旦被定义，它的维数和维界就不再改变因此，除了结构的初始化和不再改变因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元销毁之外，数组只有存取元素和修改元素值的操作素值的操作 5.2 数组的顺序表示和实现 由于计算机的内存储结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。

又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化因此，一般都是采用顺序存储的方法来表示数组 5.1 数组的类型定义数组的类型定义5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义 广义表的表示方法广义表的表示方法5.6 广义表操作的递归函数广义表操作的递归函数5.1 数组的类型定义数组的类型定义ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:二维数组的定义二维数组的定义:数据对象数据对象: : D = aij | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2基本操作基本操作：InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn) InitArray(&A, n, bound1, ., boundn) 操作结果：操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。

DestroyArray(&A) 操作结果：操作结果：销毁数组A Value(A, &e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值 操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值 操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK5.2 数组的顺序表示和实现数组的顺序表示和实现 类型特点类型特点:1) 只有引用型操作，没有加工型操作；2) 数组是多维的结构，而存储空间是 一个一维的结构 有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)例如：例如： 称为基地址基地址或基址以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。

数组元素数组元素的存储位置是其下标的线性函数的存储位置是其下标的线性函数其中 cn = L，ci-1 = bi ci , 1 i nLOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子通常认为通常认为 0.05 的矩阵为稀疏矩阵的矩阵为稀疏矩阵5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储何谓稀疏矩阵？ 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1) 零值元素占了很大空间零值元素占了很大空间;2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零1) 尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算；3) 操作方便 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元1) 特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵2) 随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。

1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1则称A为对称矩阵如图便是一个5阶对称矩阵 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(n+1)/2-1中为了便于访问对称矩阵A中的元素，我们必须在aij和sak 之间找一个对应关系 若ij，则ai j在下三角形中 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。

因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2 因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n+1)/2-1例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0 an-1,n-12、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。

在大多数情况下，三角矩阵常数为零 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pjk= 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . 图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1k=非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。

显然，当i-j1时，元素aij=0由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零 对这种矩阵，我们也可按行优序为主序来存储除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5由此，我们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。

上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取 5.3.2 稀疏矩阵随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型如何。