1、第第5章章 数组和广义表数组和广义表5 51 1数组的定义数组的定义 二维数组：二维数组：我们可以把二维数组看成是这样一个定长线性表：我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如。图它的每个数据元素也是一个定长线性表。例如。图51 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。毁之外，数组只有存取元素和修改元素值的操作。52数组的顺序表示和实现数组的顺序表示和实现一采用顺序存储结构：一采用顺序存储结构：一般不作插入或删除操
2、作一般不作插入或删除操作,因此，采用顺序存储结构因此，采用顺序存储结构二存储顺序：二存储顺序：存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据元素就有次序约定问题。数组的数据元素就有次序约定问题。对二维数组可有两种存储方式：对二维数组可有两种存储方式：1以列序为主序以列序为主序(co1umn major order)的存储方式，的存储方式，如图如图52(a)所示所示2以行序为主序以行序为主序(row major order)的存储方式，的存储方式，如图如图52(b)所示。所示。三元素存储位置计算：三元素存
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的基地址的基地址或基址。或基址。由于计算各个元素存储位置的时间相等，所以存取由于计算各个元素存储位置的
4、时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。的存储结构为随机存储结构。53矩阵的压缩存储矩阵的压缩存储压缩存储是指：压缩存储是指：为多个值相同的元只分配一个存储空间；为多个值相同的元只分配一个存储空间；对零元不分配空间。对零元不分配空间。531 特殊矩阵：特殊矩阵：一对称矩阵：一对称矩阵：1特点：特点：aij=aji 1i,jn2存储：可压缩存储，不失一般性，以行主序存储下存储：可压缩存储，不失一般性，以行主序存储下 三角中的元（包括对角线上的元）。三角中的元（包括对角线上的元）。3映像关系：映像关系：
5、以数组以数组san(n+1)/2存储存储n阶对称矩阵阶对称矩阵A，)35(12)1(12)1(jiijjjijiik当当称称san(n+1)/2为为n阶对称矩阵阶对称矩阵A的压缩存储。（图的压缩存储。（图5.3）则则sak和矩阵元和矩阵元aij间关系：间关系：二三角矩阵：二三角矩阵：1特点：下特点：下(上上)三角矩阵指矩阵的上三角矩阵指矩阵的上(下下)三角三角(不包括不包括 对角线对角线)中的元均为常数中的元均为常数c或零的或零的n阶矩阵。阶矩阵。2存储：存储其下存储：存储其下(上上)三角中的元和常数三角中的元和常数c。3映像关系：映像关系：以数组以数组san(n+1)/2存储，存储，sa0可
6、用来存储常数可用来存储常数cjijijiik当当下三角行主序：02)1(jiijjjik当当上三角列主序：2)1(0三对角矩阵：三对角矩阵：1特点：特点：所有的非零元都集中在以主对角线为中心的带状区域中。所有的非零元都集中在以主对角线为中心的带状区域中。如图如图54所示。所示。2存储：亦可按某个原则存储：亦可按某个原则(或以行为主，或以对角线的顺或以行为主，或以对角线的顺序序)将其压缩存储到一维数组上。将其压缩存储到一维数组上。532 稀疏矩阵：稀疏矩阵：一什么是稀疏矩阵：一什么是稀疏矩阵：二抽象数据类型稀疏矩阵的定义：（二抽象数据类型稀疏矩阵的定义：（P96）三稀疏矩阵压缩存储：只存非零元。
7、以图三稀疏矩阵压缩存储：只存非零元。以图5.5矩阵为例矩阵为例1三元组顺序表：三元组顺序表：#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未用未用 TSMatr
8、ix;/三元组顺序表数据类型名三元组顺序表数据类型名矩阵转置运算：矩阵转置运算：(1)将矩阵的行列值相互交换；将矩阵的行列值相互交换；(2)将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；(3)重排三元组之间的次序。重排三元组之间的次序。实现第三条有两种处理方法：实现第三条有两种处理方法：(1)(1)按照按照b.data中三元组的次序依次在中三元组的次序依次在a.data中找到相应中找到相应的三元组进行转置。的三元组进行转置。1 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
9、 244 6 -76 3 14算法算法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;这个算
10、法主要的工作是在这个算法主要的工作是在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
11、的矩阵中有的矩阵中有tu10000个非零元个非零元)，虽然节省了存储空间，但时间复杂，虽然节省了存储空间，但时间复杂度提高了，因此算法度提高了，因此算法51仅适于仅适于tumunu的情况。的情况。(2)快速转置：快速转置：需两个向量需两个向量:num和和cpotnumcol表示矩阵表示矩阵M中第中第col列中非零元的个数，列中非零元的个数，cpotcol指示指示M中第中第col列的第一个非零元在列的第一个非零元在b.data中的恰中的恰当位置。则有当位置。则有cpot1=1;cpotcol=cpotcol-1+numcol-1 2cola.nu例如，对图例如，对图5.5的矩阵的矩阵M，num和
12、和cpot的值如表的值如表5.1所示所示（下页图）（下页图）123456781 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14000000011112221135788946297538算法算法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;
13、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;if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;else for(q=M.cheadj;(q-down)&q-
14、down-idown);p-down=q-down;q-down=p;return OK;/CreateSMatrix_OL2)将矩阵将矩阵B加到矩阵加到矩阵A上上:十字链表表示稀疏矩阵十字链表表示稀疏矩阵假设两个矩阵相加后的结果为假设两个矩阵相加后的结果为A，则和矩阵，则和矩阵A 中的非中的非零元零元“aij可能有以下情况：可能有以下情况：1aij=aij+bij 改变结点的改变结点的e 域值域值2aij=aij (bij=0)结点不变结点不变3aij=bij (aij=0)增加结点增加结点4aij=0 (aij=-bij)删除结点删除结点5.4 广义表的定义广义表的定义广义表是线性表的推广
15、。广义表是线性表的推广。一抽象数据类型广义表定义：一抽象数据类型广义表定义：(P107)二术语：二术语：广义表记作广义表记作 LS=(a1,a2,an)LS是广义表的名称，是广义表的名称，n是其长度。是其长度。ai可以是单个元素（可以是单个元素（原子原子），也可以是广义表（），也可以是广义表（子表子表）。）。习惯上用大写字母表示广义表的名称，用小写字母表示习惯上用大写字母表示广义表的名称，用小写字母表示原子。原子。广义表非空时，称广义表非空时，称第一个元素第一个元素a1为其为其表头表头，称，称其余元素其余元素组成的组成的表表（a2,an）为其）为其表尾表尾。例：例：(1)A()A是一个空表，它
16、的长度为零。是一个空表，它的长度为零。(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，)。三三个重要结论：三三个重要结
17、论：(1)列表的元素可以是子表，而子表的元素还可以是子列表的元素可以是子表，而子表的元素还可以是子表，表，。(2)列表可为其它列表所共享。列表可为其它列表所共享。(3)列表可以是一个递归的表，即列表也可以是其本身的列表可以是一个递归的表，即列表也可以是其本身的一个子表。一个子表。根据前述对表头、表尾的定义可知：根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表，任何一个非空列表其表头可能是原子，也可能是列表，而其而其表尾必定为列表表尾必定为列表。A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)例如：例如：GetHead(B)=e GetTail(B)
18、()GetHead(D)A GetTail(D)(B，C)由于由于(B，C)为非空列表，则可继续分解得到：为非空列表，则可继续分解得到：GetHead(B,C)B GetTail(B,C)(C)列表列表()和和()不同。前者为空表、长度不同。前者为空表、长度n0；后者长度后者长度n1，可分解得到其表头、表尾均为空表，可分解得到其表头、表尾均为空表()。5.5 广义表的存储结构广义表的存储结构由于广义表中的数据元素可以具有不同的结构，由于广义表中的数据元素可以具有不同的结构，(或是或是原子，或是列表原子，或是列表)，因此难以用顺序存储结构表示，通，因此难以用顺序存储结构表示，通常采用链式存储结构
19、，每个数据元素可用一个结点表示。常采用链式存储结构，每个数据元素可用一个结点表示。一一.广义表的头尾链表存储广义表的头尾链表存储 1设定结点的结构：设定结点的结构：由于列表中的数据元素可能为原子或列表，由此需要两由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：种结构的结点：一种是表结点，用以表示列表；一种是表结点，用以表示列表；一种是原子结点，用以表示原子。一种是原子结点，用以表示原子。若列表不空，则可分解成表头和表尾；若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成；一个表
20、结点可由三个域组成；标志域、标志域、指示表头的指针域指示表头的指针域 指示表尾的指针域；指示表尾的指针域；而原子结点只需两个域；而原子结点只需两个域；标志域标志域 值域值域(如图如图58所示所示)。2.举例：举例：A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)3广义表的头尾链表存储结构的特点：广义表的头尾链表存储结构的特点：在上述广义表的头尾链表存储结构中有几种情况：在上述广义表的头尾链表存储结构中有几种情况：(1)除空表的表头指针为空外，对任何非空列表，其表除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的头指针均指向一个表结点，且该结点中的h
21、p域指示列域指示列表表头表表头(或为原子结点，或为表结点或为原子结点，或为表结点)，tp域指向列表表域指向列表表尾尾(除非表尾为空，则指针为空，否则必为表结点除非表尾为空，则指针为空，否则必为表结点)；(2)容易分清列表中原子和子表所在层次。容易分清列表中原子和子表所在层次。(3)最高层的表结点个数即为列表的长度。最高层的表结点个数即为列表的长度。这三个特点在某种程度上给列表的操作带来方便。这三个特点在某种程度上给列表的操作带来方便。也可采用另一种结点结构的链表表示列表也可采用另一种结点结构的链表表示列表 二广义表的扩展线性链表存储：二广义表的扩展线性链表存储：1形式定义说明：形式定义说明：typedef enumATOM,LIST ElemTag;typedef struct GLNodeElemTag tag;union ElemTag atom;struct GLNode *hp;struct GLNode *tp;*GList;2.举例：举例：A()B(e)C(a，(b，c，d)D(A，B，C)E(a，E)
