数据结构chapter5数组和广义表

1、1数数 据据 结结 构构5.1 数组的定义和运算数组的定义和运算第第 5 章章 数组和广义表数组和广义表5.2 数组的顺序存储和实现数组的顺序存储和实现5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储5.4 广义表广义表2数数 据据 结结 构构5.1 数组的定义和运算数组的定义和运算定义定义第第 5 章章 数组和广义表数组和广义表mnmmnnnmaa.aa.a.aaa.aa212222111211= =nm也可以看成是也可以看成是m个行向量个行向量可以看成是可以看成是 个列向量个列向量n可看成是一种特殊的线性表，其特殊在可看成是一种特殊的线性表，其特殊在于表中的于表中的数据元素本身也是一个线性表数

2、据元素本身也是一个线性表。数组是数组是一组有固定个数的元素的集合一组有固定个数的元素的集合。3数数 据据 结结 构构5.1 数组的定义和运算数组的定义和运算抽象数据类型定义抽象数据类型定义第第 5 章章 数组和广义表数组和广义表adt arrayadt array数据对象：数据对象：d=aj1j2jn|n0,称为数组的维数，称为数组的维数，ji是数组的是数组的 第第i维下标，维下标，1jibi,bi为数组第为数组第i维的长度，维的长度， aj1j2jnelementset数据关系：数据关系：r=r1,r2,rn ri=| 1jkbk, 1kn, 且且ki, 1jibi-1, aj1jijn,

3、aj1ji+1jn d, i=1,n 基本操作：基本操作： 1.initarray(a,n,bond1,bondn) 2.destroy(a) 3.getvalue(a,e,index1,indexn) 4.setvalue(a,e,index1,indexn)4数数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现类型特点类型特点:第第 5 章章 数组和广义表数组和广义表 1）不考虑插入和删除操作；）不考虑插入和删除操作；2）数组是多维的结构，而存）数组是多维的结构，而存 储空间是一个一维的结构。储空间是一个一维的结构。5数数 据据 结结 构构5.1 数组的定义和运算数组的定

4、义和运算运算运算第第 5 章章 数组和广义表数组和广义表获得特定位置的元素值；获得特定位置的元素值；修改特定位置的元素值。修改特定位置的元素值。 主要操作是主要操作是数据元素的定位数据元素的定位，即给定元素，即给定元素的下标，得到该元素在计算机中的存放位置。的下标，得到该元素在计算机中的存放位置。 其本质是其本质是地址计算问题地址计算问题。有两种顺序映象的方式有两种顺序映象的方式:以行序为主序；以行序为主序；以列序为主序。以列序为主序。6数数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现以行序为主序以行序为主序第第 5 章章 数组和广义表数组和广义表例如：例如： a1,2a

