数组与广义表

1、第五章数组与广义表一基本内容数组的类型定义和表示方式：特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构、m元多项式的广义表表示以及广义表的操作的递归算法举例。二学习要点1. 了解数组两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2 掌握对特殊矩阵进行压缩存储时的下标变换公式。3了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵 时进行矩阵运算采用的处理方法。4掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一 种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或

2、者分解为n个子表。5学习利用分治法的算法设计思想编制递归算法的方法。三重点与难点5.1.1数组结构的基本概念1 .数组的定义数组是由下标和值组成的有序对的集合。在数组中对于每组有定义的下标，都存在一个与其相对应的值，该值通常称为数组元素值。例如，一个形如mx n阶矩阵厂AA1,1A1,2A1,nA2,1A2,2A2,n:(5.1)Am,1 Am,2 Am,nl 一 J就是一个二维数组。其中的每个元素Al,j都与一个二维空间的数(i, j)|(1<=i<=m,1<=j<=n) 相对应。类似的，一个N维数组中的每个元素都与一个N维空间的数(i, j, k，)相对应。若N =

3、 1则为一维数组，变化成线性表即 Al。因此，数组可看成是线性表的最简单的推广， 但这样一推就把数组结构由线性结构推到非线性结构了。以式5。1矩阵为例，每个元素Ai,j属于两个线性队列，即第i行的队列Ai,1,Ai,2，, Ai,n共n个元素；第j列的队列A1,j,A2,j,，Am,j共m个元素。这些正交的行队列和 列队列表示了数组的二维结构性质。2. 数组的性质数组结构中的每一个元素都与一组下标有关，一旦数组定义后，该结构就具有以下性质：(1) 数据元素的数目固定，即一旦定义了数组结构，在其被操作的过程中，元素数目不再有增减变化。(2) 元素值具有相同的数据类型。(3) 数据元素的下标关系具

4、有上、下界的约束，并且下标有序。因此，对于数组结构来说只有两种运算。(1) 给定一组下标，存取相应的数据元素；(2) 给定一组下标，修改相应的数据元素中某个数据项的值。5.1.2数组的存储结构1. 链式存储结构由于数组结构是非线性数据结构，用指针类型来描述前驱和后继关系的不唯一性很方便。例如，二维数据元素间关系用十字链表表示，如图5.1所示。图中，ROW表示行COL表示列，VALUE表示值，DOWN指向同一列的下一个元素，NEXT指向同一行的后一个元素。ROWCOLVALUEDOWNNEXT图5.1十字链表结点2. 顺序存储结构计算机内存结构是一维的，因此要存放多维数组结构就必须按某种次序将数

5、据元素排成 一个线性序列。再由于数组结构性质，使得用顺序存储方式存放数组元素是自然的了。例如，式(5.1)的两维数组以行为先排列为(A 11,A12AinA21 Aj A mn )(5.2)式中，Aj也可以表示成 Ai,j或Ai,j。同理，式(5.1)的数组以列为先排列为(A 11A21 Am1A12A22 AijA mn )(5.3)在数组的顺序存储结构中，若要检索某个元素，只要记住第一个元素的存储地址,地址a以及每个元素占用的单元数I，就能随机地计算出来。(1) 以行为主序优先的存储地址计算公式：(Ai,j)地址=a +(i-1)* n+j-1)*l 该式计算出的元素地址是归一化的，即排列

6、为式(5.2)表示的顺序。(2) 归一化的以列为主序优先的存储地址计算公式：(Ai,j)地址=a +(i-1+(j-1)*m)*l(3) 三维数组归一化以行为主序优先的存储地址计算公式：可类似写出，即(Ai,j,k) 地址 = a +(i-1)* n*p+(j-1)*p+k-1)*l 式中，对Ai,j,k来说，前面已存放(i-1)个面，每个面上有 n*p个元素；在第 中，每行有p个元素；而在第k列前已有k-1个元素。(4) 非归一化的二维数组以行为主序优先的存储地址计算公式：(Ai,j)地址=a +(i-i 0)*(j i-jo+1)+j-j 0)*l 式中，i=i o is；j=j 0jt。

7、5.1.3矩阵的压缩存储 所谓矩阵的压缩存储是指对多个值相同的元素只分配一个存储空间，或对零值元素 不分配空间单元。(5.4)(5.5)即基(5.6)i面上，前(j-1)行(5.7)1 .特殊矩阵的压缩存储对于值相同的元素或零元素在矩阵中位置分布具有一定规律的矩阵称为特殊矩阵。通过寻求k(I, j)间的对应关系来实现压缩存储。(1) 三角矩阵：如图5。2所示为下三角矩阵及其以行为主序优先的顺序存储。其中，值为零的元素不占空间，非零值的元素有(n + 1) n/2个。因此，k与(I, j)的对应关系为当 I>=j 时，k= I (I - 1) /2+j(5.8)当I<j时，对应的零元

