数据结构-第5章 数组和广义表

1、第第5 5章数组和广义表章数组和广义表5.1 5.1 数组的定义数组的定义5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 5.4 5.4 广义表的定义广义表的定义5.5 5.5 广义表的存储结构广义表的存储结构5.1.1 5.1.1 数组的定义数组的定义数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。1 1一维数组一维数组一维数组可以看成是一个线性表或一个向量（第2章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经介绍。5.1 5.1 多维数组的

2、定义多维数组的定义2 2二维数组二维数组二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。例如，设A是一个有m行n列的二维数组，则A可以表示为：a00 a01 a0n-1 a10 a11 a1n-1 . A= am-1 0 am-1 1 am-1 n-1 二维数组可以看成是这样一个定长的线性表, 它的每个数据元素也是一个定长的线性表。二维数组可以看成是一个线性表二维数组可以看成是一个线性表A=(aA=(a0 0,a,a1 1, ,a,an-1) )其中每个数据元素其中每个数据元素ajaj是一个是一个列向量列向量形式形式的线性表的线性表 A=(aA=

3、(a0 0 , a, a1 1 , , ,a ,an-1) )a00 a01 a0n-1 a10 a11 a1n-1 . A= am-1 0 am-1 1 am-1 n-1 或者或者, ,可以看成是一个线性表可以看成是一个线性表A=(a0,a1,am-1)其中每个数据元素其中每个数据元素ajaj是一个是一个行向量行向量形式的形式的线性表线性表a00 a01 a0n-1 a10 a11 a1n-1 . A= am-1 0 am-1 1 am-1 n-1 A=(a0,a1,.am-1)同理，n维数组可以看成是这样一个定长的线性表, 它的每个数据元素也是n-1维的数组。n维数组最多可有n个直接前驱和

4、n个直接后继，故n维数组是一种非线性结构。3 3n n维数组维数组数组的操作数组的操作数组一旦被定义，它的维数和维界就不再改变，因此，除了结构的初始化初始化和销毁销毁之外，数组只有存取元素存取元素和修改元素值修改元素值的操作。数组宜采用顺序存储结构：数组宜采用顺序存储结构：由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。本章仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。5.2 5.2 数组顺序表示和实现数组顺序表示和实现由于计算机内存结构是一维的（线性的），因此，用一维内

5、存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。二维数组的顺序存储有两种形式:怎样将数组中元素存入到计算机内存中呢？怎样将数组中元素存入到计算机内存中呢？1.行优先顺序a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1在BASIC语言、PASCAL语言、C/C+语言等高级语言程序设计中，都是按行优先顺序存放的。可以得出多n维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。a0a1am-12.列优先顺序a00a10am-1,0a01a11am

6、-1, 1a0, n-1a1,n-1am-1,n-1在FORTRAN语言程序设计中，数组是按列优先顺序存放的。可以得出n维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。a0a1am-1二维数组元素存储位置的计算设二维数组设二维数组AmAmn n的起始地址的起始地址( (基地址基地址),),即即a a0000的的起始地址为起始地址为LOC(0,0),LOC(0,0),每个数据元素占每个数据元素占L L个存储个存储单元单元, ,则则A A中任一元素中任一元素a aij的起始地址为的起始地址为: :行优先顺序行优先顺序: :LO

7、C(i,j)=LOC(0,0)+(iLOC(i,j)=LOC(0,0)+(i* *n+jn+j) )* *L L列优先顺序列优先顺序: :LOC(i,j)=LOC(0,0)+(jLOC(i,j)=LOC(0,0)+(j* *m+im+i) )* *L L三维数组元素存储位置的计算设三维数组设三维数组AmAmn np p的起始地址的起始地址( (基地址基地址),),即即a a000000的起始地址为的起始地址为LOC(0,0,0),LOC(0,0,0),每个数据元素每个数据元素占占L L个存储单元个存储单元, ,则则A A中任一元素中任一元素a aijk的起始地址的起始地址为为: :行优先顺序行

8、优先顺序: :LOC(i,j,k)=LOC(0,0,0)+(iLOC(i,j,k)=LOC(0,0,0)+(i* *n n* *p+jp+j* *p p* *k)k)* *L L列优先顺序列优先顺序: :LOC(i,j,k)=LOC(0,0,0)+(kLOC(i,j,k)=LOC(0,0,0)+(k* *m m* *n+jn+j* *m+im+i) )* *L L所以,数组元素是其下标的线性函数.由于计算各个元素存储位置的时间相等,所以存取数组中任一元素的时间也相等.我们称具有这一特点的存储结构为随机随机存储结构存储结构.矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。当矩阵的

