第五章数组精要.pptVIP

理解数组的逻辑结构定义及存储，掌握数组的存储结构，稀疏矩阵的存储及运算。 教学重点与难点： 数组的存储结构，稀疏矩阵的存储 。 思考 1. 数组的存储结构采用_______存储方式 2. 判断对错：数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。 数组的逻辑结构 数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。 在数组中通常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 数组的内存映像 通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。 对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式： 一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C 等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。 另一种是以列为主序（先列后行）的顺序存放，如FORTRAN 语言中，用的是以列为主序的分配顺序，即一列一列地分配。 例1：一个2×3 二维数组，逻辑结构可以用图1表示。以行为主序的内存映象如图2所示。分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ; 它的内存映象如图3所示。 问题总结：存储位置与数组下表之间的映射关系是什么？ 设有m×n 二维数组Amn，以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，那么aij 的物理地址可用一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L 推广到一般的三维数组：A[c1..d1] [c2..d2] [c3..d3]，则Aijk 的物理地址为： LOC(Aijk)=LOC(Ac1c2c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3))*L 例题 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储,假设存储数组元素A[1，0]的第一个字节的地址是0，若按行存储，则A[2，4]的第一个字节的地址是多少？若按列存储，则A[5，7]的第一个字节的地址是多少？ 1.对称矩阵 对称矩阵的特点是：在一个n 阶方阵中，有aij=aji ，其中1≤i , j≤n，如图5.5 所示是一个５阶对称矩阵。 1.对称矩阵 对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则它在SA 中的下标k 与i、j 的关系为： k=I*(I-1)/2+J-1 例：设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 2.三角矩阵 形如图2的矩阵称为三角矩阵，其中c 为某个常数。其中图2（a）为下三角矩阵：主队角线以上均为同一个常数；(b)为上三角矩阵，主队角线以下均为同一个常数；下面讨论它们的压缩存储方法 2.三角矩阵- 下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可。 2.三角矩阵- 上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。 3.带状矩阵 n 阶矩阵A 称为带状矩阵，如果存在最小正数m ，满足当∣i-j∣≥m 时，aij =0，这时称w=2m-1 为矩阵A 的带宽。 1.稀疏矩阵的三元组表存储 设m*n 矩阵中有t 个非零元素且tm*n，这样的矩阵称为稀疏矩阵。 将非零元素所在的行、列以及它的值构成一个三元组（i,j,v）,再将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。 1.稀疏矩阵的三元组表存储 1.设数组a[1..50,1..80]的基地址为1000，每个元素占4个存储单元，若以列序为主序顺序存储，则元素a[45,68]的存储地址为