数组和广义表1数组的定义课件

第第5章章 数组和广义表数组和广义表5 51 1数组的定义数组的定义 二维数组：二维数组：我们可以把二维数组看成是这样一个定长线性表：我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如。图它的每个数据元素也是一个定长线性表。例如。图51 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。毁之外，数组只有存取元素和修改元素值的操作。第5章 数组和广义表二维数组：数组一旦被定义，它的维数和152数组的顺序表示和实现数组的顺序表示和实现一采用顺序存储结构：一采用顺序存储结构：一般不作插入或删除操作一般不作插入或删除操作,因此，采用顺序存储结构因此，采用顺序存储结构二存储顺序：二存储顺序：存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据元素就有次序约定问题。数组的数据元素就有次序约定问题。对二维数组可有两种存储方式：对二维数组可有两种存储方式：1以列序为主序以列序为主序(co1umn major order)的存储方式，的存储方式，如图如图52(a)所示所示2以行序为主序以行序为主序(row major order)的存储方式，的存储方式，如图如图52(b)所示。所示。52数组的顺序表示和实现一采用顺序存储结构：2数组和广义表1数组的定义课件3三元素存储位置计算：三元素存储位置计算：以行序为主序的二维数组存储结构为例以行序为主序的二维数组存储结构为例:二维数组二维数组A中任一元素中任一元素aij的存储位置可由下式确定的存储位置可由下式确定 LOC(i,j)LOC(0,0)十十(b2i十十j)L (5-1)式中：式中：b2是数组的第二维长度，即列数；是数组的第二维长度，即列数；L是每个数据元素占的存储单元个数；是每个数据元素占的存储单元个数；LOC(i,j)是是aij的存储位置；的存储位置；LOC(0,0)是是a00的存储位置，即二维数组的存储位置，即二维数组A的基地址的基地址或基址。或基址。由于计算各个元素存储位置的时间相等，所以存取由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。的存储结构为随机存储结构。三元素存储位置计算：453矩阵的压缩存储矩阵的压缩存储压缩存储是指：压缩存储是指：为多个值相同的元只分配一个存储空间；为多个值相同的元只分配一个存储空间；对零元不分配空间。对零元不分配空间。531 特殊矩阵：特殊矩阵：一对称矩阵：一对称矩阵：1特点：特点：aij=aji 1i,jn2存储：可压缩存储，不失一般性，以行主序存储下存储：可压缩存储，不失一般性，以行主序存储下 三角中的元（包括对角线上的元）。三角中的元（包括对角线上的元）。53矩阵的压缩存储53映像关系：映像关系：以数组以数组san(n+1)/2存储存储n阶对称矩阵阶对称矩阵A，称称san(n+1)/2为为n阶对称矩阵阶对称矩阵A的压缩存储。（图的压缩存储。（图5.3）则则sak和矩阵元和矩阵元aij间关系：间关系：3映像关系：称san(n+1)/2为n阶对称矩阵A的压6二三角矩阵：二三角矩阵：1特点：下特点：下(上上)三角矩阵指矩阵的上三角矩阵指矩阵的上(下下)三角三角(不包括不包括 对角线对角线)中的元均为常数中的元均为常数c或零的或零的n阶矩阵。阶矩阵。2存储：存储其下存储：存储其下(上上)三角中的元和常数三角中的元和常数c。3映像关系：映像关系：以数组以数组san(n+1)/2存储，存储，sa0可用来存储常数可用来存储常数c二三角矩阵：7三对角矩阵：三对角矩阵：1特点：特点：所有的非零元都集中在以主对角线为中心的带状区域中。所有的非零元都集中在以主对角线为中心的带状区域中。如图如图54所示。所示。2存储：亦可按某个原则存储：亦可按某个原则(或以行为主，或以对角线的顺或以行为主，或以对角线的顺序序)将其压缩存储到一维数组上。将其压缩存储到一维数组上。三对角矩阵：8532 稀疏矩阵：稀疏矩阵：一什么是稀疏矩阵：一什么是稀疏矩阵：二抽象数据类型稀疏矩阵的定义：（二抽象数据类型稀疏矩阵的定义：（P96）三稀疏矩阵压缩存储：只存非零元。以图三稀疏矩阵压缩存储：只存非零元。以图5.5矩阵为例矩阵为例532 稀疏矩阵：91三元组顺序表：三元组顺序表：#define MAXSIZE 12500 /稀疏矩阵中非稀疏矩阵中非0元素的最大数目元素的最大数目typedef struct int i,j;/非非0元素的行号、列号元素的行号、列号ElemType e;/非非0元素的值元素的值Triple;/三元组数据类型名三元组数据类型名typedef struct int mu，nu，tu;/稀疏矩阵的行数、列数、非稀疏矩阵的行数、列数、非0元素的数目元素的数目Triple dataMAXSIZE+1;/三元组数组，三元组数组，data0未用未用 TSMatrix;/三元组顺序表数据类型名三元组顺序表数据类型名1三元组顺序表：10矩阵转置运算：矩阵转置运算：(1)将矩阵的行列值相互交换；将矩阵的行列值相互交换；(2)将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；(3)重排三元组之间的次序。重排三元组之间的次序。实现第三条有两种处理方法：实现第三条有两种处理方法：(1)(1)按照按照b.data中三元组的次序依次在中三元组的次序依次在a.data中找到相应中找到相应的三元组进行转置。的三元组进行转置。矩阵转置运算：111 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 141 2 121 12算法算法5.1:Status TransposeSMatrix(TSMatrix M,TSMatrix&T)/M为原三元组顺序表，行优先顺序为原三元组顺序表，行优先顺序T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(!M.tu)return FALSE;/三元组空三元组空 q=1;for(col=1;col=M.nu;col+)for(p=1;k=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;算法5.1:13这个算法主要的工作是在这个算法主要的工作是在p和和col的两重循环中完成的，的两重循环中完成的，故算法的时间复杂度为故算法的时间复杂度为O(nutu)，即和，即和M的列数和非的列数和非零元的个数的乘积成正比。一般矩阵的转置算法为零元的个数的乘积成正比。一般矩阵的转置算法为 for(col1;col=nu;+col for(row1;row=mu;+row Tcol rowMrowcol;其时间复杂度为其时间复杂度为O(munu)。当非零元的个数。当非零元的个数tu和和munu同数量级时，算法同数量级时，算法51的时间复杂度就为的时间复杂度就为O(munu2)了了(例如，假设在例如，假设在100500的矩阵中有的矩阵中有tu10000个非零元个非零元)，虽然节省了存储空间，但时间复杂，虽然节省了存储空间，但时间复杂度提高了，因此算法度提高了，因此算法51仅适于仅适于tumunu的情况。的情况。这个算法主要的工作是在p和col的两重循环中完成的，故算法的14(2)快速转置：快速转置：需两个向量需两个向量:num和和cpotnumcol表示矩阵表示矩阵M中第中第col列中非零元的个数，列中非零元的个数，cpotcol指示指示M中第中第col列的第一个非零元在列的第一个非零元在b.data中的恰中的恰当位置。则有当位置。则有cpot1=1;cpotcol=cpotcol-1+numcol-1 2cola.nu例如，对图例如，对图5.5的矩阵的矩阵M，num和和cpot的值如表的值如表5.1所示所示（下页图）（下页图）(2)快速转置：15123456781 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14000000011112221135788946297538123456781 3 -316算法算法5.2：Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(!M.tu)return FALSE;/三元组空三元组空 for(col=1;col=M.nu;col+)numcol=0;for(t=1;t=M.tu;t+)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;col+)cpotcol=cpotcol-1+numcol-1;for(p=1;ki=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else for(q=M.rheadi;(q-right)&q-right-jright);p-right=q-right;q-right=p;for(scanf(&i,&j,&e);i!=0;scan22if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;else for(q=M.cheadj;(q-down)&q-down-idown);p-down=q-down;q-down=p;return OK;/CreateSMatrix_OLif(M.cheadj=NULL|M.cheadj232)将矩阵将矩阵B加到矩阵加到矩阵A上上:十字链表表示稀疏矩阵十字链表表示稀疏矩阵假假设设两两个个矩矩阵阵相相加加后后的的结结果果为为A，则则和和矩矩阵阵A 中中的的非非零元零元“aij可能有以下情况：可能有以下情况：1aij=aij+bij 改变结点的改变结点的e 域值域值2aij=aij (bij=0)结点不变结点不变3aij=bij (aij=0)增加结点增加结点4aij=0 (aij=-bij)删除结点删除结点2)将矩阵B加到矩阵A上:245.4 广义表的定义广义表的定义广义表是线性表的推广。广义表是线性表的推广。一抽象数据类型广义表定义：一抽象数据类型广义表定义：(P107)二术语：二术语：广义表记作广义表记作 LS=(a1,a2,an)LS是广义表的名称，是广义表的名称，n是其长度。是其长度。ai可可以以是是单单个个元元素素（原原子子），也也可可以以是是广广义义表表（子子表表）。习习惯惯上上用用大大写写字字母母表表示示广广义义表表的的名名称称，用用小小写写字字母母表表示示原子。原子。广广义义表表非非空空时时，称称第第一一个个元元素素a1为为其其表表头头，称称其其余余元元素素组成的组成的表表（a2,an）为其）为其表尾表尾。5.4 广义表的定义25例：例：(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)E(a，E)这是一个递归的表，它的长度为这是一个递归的表，它的长度为2。E相当于一个无限的列表相当于一个无限的列表E(a，(a，(a，)。例：26三三个重要结论：三三个重要结论：(1)列列表表的的元元素素可可以以是是子子表表，而而子子表表的的元元素素还还可可以以是是子子表表，。(2)列表可为其它列表所共享。列表可为其它列表所共享。(3)列列表表可可以以是是一一个个递递归归的的表表，即即列列表表也也可可以以是是其其本本身身的的一个子表。一个子表。根据前述对表头、表尾的定义可知：根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表，任何一个非空列表其表头可能是原子，也可能是列表，而其而其表尾必定为列表表尾必定为列表。三三个重要结论：27A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)例如：例如：GetHead(B)=e GetTail(B)()GetHead(D)A GetTail(D)(B，C)由于由于(B，C)为非空列表，则可继续分解得到：为非空列表，则可继续分解得到：GetHead(B,C)B GetTail(B,C)(C)列表列表()和和()不同。前者为空表、长度不同。前者为空表、长度n0；后者长度后者长度n1，可分解得到其表头、表尾均为空表，可分解得到其表头、表尾均为空表()。A()285.5 广义表的存储结构广义表的存储结构由由于于广广义义表表中中的的数数据据元元素素可可以以具具有有不不同同的的结结构构，(或或是是原原子子，或或是是列列表表)，因因此此难难以以用用顺顺序序存存储储结结构构表表示示，通通常采用链式存储结构，每个数据元素可用一个结点表示。常采用链式存储结构，每个数据元素可用一个结点表示。一一.广义表的头尾链表存储广义表的头尾链表存储 1设定结点的结构：设定结点的结构：由由于于列列表表中中的的数数据据元元素素可可能能为为原原子子或或列列表表，由由此此需需要要两两种结构的结点：种结构的结点：一种是表结点，用以表示列表；一种是表结点，用以表示列表；一种是原子结点，用以表示原子。一种是原子结点，用以表示原子。5.5 广义表的存储结构29若列表不空，则可分解成表头和表尾；若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成；一个表结点可由三个域组成；标志域、标志域、指示表头的指针域指示表头的指针域 指示表尾的指针域；指示表尾的指针域；而原子结点只需两个域；而原子结点只需两个域；标志域标志域 值域值域(如图如图58所示所示)。若列表不空，则可分解成表头和表尾；302.举例：举例：A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)2.举例：313广义表的头尾链表存储结构的特点：广义表的头尾链表存储结构的特点：在上述广义表的头尾链表存储结构中有几种情况：在上述广义表的头尾链表存储结构中有几种情况：(1)除除空空表表的的表表头头指指针针为为空空外外，对对任任何何非非空空列列表表，其其表表头头指指针针均均指指向向一一个个表表结结点点，且且该该结结点点中中的的hp域域指指示示列列表表表表头头(或或为为原原子子结结点点，或或为为表表结结点点)，tp域域指指向向列列表表表表尾尾(除非表尾为空，则指针为空，否则必为表结点除非表尾为空，则指针为空，否则必为表结点)；(2)容易分清列表中原子和子表所在层次。容易分清列表中原子和子表所在层次。(3)最高层的表结点个数即为列表的长度。最高层的表结点个数即为列表的长度。这三个特点在某种程度上给列表的操作带来方便。这三个特点在某种程度上给列表的操作带来方便。也可采用另一种结点结构的链表表示列表也可采用另一种结点结构的链表表示列表 3广义表的头尾链表存储结构的特点：32二广义表的扩展线性链表存储：二广义表的扩展线性链表存储：1形式定义说明：形式定义说明：typedef enumATOM,LIST ElemTag;typedef struct GLNodeElemTag tag;union ElemTag atom;struct GLNode *hp;struct GLNode *tp;*GList;二广义表的扩展线性链表存储：332.举例：举例：A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)2.举例：A()B(e)34