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

第五章 数组和广义表,教学内容： 5.1 多维数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵 5.4 广义表 教学目的： 理解多维数组的结构特点和在内存中的两种顺序存储方式； 理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算； 领会稀疏矩阵的压缩方式和简单运算； 了解广义表的定义和基本运算。,第五章 数组和广义表,教学重点： 多维数组的逻辑结构； 多维数组的两种顺序存储方式，计算给定元素在存储区中的地址； 对称矩阵、三角矩阵的压缩存储方式； 稀疏矩阵的三元组表表示方法。 教学难点： 稀疏矩阵的压缩存储表示下的运算的实现,5.1 多维数组,数组的逻辑结构 数组的内存映象,5.1.1 数组的逻辑结构,数组是我们熟悉的一种数据结构，可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。,数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。,类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。,在数组中通常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。,5.1.2 数组的内存映象,通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。 对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。,有两种顺序映象的方式: 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。,例如一个23二维数组，逻辑结构可以用左图表示。以行为主序的内存映象如右图（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ;以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ;它的内存映象如右图（b）所示。,设有mn二维数组Amn，按元素的下标求其地址： 以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，那么aij 的物理地址可用一个线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L 称为基地址或基址。 在C语言中，数组中每一维的下界定义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * L 推广到一般的二维数组：Ac1d1 c2d2，则aij的物理地址计算函数为： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*L,同理对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*L 推广到一般的三维数组：Ac1d1 c2d2 c3d3，则aijk的物理地址为： LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*L,数组元素的存储位置是其下标的线性函数。,三维数组的逻辑结构和以行为主序的分配示意图如图所示。,例5.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。,void saddle (int A ,int m, int n) /*m,n是矩阵A的行和列*/ int i,j,min; for (i=0;i=m) printf (%d,%d,%dn, i ,k,min); 算法的时间性能为O(m*(n+m*n)。,5.2 特殊矩阵的压缩存储,对称矩阵 三角矩阵 带状矩阵,矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由mn个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵：,它是一个mn的矩阵。,所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。,5.2.1 对称矩阵,对称矩阵的特点是：在一个n阶方阵中，有aij=aji ，其中1i , jn，如图所示是一个阶对称矩阵。,对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij，其特点是ji且1in，对于上三角中的元素aij ，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。,如何只存储下三角部分？对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SAn(n+1)/2中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。,n,对于下三角中的元素aij，其特点是：ij且1in，存储到SA中后，根据存储原则，它前面有i-1行，共有1+2+i-1=i*(i-1)/2个元素，而aij又是它所在的行中的第j个，所以在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 若ij，则aij是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系： k=j*(j-1)/2+i-1 (kn*(n+1)/2 ) 综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到： k=I*(I-1)/2+J-1。,5.2.2 三角矩阵,形如下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。,下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：,1. 下三角矩阵,与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)/2+1个元素，设存入向量：SAn*(n+1)/2+1中，这种的存储方式可节约n*(n-1)/2-1个存储单元，sak与aji 的对应关系为：,),k是下三角矩阵位于（i，j）位置的元素在一维数组中的存放位置。,2. 上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个元素，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储： 个元素，aij 是它所在的行中要存储的第（j-i+1）个，也就是上三角存储顺序中的第 (i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。 综上， sak 与aji 的对应关系为：,对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个3阶对角矩阵：,5.2.3 带状矩阵(对角矩阵),n阶矩阵A称为带状矩阵，如果存在最小正数m ，满足当i-jm 时，aij =0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由下图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。,一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。 那么aij 映射为b ij，映射关系为：,另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。 如当w=3时，映象函数为： k=2*i+j-3,5.3 稀疏矩阵,稀疏矩阵的三元组表存储 稀疏矩阵的十字链表存储,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,何谓稀疏矩阵？,以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算， 如是除法，还需判别除数是否为零。,1) 尽可能少存或不存零值元素；,解决问题的原则:,2) 尽可能减少没有实际意义的运算；,3) 操作方便。 即： 能尽可能快地找到与下标值(i，j)对应的元素； 能尽可能快地找到同一行或同一列的非零值元素。,2) 特殊矩阵 非零元素在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵,1) 随机稀疏矩阵 非零元素在矩阵中随机出现,有两类稀疏矩阵：,5.3.1 稀疏矩阵的三元组表存储,将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。如图(a)稀疏矩阵对应的三元组表为图(b)。,#define SMAX 1024 /*一个足够大的数*/ typedef struct int i,j; /*非零元素的行、列*/ datatype v; /*非零元素值*/ SPNode; /*三元组类型*/ typedef struct int mu,nu,tu; /*矩阵的行、列及非零元素的个数*/ SPNode dataSMAX; /*三元组表*/ SPMatrix; /*三元组表的存储类型*/ 这样的存储方法确实节约了存储空间，但矩阵的运算从算法上可能变的复杂些。,1.稀疏矩阵的转置 设SPMatrix A; 表示一m*n的稀疏矩阵，其转置B则是一个n*m的稀疏矩阵，因此有 SPMatrix B; 。由A求B需： A的行、列转化成B的列、行； 将A.data中每一三元组的行列交换后转到B.data中； 以上两点完成之后，并没有完成B。因为我们前面规定三元组是按一行一行且每行中的元素是按列号从小到大的规律顺序存放的，因此B也必须按此规律实现，A的转置B如图(a)所示，图(b)是它对应的三元组存储，就是说，在A的三元组存储基础上得到B的三元组表存储（为了运算方便，矩阵的行列都从1算起，三元组表data也从1号单元用起）。,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,算法思路： A的行、列转化成B的列、行； 在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。,void TransM1 (SPMatrix *A) /*求A到B的转置*/ SPMatrix *B; int p,q,col; B=malloc(sizeof(SPMatrix); /*申请存储空间*/ B-mu=A-nu; B-nu=A-mu; B-tu=A-tu; /*稀疏矩阵的行、列、元素个数*/ if (B-tu0) /*有非零元素则转换*/ q=0; for (col=1; colnu); col+) /*按A的列序转换*/ for (p=1; ptu); p+) /*扫描整个三元组表*/ if (A-datap.j=col ) B-dataq.i= A-datap.j ; B-dataq.j= A-datap.i ; B-dataq.v= A-datap.v; q+; return B; /*返回的是转置矩阵的指针*/ ,分析该算法，其时间主要耗费在col和p的二重循环上，所以时间复杂性为O(n*t)，(设m、n是原矩阵的行、列，t是稀疏矩阵的非零元素个数)，显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)，和通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。,上述算法效率低的原因是算法要从A的三元组表中寻找第一列、第二列、，要反复搜索A表，若能直接确定A中每一三元组在B中的位置，则对A的三元组表扫描一次即可。这是可以做到的，因为A中第一列的第一个非零元素一定存储在B.data1，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。,根据这个想法，需引入两个向量来实现 ：numn+1和cpotn+1，numcol表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起），cpotcol初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为： cpot1=1； cpotcol=cpotcol-1+numcol-1； 2coln,依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。,例如对于矩阵A的num 和cpot的值如下：,SPMatrix * TransM2 (SPMatrix *A) SPMatrix *B; int i,j,k; int numn+1,cpotn+1; B=malloc(sizeof(SPMatrix); /*申请存储空间*/ B-mu=A-nu; B-nu=A-mu; B-tu=A-tu; if (B-tu0) /*有非零元素则转换*/ for (i=1;inu;i+) numi=0; for (i=1;itu;i+) /*求矩阵A中每一列非零元素的个数*/ j= A-datai.j; numj+; cpot1=1; /*求矩阵A中每一列第一个非零元素在B.data中的位置*/ for (i=2;inu;i+) cpoti= cpoti-1+numi-1; for (i=1; itu); i+) /*扫描三元组表*/ j=A-datai.j; /*当前三元组的列号*/ k=cpotj; /*当前三元组在B.data中的位置*/ B-datak.i= A-datai.j ; B-datak.j= A-datai.i ; B-datak.v= A-datai.v; cpotj+; return B; /*返回的是转置矩阵的指针*/ ,分析这个算法的时间复杂度：这个算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一常量，因此总的计算量是O(n+t)。当然它所需要的存储空间比前一个算法多了两个向量（numn+1和cpotn+1）。,2稀疏矩阵的乘积 已知稀疏矩阵A(m1 n1)和B(m2 n2)，n1= m2，求乘积C(m1 n2)。稀疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图所示。,由矩阵乘法规则知： C（i，j）=A(i,1)B(1,j)+A(i,2)B(2,j)+A(i,n)B(n,j) 矩阵用二维数组表示时，传统的矩阵乘法是：A的第一行与B的第一列对应相乘累加后得到c11，A的第一行再与B的第二列对应相乘累加后得到c12，因为现在按三元组表存储，三元组表是按行为主序存储的，在B.data中，同一行的非零元素其三元组是相邻存放的，同一列的非零元素其三元组并未相邻存放，因此在B.data中反复搜索某一列的元素是很费时的，因此改变一下求值的顺序。,以求c11和c12为例，因为 ： 即a11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，而同一行的非零元是相邻存放的，所以求c11和c12同时进行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，当然只有aik和bkj(列号与行号相等)且均不为零（三元组存在）时才相乘，并且累加到cij当中去。,为了运算方便，设一个累加器：datatype tempn+1；用来存放当前行中cij的值，当前行中所有元素全部算出之后，再存放到C.data中去。 为了便于B.data中寻找B中的第k行第一个非零元素，与前面类似，在此需引入num和rpot两个向量。numk表示矩阵B中第k行的非零元素的个数；rpotk表示第k行的第一个非零元素在B.data中的位置。于是有 rpot1=1 rpotk=rpotk-1+numk-1 2kn,例如 ，对于矩阵B的num和rpot如图所示。,根据以上分析，稀疏矩阵的乘法运算的粗略步骤如下： 初始化。清理一些单元，准备按行顺序存放乘积矩阵; 求B的num，rpot; 做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。,SPMatrix *MulSMatrix (SPMatrix *A, SPMatrix *B) /*稀疏矩阵A(m1 n1)和B(m2 n2) 用三元组表存储，求AB */ SPMatrix *C; /* 乘积矩阵的指针 */ int p,q,i,j,k,r; datatype tempn+1; int numB-nu+1,rpotB-nu+1; if (A-nu!=B-mu) return NULL; /*A的列与B的行不相等*/ C=malloc(sizeof(SPMatrix); /*申请C矩阵的存储空间*/ C-mu=A-mu; C-nu=B-nu; if (A-tu*B-tu=0) C-tu=0; return C; for (i=1;imu;i+) numi=0; for (k=1;ktu;k+) i= B-datak.i; numi+; /*求矩阵B中每一行非零元素的个数*/ rpot1=1; /*求矩阵B中每一行第一个非零元素在B.data中的位置*/ for (i=2;imu;i+) rpoti= rpoti-1+numi-1;,r=0; /*当前C中非零元素的个数*/ p=1; /*指示A.data中当前非零元素的位置*/ for ( i= 1;imu; i+) for (j=1;jnu;j+) tempj=0; /*cij的累加器初始化*/ while (A-datap.i=i ) ./*求第i行的*/ k=A-datap.j; /*A中当前非零元的列号*/ if (kmu) t=rpotk+1; else t=B-tu+1; /*确定B中第k行的非零元素在B.data中的下限位置*/ for (q=rpotk; qdataq.j; tempj+=A-datap.v * B-dataq.v /* B中第k行的每一个非零元素*/ p+; for (j=1;jnu;j+) if (tempj ) r+; C-datar=i,j,tempj ; C-tu=r; return C; ,分析上述算法的时间性能如下： （1）求num的时间复杂度为O(B-nu+B-tu)； （2）求rpot 时间复杂度为O(B-mu)； （3）求temp时间复杂度为O(A-mu*B-nu)； （4）求C的所有非零元素的时间复杂度为O(A-tu*B-tu/B-mu)； （5）压缩存储时间复杂度为O(A-mu*B-nu)； 所以总的时间复杂度为O(A-mu*B-nu+(A-tu*B-tu)/B-nu)。,5.3.2 稀疏矩阵的十字链表存储,三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零项数目及非零元素的位置会发生变化，这时这种表示就十分不便。 在这节中，我们介绍稀疏矩阵的一种链式存储结构十字链表，它同样具备链式存储的特点，因此，在某些情况下，采用十字链表表示稀疏矩阵是很方便的。,下图是一个稀疏矩阵的十字链表。,用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：row域存储非零元素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是两个指针域。,结点的结构定义如下: typedef struct node int row, col; struct node *down , *right; union v_next datatype v; struct node *next; MNode，*MLink;,5.4 广义表,顾名思义，广义表是线性表的推广。也有人称其为列表（Lists，用复数形式以示与统称的表List的区别）。 广义表的定义和基本运算 广义表的存储 广义表基本操作的实现,5.4.1 广义表的定义和基本运算,广义表的定义和性质 线性表是由n个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式： （俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本） 在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。,广义表（Generalized Lists）是n（n0）个数据元素a1，a2，ai，an的有序序列，一般记作： ls（a1，a2，ai，an） 其中：ls是广义表的名称，n是它的长度。每个ai（1in）是ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls的单元素和子表。当广义表ls非空时，称第一个元素a1为ls的表头（head），称其余元素组成的表（a2，ai，an）为ls的表尾（tail）。 显然，广义表的定义是递归的。,为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。 下面是一些广义表的例子： A （） B （e） C （a，（b，c，d） D （A，B，C） E （a，E） F （）, 广义表的性质 从上述广义表的定义和例子可以得到广义表的下列重要性质： 广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。 广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。 广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。,广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。 广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。 当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。 另外，树和有向图也可以用广义表来表示。 由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。, 广义表基本运算 广义表有两个重要的基本操作，即取头操作(Head)和取尾操作（Tail）。 根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如： Head（B） e Tail（B）（） Head（C） a Tail（C）（b，c，d） Head（D） A Tail（D）（B，C） Head（E） a Tail（E）（E） Head（F）（） Tail（F）（） 此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。,CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。 IsEmpty(ls)：若广义表ls空，则返回True；否则返回False。 Length(ls)：求广义表ls的长度。 Depth(ls)：求广义表ls的深度。 Locate(ls，x)：在广义表ls中查找数据元素x。 Merge(ls1，ls2)：以ls1为头、ls2为尾建立广义表。 CopyGList(ls1，ls2)：复制广义表，即按ls1建立广义表ls2。 Head(ls)：返回广义表ls的头部。 Tail(ls)：返回广义表的尾部。 ,5.4.2 广义表的存储,由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。 按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。, 头尾表示法 若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。 由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。,其形式定义说明如下： typedef enum ATOM, LIST Elemtag; /*ATOM=0：单元素；LIST=1：子表*/ typedef struct GLNode Elemtag tag; /*标志域，用于区分元素结点和表结点*/ union /*元素结点和表结点的联合部分*/ datatype data; /*data是元素结点的值域*/ struct struct GLNode *hp, *tp ptr; /*ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾*/ ; *GList; /*广义表类型*/,头尾表示法的结点形式如图所示。,对于5.5.1所列举的广义表A、B、C、D、E、F，若采用头尾表示法的存储方式，其存储结构如图所示。,A （） B （e） C （a，（b，c，d） D （A，B，C） E （a，E） F （）,从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中单元素或子表所在的层次。例如，在广义表D中，单元素a和e在同一层次上，而单元素b、c、d在同一层次上且比a和e低一层，子表B和C在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D的最高层有三个表结点，其广义表的长度为3。, 孩子兄弟表示法 广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。,其形式定义说明如下： typedef enum ATOM, LIST Elemtag; /*ATOM=0：单元素；LIST=1：子表*/ typedef struct GLENode Elemtag tag; /*标志域，用于区分元素结点和表结点*/ union /*元素结点和表结点的联合部分*/ datatype data; /*元素结点的值域*/ struct GLENode *hp; /*表结点的表头指针*/ ; struct GLENode *tp; /*指向下一个结点*/ *EGList; /*广义表类型*/,孩子兄弟表示法的结点形式如图所示。,对于5.5.1节中所列举的广义表A、B、C、D、E、F，若采用孩子兄弟表示法的存储方式，其存储结构如图所示。,A （） B （e） C （a，（b，c，d） D （A，B，C） E （a，E） F （）,从图的存储结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1的结点，且最高层结点的tp域必为NULL。,5.5.3 广义表基本操作的实现,我们以头尾表示法存储广义表，讨论广义表的有关操作的实现。由于广义表的定义是递归的，因此相应的算法一般也都是递归的。, 广义表的取头、取尾 GList Head(GList ls) if ls-tag = = 1 then p = ls-hp; return p; GList Tail(GList ls) if ls-tag = = 1 then p = ls-tp; return p; , 建立广义表的存储结构 int Create(GList *ls, char * S) Glist p; char *sub; if StrEmpty(S) *ls = NULL; else if (!(*ls = (GList)malloc(sizeof(GLNode) return 0; if (StrLength(S) = = 1) (*ls)-tag = 0; (*ls)-data = S; else (*ls)-tag = 1; p = *ls; hsub =SubStr(S,2,StrLength(S)-2); do sever(sub,hsub); Create( ,int sever(char *str, char *hstr) int n = StrLength(str); i= 1; k = 0; for (i = 1, k = 0; i = n | k != 0; +i) ch=SubStr(str,i,1); if (ch = = ( ) k+; else if (ch = = ) k-; if (i = n) hstr =SubStr(str,1,i-2); str= SubStr(str,i,n-i+1); else StrCopy(hstr,str); ClearStr(str); , 以表头、表尾建立广义表 int Merge(GList ls1,GList ls2, Glist *ls) if (!(*ls = (GList)malloc(sizeof(GLNode) return 0; *ls-tag = 1; *ls-hp = ls1; *ls-tp = ls2; return 1; , 求广义表的深度 int Depth(GList ls) if (!ls) return 1; /*空表深度为1*/ if (ls-tag = = 0) return 0; /*单元素深度为0*/ for (max = 0,p = ls; p; p = p-ptr.tp) dep = Depth(p-ptr.hp); /*求以p-ptr.hp尾头指针的子表深度*/ if (dep max) max = dep; return max+1; /*非空表的深度是各元素的深度的最大值加1*/ , 复制广义表 int CopyGList(GList ls1, GList *ls2) if (!ls1) *ls2 = NULL; /*复制空表*/ else if (!(*ls2 = (Glist)malloc(sizeof(Glnode) return 0;/*建表结点*/ (*ls2)-tag = ls1-tag; if (ls1-tag = = 0) (*ls2)-data = ls1-data; /*复制单元素*/ else CopyGList( ,1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。 3. 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,4. 掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。 5. 学习利用分治法的算法设计思想编制递归算法的方法。,