5、1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3l二维数组二维数组amxn中任一元素中任一元素ai,j 的存储位置的存储位置 loc(i,j)=loc(1,1) + (n(i-1)(j-1)称为称为基地址基地址或基址。或基址。 l 7数数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现以列序为主序以列序为主序第第 5 章章 数组和广义表数组和广义表例如：例如： l二维数组二维数组amxn中任一元素中任一元素ai,j 的存储位置的存储位置 loc(i,j)=loc(1,1) + (m(j-1)(i-1)称为称为基地址基地址或基址。或基址。

6、l a1,2a1,1a1,3a2,1a2,2a2,3a2,1a1,1a1,2a2,2a1,3a2,38数数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现第第 5 章章 数组和广义表数组和广义表三维数组三维数组a r mn中任一元素中任一元素ai,j,k 的存储位置的存储位置loc(i,j,k)=loc(1,1,1) + (i-1)mn (j-1)n+(k-1)l j1,j2,j3代替数组下标代替数组下标i,j,k，并且，并且j1,j2,j3的下限分别为的下限分别为c1,c2,c3，上，上限为限为d1,d2,d3,每个元素占每个元素占size个存储单元。则个存储单元。则a j

7、1,j2,j3的存储位置的存储位置loc(j1,j2,j3)=loc(c1,c2,c3) + (j1-c1)(d2-c2+1) (d3-c3+1) (j2-c2) (d3-c3+1) +(j3-c3)size 9数数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现第第 5 章章 数组和广义表数组和广义表推广到一般情况，可得到推广到一般情况，可得到 n 维数维数组数据元素存储位置的映象关系：组数据元素存储位置的映象关系：loc(aj1j2jn=loc(ac1c2cn)+ i(ji-ci), 1inni=1其中：其中： i=size (dk-ck+1),1in)nk=i+110数

8、数 据据 结结 构构5.2 数组的顺序存储和实现数组的顺序存储和实现第第 5 章章 数组和广义表数组和广义表例如：例如： 设有二维数组设有二维数组a1020，其每个元素占，其每个元素占2个字节，第一个元素个字节，第一个元素a1,1的存储地址为的存储地址为100，则则按行优先按行优先顺序存储时元素顺序存储时元素a6,6的存储地址为的存储地址为?若若按列优先按列优先顺序存储时元素顺序存储时元素a6,6的存储地址为的存储地址为?a 6,6=100+(6-1)*20+(6-1)*2=310按行优先按行优先按列优先按列优先a 6,6=100+(6-1)*10+(6-1)*2=21011数数 据据 结结

9、构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表特殊矩阵特殊矩阵三角矩阵三角矩阵带状矩阵带状矩阵稀疏矩阵稀疏矩阵三元组顺序表三元组顺序表十字链表十字链表12数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表特殊矩阵：特殊矩阵： 三角矩阵三角矩阵下三角矩阵下三角矩阵nnnnnccccccccca aa aa aa aa aa aa aa aa aa a321333231222111loc(i,j)=loc(1,1) + 前前i-1行非零元素个数行非零元素个数第第i行中行中aij前非零元素的个数前非零元

10、素的个数=loc(1,1) + i(i-1)/2+j-113数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表特殊矩阵：特殊矩阵： 三角矩阵三角矩阵上三角矩阵上三角矩阵loc(i,j)=loc(1,1) + 前前i-1行非零元素个数行非零元素个数第第i行中行中aij前非零元素的个数前非零元素的个数=loc(1,1) + (i-1)(2n-i+2)/2+j-i nnnnccccc0a aa aa aa aa aa aa aa aa aa a.333223221131211n14数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存

11、储第第 5 章章 数组和广义表数组和广义表特殊矩阵：特殊矩阵： 带状矩阵带状矩阵loc(i,j)=loc(1,1) +3 (i-1) -1+j-i+1=loc(1,1) + 2 (i-1) +j-1nn.4544433433322322211211a aa aa aa aa aa aa aa aa aa aa a15数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：稀疏因子：稀疏因子： 设在设在m*n的矩阵中，有的矩阵中，有t个非零元素，令个非零元素，令称称 为矩阵的为矩阵的稀疏因子稀疏因子。通常认为。通常认为 =0.

12、3时为稀疏矩阵。时为稀疏矩阵。nmt= = 16数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表三元组也是采取按三元组也是采取按行行进行存储！进行存储！ 3 0 0 0 0 0 0 0 0 0 0 4 0 0 5 2 0 0 0 0 0 0 0 6 0 1 0 0 0 7 jvi11332-435541254661165717数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表数据类型定义数据类型

13、定义#define maxsize 1000typedef struct int row, col; elementtype e ;triple; typedef struct triple datamaxsize +1; int m, n, len;tsmatrix;18数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算- - -028003600070500140- - -005280000007143600for (row=1; row =m; + row ) for

14、(col =1; col m=a.n; b-n=a.m; b-len=a.len; if(b-len0) j=1; for(k=1; k=a.n; k+) for(i=1; idataj.row=a.datai.col; b-dataj.col=a.datai.row; b-dataj.e=a.datai.e; j+; if(ja.len) break;22数数 据据 结结 构构 void transposetsmatrix(tsmatrix a,tsmatrix *b) int i,j,min; b-m=a.n; b-n=a.m; b-len=a.len; i=1; while(i=a.le

15、n) min=1;for(j=2;j=a.len;j+) if(a.dataj.coldatai.row=a.datamin.col; b-datai.col=a.datamin.row; b-datai.e=a.datamin.e; i+; a.datamin.col=a.n+1; 23数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算m第第j列在转置后，形成转置矩阵列在转置后，形成转置矩阵t的第的第j行。行。 设设m的第的第j列有列有k个非零元素，如图所示个非零元素，如图

16、所示r1,j,v1r2,j,v2rk,j,vkmj,r1,v1j,r2,v2j,rk,vkt一次定位快速转置一次定位快速转置24数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算- - -028003600070500140- - -0052800000071436001 2 142 1 -73 1 363 3 281 5 -5ijvijv1 3 362 1 141 2 -73 3 285 1 -525数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5

17、 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算一次定位快速转置一次定位快速转置算法步骤：算法步骤：a.扫描矩阵扫描矩阵a的三元组表，统计出的三元组表，统计出a的每一列的的每一列的 非零元素的个数非零元素的个数，存放到数组，存放到数组numcol中中 （numcol 存放存放m第第col列的非零元素个数）。列的非零元素个数）。b.计算转置矩阵计算转置矩阵b的每一行在三元组表中的开始的每一行在三元组表中的开始 位置位置，并存放到数组，并存放到数组positioncol中，中，（positioncol 存放存放t第第col行开始位置）。行开始位置）。

18、c.再次扫描矩阵再次扫描矩阵a的三元组表的三元组表，根据非零元素的列号根据非零元素的列号col，确定它转置后的行号确定它转置后的行号，查查position表，按查到的位置直表，按查到的位置直接将该项存入转置三元组表接将该项存入转置三元组表b中中,并并修改修改positioncol ,将将其其指向该行下一个元素的存储位置指向该行下一个元素的存储位置(positioncol + )。26数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算一次定位快速转置一次定位快速转置算法实现：算

19、法实现：a. for(col=1;col=a.n;col+) numcol=0; for(t=1;t=a.len;t+) numa.datat.col+; 1 2 142 2 -73 1 363 4 281 5 -5ijvcol12345numcol000001121127数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算一次定位快速转置一次定位快速转置算法实现：算法实现：b. position1 = 1; for(col=2;col=a.n;col+) positionco

20、l = positioncol-1+numcol-1; col12345numcol0000011211positioncol124451 2 142 2 -73 1 363 4 281 5 -5ijvijv2 1 142 2 -71 3 364 3 285 1 -528数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算一次定位快速转置一次定位快速转置算法实现：算法实现：c. for(p=1;pdataq.row=a.datap.col; b-dataq.col=a.data

21、p.row; b-dataq.e=a.datap.e; positioncol+; col12345numcol0000011211positioncol124451 2 142 2 -73 1 363 4 281 5 -5ijvijv2114351-522-7413362432865完整完整p13529数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：三元组顺序表三元组顺序表的转置运算的转置运算一次定位快速转置一次定位快速转置算法实现：算法实现：该算法的总的循环次数为：该算法的总的循环次数为：a.n+a. len +

22、a.n-1 +a.len= 2(a.n + a. len)-1时间复杂度为时间复杂度为：o(a.n + a. len)即使非零元个数即使非零元个数a. len与与a.m*a.n同数量级，其时间同数量级，其时间复杂度为复杂度为o(a.m*a.n)，与经典算法时间复杂度相同。与经典算法时间复杂度相同。30数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：十字链表十字链表的存储表示的存储表示一个结点除了数据域一个结点除了数据域(i,j,elem)之外，还应该用之外，还应该用两两个方向的指针（个方向的指针（right, dow

23、n)，分别指向行和列。，分别指向行和列。right：用于链接同一：用于链接同一行行中的下一个元素；中的下一个元素；down：用于链接同一：用于链接同一列列中的下一个元素。中的下一个元素。整个矩阵构成了一个十字交叉的链表，因此称整个矩阵构成了一个十字交叉的链表，因此称十字链表十字链表。rowcolvaluedownright每一行和每一列的头指针，用两个一维指针数组来存放。每一行和每一列的头指针，用两个一维指针数组来存放。31数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：十字链表十字链表的类型定义的类型定义typed

24、ef struct olnode int row,col; int value; struct olnode *right,*down; olnode,* olink;typedef struct olink *row_head,*col_head; int m,n,len; crosslist; rowcolvaluerightdown32数数 据据 结结 构构5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储第第 5 章章 数组和广义表数组和广义表稀殊矩阵：稀殊矩阵：十字链表十字链表的举例的举例rowcolvaluedownright-3 0 0 -50 -1 0 08 0 0 7m=11-31

25、4522-131834733数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表概念：概念：是是n=0个元素的有限序列个元素的有限序列，记作，记作 ls = ( d1, d2, ,dn )其中：其中：di 或为或为原子项原子项(原子，一般用小写字母表示原子，一般用小写字母表示) 或为或为广义表广义表(子表，一般用大写字母表示子表，一般用大写字母表示)， n 为广义表的长度。为广义表的长度。原子：原子：是作为结构上不可分割的成分，是作为结构上不可分割的成分， 它可以是一个数或一个结构。它可以是一个数或一个结构。表头与表尾：表头与表尾：ls不为空时，称不为空时，称d1

26、为表头为表头(head)， 称称其余元素组成的子表其余元素组成的子表( d2, d3， ,dn ) 为表尾为表尾(tail)。34数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表举例：举例：1）a = ( ) 2）f = (d, (e) n =3）d = (a,(b,c), f) 4）c = (a, d, f) 5）b = (a, b) = (a, (a, (a, , ) ) )n =2 n =n =head(f)=head(d)=tail(d)=head(c)=head(b)=tail(f)=0d(e)2(a,(bc)(f)3atail(c)=(d,f)at

27、ail(b)=(b)任何一个非空广义表其任何一个非空广义表其表头可能是原表头可能是原子或广义表，而其表尾必定为广义表子或广义表，而其表尾必定为广义表。35数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表结构特点：结构特点：1） 广义表中的数据元素有广义表中的数据元素有相对次序相对次序；2）广义表的）广义表的长度长度定义为定义为最外层包含元素个数最外层包含元素个数；3） 广义表的广义表的深度深度定义为所含定义为所含括弧的重数括弧的重数；4） 广义表可以广义表可以共享共享；5） 广义表可以是一个广义表可以是一个递归的表递归的表。 递归表的递归表的深度是无穷值深度是

28、无穷值，长度是有限值。长度是有限值。注意：注意：“原子原子”的深度为的深度为 0 “空表空表”的深度为的深度为 1 36数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表存储方式：存储方式：由于广义表由于广义表(a1,a2,a3,an)中的数据元素可中的数据元素可以具有不同的结构，（或是原子，或是广义以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通表），因此，难以用顺序存储结构表示，通常采用常采用链式存储结构链式存储结构来表示。来表示。 头、尾链表存储结构；头、尾链表存储结构； 扩展线性链表存储结构。扩展线性链表存储结构。37数数 据

29、据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表存储方式：存储方式： 头、尾链表存储结构头、尾链表存储结构每个元素用一个结点表示每个元素用一个结点表示,需要用两种结构的结点需要用两种结构的结点:表结点表结点原子结点原子结点标志域标志域表头指针表头指针表尾指针表尾指针tag=1hptp标志域标志域值域值域tag=0atomtypedef enum atom, list elemtag; typedef struct glnode elemtag tag; union atomtype atom; struct struct glnode*hp,*tp; htp; ato

30、m_htp;glnode,*glist; 38数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数组和广义表数组和广义表存储方式：存储方式： 头、尾链表存储结构头、尾链表存储结构分析方法：分析方法： 表头、表尾分析表头、表尾分析若表头为原子，则用若表头为原子，则用原子结点原子结点: :空表空表 l=nil l=nil ( ( l l为头指针为头指针 ) ) 非空表非空表 l l指向表头指向表头指向表尾指向表尾否则用表结点否则用表结点; ;表尾总是用表结点或空表尾总是用表结点或空; ;子表结构依次类推。子表结构依次类推。tag=1tag=0atom39数数 据据 结结 构构5.4 广义表广义表第第 5 章章 数