多维数组和广义表.ppt

2,第五章 多维数组和广义表 前面讨论的线性表、链表、栈和队列都是线性的数据结构，它们的逻辑特征是：每个数据元素至多有一个直接前驱和一个直接后继。本章要介绍的数组是指至少二维数组的多维数组，它是一种复杂的非线性结构，它的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。 5.1 多维数组 一、一维数组 一维数组可用向量（a1,a2,an）的形式来表示，因此，也把一维数组称为向量。向量中的每一个数据元素都具有统一的、相同的数据类型，数组元素的下标一般具有固定的上界和下界，同一个数组中的不同元素可通过下标来标识。向量的逻辑特征是：每个数据元素至多有一个直接前驱和一个直接后继。向量是存储在计算机的连续存储空间中，可通过数组的地址求出每个元素的地址，因此，可以随机的进行存取。多维数组是向量的推广。,二、多维数组 1、二维数组的表示 二维数组可表示成矩阵 的形式， 矩阵的每一行和每一列都可以看成是一个向量，因此，二维数组可以看成是由m个行向量组成的(列)向量，也可以看成是由n个列向量组成的(行)向量。 2、二维数组的逻辑结构 二维数组中的每个元素aij均属于两个向量：一个是第i行的行向量，另一个是第j列的列向量。因此，除边界元素外，每个元素aij都恰好有两个直接前驱aij-1和ai-1j，两个直接后继aij+1和ai+1j。而除开始结点和终端结点外的边界结点都只有一个直接前驱和一个直接后继。开始结点没有前驱只有一个直接后继，终端结点只有一个直接前驱没有后继。因此，二维数组的逻辑结构是：每个元素至多有两个直接前驱和两个直接后继。,3,4,3、多维数组的逻辑结构 1）三维数组：三维数组可以看成是以二维数组为元素的向量。三维数组的每个元素aijk至多有三个直接前驱和三个直接后继。 2）n维数组：n维数组可以看成是以n-1维数组为元素的向量。 n维数组的每个元素至多有n个直接前驱和n个直接后继。 因此，多维数组的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。 三、数组的顺序存储表示 由于计算机内存的结构是一维的，因此用内存来表示多维数组，必须将数组元素按某种次序排成线性序列后存人存储器。又由于数组一般不做插入和删除操作，即数组一旦建立，结构中元素个数和元素间关系不再发生变化。因此，一般采用顺序存储方法表示数组，通常有以下两种顺序存储方式。,1、 行优先顺序 将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。例如，二维数组Amn的按行优先存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 2、 列优先顺序 将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量后面。例如，二维数组Amn的按列优先存储的线性序列为： a11,a21,am1,a12,a22,am2,a1n,a2n,amn 注意：C语言中的数组是按行优先顺序存储的，数组元素下标的下界值为0。,5,四、数组元素的地址计算公式 按行优先方式顺序存储的数组，只要知道开始结点的存储地址、多维数组的维数和各维的上下界，以及数组元素在内存中占用的字节数，就可以求出每个元素的存储地址。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。 设二维数组Amn按行优先存储，各维的下界为0，上界分别为m-1,n-1，每个元素占内存的字节数为d，如果用LOC(a00)表示a00的地址，则aij的地址为： 同理，三维数组Amnp按行优先存储，则aijk的地址为：,6,7,7,5.2 矩阵的压缩存储 一、常用矩阵的压缩存储 1、对称矩阵 1）对称矩阵的定义：如果n阶矩阵A的元素满足 ，则称A为n阶对称矩阵。 2）对称矩阵的压缩存储：由于对称矩阵中的元素关于主对角线对称，所以只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享同一个存储空间，这样可以节约近一半的存储空间。 按“行优先顺序”存储下三角中的元素 将下三角中的元素aij(ij)按线性序列a00,a10,a11, an-10, an-11,an-1n-1的次序存放在一个含有n(n+1)/2个元素的向量sa中(因下三角元素总数为n(n+1)/2)。即将aij存放在sai(i+1)/2+j中(0in-1,0 ji)。,对称矩阵中的元素aij和sak之间的对应关系： 若ij，k=i(i+1)2+j 0k<n(n+1)2 若ij，k=j(j+1)2+i 0k<n(n+1)2 令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：k=I(I+1)2+J , 0k<n(n+1)/2。 3）对称矩阵的地址计算公式 LOC(aij)=LOC(sak)=LOC(sa0)+kd=LOC(sa0)+(I(I+1)/2+J)d。 2、三角矩阵 1）三角矩阵的定义：把主对角线以下(不包括主对角线)的元素均为常数c的n阶矩阵，称为上三角矩阵；把主对角线以上(不包括主对角线)的元素均为常数c的n阶矩阵，称为下三角矩阵；上三角矩阵和下三角矩阵统称为三角矩阵。三角矩阵中的常数c在多数情况下为0。,8,2）三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到含有n(n+1)/2+1个元素的向量sa中，其中c存放在向量的最后一个分量中。 上三角矩阵中aij和sak之间的对应关系 上三角矩阵中，主对角线之上的第i行(0i<n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时：aij前有i行(从第0行到第i-1行)，一共有：(n-0)+(n-1)+(n-2)+(n-i+1)=i(2n-i+1)/2个元素；在第i行上，aij前恰有j-i个元素，因此aij存放在 sai(2n-i+1)/2+j-i中(0in-1,ijn-1)。 下三角矩阵中aij和sak之间的对应关系 同理可以得到，按行优先顺序存放下三角矩阵中的元素aij时，aij存放在sai(i+1)/2+j中(0in-1, 0ji)。,9,9,9,9,10,10,10,3、对角矩阵1）对角矩阵的定义：所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。 2）k对角矩阵：一个满足条件若|i-j|(k-1)/2，则aij=0的矩阵A是k对角矩阵，其中k为奇数。特别，当k=3时，称为三对角矩阵。 3）三对角矩阵的压缩存储：三对角矩阵中非0元素正好有3n-2个，因此，三对角矩阵可压缩存储到含有3n-2个元素的向量sa中。 三对角矩阵中aij和sak之间的对应关系 元素aij前共有i行，其中非0元素共有3i-1个；第i行中前面已有i-1个0，所以aij前非0元素有j-(i-1)个，因此aij前已有的非零元素个数为：3i-1+j-(i-1)=2i+j。按行优先顺序元素aij存放在sa2i+j中。,11,二、稀疏矩阵的压缩存储 1、稀疏矩阵的定义：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<mn)，则称A为稀疏矩阵。 2、稀疏矩阵的压缩存储 在存储稀疏矩阵时，为了节省存储单元，只需存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。于是矩阵中每一个非零元素就由所在的行号、列号和值组成一个三元组(i，j，aij)惟一确定。稀疏矩阵的压缩存储会失去随机存取功能。 稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储（十字链表法）。,3、三元组表 若将表示稀疏矩阵的非零元素的三元组按行(或列)优先的顺序排列(跳过零元素)，则得到一个结点均为三元组的线性表，我们将该线性表的顺序存储结构称为三元组表。 对于三元组表，除了描述稀疏矩阵的非零元素外，为了运算方便，还应将矩阵的总行数、总列数和非零元素的总数也作为三元组表的属性进行描述。 4、三元组表的描述 #define MaxSize 100 /三元组表空间的最大容量typedef int DataType /结点类型typedef struct /三元组结点定义 int row,col; /非零元的行号、列号 DataType v; /非零元的值TriTupleNode;,12,typedef struct /三元组表定义 TriTupleNode dataMaxSize; /三元组表空间 int m,n,t; /矩阵总行数、总列数及非零元个数 TriTupleTable; 例如：稀疏矩阵的三元组表表示 5、用三元组表实现矩阵的转置运算 1）矩阵的转置：把一个mn矩阵A的行变成相应的列，所得到的nm矩阵B称为矩阵A的转置矩阵。 2）运算要求：由于稀疏矩阵A是按行优先的顺序存储的三元组表唯一确定的，所以，求稀疏矩阵A的转置矩阵B，就是求能唯一确定转置矩阵B的三元组表，且该三元组表必须是按行优先的顺序存储的。 3）实现方法： 方法一：简单地交换矩阵A的三元组表a-data中row和col中的内容，得到按列优先顺序存储的转置矩阵B的三元组表b-data；再将b-data重排成按行优先顺序的三元组表；,13,13,方法二：由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。我们将采用方法二来实现。 4）算法步骤： 第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。 第二步：当三元组表非空（A矩阵的非零元个数不为0）时，根据A矩阵三元组表的结点空间data，将A的三元组表a-data置换为B的三元组表b-data。 具体置换方法：为保证B的三元组表是按行优先存放的，对A中的每一列j(0ja-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于j的那些三元组，将它们的行号和列号互换后依次放人b-data中，即可得到B的按行优先的压缩存贮表示。 5）具体算法：,14,用三元组表实现矩阵的转置运算的算法：void TransMatrix(TriTupleTable *b,TriTupleTable *a) /*a,*b是矩阵A、B的三元组表表示,求A转置为B int p,q,j; b-m=a-n; b-n=a-m; /A和B的行列总数互换 b-t=a-t; /非零元总数 if(b-tn;j+) /对A的每一列 for(p=0;pt;p+) /扫描A的三元组表 if(a-datap.col=j) /找列号为j的三元组 b-dataq.row=a-datap.col; b-dataq.col=a-datap.row; b-dataq.v=a-datap.v; q+; ,作业：习题5.5 设两个mn稀疏矩阵A和B均以三元组表作为存储结构，试写出矩阵相加的算法，其结果存放在三元组表C中。 提示：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，需遍历A和B的两个三元组表的每个元素，分以下三种情况来考虑：1、当A和B的两个三元组对应的行标和列标都相等，如果对应的值相加不为0，加入C，否则不加入，再考虑它们的下一个三元组；2、当A与B的三元组行标相等，但A的三元组列标小于B的三元组列标，将A的三元组加入C，再考虑A的下一个三元组；3、当A与B的三元组的行标相等，但A的三元组列标大于B的三元组列标，将B的三元组加入C ，再考虑B的下一个三元组。最后再将A中或B中剩余三元组加入C。,15,7,7,5.3广义表的概念 一、广义表的概念 1、广义表是n个元素a1，a2，an的有限序列。其中ai是原子或是一个广义表。通常记做 LS=（a1，a2,.，an） LS是广义表的名字，n是它的长度。若ai是广义表，则称它为LS的子表。 2、通常用圆括号将广义表括起来，用逗号分割其中的元素。书写时用大写字母表示广义表，小写字母表示原子。若广义表LS非空（n=1），则a1为LS的表头，其余元素（a2，an）组成LS的表尾。 3、P67 广义表的例子 递归表，再入表，纯表和线性表 4、广义表的图形表示与转换,7,7,二、广义表的运算 1、取表头：head(LS) 2、取表尾：tail（LS） 根据表头表尾的定义可知，任何一个非空的广义表的表头是表中的第一个元素，它可以是原子，也可以是子表，而表尾是其余元素组成的子表。 例如： L=(a,b), A=(x,L(a,b) 则 head(L)=a, tail(L)=(b) Head(A)=x, tail(A)=(L(a,b) 值得注意的是广义表()和()不同。前者是一个空表，对它不能做求表头和表尾的运算，后者是表长为1的广义表，不过其中的元素是一个空表，对它可做求表头和表尾的运算，运算结果都是一个空表。,