9、阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储单元，即进行压缩存储压缩存储。所谓压缩存储压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律,则此类矩阵为特殊矩阵特殊矩阵;非零元素较零元素少,且分布没有一定规律的矩阵,为稀疏矩阵稀疏矩阵.5.3 5.3 矩阵的压缩存储矩阵的压缩存储1 1对称矩阵对称矩阵若一个n阶方阵A中元素满足下列条件：a aijij=a=ajiji 其中 1 i, jn ，则称A为对称矩阵。例如，下图是一个3*3的对称矩阵。5.3.

10、1 5.3.1 特殊矩阵特殊矩阵 A = 643452321 图 一个对称矩阵对称矩阵的压缩存储对称矩阵的压缩存储为每一对对称元分配一个存储空间,则可将n2 2个元压缩存储到n(n+1)/2个元的空间中.以行优先存储其下三角(包括对角线)中的元.假设以一维数组san(n+1)/2作为n阶对称矩阵A的存储结构,则sak和矩阵元素a aijij存在一一对应关系:K=i(i-1)/2+j-1 当ijj(j-1)/2+i-1 当ij ai1 aij aiisa a11a21a22a31 an1 annk 0123n(n-1)/2n(n+1)/2-1所谓下(上)三角矩阵中接线员矩阵的上(下)三角(不包括

11、)对角线)中的无均为常数c或零的n阶矩阵.与对称矩阵类似,除了只存储其下(上)三角中的元之个外,再加一个存储常数C的存储空间即可.2 2三角矩阵三角矩阵 111110111000.nnnnaaacaacca111111100100.nnnnacccaacaaa （a）上三角矩阵 b）下三角矩阵图5.2 三角矩阵所有的非零元都集中在以主对角线为中心的带状区域中的矩阵.如:三对角矩阵3 3对角矩阵对角矩阵( (带状矩阵带状矩阵) )在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵稀疏矩阵。按照压缩存储的概念，要

12、存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。5.3.2 5.3.2 稀疏矩阵稀疏矩阵在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元三元组表法组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存储（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表三元组表。1 1三元组顺序表三元组顺序表图 三元组的结构eji稀疏矩阵的三元组顺序表存储表示:#define MAXSIZE 12500 /*非零元素的最多个数*/

13、typedef struct int i,j; /*该非零元素的行下标和列下标*/ ElemType e； /*该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1;/* 非零元素的三元组 表。data0未用*/ int mu, nu,tu;/*矩阵的行数、列数和非零元素 的个数*/ TSMatrix；稀疏矩阵M对应的三元组表121213931-3361443245218611564-70 0 0 0 0 00 0 0 0 0 0稀疏矩阵N对应的三元组表13-3161521122518319342446-76314-T0 0 0 0 0 00

14、0 0 0 0 0在三元组表存储结构下的矩阵的转置运算所谓的矩阵转置矩阵转置是指变换元素的位置，把位于（i,j）位置上的元素换到（j,i）位置上，也就是说，把元素的行列互换。如下图的67矩阵M，它的转置矩阵就是76的矩阵N，并且N（i,j）= M（j,i），其中，1i7 ，1j6。-T算法分析算法分析显然，稀疏矩阵的转置仍旧是稀疏矩阵。假设M和T分别表示矩阵M和T.如何由M得到T呢? ije121213931-3361443245218611564-7ije13-3161521122518319342446-76314M.dataT.data只需(1)将每个元组中的i,j相互调换(2)重排三元

15、组的次序处理方法处理方法1:1:按照按照T.dataT.data中三元组的次序依次在中三元组的次序依次在M.dataM.data中找到相应的三元组进行转置中找到相应的三元组进行转置. .即即, ,按照按照M M的的列序进行转置列序进行转置Status TransposeSMatrix(TSMatrix M,TSMatrix &T) T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if(M.datap.j=col) T.dataq.i=M.datap.j; T

16、.dataq.j=M.datap.i; T.dataq.e=M.datap.e;+q; return OK; O(nuO(nu* *tu)tu)当tu和mn*nu等数量级时为O(muO(mu* *nunu2 2) )处理方法处理方法2:2:按照按照M.dataM.data中三元组的次序依次进行转中三元组的次序依次进行转置置, ,并将转置后的三元组置入并将转置后的三元组置入T.dataT.data中恰当的位置中恰当的位置. .为了能将待转置三元组M.data中元素一次定位到三元组T.data的正确位置正确位置上，需要预先计算以下数据： 待转置矩阵M每一列列中非零元素的个数。（即转置后矩阵T每一行

