第5章数组和广义表课件.ppt

1、 数组和广义表可看成是一种特殊的线性表，其特数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。殊在于，表中的数据元素本身也是一种线性表。5.1 5.1 数组的定义数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数的结构更为简单。多维数组是向量的推广。例如，二维数组：组：mnmmnnnmaaaaaaaaaA.212222111211()()()()()

2、()()()()可以看成是由一个行向量组成的向量，也可以看成可以看成是由一个行向量组成的向量，也可以看成是由一个列向量组成的向量。是由一个列向量组成的向量。在在C C语言中，一个二维数组类型可以定义为其分语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说量类型为一维数组类型的一维数组类型，也就是说，typedef elemtype array2mn;typedef elemtype array2mn;等价于：等价于：typedef elemtype array1n;typedef elemtype array1n;typedef array1 array2m;t

3、ypedef array1 array2m;数组一旦被定义，它的维数和维界就不再改变数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。存取元素和修改元素值的操作。由于计算机的内存结构是一维的，因此用一维内存来由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说又由于对数组一般不做

4、插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。表示数组。通常有两种顺序存储方式：通常有两种顺序存储方式：以行序为主序以行序为主序 以列序为主序以列序为主序 a11 a12 .a1n a21 a22 .a2n am1 am2 .amn .Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a1101n

5、-1m*n-1n 按列序为主序存放按列序为主序存放01m-1m*n-1m amn .a2n a1n .am2 .a22 a12 am1 .a21 a11 a11 a12 .a1n a21 a22 .a2n am1 am2 .amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 无论规定行优先或列优先，只要知道以下三要素便可随时求出无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：任一元素的地址（这样数组中的任一元素便可以随机存取！）：二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC

6、(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素单个元素长度长度aijaij之前的之前的行数行数数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aijaij本行前面本行前面的元素个数的元素个数开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)

7、*L Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）例1软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。288例3：00年某校考研题设数组a160,170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+

8、1)+32-1)*28950答：请注意审题！答：请注意审题！利用列优先通式：答：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪

9、费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.3.15.3.1特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。存储。1 1、对称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：a aijij=a=ajiji 0i,jn-1 0i,jn-1则称则称A A为对称矩阵。如图为对称矩阵。如图5.15.1便是一个便是一个5 5阶对称矩

10、阵。阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按一半的存储空间。不失一般性，我们按“行优先行优先顺序顺序”存储主对角线（包括对角线）以下的元素，其存储形式如存储主对角线（包括对角线）以下的元素，其存储形式如图所示：图所示：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

11、 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 图图 5.1 对称矩阵对称矩阵 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：n(n+1)/2n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在因此，我们可以按从上到下、从左到右将这些元素存放在一个向量一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中的中的元素，我们必须在元素，我们必须在a aijij和和saksak 之间找一个对应关系。之间找一个对

12、应关系。若若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 2、三角矩阵、三角

13、矩阵 以主对角线划分，三角矩阵有上三角和下三角两以主对角线划分，三角矩阵有上三角和下三角两种。种。上三角矩阵如图所示，它的下三角（不包括主对角上三角矩阵如图所示，它的下三角（不包括主对角线）线）中的元素均为常数。下三角矩阵正好相反，它的主中的元素均为常数。下三角矩阵正好相反，它的主对对角线上方均为常数，如图所示。在大多数情况下，角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。三角矩阵常数为零。a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c .c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角

