第5章数组和广义表.pptx

1/55l数组和广义表可看成是一种特殊的线性表数组和广义表可看成是一种特殊的线性表，其特殊在于，表，其特殊在于，表中的所有元素本身也是一种线性表。中的所有元素本身也是一种线性表。l由于数组中各元素具有统一的类型，并且数组元素的下标一由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的般具有固定的上界和下界，因此，数组的处理比其它复杂的数据结构较为简单。数据结构较为简单。l多维数组是向量的推广。例如，二维数组：多维数组是向量的推广。例如，二维数组：5.1 数组的定义数组的定义2/55l二维数组可以看成是二维数组可以看成是由行向量组成的向量由行向量组成的向量，也可以看成是，也可以看成是由由列向量组成的向量列向量组成的向量。l同样，可把三维数组看成是一个线性表，表中每一个数组元同样，可把三维数组看成是一个线性表，表中每一个数组元素为一个二维数组。依次类推，可把素为一个二维数组。依次类推，可把n维数组看成是一个线维数组看成是一个线性表，表中每一个数据元素是一个性表，表中每一个数据元素是一个n-1维数组。维数组。l数组的运算：数组一旦被定义，它的维数和维界就不再改变。数组的运算：数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，因此，除了结构的初始化和销毁之外，数组只有存取元素数组只有存取元素和修改元素值的操作，和修改元素值的操作，即给定一组下标，存取或修改相应即给定一组下标，存取或修改相应的数组元素。的数组元素。5.1 数组的定义数组的定义3/551、顺序存储结构、顺序存储结构5.2 数组的顺序表示和实现数组的顺序表示和实现l用一组地址连续的存储单元依次存放数组的数据元素，称为用一组地址连续的存储单元依次存放数组的数据元素，称为数组的顺序存储结构数组的顺序存储结构。l由于计算机的内存结构是一维的，因此用一维内存来表示多由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按维数组，就必须按某种次序某种次序将数组元素排成一列序列，然后将数组元素排成一列序列，然后将这个线性序列存放在存储器中。将这个线性序列存放在存储器中。l由于对数组一般不做插入和删除操作，也就是说，数组一旦由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。建立，结构中的元素个数和元素间的关系就不再发生变化。因此，因此，一般都是采用顺序存储的方法来表示数组一般都是采用顺序存储的方法来表示数组。4/55 通常有两种顺序存储方式：通常有两种顺序存储方式：2、顺序存储方式、顺序存储方式l行优先顺序行优先顺序将数组元素按行向量排列，第将数组元素按行向量排列，第i+1个行向量紧个行向量紧接在第接在第i个行向量后面。以二维数组为例，按行优先顺序存储的个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：线性序列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在在PASCAL、C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。l列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1个列向量紧个列向量紧接在第接在第j个列向量之后。以二维数组为例，按列优先顺序存储的个列向量之后。以二维数组为例，按列优先顺序存储的线性序列为：线性序列为：a11,a21,am1,a12,a22,am2,a1n,a2n,amn 在在FORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。5/55a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放 amn am2 am1 a2n a22 a21 a1n a12 a1101n-1m*n-1n按列序为主序存放按列序为主序存放01m-1m*n-1m amn a2n a1n am2 a22 a12 am1 a21 a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l6/55l以上规则推广到多维数组的情况：以上规则推广到多维数组的情况：行优先顺序可规定为先排行优先顺序可规定为先排最右的下标，从右到左，最后排最左的下标最右的下标，从右到左，最后排最左的下标；3、n维数组维数组l按上述两种方式顺序存储的数组，只要知道开始结点的存放按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，其下标的线性函数。因此，数组中的任一元素可以在相同的数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。时间内存取，即顺序存储的数组是一个随机存取结构。l列优先顺序与此相反，先排最左的下标，从左向右，最后排列优先顺序与此相反，先排最左的下标，从左向右，最后排最右的下标。最右的下标。7/55l例如，二维数组例如，二维数组Amn按按“行优先顺序行优先顺序”存储在内存中，假设存储在内存中，假设每个元素占用每个元素占用d个存储单元。个存储单元。4、地址公式、地址公式 元素元素aij的存储地址应是的存储地址应是数组的基地址加上排在数组的基地址加上排在aij前面的元前面的元素所占用的单元数素所占用的单元数。因为。因为aij位于第位于第i行、第行、第j列，前面列，前面i-1行一共行一共有有(i-1)n个元素，在第个元素，在第i行上行上aij前面又有前面又有j-1个元素，故它前面个元素，故它前面一共有一共有(i-1)n+j-1个元素，因此，个元素，因此，aij的地址计算函数为：的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)*n+j-1*dl同样，三维数组同样，三维数组Aijk按按“行优先顺序行优先顺序”存储，其地址计算函数为：存储，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d8/55l上述讨论均是假设数组各维的下界是上述讨论均是假设数组各维的下界是1，更一般的二维数组，更一般的二维数组是是Ac1.d1,c2.d2，这里，这里c1,c2不一定是不一定是1。aij前一共有前一共有i-c1行，二维数组一共有行，二维数组一共有d2-c2+1列，故这列，故这i-c1行共有行共有(i-c1)*(d2-c2+1)个元素，在第个元素，在第i行上行上aij前一共有前一共有j-c2个元素，因此，个元素，因此，aij的的地址计算函数为：地址计算函数为：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*dl例如，在例如，在C语言中，数组各维下标的下界是语言中，数组各维下标的下界是0，因此在，因此在C语言语言中，二维数组的地址计算公式为：中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d4、地址公式、地址公式9/55l在高级语言编制程序时，将一个矩阵描述为一个二维数组。在高级语言编制程序时，将一个矩阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现大量的零元素的情况下，大量的零元素的情况下，实际上占用了许多单元去存储重复实际上占用了许多单元去存储重复的非零元素或零元素的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为，这对高阶矩阵会造成极大的浪费，为了节省存储空间，了节省存储空间，可以对这类矩阵进行压缩存储。可以对这类矩阵进行压缩存储。5.3 矩阵的压缩存储矩阵的压缩存储l压缩存储：压缩存储：为多个值相同的非零元素只分配一个存储空间；为多个值相同的非零元素只分配一个存储空间；对零元素不分配空间。对零元素不分配空间。l假若值相同的元素或零元素在矩阵中的分布有一定规律，则假若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为称此类矩阵为特殊矩阵特殊矩阵；反之，称为；反之，称为稀疏矩阵稀疏矩阵。10/551、对称矩阵、对称矩阵 5.3.1 特殊矩阵特殊矩阵l在一个在一个n阶方阵阶方阵A中，中，若元素满足下述性质：若元素满足下述性质：aij=aji 0 i,j n-1 则称则称A为对称矩阵为对称矩阵。对称矩阵中的元素关于主对角线对称，对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，按不失一般性，按“行优先顺序行优先顺序”存储主对角线（包括对角线）存储主对角线（包括对角线）以下的元素，其存储形式如图所示：以下的元素，其存储形式如图所示：a00a01.a0n-1a10a11.a1n-1an-10an-11.an-1n-1.11/55a00a10 a11a20 a21 a22.an-1 0 an-1 1 an-1 2 a n-1 n-1 a00a01.a0n-1a10a11.a1n-1an-10an-11.an-1n-1.图 5.1 对称矩阵l在这个下三角矩阵中，第在这个下三角矩阵中，第i行恰有行恰有i+1个元素，元素总数为：个元素，元素总数为：n(n+1)/2。这样可将。这样可将n2个压缩到个压缩到n(n+1)/2个元的空间中。个元的空间中。l因此，可以按将这些元素存放在一个向量因此，可以按将这些元素存放在一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对称矩阵A中的元素，必须在中的元素，必须在aij和和sak之之间找一个对应关系。间找一个对应关系。1、对称矩阵、对称矩阵12/55l若若i j，则，则aij在下三角形中。在下三角形中。aij之前的之前的i行（从第行（从第0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，在第个元素，在第i行上，行上，aij之前之前恰有恰有j个元素（即个元素（即ai0,ai1,ai2,aij-1），因此有：），因此有：1、对称矩阵、对称矩阵 k=i*(i+1)/2+j 0 kn(n+1)/2l若若ij，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以只要交换，所以只要交换上述对应关系式中的上述对应关系式中的i和和j即可得到：即可得到：k=j*(j+1)/2+i 0 kn(n+1)/2 l令令 I=max(i,j)，J=min(i,j)，则，则k和和 i,j的对应关系可统一为：的对应关系可统一为：k=I*(I+1)/2+J 0 kd时，元素时，元素aij=0。l对带状矩阵可按对带状矩阵可按行优先顺序行优先顺序或或对角线的顺序对角线的顺序，将其压缩存储到一，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。个向量中，并且也能找到每个非零元素和向量下标的对应关系。17/55l上述的各种特殊矩阵，其非零元素的分布都是有规律的，因上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个一维数组中，并此总能找到一种方法将它们压缩存储到一个一维数组中，并且一般都能找到矩阵中的元素与该一维数组元素的对应关系，且一般都能找到矩阵中的元素与该一维数组元素的对应关系，通过这个关系，能对矩阵的元素进行随机存取。通过这个关系，能对矩阵的元素进行随机存取。5.3.2 稀疏矩阵稀疏矩阵什么是稀疏矩阵？什么是稀疏矩阵？l精确地，设在精确地，设在mn的矩阵的矩阵A中，有中，有t个非零元素。个非零元素。令令=t/(m*n)，称，称为为矩阵的稀疏因子矩阵的稀疏因子。通常认为。通常认为0.05时时可称之为可称之为稀疏矩阵稀疏矩阵。l简单说，设矩阵简单说，设矩阵A中有中有s个非零元素，若个非零元素，若s远远小于矩阵元素远远小于矩阵元素的总数（即的总数（即smn），则称），则称A为为稀疏矩阵。稀疏矩阵。18/55l在存储稀疏矩阵时，为了节省存储单元，很自然地想在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于其非零元素的分布一般到使用压缩存储方法。但由于其非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（同时记下它所在的行和列的位置（i，j)。1、三元组顺序表、三元组顺序表 l反之，一个三元组反之，一个三元组(i，j，aij)唯一确定了矩阵唯一确定了矩阵A的一个的一个非零元。非零元。l因此，因此，稀疏矩阵可由表示非零元的三元组及其行列数稀疏矩阵可由表示非零元的三元组及其行列数唯一确定唯一确定。19/55l例如，下列三元组表例如，下列三元组表 (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的另一种描述。而由上述三元组表的不同的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。表示方法可引出稀疏矩阵不同的压缩存储方法。图图5.4稀疏矩阵稀疏矩阵M和和T1、三元组顺序表、三元组顺序表 20/55#defineM20typedefstructnodeinti,j;intv;JD;JDmaM;l三元组表所需存储单元个数为三元组表所需存储单元个数为3(t+1)，其中，其中t为非零元个数为非零元个数678121213931-3361443245218611564-7maijv012345678lma0.i,ma0.j,ma0.v分别存放分别存放 矩阵行矩阵行、列维数和非零元个数列维数和非零元个数行列下标行列下标非零元值非零元值2、稀疏矩阵的压缩存储方法、稀疏矩阵的压缩存储方法21/553、求转置矩阵、求转置矩阵l问题描述：问题描述：已知一个稀疏矩阵已知一个稀疏矩阵M的三元组表的三元组表ma，求该矩阵的转置矩阵求该矩阵的转置矩阵T的三元组表的三元组表mb。l解决思路：解决思路：（1）将矩阵行、列维数互换将矩阵行、列维数互换 （2）将每个三元组中的）将每个三元组中的i和和j相互调换相互调换 （3）重排三元组次序，使）重排三元组次序，使mb中元素以中元素以T的行的行(M的的 列列)为主序为主序22/55678121213931-3361443245218611564-7ijv012345678maijv76813-3161521122518319342446-76314012345678mb?23/55l一个一个mn的矩阵的矩阵A，它的转置，它的转置B是一个是一个nm的矩阵，且的矩阵，且aij=bji，0im-1，0jn-1，即，即A的行是的行是B的列，的列，A的列是的列是B的行。的行。方法一方法一l将将A转置为转置为B，就是将，就是将A的三元组表的三元组表a.data置换为表置换为表B的三的三元组表元组表b.data，如果只是简单地交换，如果只是简单地交换a.data中中i和和j的内容，的内容，那么得到的那么得到的b.data将是一个按将是一个按列优先顺序列优先顺序存储的稀疏矩阵存储的稀疏矩阵B。l要得到按行优先顺序存储的要得到按行优先顺序存储的b.data，就必须重新排列三元，就必须重新排列三元组的顺序。组的顺序。24/55l由于由于A的列是的列是B的行，因此，按的行，因此，按a.data的列序转置，所得的列序转置，所得到的转置矩阵到的转置矩阵B的三元组表的三元组表b.data必定是按必定是按行优先顺序行优先顺序存存放的。放的。l按这种方法设计的算法，按这种方法设计的算法，其基本思想是其基本思想是：对：对A中的每一列中的每一列 col(0coln-1)，通过从头至尾扫描三元表，通过从头至尾扫描三元表a.data，找出，找出所有列号等于所有列号等于col的那些三元组，将它们的行号和列号互的那些三元组，将它们的行号和列号互换后依次放入换后依次放入b.data中，即可得到中，即可得到B的按的按行优先顺序行优先顺序的压的压缩存储表示。缩存储表示。方法一方法一25/55l#define MAXSIZE 12500 ltypedef struct int i,j;ElemType e;Triple;ltypedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;26/55Status TransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;l if(T.tu)q=1;for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;27/55678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbqppppppppqqqqppppppppcol=1col=2方法一方法一28/55l这个算法，主要的工作是在这个算法，主要的工作是在p和和col的两个循环中完成的，的两个循环中完成的，故算法的时间复杂度为故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元，即矩阵的列数和非零元的个数的乘积成正比。的个数的乘积成正比。l而一般传统矩阵的转置算法为：而一般传统矩阵的转置算法为：for(col=1;col=nu;+col)for(row=1;row=mu;+row)tcolrow=mrowcol;其时间复杂度为其时间复杂度为O(nu*mu)。方法一方法一29/55l当非零元素的个数当非零元素的个数tu和和mu*nu同数量级时，方法一的时间同数量级时，方法一的时间复杂度为复杂度为O(mu*nu2)。l三元组顺序表虽然节省了存储空间，但时间复杂度比一般三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于因此，此算法仅适用于tumu*nu的情况。的情况。方法一方法一30/55l按照按照a.data中三元组的次序进行转置，并将转置后的三元组置中三元组的次序进行转置，并将转置后的三元组置入入b.data中的恰当位置。中的恰当位置。方法二：快速转置算法方法二：快速转置算法l如果能预先确定矩阵如果能预先确定矩阵M中每一列（即中每一列（即T中每一行）的第一个非中每一行）的第一个非零元素在零元素在b.data中应有的位置，那么在对中应有的位置，那么在对a.data中的三元组依中的三元组依次作转置时，便可直接放到次作转置时，便可直接放到b.data中恰当的位置上去。中恰当的位置上去。l为了确定这些位置，在转置前，应先求得为了确定这些位置，在转置前，应先求得M的每一列中非零元的的每一列中非零元的个数，进而求得每一列的第一个非零元在个数，进而求得每一列的第一个非零元在b.data中应有的位置。中应有的位置。l快速转置算法的思想：快速转置算法的思想：对对A扫描一次，按扫描一次，按A第二列提供的列号第二列提供的列号依次确定装入依次确定装入B的一个三元组的位置。具体实施如下：一遍扫的一个三元组的位置。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，可见，位置关系是此种算法的关键。位置关系是此种算法的关键。31/55实现：需要附设实现：需要附设num和和cpot两个数组。两个数组。lnumcol：表示矩阵：表示矩阵M中第中第col列中非零元列中非零元的的个数个数；lcpotcol：指示指示矩阵矩阵M中第中第col列第一个非零元在列第一个非零元在mb中中的的位置位置显然有：显然有：lcpot1=1;lcpotcol=cpotcol-1+numcol-1;(2 col a.nu)1357889colnumcolcpotcol12223241506170方法二：快速转置算法方法二：快速转置算法32/55Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)lT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;lif(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;/求求M中每一列含非零元个数中每一列含非零元个数 cpot1=1;方法二：快速转置算法方法二：快速转置算法33/55 for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;/求第求第col列中第列中第1个非零元素在个非零元素在b.data中的序号。中的序号。for(p=1;p=1)非空，则非空，则a1是是LS的的表表头头，其余元素组成的表，其余元素组成的表(a2,a3,an)称为称为LS的的表尾表尾。l显然广义表是递归定义的，这是因为在定义广义表时又用到显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：了广义表的概念。广义表的例子如下：（1）A=（）（）A是一个空表，其长度为零。是一个空表，其长度为零。（2）B=（e）表表B只有一个原子只有一个原子e，B的长度为的长度为1。（3）C=（a,(b,c,d)表表C的长度为的长度为2，两个元素分别为原，两个元素分别为原子子a和子表和子表(b,c,d)。（4）D=（A，B，C）表表D的长度为的长度为3，三个元素都是广义，三个元素都是广义表。显然，将子表的值代入后，则有表。显然，将子表的值代入后，则有D=(),(e),(a,(b,c,d)。5.4 广义表的定义广义表的定义43/55 （5）E=（a,E）这是一个递归的表，它的长度为这是一个递归的表，它的长度为2，E相相当于一个无限的广义表当于一个无限的广义表E=(a,(a,(a,(a,).l例如：例如：D=(E,F)其中其中:E=(a,(b,c)F=(d,(e)DEFa()d()bcel从上述定义和例子可推出广义表的三个重要结论：从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表。）广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。由此，广义表是一个多层次的结构，可以用图形象地表示。5.4 广义表的定义广义表的定义44/55（2）广义表可为其它表所共享。）广义表可为其它表所共享。例如在上述例（例如在上述例（4）中，广义）中，广义表表A，B，C为为D的子表，则在的子表，则在D中可以不必列出子表的值，中可以不必列出子表的值，而是通过子表的名称来引用。而是通过子表的名称来引用。（3）广义表的递归性。）广义表的递归性。l综上所述，综上所述，广义表不仅是线性表的推广，也是树的推广。广义表不仅是线性表的推广，也是树的推广。l广义表中所含括弧的重数称为广义表中所含括弧的重数称为表的深度表的深度，表中元素的层数就，表中元素的层数就是包括该元素的括弧重数。例如：是包括该元素的括弧重数。例如：F（a，b，（，（c，（，（d）其中，单元素其中，单元素a、b在第一层，在第一层，d在第三层，广义表的深度为在第三层，广义表的深度为3。5.4 广义表的定义广义表的定义45/55l由于广义表由于广义表(a1,a2,a3,an)中的数据元素可以具有不同的结中的数据元素可以具有不同的结构（或是原子，或是广义表），因此，构（或是原子，或是广义表），因此，难以用顺序存储结难以用顺序存储结构表示，通常采用链式存储结构构表示，通常采用链式存储结构，每个数据元素可用一个，每个数据元素可用一个结点表示。结点表示。tag=1 hp tp tag=0 atom表结点表结点原子结点原子结点l由于广义表中有两种数据元素：原子或广义表，因此，需由于广义表中有两种数据元素：原子或广义表，因此，需要两种结构的结点：要两种结构的结点：一种是表结点，一种是原子结点一种是表结点，一种是原子结点。l表结点由三个域组成：表结点由三个域组成：标志域、指示表头的指针域和指示标志域、指示表头的指针域和指示表尾的指针域；表尾的指针域；l而原子结点只需两个域：而原子结点只需两个域：标志域和值域标志域和值域。5.5 广义表的存储结构广义表的存储结构46/55L=(a,(x,y),(x)a(x,y)()1L0a111110 x ()x47/55BCDE1 0 e1 1 0 a1 1 1 1 0 a1 1 0 d0 c0 b1 1 广义表的存储结构示例广义表的存储结构示例l（1）A=（）（）l（2）B=（e）l（3）C=（a,（b,c,d）l（4）D=（A，B，C）l（5）E=（a,E）48/55*5.6 m元多项式的表示元多项式的表示1、一元多项式、一元多项式l一个多项式可以用一个长度为一个多项式可以用一个长度为m且每个数据元素有两个数且每个数据元素有两个数据项（系数项和指数项）的线性表来表示。据项（系数项和指数项）的线性表来表示。2、m元多项式元多项式l一个一个m元多项式的每一项，最多有个元多项式的每一项，最多有个m变元，如果用线性表变元，如果用线性表来表示，则每个数据元素需要来表示，则每个数据元素需要m+1个数据项，以存储一个个数据项，以存储一个系数值和系数值和m个指数值。将产生两个问题：个指数值。将产生两个问题：l造成浪费造成浪费 l线性表中结点大小不一样线性表中结点大小不一样49/55l因此，由于因此，由于m 元多项式中每一项的变化数目不均匀性和变元多项式中每一项的变化数目不均匀性和变元信息的重要性，故不适于用线性表表示。例如：元信息的重要性，故不适于用线性表表示。例如：l上式是变元上式是变元Z的多项式，即的多项式，即 其中：其中：A和和B本身又是一个（本身又是一个（x,y）的二元多项式，）的二元多项式，15是是Z的零的零次项的系数。次项的系数。l进一步考察进一步考察A(x,y)，又可把它看成是，又可把它看成是y的多项式。的多项式。lCy3+Dy2，而其中，而其中C和和D为为x的一元多项式。循环以往，每个多的一元多项式。循环以往，每个多项式都可看作是由一个变量加上若干个系数指数偶对组成。项式都可看作是由一个变量加上若干个系数指数偶对组成。*5.6 m元多项式的表示元多项式的表示50/55l任何一个任何一个m 元多项式都可如此做：元多项式都可如此做：先分解出一个主变元，随后先分解出一个主变元，随后再分解出第二个变元，等等再分解出第二个变元，等等。由此，一个。由此，一个m元的多项式首先是元的多项式首先是它的主变元的多项式，而其系数又是第二变元的多项式，由此，它的主变元的多项式，而其系数又是第二变元的多项式，由此，可用广义表来表示可用广义表来表示m元多项式。例如上述三元多项式可用下式元多项式。例如上述三元多项式可用下式的广义表表示，广义表的深度即为变元个数。的广义表表示，广义表的深度即为变元个数。lP=Z（A，2），（），（B，1），（），（15，0）在广义表的括号之前加一个变元，以示各层的变元。在广义表的括号之前加一个变元，以示各层的变元。lA=y(C,3),(D,2)B=y(E,4),(F,1)lC=x(1,10),(2,6)D=x(3,5)lE=x(1,4),(6,3)F=x(2,0)*5.6 m元多项式的表示元多项式的表示51/55l可以类似广义表的第二种存储结构来定义表示可以类似广义表的第二种存储结构来定义表示m元多项式的元多项式的广义表的存储结构。链表的结点结构为：广义表的存储结构。链表的结点结构为：lexp为指数域，为指数域，coef为系数域，为系数域，hp指向其系数子表，指向其系数子表，tp指指向同一层的下一个结点。向同一层的下一个结点。l在每一层上增设一个表头结点，并利用在每一层上增设一个表头结点，并利用exp指示该层的变元，指示该层的变元，可用一维数组存储多项式中所有变元，故可用一维数组存储多项式中所有变元，故exp域存储的是该域存储的是该变元在一维数组中的下标。变元在一维数组中的下标。l头指针头指针p所指表结点中所指表结点中exp的值的值3为多项式中变元的个数。为多项式中变元的个数。P112页的图为三元多项式页的图为三元多项式P(x,y,z)的存储结构示意图。的存储结构示意图。tp hp tag=1 exp tp coef tag=0 exp表结点表结点原子结点原子结点*5.6 m元多项式的表示元多项式的表示52/551.了解数组的两种存储表示方法，并掌握数组在以行为主的了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。存储结构中的地址计算方法。第第5章章 小结小结2.掌握对特殊矩阵进行压缩存储时的下标变换公式。掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法，可根据自己的掌握广义表的结构特点及其存储表示方法，可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为头和表尾两部分或者分解为n个子表。个子表。53/55一、选择题一、选择题 1、一维数组和线性表的区别是、一维数组和线性表的区别是 。（A）前者长度固定，后者长度可变）前者长度固定，后者长度可变 （B）后者长度固定，前者长度可变）后者长度固定，前者长度可变 （C）两者长度均固定）两者长度均固定 （D）两者长度均可变）两者长度均可变 2、数组、数组A中，每个元素的长度为中，每个元素的长度为3个字节，行下标个字节，行下标i从从1到到8，列，列下标下标j从从1到到10，从首地址，从首地址SA开始连续存放在存储器内，该数组开始连续存放在存储器内，该数组按行存放时，元素按行存放时，元素A85的起始地址为的起始地址为 。（A）SA+141 （B）SA+144 （C）SA+222 （D）SA+225第第5章章 习题习题54/55 3、设有一个、设有一个10阶的对称矩阵，采用压缩存储方式，以行序为阶的对称矩阵，采用压缩存储方式，以行序为主序存储其下三角中的元素，主序存储其下三角中的元素，a1,1为第一个元素，其存储地址为第一个元素，其存储地址为为1，每个元素占，每个元素占1个地址空间，则个地址空间，则a8,5的地址的地址 。（A）13 （B）33 （C）18 （D）40二、填空题二、填空题 广义表（广义表（a，（，（a，b），），d，e，（，（I，j），），k）表的长）表的长度是度是 ，深度是，深度是 。第第5章章 习题习题