17、行中非零元素的个数）。 待转置矩阵M每一列列中第一个第一个非零元素在三元组T.data中的正确位置（即转置后矩阵T每一行行中第一个第一个非零元素在三元组T.data中的正确位置。）为此，需要设两个num 和cpot 。其中numcol用来存放矩阵M中第col列中非零元素个数（转置矩阵T中第col行非零元素的个数）。cpotcol用来存放转置前矩阵M中第col列（转置后矩T中第col行）中第一个非零元素在三元组T.data中的正确位置。则cpot1=1，cpotcol=cpotcol-1+numcol-1。 其中其中 2colM.nu。cStatus TransposeSMatrix(TSMat

18、rix M,TSMatrix &T) T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) 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;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.datap.e;

19、+cpotcol; /for /if return OK; O(nu+tu)O(nu+tu)当tu和mn*nu等数量级时为O(muO(mu* *nu)nu)为了便于随机存取任意一行的非零元,则需知道每一行的第一个非零元在三元组表中的位置。为此可将上节快速转置矩阵的算法中创建的，指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。其类型描述如下：typedef struct Triple dataMAXSIZE+1; / 非零元素的三元组表 int rposMAXRC+1; /各行第一个非零元的位置表 int mu, nu,tu;/矩阵的行数、列数和非零元素的个数 RLSMatrix2

20、2行逻辑链接的顺序表行逻辑链接的顺序表当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示了。如“将矩阵B加至矩阵A”操作，由于非零元的插入或删除将会引起A.data中元素的移动，此时宜采用链式存储。十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法3 3十字链表十字链表每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组（i,j,e）外，还需增加两个链域：行指针域（right），用来指向本行中下一个非零元素；列指针域（down），用来指向本列中下一个非零元素。十字链表结点定义ijrightdowne稀疏矩阵中同一行的非零元通过向右的ri

21、ght指针链接成一个带表头结点的线性链表。同一列的非零元也通过down指针链接成一个带表头结点的线性链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。十字链表类型定义M=3 0 0 50 -1 0 02 0 0 011314522-1312M.rheadM.chead例：矩阵M的十字链表稀疏矩阵的十字链表存储表示typedef struct OLNodetypedef struct OLNode int i,j int i,j; ; / /* *该

22、非零元素的行下标和列下标该非零元素的行下标和列下标* */ / ElemTypeElemType e e； / /* *该非零元素的值该非零元素的值* */ / struct OLNode struct OLNode * *right,right,* *down;down;OLNode;OLNode;* *OlinkOlink; ;typedef structtypedef struct Olink Olink * *rhead,rhead,* *chead; chead; int mu,int mu, nu,tu ;nu,tu ;CrossListCrossList；广义表是第2章提到的线性

23、表的推广。线性表中的元素仅限于原子项，即不可以再分，而广广义表中的元素既可以是原子项，也可以是子表义表中的元素既可以是原子项，也可以是子表（另一个线性表）。（另一个线性表）。广义表也称为列表（lists).1 1广义表的定义广义表的定义广义表是n0个元素a1，a2，an的有限序列，其中每一个ai或者是原子，或者是一个子表。5.4 5.4 广义表的定义广义表的定义广义表通常记为LS=(a1,a2,LS=(a1,a2,an),an)，其中LS为广义表的名字名字，n为广义表的长度长度， 每一个ai为广义表的元素元素,可以是单个元素（原子原子），也可以是广义表（子表子表）。在习惯中，一般用大写字母表示

24、广义表，小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头（表头（Head)Head),称其余元素组成的表（ a2,an)是LS的表尾（表尾（Tail)Tail).（1）A=( )，A为空表，长度为0。（2）B=(a,（b,c）)，B是长度为2的广义表，第一项为原子，第二项为子表。（3）C=(x,y,z)，C是长度为3的广义表，每一项都是原子。（4）D=(B,C)，D是长度为2的广义表，每一项都是上面提到的子表。（5）E=(a,E)，是长度为2的广义表，第一项为原子，第二项为它本身。2 2广义表举例广义表举例（1）用LS=(a1，a2，an)形式，其中每一个ai为原子或广义表例

25、如：A=(b,c) B=(a,A) E=(a,E)都是广义表。3 3广义表的表示方法广义表的表示方法（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套例如，上面提到的广义表A、B、C可以描述为：A(b,c)B(a,A(b,c)E(a,E(a,E（）)（3 3）将广义表用树和图来描述）将广义表用树和图来描述BACbacAbcBaAbc（a）A=(b,c) （b）B=(a,A) （c）C=(A,B) 图 广义表用树或图来表示一个广义表的深度是指该广义表展开后所含括号的层数。例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为34 4广义表的深度广义表的深度GetHead(A)=b GetTail(A)=(c)GetHead(A)=b GetTail(A)=(c)GetHead(B)=A GetTail(B)=(d)GetHead(B)=A GetTail(B)=(d)GetHead(C)=f GetTail(C)=(B,h)GetHead(C)=f GetTail(C)=(