特殊矩阵广义表及其应用精品文稿.ppt

特殊矩阵广义表及其应用第1页，本讲稿共85页 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构6.1 数组与矩阵第2页，本讲稿共85页数组的定义：数组的定义：数组的定义：数组的定义：数组是满足下列条件的同类型数据元素数组是满足下列条件的同类型数据元素的集合：的集合：对于该集合中任一数据元素对于该集合中任一数据元素来说，来说，ji=0，bi-1，i=1，2，n，n0称为数组的维数，称为数组的维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维下标；维下标；数据元素之间的关系表示为数据元素之间的关系表示为Ri=|，0jkbk-1，1kn且且ki，0jibi-2，i=1，2，n，且，且R=R1，R2，.Rn；第3页，本讲稿共85页下面以二维数组为例解释上述关于数组的定义。下面以二维数组为例解释上述关于数组的定义。【例【例6.1】设有二维数组设有二维数组A，其第，其第1维的长度维的长度b1=3，第，第2维的长度维的长度b2=4；数据元素描述为，其中数据元素描述为，其中j1=0，b1-1=0，1，2，j2=0，b2-1=0，1，2，3；则该二维数组共有；则该二维数组共有12个具有相同数据类个具有相同数据类型的数据元素，分别为：型的数据元素，分别为：Amn=a11 a12a1na21a22a2nam1 am2 amn(1im,1jn)第4页，本讲稿共85页可以看出，二维数组每一行是一个一维数组，元素可以看出，二维数组每一行是一个一维数组，元素间存在序偶关系；每一列也是一个一维数组，元素间也间存在序偶关系；每一列也是一个一维数组，元素间也同样存在序偶关系。即：每个元素都受着两个关系的约同样存在序偶关系。即：每个元素都受着两个关系的约束：束：、。若把每一行看作是一个整体，则行与行之间是线性若把每一行看作是一个整体，则行与行之间是线性关系；若把每一列看作是一个整体，则列与列之间也是关系；若把每一列看作是一个整体，则列与列之间也是线性关系。线性关系。第5页，本讲稿共85页这样，我们可以把二维数组看成是一个线性表，它这样，我们可以把二维数组看成是一个线性表，它的每一个数据元素是一个一维数组，也是一个线性表。的每一个数据元素是一个一维数组，也是一个线性表。由此可以推广到由此可以推广到n维数组。我们说维数组。我们说n维数组是一个线性维数组是一个线性表，它的每一个数据元素是表，它的每一个数据元素是n-1维数组，也是一个线性维数组，也是一个线性表。表。数组一旦被定义，其维数及每维的长度数组一旦被定义，其维数及每维的长度(维界维界)就不就不再改变。因此，数组的运算除了初始化和销毁之外，只再改变。因此，数组的运算除了初始化和销毁之外，只有查找元素和修改元素值的操作。有查找元素和修改元素值的操作。第6页，本讲稿共85页矩阵的定义：矩阵的定义：矩阵的定义：矩阵的定义：矩阵是由矩阵是由mn个数排列成个数排列成m行行(横向横向)、n列列(纵向纵向)所所形成的矩形数表：形成的矩形数表：称为称为mn矩阵，简记为矩阵，简记为A=(aij)mn，其中，其中aij为为A的第的第i行第行第j列列的元素。的元素。第7页，本讲稿共85页矩阵与数组的关系矩阵与数组的关系矩阵与数组的关系矩阵与数组的关系：对照上述数组的定义，我们不难看出，矩阵中所有对照上述数组的定义，我们不难看出，矩阵中所有数据元素组成了一个二维数组，矩阵的每一行、每一数据元素组成了一个二维数组，矩阵的每一行、每一列的数据元素分别组成等长的一维数组。列的数据元素分别组成等长的一维数组。我们也可以说，矩阵是一个线性表，其每一个数据我们也可以说，矩阵是一个线性表，其每一个数据元素元素(行或列行或列)也是一个线性表。也是一个线性表。第8页，本讲稿共85页 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构6.1 数组与矩阵第9页，本讲稿共85页 由于数组一般不作插入和删除操作，因此采用顺序存储结构是理所当然的。问题是：以什么次序来存储各元素的值？问题是：以什么次序来存储各元素的值？下面以二维数组为例来说明：二维数组一般有两种方法来存储：1、按行优先顺序存储、按行优先顺序存储将数组元素按行向量排列，i+1行向量接在 i 行向量后面。第10页，本讲稿共85页a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放amn.am2am1.a2n.a22a21a1n.a12a1101n-1m*n-1n第11页，本讲稿共85页2、按列优先顺序存储、按列优先顺序存储 将数组元素按列向量排列，j+1列向量接在 j 列向量后面。第12页，本讲稿共85页按列序为主序存放按列序为主序存放01m-1m*n-1mamn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l第13页，本讲稿共85页二维数组中任一元素的地址二维数组中任一元素的地址二维数组中任一元素的地址二维数组中任一元素的地址按上述两种方式顺序存储的数组，只要知道按上述两种方式顺序存储的数组，只要知道开始开始开始开始结点的存放地址和每维的上下界（结点的存放地址和每维的上下界（结点的存放地址和每维的上下界（结点的存放地址和每维的上下界（mm、nn的值），以的值），以及及每个数组元素所占用的字节数每个数组元素所占用的字节数每个数组元素所占用的字节数每个数组元素所占用的字节数d d，就可求出各个数，就可求出各个数组元素的存储地址。组元素的存储地址。第14页，本讲稿共85页设设数组的首地址数组的首地址即：即：a11的地址的地址记为：记为：LOC(a11)则：二维数组按则：二维数组按“行优先顺序行优先顺序”存储，数组元素的存储存储，数组元素的存储地址为：地址为：LOC(a11)+前面前面i1行元素所占字节数行元素所占字节数+第第j行中前行中前j1个元素所占字节数个元素所占字节数即：即：LOC(aij)=LOC(a11)+(i-1)*n*d+(j-1)*d前面前面i1行元素的行元素的个数（每行个数（每行n个）个）每个元素所占每个元素所占的字节数的字节数第15页，本讲稿共85页【例【例【例【例2 2 2 2】已知二维数组】已知二维数组】已知二维数组】已知二维数组AmmAmmAmmAmm按行存储的元素地址公式是：按行存储的元素地址公式是：按行存储的元素地址公式是：按行存储的元素地址公式是：LocLoc(a(aij ij)=Loc(a)=Loc(a1111)+(i-1)*m+(j-1)*K)+(i-1)*m+(j-1)*K 按列存储的公式是？按列存储的公式是？按列存储的公式是？按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）【例【例1 1】一个二维数组一个二维数组A A，行下标的范围是，行下标的范围是1 1到到6 6，列下标的范围是，列下标的范围是0 0到到7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，存储器按字节编址。个字节存储，存储器按字节编址。那么，这个数组占用那么，这个数组占用 个字节。个字节。答：答：m*n*L=(6-1+1)*(7-0+1)*6=48*6=288第16页，本讲稿共85页 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第17页，本讲稿共85页在用高级语言编写程序时，通常在用高级语言编写程序时，通常用二维数组来存储用二维数组来存储用二维数组来存储用二维数组来存储矩阵矩阵矩阵矩阵。但对一些数据分布呈某种规律的矩阵，或是。但对一些数据分布呈某种规律的矩阵，或是0元元素大量存在素大量存在(远远多于非远远多于非0元素元素)的矩阵，采用上述存储的矩阵，采用上述存储方法会造成存储空间的极大浪费。方法会造成存储空间的极大浪费。第18页，本讲稿共85页 若矩阵中非若矩阵中非0 0元素呈某种规律分布，或存在大量元素呈某种规律分布，或存在大量0 0元元素，为节省存储空间，可对这类素，为节省存储空间，可对这类矩阵压缩存储矩阵压缩存储矩阵压缩存储矩阵压缩存储：即：即：为多个相同的非为多个相同的非为多个相同的非为多个相同的非0 0 0 0元素只分配一个存储空间，元素只分配一个存储空间，元素只分配一个存储空间，元素只分配一个存储空间，对对对对0 0 0 0元素不分配存储空间元素不分配存储空间元素不分配存储空间元素不分配存储空间。若值相同的非若值相同的非0 0元素或元素或0 0元素在矩阵中的分布有一元素在矩阵中的分布有一定的规律，我们称此矩阵为定的规律，我们称此矩阵为特殊矩阵特殊矩阵特殊矩阵特殊矩阵；反之，称为；反之，称为稀稀稀稀疏矩阵疏矩阵疏矩阵疏矩阵。第19页，本讲稿共85页特殊矩阵特殊矩阵特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。储。1 1 1 1、对称矩阵、对称矩阵、对称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：aij=aji0=i,j=0)(i=0)，元，元素总数为：素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在因此，我们可以按从上到下、从左到右将这些元素存放在一个向量一个向量san(n+1)/2中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中的元素，我中的元素，我们必须在们必须在aij和和sak之间找一个对应关系。之间找一个对应关系。a11 a12a1na21a22a2nan1an2ann第22页，本讲稿共85页若若i ij j，则，则aij在下三角形中。在下三角形中。aij之前的之前的i i行（从第行（从第0 0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，在第个元素，在第i i行上，行上，aij之前恰有之前恰有j个元素（即个元素（即ai0,ai1,ai2,aij-1），因此有：），因此有：k=i*(i+1)/2+j0kn(n+1)/2 若若ijij，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以只要交，所以只要交换上述对应关系式中的换上述对应关系式中的i和和j即可得到：即可得到：k=j*(j+1)/2+i0kn(n+1)/2 第23页，本讲稿共85页2 2 2 2、三角矩阵、三角矩阵、三角矩阵、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图上三角矩阵如图(a)所示，它的下三角（不包括主对角线）所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图上方均为常数，如图(b)所示。在大多数情况下，三角矩所示。在大多数情况下，三角矩阵常数为零。阵常数为零。a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c .c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 第24页，本讲稿共85页 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，其余可共享一个存储空间，其余的元素正好有的元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压缩存个，因此，三角矩阵可压缩存储到向量储到向量san(n+1)/2+1san(n+1)/2+1中，其中中，其中c c存放在向量的最存放在向量的最后一个分量中。后一个分量中。a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c .c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 第25页，本讲稿共85页 上三角矩阵上三角矩阵上三角矩阵上三角矩阵中，主对角线之上的中，主对角线之上的第第第第i i行行行行(0 0 inij第26页，本讲稿共85页 下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，sak和和aij对应对应关系是：关系是：i(i+1)/2+jijn(n+1)/2ij k=第27页，本讲稿共85页3 3 3 3、对角矩阵、对角矩阵、对角矩阵、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，下图给出了一个三对角矩阵，a00a01a10a11a12a21a22a23.an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1 第28页，本讲稿共85页三对角矩阵有如下特点：三对角矩阵有如下特点：当当时，时，aij非非0；其它情况时，其它情况时，aij的值为的值为0。第29页，本讲稿共85页我们以行序为主序进行存储三对角矩阵，并且只存储我们以行序为主序进行存储三对角矩阵，并且只存储矩阵中的非矩阵中的非0元素。元素。在在n阶三对角矩阵中，除了第一行和最后一行只有阶三对角矩阵中，除了第一行和最后一行只有2个个非非0元素外，其余各行均有元素外，其余各行均有3个非个非0元素，元素，共共2+2+3*(n-2)=3n-2个非个非0元素。元素。这样，可以将该三对角矩阵存储在一维数组这样，可以将该三对角矩阵存储在一维数组sa3n-2中。现在，对给定的非中。现在，对给定的非0元素元素aij，与其对应的数组元素的，与其对应的数组元素的下标是什么呢？下标是什么呢？第30页，本讲稿共85页由三对角矩阵的特点知，矩阵中的非由三对角矩阵的特点知，矩阵中的非0元素元素aij的前的前面有面有i行，共有行，共有3i-1个非个非0元素；在元素元素；在元素aij所在的第所在的第i行，行，aij之前有之前有j-i+1个非个非0元素。因此可得与非元素。因此可得与非0元素元素aij对应对应的数组元素的下标为：的数组元素的下标为：k=3i-1+j-i+1=2i+j 这样，非零元素这样，非零元素aij的地址为：的地址为：LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d第31页，本讲稿共85页 上述的各种特殊矩阵，其非零元素的分布都是有上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。随机存取。第32页，本讲稿共85页稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵 什么是稀疏矩阵？什么是稀疏矩阵？简单说，设矩阵简单说，设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩远远小于矩阵元素的总数（即阵元素的总数（即smnst 存放矩阵M的数组是 adatamaxsize am,n,tdata13-3161521122518 3 19342446-75314 第39页，本讲稿共85页 第一个数组元素（三元组）所在的行号、列号分别第一个数组元素（三元组）所在的行号、列号分别是：是：(adata0).i(adata0).j 它的值为：它的值为：(adata0).v 第40页，本讲稿共85页2 2、十字链表、十字链表、十字链表、十字链表若矩阵的非若矩阵的非0元素的个数和位置在操作过程中变化元素的个数和位置在操作过程中变化较大，则不宜采用顺序存储结构来表示三元组的线较大，则不宜采用顺序存储结构来表示三元组的线性表。性表。可采用链式存储结构来表示三元组的线性表。可采用链式存储结构来表示三元组的线性表。第41页，本讲稿共85页 在链表中，每个非在链表中，每个非0 0元素可用一个含有五个域的结元素可用一个含有五个域的结点表示：点表示：ijvcptrrptr其中：其中：其中：其中：i,j,v三个域分别表示该元素所在的行、列和非三个域分别表示该元素所在的行、列和非0元素的值。行指针域元素的值。行指针域rptr用以链接同一行中下一个非用以链接同一行中下一个非0元素；元素；列指针域列指针域cptr用以链接同一列中下一个非用以链接同一列中下一个非0元素。元素。第42页，本讲稿共85页 存储时，每个非存储时，每个非0 0元既是某个行链表中的一个结点，元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了一个十又是某个列链表中的一个结点；整个矩阵构成了一个十字交叉的链表字交叉的链表故称这样的存储结构为故称这样的存储结构为十字链表。十字链表。十字链表。十字链表。可用可用可用可用两个两个分别存储行链表和列链表的头指针的分别存储行链表和列链表的头指针的分别存储行链表和列链表的头指针的分别存储行链表和列链表的头指针的一维一维数组数组表示十字链表。表示十字链表。表示十字链表。表示十字链表。M-cheadM-rhead第43页，本讲稿共85页十字链表中非十字链表中非0元结点的类型说明如下：元结点的类型说明如下：typedefstructlnodeinti,j;datatypev;structlnode*cptr,*rptr;OLnode；ijvcptrrptr第44页，本讲稿共85页十字链表的类型描述如下：十字链表的类型描述如下：#defineN10/预设稀疏矩阵的行数预设稀疏矩阵的行数#defineK10/预设稀疏矩阵的列数预设稀疏矩阵的列数 typedefstructstructOLnode*cheadN,*rheadK;OLnode*cheadN,*rheadK;intm,n,t;intm,n,t;/*行数、列数、非行数、列数、非0元个数元个数*/Crosslist;Crosslist*M;第45页，本讲稿共85页 讨论：讨论：如何建立一个十字链表如何建立一个十字链表算法步骤：算法步骤：1、建立两个一维数组 Mchead、Mrhead分别存储列链表及行链表的头指针。初始时，Mcheadj=NULL,Mrheadj=NULL.2、读入非0元结点的三元组（i,j,v），生成一个结点*p,将其插入第 i 个行链表和第j个列链表的正确位置上。第46页，本讲稿共85页 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第47页，本讲稿共85页【例】【例】【例】【例】求稀疏矩阵求稀疏矩阵A A的转置矩阵的转置矩阵B B 一个一个mnmn的矩阵的矩阵A A，它的转置，它的转置B B是一个是一个nmnm的矩阵，的矩阵，且且aij=bjiaij=bji，0im0im，0jn0jn，即，即A A的行是的行是B B的的列，列，A A的列是的列是B B的行的行。0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 -7 0 0 0B=第48页，本讲稿共85页 将将A A转置为转置为B B，就是将，就是将A A的三元组表的三元组表a-dataa-data置换为表置换为表B B的三元组表的三元组表b-datab-data。有有：at=bt;am=bn;an=bm;但但:(adatax).i(bdatax).j为什么？第49页，本讲稿共85页也不能将也不能将(adatax).i与与(adatax).j简单互简单互换！换！为什么？答：答：答：答：如果只是简单地交换如果只是简单地交换a-dataa-data中中i i和和j j的内容，那的内容，那么得到的么得到的b-datab-data将是一个按列优先顺序存储的稀疏矩将是一个按列优先顺序存储的稀疏矩阵阵B B，要得到按行优先顺序存储的，要得到按行优先顺序存储的b-datab-data，就必须重新，就必须重新排列三元组的顺序。排列三元组的顺序。由于由于由于由于A A A A的列是的列是的列是的列是B B B B的行，因此按的行，因此按的行，因此按的行，因此按a-dataa-dataa-dataa-data的列序转置，的列序转置，的列序转置，的列序转置，所得到的转置矩阵所得到的转置矩阵所得到的转置矩阵所得到的转置矩阵B B B B的三元组表的三元组表的三元组表的三元组表b-datab-datab-datab-data必定是按行优先必定是按行优先必定是按行优先必定是按行优先存放的。存放的。存放的。存放的。第50页，本讲稿共85页0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 -7 0 0 0B=行号行号i列号列号j值值v行号行号i列号列号j值值v13-31615211225183 19342446-7531412121 3931-3351443245218611564-7第51页，本讲稿共85页算法步骤如下：算法步骤如下：(1)产生顺序表b，存放转置后的矩阵BSpmatrix*b;b=malloc(sizeof(Spmatrix);并并确定其结点个数、行数、列数。即：bt=at;bm=an;bn=am;第52页，本讲稿共85页(2)一维数组一维数组bdata结点个数结点个数中各数组元素赋值，且中各数组元素赋值，且bdata按行优先。按行优先。具体做法如下：具体做法如下：对三元组表对三元组表adata扫描扫描(从第一行开始从第一行开始)令：令：x为数组为数组adata中数组元素的下标中数组元素的下标y为数组为数组bdata中数组元素的下标中数组元素的下标第53页，本讲稿共85页扫描过程：扫描过程：首先，令首先，令y=0;for(x=0;x datax).j=1(1是列号是列号)若为1 则 (bdatay).v=(adatax).v (bdatay).i=(adatax).j(bdatay).j=(adatax).iy+该轮该轮该轮该轮forfor循环结束后，矩阵循环结束后，矩阵循环结束后，矩阵循环结束后，矩阵N N中第一行（即矩阵中第一行（即矩阵中第一行（即矩阵中第一行（即矩阵MM中中中中第一列）的元素的三元组已存放在三元组表（数组）第一列）的元素的三元组已存放在三元组表（数组）第一列）的元素的三元组已存放在三元组表（数组）第一列）的元素的三元组已存放在三元组表（数组）b bdatadata中了。中了。中了。中了。第54页，本讲稿共85页下面再次扫描三元组表（数组）下面再次扫描三元组表（数组）adata，查，查寻矩阵寻矩阵M中第二列的元素：中第二列的元素：此时，此时，y y值为上轮值为上轮值为上轮值为上轮forfor循环后的结果循环后的结果循环后的结果循环后的结果；for(x=0;xdatax).j=2(2是列号是列号)若为若为2则则(bdatay).v=(adatax).v(bdatay).i=(adatax).j(bdatay).j=(adatax).iy+第55页，本讲稿共85页这样，整个扫描的过程可描述为：y=0;y=0;for(z z=1;z z=矩阵矩阵矩阵矩阵M M M M的列数的列数的列数的列数；z z+)for(x=0;xdatax).j=z z)(bdatay).v=(adatax).v;(bdatay).i=(adatax).j;(bdatay).j=(adatax).i;y+;第56页，本讲稿共85页算法分析：算法分析：该算法的时间主要耗费在 z 和 x 的二重循环上，若矩阵M的列数为 n，非0元素个数为 t，则 算法的时间复杂度数量级为算法的时间复杂度数量级为:O(n*t)第57页，本讲稿共85页 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第58页，本讲稿共85页6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第59页，本讲稿共85页广义表的概念广义表的概念广义表的概念广义表的概念广广义义表表是是n(n0)个个元元素素的的有有限限序序列列,记记作作A=(a1,a2,an)其其中中,A是是广广义义表表的的名名称称,n是是它它的的长长度度,ai(1in)或者是数据元素或者是数据元素,或者是广义表。或者是广义表。习习惯惯上上：用用英英文文大大写写字字母母表表示示广广义义表表的的名名称称,小小写写字字母表示数据元素。母表示数据元素。第60页，本讲稿共85页对于广义表对于广义表A中的某个元素中的某个元素ai：若它是一个数：若它是一个数据元素时据元素时,称其为称其为A的一个原子的一个原子;当其不是一个数据当其不是一个数据元素时元素时,则称它为广义表则称它为广义表A的子表。的子表。当广义表当广义表A非空时非空时,称第一个元素称第一个元素a1为为A的表头的表头(head),称其余元素组成的表称其余元素组成的表(a2,an)为为A的表的表尾尾(tail)。广义表举例如下广义表举例如下:A=()A是一个空表是一个空表,其长度为零。其长度为零。B=(e)广义表广义表B只有一个原子只有一个原子e,B的长度为的长度为1。第61页，本讲稿共85页C=(a,(b,c,d),广广义义表表C的的长长度度为为2,两两个个元元素素分分别别为原子为原子a和子表和子表(b,c,d)D=(A,B,C),广广义义表表D的的长长度度为为3,3个个元元素素都都是是广广义表。义表。E=(a,E),这这是是一一个个递递归归的的表表,其其长长度度为为2,E表表相相当当于一个无穷表。于一个无穷表。从以上例子可以看出：从以上例子可以看出：广义表可以共享子表广义表可以共享子表,且允许递归。且允许递归。广广义义表表的的元元素素之之间间除除了了存存在在次次序序关关系系外外,还还存存在在层层次关系。次关系。第62页，本讲稿共85页广广义义表表中中元元素素的的最最大大层层次次为为表表的的深深度度。元元素素的的层层次次就是包含该元素的括号对的数目。就是包含该元素的括号对的数目。例如例如:F=(a,b,(c,(d)其其中中,数数据据元元素素a,b在在第第一一层层,数数据据元元素素c在在第第二二层层,数据元素数据元素d在第三层。广义表在第三层。广义表F的深度为的深度为3。任任何何一一个个非非空空广广义义表表，其其表表头头可可能能是是原原子子,也也可可能能是是广义表广义表,而其表尾必定为广义表。而其表尾必定为广义表。第63页，本讲稿共85页例如例如:若若C=(a,(b,c,d)D=(A,B,C)则：Head(D)=A Tail(D)=(B,C)Head(C)=a Tail(C)=(b,c,d)以上是广义表的两个操作以上是广义表的两个操作：取表头 Head、取表尾Tail 这些操作还可以嵌套调用：这些操作还可以嵌套调用：Head（Tail(D)）Head(B,C)=B取广义表取广义表D D的第二个元的第二个元素素第64页，本讲稿共85页注意：注意：广义表广义表（）（）和广义表和广义表()不同。不同。（）（）为空表，长度为空表，长度n0，不能分解成表头和表尾。，不能分解成表头和表尾。()不是空表，其长度不是空表，其长度n=1，可以分解得到表头，可以分解得到表头是空表是空表(),表尾是空表表尾是空表().第65页，本讲稿共85页 6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第66页，本讲稿共85页由由于于广广义义表表（a1,a2,an)中中的的数数据据元元素素可可以以具具有有不不同同的的结结构构(或或是是原原子子,或或是是列列表表）,因因此此难难以以用用顺顺序序存存储储结结构构表表示示,通通常常采采用用链链式式存存储储结结构构,每每个个数数据据元元素素可可用一个结点表示。用一个结点表示。如如何何设设定定结结点点的的结结构构？由由于于列列表表中中的的数数据据元元素素可可能能为原子或列表为原子或列表,由此需要两种结构的结点由此需要两种结构的结点:一一种种是是表表结结点点,用用以以表表示示列列表表;一一种种是是原原子子结结点点,用用以表示原子。以表示原子。第67页，本讲稿共85页按按前前述述分分析析：若若若若列列列列表表表表不不不不空空空空,则则则则可可可可分分分分解解解解成成成成表表表表头头头头和和和和表表表表尾尾尾尾;反之反之反之反之,一对确定的表头和表尾可唯一确定列表。一对确定的表头和表尾可唯一确定列表。一对确定的表头和表尾可唯一确定列表。一对确定的表头和表尾可唯一确定列表。由由此此,一一个个表表表表结结结结点点点点可可由由3个个域域组组成成:标标标标志志志志域域域域、指指指指示示示示表表表表头头头头的的的的指指指指针针针针域域域域和和和和指指指指示示示示表表表表尾尾尾尾的的的的指指指指针针针针域域域域;而而原原原原子子子子结结结结点点点点只只需需两两个个域域:标志域和值域标志域和值域标志域和值域标志域和值域：原子结点原子结点atomtag=0tag=1hptp表结点表结点第68页，本讲稿共85页原子结点原子结点atomtag=0类型说明如下：类型说明如下：typedef enumATOM,LISTElemTag;/*ATOM=0：原子,LIST=1:子表*/tag=1hptp表结点表结点枚举类型枚举类型第69页，本讲稿共85页typedef structGLNodeElemTagtag;unionAtomTypeatom;structstructGLNode*hp,*tp;ptr;Glist;公共部分公共部分,用于区分用于区分原子结点和表结点原子结点和表结点原子结点和原子结点和表结点的联表结点的联合部分合部分ptr.hp和和ptr.pt分别指分别指向表头和表尾向表头和表尾广义表类型广义表类型第70页，本讲稿共85页 A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)Glist*A;A=NULL10eBCDE110a1110b0c0d111110a第71页，本讲稿共85页在这种存储结构中有几种情况：在这种存储结构中有几种情况：除空表的表头指针为空外，对任何非空广义表，除空表的表头指针为空外，对任何非空广义表，其表头指针均指向一个表结点，且该结点中的其表头指针均指向一个表结点，且该结点中的hphphphp域指域指域指域指示广义表表头示广义表表头示广义表表头示广义表表头（或为原子结点，或为表结点），（或为原子结点，或为表结点），tptptptp域域域域指向广义表表尾指向广义表表尾指向广义表表尾指向广义表表尾（除非表尾为空，则指针为空，否则（除非表尾为空，则指针为空，否则必为表结点）；必为表结点）；第72页，本讲稿共85页容易分清广义表中原子和子表所在层次。容易分清广义表中原子和子表所在层次。容易分清广义表中原子和子表所在层次。容易分清广义表中原子和子表所在层次。如在广如在广义表义表D中，原子中，原子a和和e在同一层次上，而在同一层次上，而b、c和和d在同一在同一层次且比层次且比a和和e低一层，低一层，B和和C是同一层的子表；是同一层的子表；最高层的表结点个数即为广义表的长度。最高层的表结点个数即为广义表的长度。最高层的表结点个数即为广义表的长度。最高层的表结点个数即为广义表的长度。第73页，本讲稿共85页 6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第74页，本讲稿共85页mm元多项式的表示元多项式的表示元多项式的表示元多项式的表示一个一个m元多项式的每一项最多有元多项式的每一项最多有m个变元，如果用个变元，如果用单链表表示，则每个节点应该包括单链表表示，则每个节点应该包括m个指数项和一个数个指数项和一个数据项；如果多项式各项的变元数不相同，将势必造成存据项；如果多项式各项的变元数不相同，将势必造成存储空间的浪费。为此，我们考虑采用其它的方式来存储储空间的浪费。为此，我们考虑采用其它的方式来存储一个一个m元多项式。元多项式。我们以三元多项式：我们以三元多项式：P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15为例，讨论其存储表示。为例，讨论其存储表示。第75页，本讲稿共85页P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15该多项式中各项的变元数目不尽相同，某些因子多该多项式中各项的变元数目不尽相同，某些因子多次出现，我们可以将其改写为：次出现，我们可以将其改写为：P(x,y,z)=(x10+2x6)y3+3x5y2)z2+(x4+6x3)y4+2y)z+15此时，该多项式就变成了变元此时，该多项式就变成了变元z的多项式，的多项式，即即Az2+Bz1+15z0，对这个一元多项式我们用单链表，对这个一元多项式我们用单链表表示为：表示为：第76页，本讲稿共85页变元变元z的多项式的多项式Az2+Bz1+15z0中的中的A、B又是一个又是一个多项式。多项式。其中，其中，A=(x10+2x6)y3+3x5y2=Cy3+Dy2，用单，用单链表表示为：链表表示为：而而C=x10+2x6，D=3x5，它们的单链表表示如下：，它们的单链表表示如下：第77页，本讲稿共85页对于多项式对于多项式B，B=(x4+6x3)y4+2y=Ey4+Fy，且，且E=x4+6x3，F=2，用单链表分别表示为：，用单链表分别表示为：第78页，本讲稿共85页通过这样的分解，一个通过这样的分解，一个m元多项式就被分解成若干元多项式就被分解成若干个一元多项式。在这些一元多项式的单链表表示中，个一元多项式。在这些一元多项式的单链表表示中，有的链表节点的系数域中是系数有的链表节点的系数域中是系数(如链表如链表C、D、E、F)，而有的链表节点的系数域中却是另一个多项式，而有的链表节点的系数域中却是另一个多项式(如链如链表表P、A、B)。第79页，本讲稿共85页我们不妨这样认为：多项式我们不妨这样认为：多项式P是一个广义表，表示为：是一个广义表，表示为：P=(A，B，15)其中，其中，A和和B也是一个广义表：也是一个广义表：A=(C，D)B=(E，F)而而C、D、E、F也是广义表：也是广义表：C=(1，10)D=(3)E=(1，6)F=(2)至此，各广义表中的元素均为原子。至此，各广义表中的元素均为原子。第80页，本讲稿共85页既然一个既然一个m元多项式可以描述为一个广义表，那我元多项式可以描述为一个广义表，那我们就可以用广义表的存储结构来存储一个们就可以用广义表的存储结构来存储一个m元多项式。元多项式。这里，我们用类似于广义表的双链存储法来存储该多这里，我们用类似于广义表的双链存储法来存储该多项式。其中，链表的节点结构定义为：项式。其中，链表的节点结构定义为：其中，其中，exp为指数域，为指数域，coef为系数域，为系数域，hp指向其子表，指向其子表，tp指向后继节点。指向后继节点。第81页，本讲稿共85页按照