数组与广义表-数组

《数组与广义表-数组》由会员分享，可在线阅读，更多相关《数组与广义表-数组（23页珍藏版）》请在金锄头文库上搜索。

1、第5章 数组与广义表嘉应学院 数学系数据结构讲义数组数组和广义表l数组和广义表可看成是一种特殊的 线性表，其特殊在于，表中的数据 元素本身也是一种线性表。l几乎所有的程序设计语言都有数组 类型。本节重点讲解稀疏矩阵的实 现。5.1 数组的定义l由于数组中各元素具有统一的类型，并且 数组元素的下标一般具有固定的上界和下 界，因此，数组的处理比其它复杂的结构 更为简单。l多维数组是向量的推广。例如，二维数组 ： ( )( )( ) ( ) ( )( )( )( ) ( )可以看成是由一个行向 量组成的向量，也可以 看成是由一个列向量组 成的向量。5.2 5.2 数组的顺序表示和实现数组的顺序表示和

2、实现l由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。l又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组。通常有两种顺序存储方式: (1)以行序为主序 (2)以列序为主序a11 a12 a1n a21 a22 a2n am1 am2 amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放amn am2am1 .a2n a22a21 a1n .a12a110

3、1n-1m*n-1n按列序为主序存放01m-1m*n-1mamn a2na1n .am2 a22a12 am1 .a21a11a11 a12 a1n a21 a22 a2n am1 am2 amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 计算二维数组元素地址的通式 设一般的二维数组是Ac1d1, c2d2，这里c1,c2不一定是0 。无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址（这样数组中的任一元素便可以随机存取！） ：二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*La

4、c1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素 长度aij之前的 行数数组基址总列数，即 第2维长度aij本行前面 的元素个数开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数则行优先存储时的地址公式为： LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L例2：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同

5、）例1软考题：一个二维数组A，行下标的范围是1到6， 列下标的范围是0到7，每个数组元素用相邻的6个字节存储 ，存储器按字节编址。那么，这个数组的体积是 个字 节。 288例3：某考研题设数组a160, 170的基地址为2048 ，每个元素占2个存储单元，若以列序为主序顺序存储，则 元素a32,58的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L 得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：请注意审题 ！利用列优先通式：答： Volume=m*n*L=(6-1+1)*(7- 0

6、 +1)*6=48*6=2885.3 矩阵的压缩存储l在矩阵中非零元素呈某种规律分布或者 矩阵中出现大量的零元素的情况下，占 用了许多单元去存储重复的非零元素或 零元素，这对高阶矩阵会造成极大的浪 费，为了节省存储空间， 我们可以对这 类矩阵进行压缩存储： 即为多个相同的非零元素只分配一个存储 空间； 对零元素不分配空间。5.3.1特殊矩阵l所谓特殊矩阵是指非零元素或零元素的分布 有一定规律的矩阵，下面我们讨论几种特殊 矩阵的压缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质 ：aij=aji 0i,jn-1则称A为对称矩阵。如图5.1便是一个5阶对 称矩阵。对称矩阵中的元素关于

7、主对角线对 称，故只要存储矩阵中上三角或下三角中的 元素。其存储形式如图所示：1 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1图 5.1 对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总 数为： n(n+1)/2因此，我们可以按从上到下、从左到右将这些元 素存放在一个向量sa0n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们 必须在aij和sak之间找一个对应关系。若ij，则ai j在下三角形中。 ai j之前的i

8、 行（从第0行到第i-1行）一共有1+2+i = i(i+1)/2 个元素，在第i行上， ai j之前恰有j个 元素（即ai0,ai1,ai2,aij-1），因此有：k=i*(i+1)/2+j 0kj5.3.2 稀疏矩阵l什么是稀疏矩阵？简单说，设矩阵A中有 s个非零元素，若s远远小于矩阵元素的 总数（即smn），则称A为稀疏矩阵 。l精确地说，设在的矩阵A中，有s个非零 元素。令 e=s/(m*n)，称e为矩阵的稀疏 因子。通常认为e0.05时称之为稀疏矩 阵。用三元组表存储稀疏矩阵l三元组表(1,2,12)(1,3,9),(3,1,- 3),(3,6,14), (4,3,24), (5,2

9、,18), (6,1,15), (6,4,-7) ，加上 (6,7,8)这一对行、列、非零元的个数的 描述，便可代表矩阵M：0 12 9 0 0 0 0 0 0 -3 0 0 150 0 0 0 0 0 0 12 0 0 0 18 0-3 0 0 0 0 14 0 9 0 0 24 0 00 0 24 0 0 0 0 0 0 0 0 0 70 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 00 0 0 0 0 0图5.4 稀疏矩阵M和TM=T=一、三元组顺序表假设以顺序存储结构来表示三元组表， 则可得到稀疏矩阵的一种压缩存储方法 三元顺序

10、表。#define maxsize 10000typedef int datatype;typedef structint i,j;datatype v;triplet;typedef structtriple datamaxsize;int m,n,t; tripletable;稀疏矩阵的转置的实现一个mn的矩阵A，它的转置B是一个nm的 矩阵，且aij=bji，0im，0jn ，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置 换为表B的三元组表b.data，如果只是简单地交 换a.data中i和j的内容，那么要得到按行优先顺 序存储的b.data，就必须重

11、新排列三元组的顺序 。由于A的列是B的行，因此，按a.data的列 序转置，所得到的转置矩阵B的三元组表b.data 必定是按行优先存放的。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v 7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8mb?Y解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)

12、为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进 行转置。为找到M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由 此得到的恰是mb中应有的顺序。 算法描述：P99 算法5.1Y算法分析：T(n)=O(M的列数n非零元个数t)， 若 t 与mn同数量级，则三元组表的转置算法演示6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbqp p pp p p ppq q q qp p p p p p p pcol=1col=2方法二：快速转置 即按ma中三元组次序转置，转置结果放入b中恰当位置 此法关键是要预先确定