软件技术基础2_3.ppt

1、第二章基本数据结构及其运算、*2.4数组2.4.1数组的顺序存储结构2.4.2规则矩阵的压缩2.4.3一般稀疏矩阵的表现、2.4.1数组的顺序存储、一、数组的定义数组是同种数据元素的有限集合数组内的各组件称为数组元素各数组元素的值数组中的所有元素具有相同的特性。 每个数组元素由数组名称和下标组成。 每个具有下标值的数组元素都有与该下标值相对应的数组元素值。 二维阵列三维阵列，行向量下标I页向量下标I列向量下标j行向量下标j列向量下标k，二，以逻辑结构形式定义，二维阵列2_Array=(D， R) D是某个数据类型的有限元集合，并且是D=aij|i=c1的R=ROW、COL、ROW=|c1id1

2、、c2jd2-1、aij、aij 1 D0 COL=|c1id1-1、c2jd2、aij、ai1jd0二、数组元素之间的函数可以认为是对m个或n个一维阵列3360 a-Mn=(a 11 a-12 a-1 n )、(a21a22a2n )、 (am1am2amn ) )、三维阵列的操作。 指定下标以更改相应数组元素的值。 四、数组的顺序存储结构，因为数组元素是连续存储的，所以采用顺序存储结构。 无论二维阵列，均以一维阵列存储在校正计算机中。 数组存储通常根据行优先级(Pascal，c )来存储列优先级(Fortran )，1 .根据行优先级来存储结构，例如，可以将二维数组Amn认为是m个行向量，

3、每个行向量的n个元素。 数组中的每个元素由元素的两个下标表达式唯一确定。 地址校正公式： loc (AIJ )=loc (a 11 ) (I-1 ) n (j-1 ) ) l其中，l是各要素所占据的存储单元。 二维阵列是按每行优先存储的例子，loc (a 23 )=loc (a 11 ) (2-1)4(3-1)=7loc (a 34 )=1(3)，例如，二维阵列Amxn可以看作n个列向量、各列向量的m个元素。 数组中的每个元素由元素的两个下标表达式唯一确定。 地址修正公式： loc (AIJ )=loc (a 11 ) (j-1 ) * m (I-1 ) ) * l其中，l是各要素所占据的存储

4、单元。 二维数组按列优先存储示例，这些矩阵通常被压缩以节省loc (a 23 )=loc (a 11 ) (3-1) *4(2-1)=10 loc (a 34 )=1(4-1)存储空间。 压缩是指具有相同值的多个元素占用一个存储单元零元素不分配存储单元。 另一方面，也可以采用压缩存储的矩阵，对称矩阵3360存储主对角线以上(下)的元素，上(下)三角矩阵3360仅存储三角数组元素，条矩阵3360仅存储条元素，稀疏矩阵3360仅存储非零元素，二、下三角矩阵的行主压缩存储器、列主压缩存储器、三角、对称矩阵压缩存储器和对称矩阵元素将n*n个元素压缩存储到n(n 1)/2个单元格的一维阵列S(n 1)*

5、n/2 )，以满足aij=aji 1 i，j naij的地址是：对称矩阵的压缩存储示例，一维数组S6 S6=(a11，a21，a22，a31，a32，a 33 ) 12356 loc (a 31 )=3-1)/2=4loc (a 22 )=2(2-1)/2=3loc (a 21 ) 对角矩阵的压缩存储器是行主存储：列主存储：2.4.3一般稀疏矩阵的表示，如果一个矩阵的大部分元素值为零，大部分元素值为非零，就把该矩阵称为稀疏矩阵。1、3列的2维数组表示(1)存在非零元素的行号I。 (2)非零要素存在的列号j (3)非零要素的值v。 也就是说，每个非零元素可以由三组(I，j，v )表示，例如，稀疏

6、矩阵a中的8个非零元素，可以由八组(1，3，3 )、(1，8，1 )表示的非零元素用一个三元组表示(I，j，t )其中I表示稀疏矩阵的总行数，j表示稀疏矩阵的总列数，t表示稀疏矩阵中非零元素的数。 可由九个三维组(7，8，8 ) (3，1，9 ) (5，7，6 ) (6，6，3 ) (1，3，3 ) ()表示稀疏矩阵a，为了使每一三维组的结构更紧凑，通常将这些三维组组织成三列二维表的形式，通常以三列二维阵列的形式为了便于在3列二维阵列b中访问稀疏矩阵a的各元素，通常附设两个与稀疏矩阵a的行数相同长度的向量POS和NUM，POS(k )表示稀疏矩阵a的第k行的最初的非零元素(如果有)在3列二维阵列b中的行号，NUM(k )表示稀疏用2pos(k)pos(k-1)10num(k-1 )、2 k m、2、线性链表表示，具有在稀疏矩阵运算后的非零元素个数发生变化的情况下采用三列二维的关系的节点定义是行域、列域、值域、下域、右域这5个域十字链表表示稀疏矩阵，(1)稀疏矩阵的各行和各列用具有报头节点的循环链表表示。 (2)将报头节点中的行字段和列字段的值都设为0 (也就是说，row0、col0)。 (3)使用行、列链接表的报头节