14、矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，可共享一个存储空间，其余的元素正好有其余的元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵个，因此，三角矩阵可压缩存储到向量可压缩存储到向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中，其中c c存存放在向量的最后一个分量中，放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第i i行行(0in)(0ij 下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，saksak和和a aijij对应关系是：对应关系是

15、：i(i+1)/2+j iji(i+1)/2+j ij n(n+1)/2 ij n(n+1)/2 i1i-j1时，元素时，元素a aijij=0=0。由此可知，一个由此可知，一个k k对角矩阵对角矩阵(k(k为奇数为奇数)A)A是满足下述条件的是满足下述条件的矩阵：若矩阵：若i-j(k-1)/2 i-j(k-1)/2，则元素，则元素 a aijij=0=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。下标的对应关系。在三对角矩阵里除满足

16、条件在三对角矩阵里除满足条件i=0i=0，j=0j=0、1 1，或，或i=n-1j=n-2i=n-1j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，其余元素都是零。外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第对这种矩阵，我们也可按行优序为主序来存储。除第0 0行和第行和第n-1n-1行是行是2 2个元素外，每行的非零元素都要是个元素外，每行的非零元素都要是3 3个，因此，需存储个，因此，需存储的元素个数为的元素个数为3n-23n-2。a00a01 a10a11a12a21 a n-1 n-2a n

17、-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 数组数组sa中的元素中的元素sak与三对角带状矩阵中的元素与三对角带状矩阵中的元素aij存在存在一一对应关系，在一一对应关系，在aij之前有之前有i行行,共有共有3*i-1个非零元素，在个非零元素，在第第i行，有行，有j-i+1个非零元素，这样，非零元素个非零元素，这样，非零元素aij的地址为：的地址为：LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，上例中，a a3434对应着对应着sa10sa10。k=2k=2*i+j=2i+j=2*3+4=103+4=10 a a

18、2121对应着对应着sa5 sa5 k=2 k=2*2+1=52+1=5由此，我们称由此，我们称sa0.3sa0.3*n-3n-3是阶三对角带状矩阵是阶三对角带状矩阵A A的压缩的压缩存储表示。存储表示。上述的各种特殊矩阵，其非零元素的分布都是有规律的，上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。通过这个关系，仍能对矩阵的元素进行随机存取。5.3.2 5.

19、3.2 稀疏矩阵稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵A A中有中有s s个非零元素，个非零元素，若若s s远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即smstag=1;h-dd.sublist=creat_GL(s);elseh-tag=0;h-dd.data=ch;elseh=NULL;ch=*(*s);(*s)+;if(h!=NULL)if(ch=,)h-link=creat_GL(s);elseh-link=NULL;return(h);该算法的时间复杂度为O(n)。2.输出广义表prn_GL(p)对于广义表的表头结点p，若为表结点，输出空表或递

20、归输出子表的内容，否则，输出元素值；若当前的结点还有后续结点，则递归输出后续表的内容。下面的函数把按链接存储的广义表以字符串形式输出。void prn_GL(NODE*p)if(p!=NULL)if(p-tag=1)printf();if(p-dd.sublist=NULL)printf();elseprn_GL(p-dd.sublist);elseprintf(%c,p-dd.data);if(p-tag=1)printf();if(p-link!=NULL)printf(,);prn_GL(p-link);该算法的时间复杂度为O(n)。3.广义表的复制对于广义表的头结点p，若为空，返回空指

21、针；若为表结点，递归复制子表；否则，复制原子结点；然后递归复制后续表。NODE*copy_GL(NODE*p)NODE*q;if(p=NULL)return(NULL);q=(NODE*)malloc(sizeof(NODE);q-tag=p-tag;if(p-tag)q-dd.sublist=copy_GL(p-dd.sublist);elseq-dd.data=p-dd.data;q-link=copy_GL(p-link);return(q);四、几个运算的调用下列主函数的功能是:创建带表头结点链式存储的广义表然后复制一个新的广义表,并把广义表按字符串的方式输出.main()NODE*h

22、d,*hc;char s100,*p;p=gets(s);hd=creat_GL(&p);hc=copy_GL(hd);printf(copy after:);prn_GL(hc);求广义表深度求广义表原子结点个数求广义表原子结点数据域之和深度公式:maxdh(p)=0 p-tag=1maxdh(p)=1 空表空表(p-tag=1&p-dd.sublist=NULL)maxdh(p)=max(maxdh(p1),.,maxdh(pn)+1 其余情况 p=(p1,p2,.,pn)int depth(NODE*p)/*求表的深度函数 */int h,maxdh;NODE*q;if(p-tag=0)

23、return(0);else if(p-tag=1&p-dd.sublist=NULL)return 1;else maxdh=0;while(p!=NULL)if(p-tag=0)h=0;else q=p-dd.sublist;h=depth(q);if(hmaxdh)maxdh=h;p=p-link;return(maxdh+1);原子结点个数公式:(f(p)=0 p=NULLf(p)=1+f(p-link)p-tag=0f(p)=f(p-dd.sublist)+f(p-link)p-tag=1int count(NODE*p)/*求原子结点的个数函数 */int m,n;if(p=NUL

24、L)return(0);elseif(p-tag=0)n=1;else n=count(p-dd.sublist);if(p-link!=NULL)m=count(p-link);else m=0;return(n+m);原子结点数据域之和公式:(f(p)=0 p=NULLf(p)=p-data+f(p-link)p-tag=0f(p)=f(p-dd.sublist)+f(p-link)p-tag=1int sum(NODE*p)/*求原子结点数据域之和函数 */int m,n;if(p=NULL)return(0);elseif(p-tag=0)n=p-dd.data-0;else n=sum(p-dd.sublist);if(p-link!=NULL)m=sum(p-link);else m=0;return(n+m);