数据结构 第5章.ppt

第第5章章 数组和广义表数组和广义表 5.1 数组的定义和运算数组的定义和运算5.2 数组的顺序存储和实现数组的顺序存储和实现5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.4 广义表广义表 教学目的与要求：教学目的与要求：掌握三角矩阵的概念及其在计算机中的存储方法；掌握三角矩阵的概念及其在计算机中的存储方法；掌握稀疏矩阵的概念及其在计算机中的存储方法；掌握稀疏矩阵的概念及其在计算机中的存储方法；掌握稀疏矩阵的运算，如转置等；掌握稀疏矩阵的运算，如转置等；了解本章内容在数据结构中的作用，及其在数值分析了解本章内容在数据结构中的作用，及其在数值分析中的应用。中的应用。教学重点与教学难点：教学重点与教学难点：三角矩阵的压缩存储；三角矩阵的压缩存储；稀疏矩阵的压缩存储及其转置运算。稀疏矩阵的压缩存储及其转置运算。5.1 数组的定义和运算数组的定义和运算 图图5.1 Amn的二维数组的二维数组 图图5.2 矩阵矩阵Amn看成看成n个列向量的线性表个列向量的线性表 图图5.3 矩阵矩阵Amn看成看成m个行向量的线性表个行向量的线性表 以以上上我我们们以以二二维维数数组组为为例例介介绍绍了了数数组组的的结结构构特特性性，实实际际上上数数组组是是一一组组有有固固定定个个数数的的元元素素的的集集合合。也也就就是是说说，一一旦旦定定义义了了数数组组的的维维数数和和每每一一维维的的上上下下限限，数数组组中中元元素素的的个个数数就就固固定定了了。例例如如二二维维数数组组A34，它它有有3行行、4列列，即即由由12个个元元素素组组成成。由由于于这这个个性性质质，使使得得对对数数组组的的操操作作不不像像对对线线性性表表的的操操作作那那样样可可以以在在表表中中任任意意一一个个合合法法的的位位置置插插入入或或删删除除一一个个元元素素。对于数组的操作一般只有两类：对于数组的操作一般只有两类：(1）获得特定位置的元素值；获得特定位置的元素值；(2）修改特定位置的元素值。修改特定位置的元素值。基本操作：基本操作：（1）InitArray(A,n,bound1,boundn)：若若维维数数n和和各各维的长度合法，则构造相应的数组维的长度合法，则构造相应的数组A，并返回并返回TRUE。（2）DestroyArray（A）：）：销毁数组销毁数组A。（3）GetValue（A，e,index1,indexn）：若若下下标标合合法法，则则用用e返返回回数数组组A中中由由index1,indexn所所指指定定的的元元素素的的值值。（4）SetValue（A，e，index1,indexn）：若若下下标标合合法法，则则将将数数组组A中中由由index1,indexn所所指指定定的的元元素素的的值值置置为为e。这里定义的数组，与这里定义的数组，与C语言的数组略有不同，下标是从语言的数组略有不同，下标是从1开始的。开始的。5.2 数组的顺序存储和实现数组的顺序存储和实现 数数组组的的顺顺序序存存储储结结构构有有两两种种：一一种种是是按按行行序序存存储储，如如高高级级语语言言BASIC、COBOL和和PASCAL语语言言都都是是以以行行序序为为主主；另另一一种种是是按按列列序序存存储储，如如高高级级语语言言中中的的FORTRAN语语言言就就是是以以列列序序为主显然，二维数组为主显然，二维数组Amn以行为主的存储序列为：以行为主的存储序列为：a11,a12,，a1n,a21,a22,a2n,am1,am2,amn而而以列为主的存储序列为：以列为主的存储序列为：a11,a21,，am1，a12,a22,am2,a1n,a2n,amn 假设有一个假设有一个342的三维数组的三维数组A，共有共有24个元素，其逻个元素，其逻辑结构如图辑结构如图5.4所示。所示。图图5.4 三维数组的逻辑结构图三维数组的逻辑结构图 三三维维数数组组元元素素的的标标号号由由三三个个数数字字表表示示，即即行行、列列、纵纵三三个个方方 向向。a142表表 示示 第第 1行行，第第 4列列，第第 2纵纵 的的 元元 素素。如如 果果 对对A342（下下标标从从1开开始始）采采用用以以行行为为主主序序的的方方法法存存放放，即即行行下标变化最慢，纵下标变化最快，则顺序为：下标变化最慢，纵下标变化最快，则顺序为：a111，a112，a121，a122，a331，a332，a341，a342 采采用用以以纵纵为为主主序序的的方方法法存存放放，即即纵纵下下标标变变化化最最慢慢，行行下下标变化最快，标变化最快，则顺序为：则顺序为：a111，a211，a311，a121，a221，a321，a132，a232，a332，a142，a242，a342 以以上上的的存存放放规规则则可可推推广广到到多多维维数数组组的的情情况况。总总之之，知知道道了了多多维维数数组组的的维维数数，以以及及每每维维的的上上下下界界，就就可可以以方方便便地地将将多多维维数数组组按按顺顺序序存存储储结结构构存存放放在在计计算算机机中中了了。同同时时，根根据据数数组组的的下下标标，可可以以计计算算出出其其在在存存储储器器中中的的位位置置。因因此此，数数组组的的顺顺序序存存储储是是一一种随机存取的结构。种随机存取的结构。以以二二维维数数组组Amn为为例例，假假设设每每个个元元素素只只占占一一个个存存储储单单元元，“以以行行为为主主”存存放放数数组组，下下标标从从1开开始始，首首元元素素a11的的地地址址为为Loc1,1，求求任任意意元元素素aij的的地地址址。aij是是排排在在第第i行行，第第j列列，并并且且前前面面的的第第i-1行行有有n（i-1）个个元元素素，第第行行第第j个个元元素素前前面面还有还有-个元素。由此得到如下地址计算公式：个元素。由此得到如下地址计算公式：Loci,j=Loc1,1+n(i-1)+(j-1)根根据据计计算算公公式式，可可以以方方便便地地求求得得aij的的地地址址是是Loci,j。如如果果每每个元素占个元素占size个存储单元，则任意元素个存储单元，则任意元素aij的地址计算公式为：的地址计算公式为：Loci,j=Loc1,1+(n(i-1)+j-1)size 三维数组三维数组A（1.r,1.m,1.n）可以看成是可以看成是r个个mn的二维数组，的二维数组，如图如图5.5所示。所示。图图5.5 三维数组看成三维数组看成r个个mn的二维数组的二维数组 假假定定每每个个元元素素占占一一个个存存储储单单元元，采采用用以以行行为为主主序序的的方方法法存存放放，即即行行下下标标r变变化化最最慢慢，纵纵下下标标n变变化化最最快快。首首元元素素a111的的地地址为址为Loc1,1,1，求任意元素求任意元素aijk的地址。的地址。显显然然，ai11的的地地址址为为Loci,1,1=Loc1,1,1+(i-1)mn，因因为为在在该该元元素素之之前前，有有-个个的的二二维维数数组组。由由ai11的的地地址址和和二二维维数数组组的的地地址址计计算算公公式式，不不难难得得到到三三维维数数组组任任意元素意元素aijk的地址：的地址：Loci,j,k=Loc1,1,1+(i-1)mn+(j-1)n+(k-1)其中其中1i，1j，1k。如如果果将将三三维维数数组组推推广广到到一一般般情情况况，即即：用用j1、j2、j3代代替替数数组组下下标标i、j、k，并并且且j1、j2、j3的的下下限限为为c1、c2、c3，上上限限分分别别为为d1、d2、d3，每每个个元元素素占占一一个个存存储储单单元元，则则三三维维数数组组中中任任意意元素元素a(j1，j2，j3)的地址为：的地址为：Locj1,j2,j3=Locc1,c2,c3+l(d2-c2+1)(d3-c3+1)(j1-c1)+l(d3-c3+1)(j2-c2)+l(j3-c3)其中其中l为每个元素所占存储单元数。为每个元素所占存储单元数。令令1=l(d2-c2+1)(d3-c3+1),2=l(d3-c3+1),3=1，则：则：Loc j1,j2,j3=Loc c1,c2,c3+1(j1-c1)+2(j2-c2)+3(j3-c3)=Locc1,c2,c3+i(ji-ci)（1i3）由公式可知由公式可知Locj1,j2,j3与与j1,j2,j3呈线性关系。呈线性关系。对对于于维维数数组组A(c1 d1,c2 d2，,cn dn)，我我们们只只要要把把上上式式推推广广，就就可可以以容容易易地地得得到到维维数数组组中中任任意意元元素素aj1j2jn的的存存储地址的计算公式储地址的计算公式:其中(1in)。5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.3.1 三角矩阵三角矩阵 三三角角矩矩阵阵大大体体分分为为三三类类：下下三三角角矩矩阵阵、上上三三角角矩矩阵阵和和对对称称矩矩阵阵。对对于于一一个个n阶阶矩矩阵阵A来来说说，若若当当ij时时，有有aij=0，则则称称此此矩矩阵阵为为上上三三角角矩矩阵阵；若若矩矩阵阵中中的的所所有有元元素素均均满满足足aij=aji，则称则称此矩阵为对称矩阵此矩阵为对称矩阵。图图5.6 下三角矩阵下三角矩阵A 对对于于下下三三角角矩矩阵阵的的压压缩缩存存储储，只只存存储储下下三三角角的的非非零零元元素素，对对于于零零元元素素则则不不存存。我我们们按按“行行序序为为主主序序”进进行行存存储储，得得到到的的序序列列是是a11,a21,a22,a31,a32,a33,an1,an2,ann。由由于于下下三三角角矩矩阵阵的的元元素素个个数数为为n(n+1)/2，即：即：第第1行：行：1个个第第2行：行：2个个第第3行：行：3个个 第第n行：行：n个个 1+2+3+4+5+n=n(n+1)/2 所以可压缩存储到一个大小为所以可压缩存储到一个大小为n(n+1)/2的一维数组的一维数组C中，如图中，如图5.7所示。所示。图图5.7 三角矩阵的压缩形式三角矩阵的压缩形式 Loc(1,1)Loc(i,j)下三角矩阵中元素下三角矩阵中元素aij(ij)在一维数组在一维数组A中的位置为中的位置为(设每个元素占一个字节设每个元素占一个字节）：Loci,j=Loc1,1+前前i-1行行非非零零元元素素个个数数+第第i行行中中aij前前非非零零元元素素个个数数前前。i-1行行元元素素个个数数=1+2+3+4+（i-1）=i(i-1)/2，第，第i行中行中aij前非零元素个数前非零元素个数=j-1，所以有所以有Loci,j=Loc1,1+i(i-1)/2+j-1 同同样样，对对于于上上三三角角矩矩阵阵，也也可可以以将将其其压压缩缩存存储储到到一一个个大大小小为为n(n+1)/2的的一一维维数数组组C中中。其其中中元元素素aij(ij)在在数数组组C中中的的存存储储位置为：位置为：Loci,j=Loc1,1+j(j-1)/2+i-1 对对于于对对称称矩矩阵阵，因因其其元元素素满满足足aij=aji，我我们们可可以以为为每每一一对对相相等等的的元元素素分分配配一一个个存存储储空空间间，即即只只存存下下三三角角（或或上上三三角角）矩矩阵阵，从而将从而将n2个元素压缩到个元素压缩到n(n+1)/2个空间中。个空间中。1.1.设设A A是是n*nn*n的的对对称称矩矩阵阵，将将A A的的对对角角线线及及对对角角线线上上方方的的元元素素以以列列为为主主的的次次序序存存放放在在一一维维数数组组B1.n(n+1)/2B1.n(n+1)/2中中，对对上上述述任任一一元元素素a aijij(1i(1i，jnjn，且且ij)ij)在在B B中中的的位位置为置为()()。A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1 2.ANAN，NN是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 T1.NT1.N（N+1N+1）/2/2中，则对任一上三角元素中，则对任一上三角元素aijaij对应对应TkTk的下标的下标k k是（是（）。）。A.iA.i（i-1i-1）/2+j B.j/2+j B.j（j-1j-1）/2+i C.i/2+i C.i（j-ij-i）/2+1 D.j/2+1 D.j（i-1i-1）/2+1/2+1 3.3.假设一个假设一个1515阶的上三角矩阵阶的上三角矩阵A A按行优先顺序压缩存储在一维数组按行优先顺序压缩存储在一维数组B B中，则非零元中，则非零元素素A A9,99,9在在B B中的存储位置中的存储位置k=_k=_。（。（注：矩阵元素下标从注：矩阵元素下标从1 1开始）开始）【北京工商大学北京工商大学 2001 2001】图图5.8 带状矩阵带状矩阵A 三对角带状矩阵有如下特点：三对角带状矩阵有如下特点：i=1,j=1,2;1in,j=i-1,i,i+1;i=n,j=n-1,n;时，时，aij非零，其它元素均为零。非零，其它元素均为零。当5.3.2 带状矩阵带状矩阵 1.确定存储该矩阵所需的一维向量空间的大小确定存储该矩阵所需的一维向量空间的大小 在在这这里里我我们们假假设设每每个个非非零零元元素素所所占占空空间间的的大大小小为为1个个单单元元。从从图图中中观观察察得得知知，三三对对角角带带状状矩矩阵阵中中，除除了了第第一一行行和和最最后后一一行行只只有有2个个非非零零元元素素外外，其其余余各各行行均均有有3个个非非零零元元素素。由由此此得得到到，所所需需一一维维向向量量空空间间的的大大小小为为2+2+3（n-2）=3n-2，如图如图5.9所示。所示。图图5.9 带状矩阵的压缩形式带状矩阵的压缩形式 2.确定非零元素在一维数组空间中的位置确定非零元素在一维数组空间中的位置 Loci,j=Loc1,1+前前i-1行行非非零零元元素素个个数数+第第i行行中中aij前前非非零零元元素素个个数数；前前i-1行元素个数行元素个数=3（i-1）-1（因为第因为第1行只有行只有2个非零元素）；个非零元素）；第第i行中行中aij前非零元素个数前非零元素个数=j-i+1，其中其中-1(ji)j-i=由此得到由此得到 Loci,j=Loc1,1+3(i-1)-1+j-i+1 =Loc1,1+2(i-1)+j-1 5.3.3 稀疏矩阵稀疏矩阵 图图5.10 稀疏矩阵稀疏矩阵 1.稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法 图图5.11 三元组的结构三元组的结构 图图5.12 稀疏矩阵的三元组表表示稀疏矩阵的三元组表表示 三元组表所三元组表所需存储单元需存储单元个数为个数为3(t+1)其中其中t为非零为非零元个数元个数6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8分别存放矩阵行列分别存放矩阵行列维数和非零元个数维数和非零元个数行列下标行列下标非零元值非零元值三元组表的类型说明如下：三元组表的类型说明如下：define MAXSIZE 1000 /*非零元素的个数最多为非零元素的个数最多为1000*/typedef struct int row,col;/*该非零元素的行下标和列下标该非零元素的行下标和列下标*/ElementType e；/*该非零元素的值该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1;/*非零元素的三元组表，非零元素的三元组表，data0未用未用*/int m,n,len;/*矩阵的行数、矩阵的行数、列数和非零元素的个数列数和非零元素的个数*/TSMatrix；1)用三元组表实现稀疏矩阵的转置运算用三元组表实现稀疏矩阵的转置运算 所所谓谓的的矩矩阵阵转转置置，是是指指变变换换元元素素的的位位置置，把把位位于于（row，col）位位置置上上的元素换到（的元素换到（col，row）位置上，也就是说，位置上，也就是说，把元素的行列互换。把元素的行列互换。如如图图5.10所所示示的的67矩矩阵阵M，它它的的转转置置矩矩阵阵就就是是76的的矩矩阵阵N，并并且且N（row，col）=M（col，row），），其中，其中，1row7，1col6。采用矩阵的正常存储方式时，采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：实现矩阵转置的经典算法如下：void TransMatrix（ElementType sourcenm,ElementType destmn）/*source和和dest分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/int i,j;for(i=0;im;i+)for(j=0;jm=A.n;B-n=A.m;B-len=A.len;if(B-len0)j=1;for(k=1;k=A.n;k+)for(i=1;idataj.row=A.datai.col B-dataj.col=A.datai.row;B-dataj.e=A.datai.e;j+;【算法算法5.1 基于稀疏矩阵的三元组表示矩阵的转置算法基于稀疏矩阵的三元组表示矩阵的转置算法】算法分析：算法分析：算算法法的的时时间间耗耗费费主主要要是是在在双双重重循循环环中中，其其时时间间复复杂杂度度为为O（A.nA.len）,最最坏坏情情况况下下，当当A.len=A.mA.n时时，时时间间复复杂杂度度为为O（A.mA.n2）。采采用用正正常常方方式式实实现现矩矩阵阵转转置置的的算算法法时时间复杂度为间复杂度为O（A.mA.n）。）。方法二：方法二：依次按三元组表依次按三元组表A的次序进行转置，转置后直接放到三元组表的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。的正确位置上。这种转置算法称为快速转置算法。为为了了能能将将待待转转置置三三元元组组表表A中中元元素素一一次次定定位位到到三三元元组组表表B的的正正确确位位置上，需要预先计算以下数据：置上，需要预先计算以下数据：(1)待待转转置置矩矩阵阵source每每一一列列中中非非零零元元素素的的个个数数（即即转转置置后后矩矩阵阵dest每一行中非零元素的个数）。每一行中非零元素的个数）。(2)待待转转置置矩矩阵阵source每每一一列列中中第第一一个个非非零零元元素素在在三三元元组组表表B中中的的正正确确位位置置（即即转转置置后后矩矩阵阵dest每每一一行行中中第第一一个个非非零零元元素素在在三三元组元组B中的正确位置中的正确位置)。为为此此，需需要要设设两两个个数数组组num 和和position，其其中中numcol用用来来存存放放三三元元组组表表A中中第第col列列中中非非零零元元素素个个数数（三三元元组组表表B中中第第col行行非非零零元元素素的的个个数数），positioncol用用来来存存放放转转置置前前三三元元组组表表A中中第第col列列（转转置置后后三三元元组组表表B中中第第col行）中第一个非零元素在三元组表行）中第一个非零元素在三元组表B中的正确位置。中的正确位置。numcol的计算方法：的计算方法：将三元组表将三元组表A扫描一遍，对于其中列号为扫描一遍，对于其中列号为k的元素，给相应的的元素，给相应的numk加加1。positioncol的计算方法：的计算方法：position1=1，positioncol=positioncol-1+numcol-1，其中其中2colA.n。图图5.16 图图5.10中矩阵中矩阵M的的numcol和和positioncol的值的值 colnumcolpositioncol112232352471580681790 将将三三元元组组表表A中中所所有有的的非非零零元元素素直直接接放放到到三三元元组组表表B中中正正确位置上的方法：确位置上的方法：positioncol的的初初值值为为三三元元组组表表A中中第第col列列（三三元元组组表表B的的第第col行行）中中第第一一个个非非零零元元素素的的正正确确位位置置，当当三三元元组组表表A中中第第 col列列 有有 一一 个个 元元 素素 加加 入入 到到 三三 元元 组组 表表 B时时，则则positioncol=positioncol+1，即即：使使positioncol始始终终指指向向三三元元组组表表A中中第第col列列中中下下一一个个非非零零元元素素的的正正确确位位置置。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 row col e0 1 2 3 4 5 6 7 8Mrow col e0 1 2 3 4 5 6 7 8Ncolnumcolpositioncol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753FastTransposeTSMatrix(TSMatrix A,TSMatrix*B)/*基于矩阵的三元组表示，基于矩阵的三元组表示，采用快速转置法，采用快速转置法，将矩阵将矩阵A转置为转置为B所指的矩阵所指的矩阵*/int col,t,p，q;int numMAXSIZE,positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len)for(col=1;col=A.n;col+)numcol=0;具体算法如下：具体算法如下：for(t=1;t=A.len;t+)numA.datat.col+;/*计算每一列的非零元素的个数计算每一列的非零元素的个数*/position1=1;for(col=2;col=A.n;col+)/*求求col列中第一个非零元素在列中第一个非零元素在B.data 中的正确位置中的正确位置*/positioncol=positioncol-1+numcol-1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e;positioncol+;【算法算法5.2 快速稀疏矩阵转置算法快速稀疏矩阵转置算法】快快速速转转置置算算法法的的时时间间主主要要耗耗费费在在四四个个并并列列的的单单循循环环上上，这这四四个个并并列列的的单单循循环环分分别别执执行行了了A.n，A.len，A.n-1，A.len次次，因因而而总总的的时时间间复复杂杂度度为为O(A.n)+O(A.len)+O(A.n)+O(A.len)，即即为为O（A.n+A.len）。当当待待转转置置矩矩阵阵M中中非非零零元元素素个个数数接接近近于于A.mA.n 时时，其其时时间间复复杂杂度度接接近近于于经经典典算算法法的的时时间复杂度间复杂度O(A.mA.n)。快快速速转转置置算算法法在在空空间间耗耗费费上上除除了了三三元元组组表表所所占占用用的的空空间间外外，还还需需要要两两个个辅辅助助向向量量空空间间，即即num1.A.n，position1.A.n。可可见见，算算法法在在时时间上的节省，是以更多的间上的节省，是以更多的存储空间为代价存储空间为代价的。的。算法分析：算法分析：2.稀疏矩阵的链式存储结构稀疏矩阵的链式存储结构:十字链表十字链表 与与用用二二维维数数组组存存储储稀稀疏疏矩矩阵阵比比较较，用用三三元元组组表表表表示示的的稀稀疏疏矩矩阵阵不不仅仅节节约约了了空空间间，而而且且使使得得矩矩阵阵某某些些运运算算的的运运算算时时间间比比经经典典算算法法还还少少。但但是是在在进进行行矩矩阵阵加加法法、减减法法和和乘乘法法等等运运算算时时，有有时时矩矩阵阵中中的的非非零零元元素素的的位位置置和和个个数数会会发发生生很很大大的的变变化化。如如A=A+B，将将矩矩阵阵B加加到到矩矩阵阵A上上，此此时时若若还还用用三三元元组组表表表表示示法法，势必会为了保持三元组表势必会为了保持三元组表“以行序为主序以行序为主序”而大量移动元素。而大量移动元素。在在十十字字链链表表中中，矩矩阵阵的的每每一一个个非非零零元元素素用用一一个个结结点点表表示示，该结点除了（该结点除了（row，col，value）以外，还要有以下两个链域：以外，还要有以下两个链域：right：用于链接同一行中的下一个非零元素；用于链接同一行中的下一个非零元素；down：用于链接同一列中的下一个非零元素。用于链接同一列中的下一个非零元素。rowcolValueDown right图图5.22 十字链表中结点的结构示意十字链表中结点的结构示意 图图5.23 十字链表的结构十字链表的结构 十字链表的结构类型说明如下：十字链表的结构类型说明如下：typedef struct OLNode int row,col;/*非零元素的行和列下标非零元素的行和列下标*/ElementType value;struct OLNode *right,*down;/*非零元素所在行表、列表的后继链域非零元素所在行表、列表的后继链域*/OLNode;*OLink;typedef struct OLink *row_head,*col_head;/*行、行、列链表的头指针向量列链表的头指针向量*/int m,n,len;/*稀疏矩阵的行数、稀疏矩阵的行数、列数、列数、非零元素的个数非零元素的个数*/CrossList;CreateCrossList(CrossList*M)/*采用十字链表存储结构，采用十字链表存储结构，创建稀疏矩阵创建稀疏矩阵M*/if(M!=NULL)free(M);scanf(&m,&n,&t);/*输入输入M的行数的行数,列数和非零元素的个数列数和非零元素的个数*/M-m=m;M-n=n;M-len=t;if(!(M-row_head=(OLink*)malloc(m+1)sizeof(OLink)exit(OVERFLOW);if(!(M-col_head=(OLink*)malloc(n+1)sizeof(OLink)exit(OVERFLOW);M-row_head=M-col_head=NULL;/*初始化行、初始化行、列头指针向量，列头指针向量，各行、各行、列链表为空的链表列链表为空的链表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);p-row=i;p-col=j;p-value=e;/*生成结点生成结点*/if(M-row_headi=NULL)M-row_headi=p;else /*寻找行表中的插入位置寻找行表中的插入位置*/for(q=M-row_headi;q-right&q-right-colright)p-right=q-right;q-right=p;/*完成插入完成插入*/if(M-col_headj=NULL)M-col_headj=p;else /*寻找列表中的插入位置寻找列表中的插入位置*/for(q=M-col_headj;q-down&q-down-rowdown)p-down=q-down;q-down=p;/*完成插入完成插入*/【算法算法5.4 建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表】建十字链表的算法的时间复杂度为建十字链表的算法的时间复杂度为O（ts），），s=max（m，n）。）。5.4 广广 义义 表表 广广义义表表，顾顾名名思思义义，也也是是线线性性表表的的一一种种推推广广。广广义义表表被被广广泛泛地地应应用用于于人人工工智智能能等等领领域域的的表表处处理理语语言言LISP语语言言中中。在在LISP语语言言中中，广广义义表表是是一一种种最最基基本本的的数数据据结结构构，就就连连LISP 语言的程语言的程序也表示为一系列的广义表。序也表示为一系列的广义表。广广义义表表是是n个个数数据据元元素素（d1，d2，d3，dn）的的有有限限序序列列，但但广广义义表表中中的的di既既可可以以是是单单个个元元素素，还还可可以以是是一一个个广广义义表表，通通常记作：常记作：GL=（d1，d2，d3，dn）。）。GL是是广广义义表表的的名名字字，通通常常广广义义表表的的名名字字用用大大写写字字母母表表示示。n是是广广义义表表的的长长度度。若若其其中中di是是一一个个广广义义表表，则则称称di是是广广义义表表GL的的子子表表。在在广广义义表表GL中中，d1是是广广义义表表GL的的表表头头，而而广广义义表表GL其其余余部部分分组组成成的的表表（d2，d3，dn）称称为为广广义义表表的的表表尾尾。由由此此可可见见广广义义表表的的定定义义是是递递归归定定义义的的，因因为为在在定定义义广广义义表表时时又又使使用了广义表的概念。用了广义表的概念。D=（）（）空表；其长度为零。空表；其长度为零。A=（a，（b，c）表表长长度度为为2的的广广义义表表，其其中中第第一一个元素是单个数据个元素是单个数据a，第二个元素是一个子表（第二个元素是一个子表（b，c）。）。B=（A，A，D）长长度度为为3的的广广义义表表，其其前前两两个个元元素素为表为表A，第三个元素为空表第三个元素为空表D。C=（a，C）长长度度为为2递递归归定定义义的的广广义义表表，C相相当当于于无穷表无穷表C=（a，（，（a,（a，（，（）。）。其其中中，A、B、C、D是是广广义义表表的的名名字字。下下面面以以广广义义表表A为为例例，说明求表头、说明求表头、表尾的操作：表尾的操作：head（A）=a 表表A的表头是的表头是a。tail（A）=(b,c)表表A的表尾是的表尾是(b,c)。广义表的表尾一广义表的表尾一定是一个表定是一个表。从上面的例子可以看出：从上面的例子可以看出：（1）广广义义表表的的元元素素可可以以是是子子表表，而而子子表表还还可可以以是是子子表表由此可见，广义表是一个多层的结构。由此可见，广义表是一个多层的结构。（2）广广义义表表可可以以被被其其它它广广义义表表共共享享，如如广广义义表表B就就共共享享表表A。在在表表B中中不不必必列列出出表表A的的内内容容，只只要要通通过过子子表表的的名名称称就就可以引用该表。可以引用该表。（3）广义表具有递归性，广义表具有递归性，如广义表如广义表C。思考：思考：广义表广义表(a),(b),c),(d)的表头是的表头是_；表尾是；表尾是_；长度是长度是。HEAD（(a),(b),c),(d)）TAIL （(a),(b),c),(d)）由由于于广广义义表表GL=（d1，d2，d3，dn）中中的的数数据据元元素素既既可可以以是是单单个个元元素素，也也可可以以是是子子表表，因因此此对对于于广广义义表表来来说说，我我们们难难以以用用顺顺序序存存储储结结构构来来表表示示它它，通通常常我我们们用用链链式式存存储储结结构构来来表表示示。表表中中的的每每个个元元素素可可用用一一个个结结点点来来表表示示。广广义义表表中中有有两两类类结结点点：一一类类是是单单个个元元素素结结点点；另另一一类类是是子子表表结结点点。任任何何一一个个非非空空的的广广义义表表都都可可以以分分解解成成表表头头和和表表尾尾两两部部分分，反反之之，一一对对确确定定的的表表头头和和表表尾尾可可以以唯唯一一地地确确定定一一个个广广义义表表。由由此此，一一个个表表结结点点可可由由三三个个域域构构成成：标标志志域域、指指向向表表头头的的指指针针域域和和指指向向表表尾尾的的指指针针域域。而而元元素素结结点点只只需需要要两两个个域域：标标志志域域和和值值域。域。/*广义表的头尾链表存储结构广义表的头尾链表存储结构*/typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；表示原子；LIST1，表示子表表示子表*/typedef struct GLNode ElemTag tag;/*标志位标志位tag用来区别原子结点和表结点用来区别原子结点和表结点*/union AtomType atom;/*原子结点的值域原子结点的值域atom*/struct struct GLNode *hp,*tp;htp;/*表结点的指针域表结点的指针域htp，包括表头指针域包括表头指针域hp和表尾指针域和表尾指针域tp*/atom-htp;/*atom-htp 是是原原子子结结点点的的值值域域atom和和表表结结点点的的指指针针域域htp的的联联合合体体域域*/*GList；图图5.24 广义表广义表A、B、C、D的存储结构的存储结构 图图5.25 广义表的另一种结点结构广义表的另一种结点结构 Tag=1hptpTag=1atomtp表结点 原子结点 图图5.26 广义表的第二种存储结构广义表的第二种存储结构 这种存储结构的形式说明如下：这种存储结构的形式说明如下：typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；表示原子；LIST1，表示子表表示子表*/typedef struct GLNode ElemTag tag;union AtomType atom;struct GLNode *hp;atom-hp;/*atom-hp 是原子结点的值域是原子结点的值域atom和表结点的表头指针域和表结点的表头指针域hp的联合的联合体域体域*/struct GLNode *tp;*GList;