• 1. 第5章 数组 数组的特点。 数组的存储。 几种特殊矩阵的存储及运算。 本章要点:
  • 2. 数组和广义表,可以看成是一种扩展的线性数据结构,其特殊性不像栈和队列那样表现在对数据元素的操作受限制,而是反映在数据元素的构成上。通过数组、广义表的学习,将数据结构形式由线性向非线性结构过渡。在线性表中,每个数据元素都是不可再分的原子类型;而数组和广义表中的数据元素可以推广到是一种具有特定结构的数据。本章以抽象数据类型的形式讨论数组和广义表的逻辑定义、存储结构、操作的实现,加深对这两种特殊的线性结构的理解。
  • 3. 5.1 数组的定义和运算 数组是十分熟悉的一种数据类型,很多高级语言都支持数组这种数据类型。从逻辑结构上看,数组可以看成是一般线性表的扩充。二维数组可以看成数据元素是由一维数组组成的线性表,下面以二维数组为代表讨论。如图5.1所示的二维数组,把二维数组中的每一行i(i=1..n)作为一个元素,可以把数组看成是由n个元素1,2, n组成的线性表。其中i (1≤i≤n)本身也是一个线性表即向量,i=(a i1,a i2,…,a i j,… ,a i n)是一维数组,如图5.2所示。同理也可以将数组的某一列(一个向量)做为基本数据元素βj=(a1j,a2j,…,aj j,…,an j)。数组可看成是线性表的推广。
  • 4. 图5.2 向量表示数组的行或列图5.1 二维数组a11 a1 2 … a1 j … a1 n a2 1 a2 2 … a2 j …a2 n ┇ ┇ ┇ ┇ ai 1 ai 2 … ai j … ai n ┇ ┇ ┇ ┇ am 1 am 2 … am j… am na11 a12…a1j …a1n a21 a22 …a2j …a2n ┇ ┇ ┇ ┇ ai1 ai2… ai j …ai n ┇ ┇ ┇ ┇ am1 am2…am j…am n(β1 β2 …βj … βn)( )1 2 ┇ i ┇ m5.1 数组的定义和运算(续)
  • 5. 二维数组的逻辑结构可形式地表示为: 2—Array=(D,R) 其中: D={ai j丨ai j∈D0,i=c1,c1+1,…,d1,j=c2,c2+1,…,d2, c1≤d1,c2≤d2, (c1,d1,c2, d2 )∈整数} R={ROW,COL} ROW={丨ai j,ai j+1∈D,c1≤i≤d1,c2≤j丨c1≤i≤d1-1,c2≤j≤d2,ai j,ai+1 j∈D} D0为某个数据对象。二维数组中含有(d1-c1+1)(d2-c2+1)个数据元素,每个数据元素ai j都受两个关系:ROW(行关系)和COL(列关系)的约束。ai j+1是ai j的直接后继元素;而ai+1 j是ai j在列关系中的直接后继元素。和线性表一样,所有的数据元素都必须属于同一数据对象类型。每个数据元素对应于一组下标(i,j)。(c1,d1)和(c2,d2)分别为下标i和j的一对界偶(即i和j的上界和下界)。
  • 6. 5.1 数组的定义和运算(续)同样三维数组中的每个元素ai j k都属于三个向量,每个元素有三个前趋和三个后继,可以理解三维数组是由二维数组为基本元素的线性表。推而广之n维数组可以理解为由n-1维数组组成的线性表。三维数组的逻辑结构的形式定义如下: n_Array=(D,R) 其中: D={aj1 …ji …jn | ji =ci … di , i=1…n(n>0) , aj1 …ji …jn∈D0且ci 、 di均为正数} R={R1,R2,…,Rn} Ri={ | jj =cj … dj , j=1…n(j<>i) , ji =ci … di -1 , aj1 …ji …jn , aj1 …ji+1 …jn ∈D0}
  • 7. 5.1 数组的定义和运算(续) 可见n维数组含有: (d1-c1+1)*(d2-c2+1)*…*(dn-cn+1)个数据元素,每个元素都属于n个“线性表”,每个数据元素都受着n个关系的约束,在n个方向上有n个前趋和n个后继。 对于n维数组,则存在着n对界偶(c1,d1),(c2,d2),…(cn,dn),分别对应其n个下标j1,j2 ,…,jn,。由此可见,n 维数组是一种较复杂的数据结构,但由于数组中各元素有统一的类型并且在通常的讨论中,数组元素的下标具有固定的上界和下界,因此数组的处理与其它复杂结构相比较为简单。
  • 8. 数组的基本操作:  ⑴ Initarray(A, n, bound1, …, boundn):构造相应的数组A的存储空间,n是维数, boundi=di-ci+1,如果各维的长度合法,则构造相应的数组A的存储空间,并返回TRUE。 ⑵ Destroyarray(A):撤销数组A,释放空间。 ⑶ Getvalue(A,e, index1, …, indexn):若下标合法,则用e返回数组A中由index1,…, indexn下标所指定的元素的值。即给出一组下标,取相应的数据元素; ⑷ Setvalue(A,e,index1, …, indexn):若下标合法,则将数组A中由index1, …, indexn所指定的元素的值置为e。即给定一组下标,修改相应数据元素中的某一个或几个数据项的值。 这里定义的数组,与C语言的数组略有不同,下标是任意整数开始,而C语言要求从零开始的。在具体问题中可以将下标转换到从零开始。
  • 9. 5.2 数组顺序存储结构 一般说来,数组一旦建立,则结构中的数据元素个数和元素之间的关系就不再发生变动(因为一般数组不做插入、删除操作,不移动元素),所以采用顺序存储结构存储数组是很合适的。 在计算机中,内存储器的结构是一维的。用一维的内存表示多维数组,就必须按某种次序,将数组元素排成一个线性序列,然后将这个线性序列存放在存储器中。比如二维数组的顺序存储可以有两种方式:一种是按行序存储,另一种是按列序存储。如高级语言BASIC、Pascal、C语言都以行序为主存储,Fortran语言以列为主存储。
  • 10. 5.2 数组顺序存储结构(续) 显然,二维数组Am×n以行为主的存储序列 (row major order),是将元素按行排列,顺序为第i+1行紧很在第i个行后面,于是便可以得到以下线性化的序列:(a1 1,a1 2,…,a1 n),(a2 1,a2 2,…,a2 n),(a3 2,a3 2,…,a3 n),…,(am 1,am 2…,am n) 的存储结构。如图5.3(a)所示。图5.3(b)是将数组元素按列向量排列,存储的线性化的序列为:(a11,a21,…,am1);(a12,a22,…,am2);…(a1i,a2i,…,ami);…(am1,am2,…,amn)。C语言是按行序方式存储的,所以以下涉及的数组存储均采用行序为主序存储。
  • 11. 5.2 数组顺序存储结构(续)(a)以行方式存储 (b)以列方式存储 图5.3 二维数组的两种存储方式
  • 12. 5.2 数组顺序存储结构(续) 在数组中若要检索某个元素,就要得到这个元素的存储位置。每个元素的存储位置可以通过数组各维的界偶、第一个元素的存放地址、元素的下标和每个元素在内存中占用的单元数计算得出。假设二维数组Am×n(行:1..m,列:1..n)每个元素占L个存储单元,以行为主序存储,元素aij地址计算函数为: LOC(ai j)=LOC(a11)+[(i-1)×n+(j-1)]×L 上面我们是以数组各维的下标从1开始的,不失一般性,二维数组Am×n(行:c1..d1,列:c2..d2)每个元素占L个存储单元,我们得到元素aij地址计算函数为: LOC(aij) [i,j]=LOC(ac1,c2)+[(d2-c2+1)(i-c1)+(j-c2)]×l
  • 13. 5.2 数组顺序存储结构(续) 二维数组只有行和列,按行方式存储时,存储顺序是行号从小到大,同行内先存放列号小的。那么三维数组如何存放?有Ak×m×n以k=1‥3,m=1‥3,n=1‥4为例。在行序为主的序列中,依照存储第一维下标由小到大的顺序存储;第一维下标相同时依照第二维下标由小到大的顺序存储;第二维下标相同时依照第三维下标由小到大的顺序存储。图5.4是图示三维数组的存储顺序,首先存储的是三维数组中第一维下标k=1的,图5.4中的第一层(平面)。在同一层内按二维数组的存储方式,即按第二维下标从小到大依次存储,在平面中每行内,按第三维下标从小到大依次存储。
  • 14. 5.2 数组顺序存储结构(续)                                m n a111 a112 a 113 a 114 a121 a 122 a 123 a 124 a 131 a 132 a 133 a 134   a 211 a212 a 213 a 214 a 221 a 222 a 223 a 224 a 231 a 232 a 233 a 234   a 311 a312 a313 a 314 a 321 a 322 a323 a324 a331 a332 a 333 a 334 第一层       第二层       第三层 图5.4 三维数组的存储结构 k
  • 15. 5.2 数组顺序存储结构(续) 例如求元素a233的存储位置。a233元素为图5.4中立体中画阴影元素。 要求某一个元素的存储位置,首先要求出该元素前面存放了多少个元素,然后再与第一个元素的存储位置求和即可求解。在三维数组中,某一个元素之前存放的元素个数是多少?先要按图5.4找出该元素所在平面pm,然后要求出在元素所在平面内该元素所处的行hs,还有该元素在所在的行存储在第几个位置hw。我们知道图5.4中一个平面内元素个数为:pms=m×n,每个平面内有m行,每行中元素个数为n。则元素a233前面存储的元素个数为: (pm-1)*(pms)+(hs-1)*n+hw-1=(2-1*)*12+(3-1) *4+(3-1)=22
  • 16. 5.2 数组顺序存储结构(续) 不失一般性,如果三维数组的下标界偶分别为(c1,d1)、(c2,d2)、(c3,d3)按图5.4 就可以划分成d1-c1+1个平面(或层)。元素ai j r前存储的数据元素个数为: (i-c1) ×(d2-c2+1)×(d3-c3+1)+(j-c2)×(d3-c3+1)+(r-c3) 通过运算我们可以求出ai j r的存储位置。 可以推广到n维数组中的数据元素存储位置的计算函数,请同学们思考!
  • 17. 5.3 矩阵的压缩存储 二维数组可以来存储矩阵元素。有的程序设计语言中还供了各种矩阵运算,给用户使用带来很大的方便。然而,在数值分析中经常出现一些高阶矩阵,在这些高阶矩阵中有许多值相同的元素或者是零元素,为了节省存储空间对这类矩阵采用多个值 相同的元素只分配一个存储空间,有时零元素不存储的存储策略,称为矩阵的压缩存储。 如果值相同的元素或者零元素在矩阵中的分布有一定规律,称此类矩阵为特殊矩阵。还有一类矩阵非零的数据元素个数很少称为稀疏矩阵。下面分别讨论这两类矩阵的压缩存储。
  • 18. 5.3.1 特殊矩阵 这里只讨论最常见的几种特殊矩阵。 1.    对称矩阵与上下三角阵 若一个n阶矩阵的主满足ai j=aj i 1≤i,j≤n,则称该矩阵为n阶对称矩阵。 由于对称矩阵有上述性质,可以为每一对对称元分配一个存储空间,这样就将n2个元的存储空间压缩成n(n+1)/2个单元的存储空间,以行序为主序存储对称矩阵的下三角(包括对角线)的元素。 假设以一维数组sa[1..MAX](MAX>(1+n)×n/2)作为n阶对称矩阵A的存储结构,按存储下三角中的元素,上三角中的元素到对称的位置取,则矩阵中任意元素ai j 存放在一维数组sa[k]的对应的关系为:
  • 19. 5.3.1 特殊矩阵(续) k= 如果将a11存储在sa数组下标为1的单元中,当数据元素ai j在下三角中时1≤j≤i≤n,存储位置为:i(i-1)/2 +j 否则该元素在上三角中,我们可以到对称的位置取元素。矩阵中对于任意给定一组下标(i,j),均可在sa中找到矩阵元素ai j 。反之,对所有的k=1,2,…,n(n+1)/2,都能确定sa[k] 中的矩阵元在矩阵中的位置(i,j)由此,称sa【1..n(n+1)/2+1】为n阶对称矩阵A的压缩存储,如图5.5(a)为对称矩阵A,图5.5(b)为A矩阵的压缩存储结构。 i(i-1)/2+j 当i>=j j(j-1)/2+i 当i
  • 20.                     下三角中元素存储在sa数组中的位置: k=i*(i+1)/2+j   sa a11 a21 a22 … a i j … 0 1 2 3 k a11 a12 a13 … a1 n a21 a 22 a 23… a 2n a31 a 32 a 33… a 3n ……………… an1 a n2 a n3…a n n(a)对称矩阵A (b)矩阵A存储在一维数组sa中 图5.5对称矩阵的压缩存储  这种压缩存储方法同样适合于三角矩阵,包括:上三角和下三角矩阵。所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶对称矩阵,它的存储只需要在上(下)三角中的元素和一个常数c的存储空间。 5.3.1 特殊矩阵(续)
  • 21. 5.3.1 特殊矩阵(续) 如果图5.5(a)中只有阴影部分元素非零,其余部分元素为常数c,就是下三角矩阵。下三角矩阵可以用相似对称矩阵的存储方法存储,可以将图5.5(a)中阴影部分元素按图5.5(b)中形式存储在数组sa中,将常数c存储在数组sa的0下标内。对称矩阵压缩存储到一维数组中后,矩阵元素ai j下标与一维数组sak下标对应关系为: i×(i+1)   i *(i+1)/2+j ( i ≥ j ) K = 0 ( i < j) 按图5.5(a)中,矩阵只有上三角部分,同样方法导出上三角矩阵压缩存储在一维数组中对应的存储关系。常数存放在sa数组0下标中,ai j对应存储关系为: (2n-i+2)×(i+1)     (2n-i+2)*(i+1)/2+j (j ≥ i ) K = 0 ( i >j)
  • 22. 5.3.1 特殊矩阵(续) 2. 三对角矩阵 在数值分析中经常出现的还有一类特殊矩阵是对角矩阵。在这种矩阵中所有非零元集中在主对角线为中心的带状区域中,如图5.6(a)所示。对于对角矩阵我们按某个原则(或以行为主,或以对角线的顺序)将其压缩存储到一维数组上。 在三对角矩阵里,除了三个对角上的元素外,其它元素都是零,数据元素可以表示为:aii=非零元素 (︱i-j︱≤1) 0 (︱i-j︱>1)
  • 23. 5.3.1 特殊矩阵(续) 如何将ai j元素与一维数组的下标k对应?按行方式存储数据,应该先存储行号小于i的,即:1~i-1行。前i-1行共有非零元3(i-1)-1个,第i行ai j元素前还有非零元素个数为j-(i-1),因此非零元素按行顺序存储方式,aij元素前存放元素个数为: 3(i-1)-1+j-(i-1)=2i+j-3 aij元素的地址可用下式求出: LOC(ai j)=LOC(a11)+2×(i-1)+j-1 其中: 1≤i≤n,j=i-1,i,i+1
  • 24. 5.3.1 特殊矩阵(续)n条对角线 0 a11 a12 a21 a22 a23 0 n列 0 an-1 n 0 an n-1 an n (a)一般情形 (b) 三对角矩阵 图5.6 对角矩阵
  • 25. 5.3.2 稀疏矩阵 在特殊矩阵中,非零元都有明显的规律,从而都可以压缩到一维数组。然而,实际应用中经常会遇到一类矩阵,其非零元少,且分布没有明显的规律,称之为稀疏矩阵。例如图5.7(a)中的M是一个6×7的稀疏矩阵,只有8个非零元。按压缩存储的思想,只存储稀疏矩阵中的非零元。为了便于检索和存取,在存储中必须带有适当的辅助信息,既同时记下它所在行和列的位置。下面介绍两种方法。 1.三元组表示法及转置运算
  • 26. 5.3.2 稀疏矩阵(续) 一个三元组(i,j,ai j)可唯一确定了矩阵M的一个非零元。由此,稀疏矩阵由表示非零元的三元组线性表确定,图5.7(b)表示的是M矩阵的三元组构成。这个三元组是否与矩阵M一一对应?如果在M矩阵中再增加一行第七行,且第七行元素均为零。再用三元组表示这个矩阵,仍然是图5.7(b)。这说明表示稀疏矩阵只有一个三元组表是不够的,还需要表示矩阵的行数和列数,才能唯一对应。三元组表加上稀疏矩阵的行数和列数值描述,就可以得到稀疏矩阵的压缩存储的三元组表示法。
  • 27. 5.3.2 稀疏矩阵(续)0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 –7 0 0 0M= (b) 图5.7稀疏矩阵及三元组表示ijv112122139331-343614543246521876115864-7
  • 28. 5.3.2 稀疏矩阵(续)数据类型说明如下: typedef struct { int i,j; /*行号、列号*/ elemtype v; /*非零元素*/ }tuple3tp; typedef struct { int mu,nu,tu; /*行数、列数和非零元素的个数*/ tuple3tp data[maxnum]; /*三元组表*/ }sparmattp;
  • 29. 5.3.2 稀疏矩阵(续) 三元组表示稀疏矩阵,如何实现转置运算?矩阵的转置是最简单的矩阵运算,对于一个m×n的矩阵M它的转置矩阵N是一个n×m的矩阵,且N(i,j)=M(j,i) 1≤i≤n 1≤j≤m。例如图5.7(a)和图5.8(a)中M与N互为转置矩阵,显然,一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。假设a,b是sparmattp型的变量分别表示矩阵M和N。下面的问题是如何由a得到b呢? 三元组表示的稀疏矩阵转置时将每个三元组中的行号、列号交换,并按新的行号(转置前的列号)排列三元组,因为我们所有的存储方式都是行方式存储。5.8(b)是N矩阵的三元组表示。
  • 30. 5.3.2 稀疏矩阵(续)实现转置操作主要有两步: (1)  在三元组表中,将i,j值交换; (2)重新排列三元组之间的次序便可矩阵的转置。 N =0 0 –3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 –7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 (a)M的转置 (b)N的三元组表 图5.8ijv113-3216153211242518531963424746-786314
  • 31. 5.3.2 稀疏矩阵(续) 第一步很容易,第二步实质是如何实现使b.data三元组以矩阵N的行(M的列)为存储主序来存储。 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置,即按照矩阵M的序列进行转置。为了找到M的每一列中所有的非零元素,需要对其三元组表a.data从第一行起整个扫描一遍,由于a.data是以M的行序为主为存放每个非零元的,由此得到的恰是b.data应有的顺序,算法如下:
  • 32. 5.3.2 稀疏矩阵(续)traxs_sparmat(sparmattp M, sparmattp *N) { /*求三元组矩阵M的转置,并将结果存放在N中。*/ N->mu=M.mu; N->nu=M.nu;N->tu=M.tu; if (N->tu!=0) { q=1; for(col=1;col<=M.nu;col++)/*列号col从1~M.nu循环 */ for(p=1;pdata[q].i=M.data[p].j; N->data[q].j=M.data[p].i; N->data[p].x=M.data[p].x } } }
  • 33. 5.3.2 稀疏矩阵(续) 2.十字链表 当矩阵非零元的位置或个数变动时,三元组就不适合作稀疏矩阵的存储,这时采用链表存储结构更恰当。 稀疏矩阵的十字链表(orthgcoral list)表示法是将矩阵中的每个非零元用一个结点来表示。这种结点有五个域组成,如图5.9(a)。 (a)非零结点 (b)行列结点 (c)总表头 图5.9 十字链表结点 其中:行域(row)、列域(col)、值域(val)分别表示非零元所在的行号、列号和数值。向下域(down)用于链接同一列中下一个非零元素的结点,向右域(right)用以链接同一行中下一个非零元素的结点。这样一来,表示上一行中非零元的结点之间构成一个链表,表示上一列中非零元的结点之间也构成一个链表,把每行、列的链表用循环线性链表来表示,且使第k行和第k列的两个表头联合用一个表头结点。 0nextdownrightmnnext不用不用rowcolvaldownright1
  • 34. 5.3.2 稀疏矩阵(续)这种行(列)表头结点也由五个域组成,如图5.8(b)所示,其中相应的col,row域内输入零,next域链接下一行(列)循环线性链表的表头结点。且设置总表头结点,为了使结点上格式统一,总表头结点也用五个域,如图5.8(c)所示,其中m、n为稀疏矩阵行数和列数。 如何实现建立十字链表的算法?图5.9(a)中(row,col,val)简写为(r,c,v),其中:r为行号,c为列号,v为数值。建立十字链表的算法描述如下。 ⑴ 输入稀疏矩阵的行数m,列数n及非零元个数t,然后使s=max(m,n)。 如s=0则只建立一个总表头便结束(此时矩阵没有非零元),否则建立s个行(列)表头结点。设立一个向量h1,其每个分量就是各行(列)表头指针h1[i] ⑵ 循环实现:以行优先顺序依次将t个非零元输入,再插入到相应行(列)的链表中。 ⑶建立完行(列)循环线性链表后,再建立总表头结点h,最后完成行(列)循环线性链接。
  • 35. 5.3.2 稀疏矩阵(续)稀疏矩阵及其十字链表表示如图5.10所示。5 4     0 0     0 0     0 0     0 0     0 0     0 0     1 1 3   0 0     0 0     0 0     4 1 2   3 2 4   5 2 8   5 4 6   0 0     (a) (b)M矩阵的十字链表表示 图5.10十字链表表示例子 M= 3 0 0 0 0 0 0 0 0  4 0 0 2 0 0 0 0 8 0 6