8、素不存储。XXXXXXXXX(2) 对称矩阵：在 m阶方阵A中，若A中元素满足Aij = Aji(5.9)则称为对称矩阵。显然，可用式(5.9)对称性来实现压缩存储，有k与(I, j)的对应关系为k= I (I - 1) /2+j(5.10)式中，I = max (I, j); J= min (I, j)。(3) 对角矩阵：对角矩阵如图5。3所示。在对角矩阵中所有的非零元素都集中在以主对角线为中心的带状区域上，即除了主对角线上的元素及 与其上、下相邻的元素以外，其余元素都为零元素。，图5。3所示中有非零元素的个数为(3m 2)个，而零元素个数为m2 -( 3m- 2)=m(m-3)+2个。XX

9、XXXXXXXXXXX当用一维数组 Ak来存储(以行为先的顺序)三对角矩阵时，有 k与(I, j)之间的对应关 系为k = 2 (i - 1)+ j当j=I-,I,I+1时，上式成立；若当j为其它值时，其对应的元素是不存储的零元素。3. 稀疏矩阵的压缩存储设矩阵A中有s个非零元素，且s<<t,则称A为稀疏矩阵。在稀疏矩阵中非零值元素的分布是无规律的，例如，图5.4所示的矩阵A(8*6),其中 s= 7,t= 41 o05003000000010300000000000-100000000000000001000 -1图5.4一个8X 6阶的稀疏矩阵A显然，为存储非零元素，除其值之外

10、，还必须同时存储它的下标位置，既非零元素由(i,j,value )(5.12)表征。其中，(i, j)为元素下标，value为元素值。(1) 三元组表压缩存储：如图5.4所示的稀疏矩阵，用三元组表存储，如图5.5所示。其中，共有8行，0行是特殊行，相应的数表示稀疏距阵是一个8X 6阶的矩阵，并且只有7个非零元素；17行对应7个非零元素的(i,j,Value )，并且以(i,j) 下标为递增次序排列。设某稀疏矩阵 M中具有非零元素为t个，该矩阵是 m行n列的，若令每个信息在存储 中占用一个单元，则用三元组表存储后可压缩的存储空间为m* n-3(t+1)(5.13)设压缩空间的百分比为n，则n =

11、 (m* n-3(t+1)/(m* n)=1-3p-3/(m* n) 1-3p(5.14)式中，p=t/(m*n)表示稀疏矩阵的稀疏程度，当p<<1/3时，可节省大量的存储空间。(2) 十字链表存储压缩：十字链表的结点构造如图5.1所示。当用它来存储稀疏矩阵时，零元素不形成结点，非零元素才有结点，从而节省存储空间。5.1.4三维图形信息的压缩存储在光栅扫描的图形系统中，通常对任一物体以其外接立方体为边界，且以一个单位立方体为分割精度，沿三个轴向对外接立方体进行分割。在此仅讨论最简单的情况，即处理黑白图象。若物体占据该单位立方体，则称该单位立方体为满，令相应的编码为1;否则称该单位立

12、方体为空，令相应的编码为0。假定作为边界的是外接正立方体，且沿着每个坐标轴分割成n份，则整个外接立方体共被分割差那个n3个单位立方体，相应产生n3个编码。如图5.6（a）所示。当然，这n3个信息可以存储在一个三维数组内，根据三维数组的地址公式是容 易存取图形信息的。 但存储量太大，而前面所讨论的方法又用不上，因为，在这样的三维数组中零元素的分布没有规律，而且其数量也不一定很多。如何对上述三维数组进行压缩存储呢？可用一个多重链表来表示，链表的每个结点设立n个域。如果按xyz的检索顺序进行，即现在x方向上把外接正立方体分割成n片，如图5.6（c）所示。链表的第一个结点的n个域就对应这n片，若第I个

13、（1<=l<=n ）片的编码都相同，都是1 （或0），则结点第I个域即赋值为1 （或0），否则，结点第I个域中存放指针， 并把第I片再在y方向上分割成n条，这n条与另一结点的n个域相对应，而该结点的地址 即为链表第一个结点第I个域的指针值。同样，若某条中的编码相同，则在相应的域中赋上 此编码值，否则，还要把该条在z方向上分割成n个单元。0000011011110110yox=10000111111111110yox=21111111111111111yo0000000000000110yox=3z这样，就把一个三维数组表示成一个三层的多重链表。层，且第一层只有一个结点，对应物体的 点对应某片（也可以是几片，但这几片的编码相同）的 有若干个结点，每个结点对应某条（也可以是若干条）的 层只有一个结点，由于 x=3，4两片的编码分别全是 而x= 1, 2两片的编码不相同， 个结点对应的是x=4z若按照xyz的顺序，则x在第- n个片；y在第二层，可以有若干个结点，每个结 n个条；z在第三层，第三层也可以 n个单元。如图5.6（b）