第5章 数组与广义表.doc

第5章数组和广义表（4学时）（一）教学目的： 掌握数组的定义及顺序表示与实现；掌握矩阵的压缩存储；广义表的定义及存储结构。（二）教学重点：1、数组的定义及其存储2、特殊矩阵的压缩存储3、稀疏矩阵逻辑结构和存储结构4、广义表的逻辑结构和存储结构5、数组和广义表的操作应用举例（三）教学难点：1、矩阵的压缩存储2、广义表的存储结构51数组的定义一、数组的抽象类型定义：数据对象：D= |n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，ElemSet数据关系：R=R1，R2，Rn Ri=> 0jkbk-1，1kn且ki，0jibi-2，D，I=2,n二、数组基本操作：1、InitArray(&A,n,bound1,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。2、DestroyArray（&A）操作结果：销毁数组A。3、Value(A,&e,indeex1,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。4、Assign(&A,e,index1,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。三、数组与线性表的关系：1、二维数组与线性表的关系：以把二维数组看成是这样一具定长线性表：它的每个数据元素也是一个定长线性表。A=(a0,a1,ap) (p=m-1或n-1)其中每个数据元素aj是一个列向量形式的线性表aj=(a0j,aij,am-1j) 0jn-1ai=(ai0,ai1,ai,n-1) 0im-1在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef ElemType Array2mn;等价于 typedef ElemType Array1n;typedef Array1 Array2m;(a) (b) (C )图5·1二维数组图例（a）矩阵形式表示；（b）列向量的一维数组；（c）行向量的一维数组2、n维数组与线性表的关系：同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。四、数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。52数组的顺序表示和实现一、二维数组的顺序存储：则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有两种存储方式：在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列序为主序的存储结构。（a） 以列序为主序 （b）以行序为主序图5.2 二维数组的两种存储结构二、数组的地址计算：1、二维数组的地址计算：假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定LOC（i,j）=LOC（0，0）+（b2×i+j）L (51)式中，LOC（i,j）是aij的存储位置；LOC（0，0）是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。2、n维数组地址计算：LOC(j1,j2,jn)=LOC(0,0,0)(b2×bn×j1b3×bn×j2bn×jn-1jn)L=LOC(0,0,0)()L或缩写成LOC（j1,j2,jn）=LOC(0,0,0)+ (52)其中Cn=L,ci-1=bi×ci, 1<in。5.3 矩阵的压缩存储1、压缩存储：为多个值相同的元只分配一个存储空间；对零元不分配空间。2、特殊矩阵：假若值相同的元素或者零元素的矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵。3、稀疏矩阵：非零元分布没有任何规律，但是数量很少，这样的矩阵我们称为稀疏矩阵。531特殊矩阵一、对称矩阵：1、对称矩阵定义：若n阶矩阵A中的元满足下述性质aij=aji 1i,jn，则称为n阶对称矩阵。2、对称矩阵的压缩存储：对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1 )/2个元的空间中。3、压缩存储元素与存储地址之间的对应关系：假设以一维数组san(n+1)/2作为n阶对称矩阵A的存储结构，则sak和矩阵元aij之间存在着一一对应的关系： （53）a11a21a31a41an,1an,nk= 0 1 2 3 图5.3 对称矩阵的压缩存储二、三角矩阵：所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c或零的n阶矩阵。则除了和对称矩阵一样只存储其下（上）三角中的元之外，再加一个存储常数c的存储空间即可。三、对角矩阵：所谓对角矩阵是指所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零。如图5.4所示。对这种矩阵，我们也可按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数组上。 图5.4 三对角矩阵5.3.2 稀疏矩阵假设在m×n的矩阵中，有t个元素不为零。令为矩阵的衡疏因子。通常认为时称为稀疏矩阵。图5.5 稀疏矩阵M和T一三元组顺序表1、三元组顺序表的定义：假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式我们称之为三元组顺序表。#define MAXSIE 12500 /假设非零元个数的最大值为12500Typedef struct int i,j: /该非零元的行下标和列下标 ElemType e;Triple;Typedef struct Triple dataMAXSIZE+1；/非零元三元组表，data0未用 int mu, nu, tu; /矩阵的行数、列数和非零元个数TSMatrix;在此，data域中表示非零元的三元组是以行序为主序顺序排列的。2、矩阵的转置运算。从a转置为b的主要过程：（1）将矩阵的行列值相互交换；（2）将每个三元组中的i和j要互调换；（3）重排三元组之间的次序便可实现矩阵的转置。ijv121213931-3351443245218611564-7a.dataijv13-3161521122518313342446-76314 b.data可以把两种处理方法：（1）按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。换句话说，按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素，需要对其三元组表a.data从第一行起整个扫描一遍，由于a.data是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应有的顺序。其具体算法描述如算法5.1所示。Status TransposeSMatrix(TSMatrix M, TSMatrix &T)/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu)q=1;for(col=1;colM.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;/TransposeSMatrix算法 5.1（2）按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中应有的位置，那么在对a.data的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。在此，需要附设num和cpot两个向量。Numcol表示矩阵M中第col列中非零元的个数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置。显然有 （5-4）例如，对图5.5的矩阵M.num和cpot的值如表5.1所示。表5.1 矩阵M的向量cpot的值Col1234567Numcol2221010Cpotcol1357889这种转置方法称为快速转置，其算法如算法5.2所示。Status FastransposeSMatrix(TSMatrix M, TSMatri×&T)T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu) for(col=1; colM.nu; +col） numcol=0; for(t=1;tM.tu; +t） +numM.datat.j；/求M中每一列含非零元个数cpot1=1；/求第col列中第一个非零元在b.data中的序号for(col=2；colM.nu; +col） cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu; +p） col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datape; +cpotcol;/for/ifreturn OK;/FastTransposeSMatrix算法 5.2这个算法仅比前一个算法多用了两个辅助向量。从时间上看，算法中有4个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O(nu+tu)。在M的非零元个数tu和mu×nu等数量级时，其时间复杂度为O(mu×nu)，和经典算法的时间又复杂度相同。二、十字链表1、十字链表的定义在链表中，每个非零元可用一个含5个域的结点表示，其中i、j和e这3个域分别表示该非零元所有的行、列和非零元的值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数相表示之。2、十字链表的举例：例如，式（5-5）中的矩阵M的十字链表如图5.6所示。三、稀疏矩阵的十字链表表示和建立十字链表的算法1、稀疏矩阵的十字链表存储表示Typedef struct OLNode int i,j; /该非零元的行和列下标ElemType e;Struct OLNode * right, * down； /该非零元所在行表和列表的后继链域OLNode; *OLink;typedef struct OLink * rhead, * chead; /行和列链表头指针向量基址由CreateSMatrix分配 int mu, nu, tu; /稀疏矩阵的行数、列数和非零个数CrossList;2、创建稀疏矩阵的十字链表算法：Status CreateSMatrix_OL (CrossList &M) /创建稀疏矩阵M。采用十字链表存储表示。if (M)free(M);scanf(&m, &n, &t); /输入M的行数、列数和非零元个数M.mu; =m; M.nu:=n; m.TU;=t;if (!(M.rhead=(OLink * )malloc(m+1) * sizeof(OLink)exit(OVERFLOW);if (!(M.chead =(OLink * )malloc(n+1) * sizeof(OLink)exit(OVERFLOW);M.rhead =M.chead =NULL; /初始化行列头指针向量；各行列链表为空链表for(scanf(&I,&j,&e)；i!=0;scanf(&I,&j,&e) /按任意次序输入非零元 if(!(p=(OLNode *)malloc(sizeof(OLNode)exit(OVERFLOW);p-i=i; p->j=j; p-e=e;if(M.rheadpi=NULLp-right=M.rheadi;M.rheadi=p; else /寻查在行表中的插入位置 for (q=M.rheadi;（q-right）&&q-right-jj; q=q-right);else /寻查在列表中的插入位置 for(q=M.cheadj;(q-down)&&. Q-down-iI; q=q-down); p-down=q-down; q-=down=p; / 完成列插入 return OK;/CreateSMatrix.OL算法 5.45.4 广义表的定义顾名思议，广义表是线性表的推广。也有人称其为列表（lists，用复数形式以示与统称的表list的区别）。广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。一、广义表的定义：1、抽象数据类型定义：ADT GList 数据对象：D=数据关系：R1=ei-1,ei| ei-1, ei D, 2in2、广义表的表示：广义表一般记作 LS=（1，2，n）其中，LS是广义表（1，2，n）的名称，n是它的长度。可以是单个元素，也可是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素为LS的表头（Head），称其余元素组成的表（2，3，n）是LS的表尾（Tail）。3、广义表的举例：（1）A=（）A是一个空表，它的长度为零。（2）B=（e）列表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d)）列表C的长度为2，两个元素分别为原子和子表(b,c,d)。（4）D=（A，B，C）列表D的长度为3，3个元素都是列表。显然，将子表的值代入后，则有D=（），(e),(a,(b,c,d)。（5）E=（a,E）这是一个递归的表，它的长度为2。E相当于一个无限的列表E=(a,(a,a,)）。二、表头函数 head()和表尾函数tail()：根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。例如：GetHead(B)=e, GetTail(B)=(),GetHead(D)=A, GetHead(D)=(B,C)由于（B，C）为非空列表，则可继续分解得到：GetHead(B,C)=B, GetHead(B,C)=C，值得提醒的是列表（）和（）不同。前者为空表，长度n=0；后者长度n=1，可分解得到其表头、表尾均为空表（）。图5.7 列表的图形表示5.5广义表的存储结构一、广义表结点的设定：两种结构的结点：（1）一种是表结点，用以表示列表；一个表结点可由3个域组成：标示域、指示表头的指针域和指示表尾的指针域；（2）一种是原子结点，用以表示原子。而原子结点只需两个域：标志域和值域（如图5.8所示）。其形式定义说明如下：二、广义表的存储结构图：图5.9 广义表的存储结构示例