数结_4数组j1.ppt

1、第五章数组,数组 5.1 数组的定义 5.2 数组的表示与实现 5.2.1 行主序/列主序存储方式 5.2.2 地址计算 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.2.2 稀疏矩阵 三元组表 行向量链表 十字链表,4.1 数组的定义,可以从两个层面理解数组元素之间的逻辑关系。,对于一维向量： a1, a2, ., ai-1, ai, ai+1, ., an-1, an 每个结点至多有一个直接前驱，至多有一个直接后继,ai+1是ai的直接后继,ai1是ai的直接前驱,对于二维数组Amn,结点aij处在两个向量的交汇点上，至多有两个直接前驱，两个直接后继。,aij,ai-1 j,ai j1

2、,ai j1,ai+1 j,ai j,第 i 行 .,.,第 j 列,aij的两个直接前驱,aij的两个直接后继,a11 a12 . a1j . a1n a21 a22 . a2j . a2n . . ai1, ai2 . aij . ain . . am1 am2 . amj . amn,a11只有两个后继，没有前驱,am1有一个前驱和一个后继,位于边界上的结点，可能只有一个前驱或一个后继,am2有两个前驱和一个后继,二维数组Amn的形式定义： 数据对象： D= aij | i=1,2,.,m; j=1,2,.,n; aijElemSet 数据关系： R= Row, Col Row= | 1

3、im, 1jn-1 Col = | 1im-1, 1jn ,依此类推，在三维数组中结点aijk处在三个向量的交汇点上。除了边界上的结点外，每个结点有三个直接前驱和三个直接后继。,一般在n维数组中，每个结点处在n个向量的交汇点上，除了边界上的结点外，每个结点有且仅有n个直接前驱，n个直接后继: Ab0b1.bn-1 -b0 , b1,., bn-1每维的长度 数据关系：R R1,R2, ., Rn Ri= | 0jkbk1，1kn，ik 0ji bi2 ,数组的基本运算：,初始化： InitArray( /数组基地址 int dim; /数组的维数 int *bounds; /存放每维长度的数组

4、 int *constants; /存放计算地址的系数的数组 Array;,Ab1b2b3.bn,A.constants,基本运算的函数原型： Status InitArray (Array ,传递数组每维的长度b1,b2,.,bn。参数的数目不固定。,传递数组元素的下标j1,j2,.,jn。参数的数目不固定。,C语言提供了三个宏，用来读取变长参数表： typedef void * valist va_start (valist ap, lastfix); /将ap指针定位于最后一个固定参数lastfix之后的位置上 va_arg (valist ap, Type); /按Type类型返回当前

5、ap所指的参数的值 /再将ap指针右移 va_end(valist ap); /调用结束,Status InitArray(Array ,数组 5.1 数组的定义 5.2 数组的表示与实现 5.2.1 行主序/列主序存储方式 5.2.2 地址计算 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.2.2 稀疏矩阵 三元组表 行向量链表 十字链表,4.3 矩阵的压缩存储,压缩存储的前提：当矩阵中含有大量零元素或值相同的元素； 压缩存储的方法：零元素不分配空间，同值元素共享一个存储空间； 根据零元素或值相同的元素在矩阵中分布是否有规律，可将矩阵分为两类： 特殊矩阵 稀疏矩阵,4.3.1特殊矩阵,一

6、、对称矩阵 aij=aji,将矩阵的下三角部分按行主序的次序压缩存储到一维数组Bn(n+1)/2中,a11, a12, ., a1j, ., a1n a21, a22, ., a2j, ., a2n . . ai1, ai2, ., ai j, ., ain . . a n1, an2,., anj, .,ann,Ann,设元素aij在B数组中的下标是K， BK=aij 关键问题是如何通过下标(i, j)来计算K K aij在行主序下的排列序号1,B,aij的前面有i1行，共有i (i1)/2个元素 在第 i 行上，aij是第 j 个元素，所以有： i (i1)/2j1 当 i j (aij位

7、于下三角)时 j (j1)/2i1 当 i j (aij位于上三角)时,二、三角矩阵,a 11 a12 a13 . a1n a22 a23 . a2n a33 . a3n . . ann,C,下三角矩阵,上三角矩阵,n(n+1)/2,下三角矩阵:,K,i (i1)/2j -1 当 i j (aij位于下三角)时 n(n+1)/2 当 i j (aij位于上三角)时,上三角矩阵:,K,(i1)(2ni2) / 2ji 当 i j (上三角)时 n(n+1) / 2 当 i j (下三角)时,n(n+1)/2,第 t 行有 nt+1 个元素，前 i1行共有 （nt+1）(i1)(2ni2) / 2 在第 i 行上，aij是第 ji1个元素，所以,i1,t=1,三、对角矩阵,a11 a12 a2