数组和广义表--信管.ppt

第五章 数 组和广义表,数组可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。,数组（Array）是由n(n1)个相同类型数据元素a0，al，ai，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解 。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。,有时也把一维数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。 数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。,数 组,1一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为An或A=( a0，al，ai，an-1) 一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*k (0in) 2二维数组 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。 例如，设A是一个有m行n列的二维数组，则A可以表示为：,数组,可以看成由m个行向量组成的向量，也可以看由n个列向量组成的向量。 数组中的每个元素由元素值aij及一组下标（i，j）来确定。aij既属于第i行的行向量，又属于第j列的列向量。 其中，ai=( ai,0 ai,1 ai,n-1) (0in) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，ai，am-1),Amn=（a00,a01,a0,n-1),(a10,a11,a1,n-1),(am-1,0 , am-1,1,am-1,n-1),(a),(b),显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。 数组的性质 数组中的数据元素数目固定。 数组中的数据元素必须具有相同的数据类型。 数组中的每个数据元素都有一组唯一的下标值。 数组是一种随机存储结构。可随机存取数组中的任意数据元素。,数 组,由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。 对于一维数组，数组的存储结构关系为: LOC(ai)=LOC(a0)+i * k (0in) 对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行/列次序问题。常用两种存储方法：以行序(row major order)为主序的存储方式和以列序(column major order)为主序的存储方式。,数组的存储结构,行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a11,a21,am1,a12,a22,am2,an1,an2,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。,顺序存储结构,二维数组的两种存储结构,对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定: LOC(ai,j)=LOC(a0,0)+(in+j)k 其中n为每行中的列数。,以“行序为主序”的存储映象,【例1】对于给定的二维数组float a34，计算： (1) 数组a中的数组元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。 【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*k =1000+(2*4+3)*4 =1044,顺序存储结构例,【例5-2】有m名学生，每人考n门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。 【解】把学生的考试成绩存放在m行n列的二维数组中，则第i(0i为10人 #define N 3 /假设为3 int scoreMN; /学生成绩二维数组,顺序存储结构例,求第j门课程总分数的算法为： int course_sum(int scoreMN,int j) int i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); ,求第i名学生总分数的算法为： int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); ,1对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 i, jn-1 ，则称A为对称矩阵。 例如，下图是一个3*3的对称矩阵。,特殊矩阵,2三角矩阵 上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式见图（a）。,（2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式见图（b）。,（a）上三角矩阵,（b）下三角矩阵,若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。例如，下图为77的三对角矩阵（即有三条对角线上元素非0）,3对角矩阵,特殊矩阵压缩,对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。 对称矩阵,对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：,特殊矩阵压缩对称矩阵,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,在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0n(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=4,三角矩阵中的重复元素0可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到sa0n(n+1)/2中，其中0存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pj 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij,特殊矩阵压缩三角矩阵,对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . 可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储,特殊矩阵压缩对角矩阵,非零元素仅出现在主对角(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-2。,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 由此，我们称sa03*n-2是阶三对角带状矩阵A的压缩存储表示。,特殊矩阵压缩对角矩阵,稀疏矩阵,上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取. 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。,在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,稀疏矩阵,稀疏矩阵例,例如 下列三元组表(1,2,12)(1,3,9),(3,1,3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0