第5章数组和稀疏矩阵 5.1数组 5.2稀疏矩阵 本章小结
第5章 数组和稀疏矩阵 5.1 数组 5.2 稀疏矩阵 本章小结
5.1.1数组的基本概念 数组是n(n>1)个相同类型数据元素a1;a2…,n构 成的有限序列,且该有限序列存储在一块地址连续的 内存单元中。 由此可见,数组的定义类似于采用顺序存储结构 的线性表
5.1.1 数组的基本概念 数组是n(n＞1)个相同类型数据元素a1 ,a2 ,…,an构 成的有限序列,且该有限序列存储在一块地址连续的 内存单元中。 由此可见,数组的定义类似于采用顺序存储结构 的线性表
数组具有以下性质: (1)数组中的数据元素数目固定。一旦定义了一个 数组,其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。 (3)数组中的每个数据元素都和一组惟一的下标值 对应。 (4)数组是一种随机存储结构。可随机存取数组中 的任意数据元素
数组具有以下性质： (1)数组中的数据元素数目固定。一旦定义了一个 数组,其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。 (3)数组中的每个数据元素都和一组惟一的下标值 对应。 (4)数组是一种随机存储结构。可随机存取数组中 的任意数据元素
5.1.2数组的存储结构 在一维数组中,一旦a1的存储地址LoCa1)确定,并假 设每个数据元素占用k个存储单元则任一数据元素a 的存储地址LOC(a)就可由以下公式求出: LOC(a =LOC(a+(i-1)*k(Osisn) 上式说明,一维数组中任一数据元素的存储地址可 直接计算得到,即一维数组中任一数据元素可直接存 取,因此,一维数组是一种随机存储结构。同样,二维及 多维数组也满足随机存储特性
5.1.2 数组的存储结构 在一维数组中,一旦a1的存储地址LOC(a1 )确定,并假 设每个数据元素占用k个存储单元,则任一数据元素ai 的存储地址LOC(ai )就可由以下公式求出： LOC(ai )=LOC(a1 )+(i-1)*k (0≤i≤n) 上式说明,一维数组中任一数据元素的存储地址可 直接计算得到,即一维数组中任一数据元素可直接存 取,因此,一维数组是一种随机存储结构。同样,二维及 多维数组也满足随机存储特性
对于一个m行n列的二维数组Amxn有: l.1 1,2 2.1 2,2 2,n nxh ,1 2 n 将Ann简记为A,A是这样的一维数组: A=(a 19a2··ai a m 其中,a1=a1;a12…,1n)(1≤≤m)
= m m m n n n m n a a a a a a a a a A ,1 ,2 , 2,1 2,2 2, 1,1 1,2 1, 对于一个m行n列的二维数组Am×n ,有： 将Am*n简记为A,A是这样的一维数组： A=(a1 ,a2 ,…,ai…,am) 其中,ai=(ai,1 ,ai,2 ,…,ai,n) (1≤j≤m)
显然,二维数组同样满足数组的定义。一个 二维数组可以看作是每个数据元素都是相同类 型的一维数组的一维数组。以此类推任何多维 数组都可以看作一个线性表,这时线性表中的每 个数据元素也是一个线性表。多维数组是线性 表的推广
显然,二维数组同样满足数组的定义。一个 二维数组可以看作是每个数据元素都是相同类 型的一维数组的一维数组。以此类推,任何多维 数组都可以看作一个线性表,这时线性表中的每 个数据元素也是一个线性表。多维数组是线性 表的推广
对于二维数组来说由于计算机的存储结构是线 性的如何用线性的存储结构存放二维数组元素就 有一个行/列次序排放问题。 以行序为主序的存储方式:即先存储第1行,然 后紧接着存储第2行,最后存储第m行。此时,二维数 组的线性排列次序为: a 1,1a1,29a1,na2,1a2,2°a2,nam,1%am,2am,n
对于二维数组来说,由于计算机的存储结构是线 性的,如何用线性的存储结构存放二维数组元素就 有一个行／列次序排放问题。 以行序为主序的存储方式：即先存储第1行,然 后紧接着存储第2行,最后存储第m行。此时,二维数 组的线性排列次序为： a1,1 ,a1,2 ,…,a1,n,a2,1 ,a2,2 ,…,a2,n,…,am,1 ,am,2 ,…am,n
对一个已知以行序为主序的计算机系统中当二 维数组第一个数据元素a1的存储地址LOC(a1)和每 个数据元素所占用的存储单元k确定后则该二维数组 中任一数据元素a;的存储地址可由下式确定: LoC(a)=LoC(a1,)+(i-1)*n+-1)k 其中n为列数
对一个已知以行序为主序的计算机系统中,当二 维数组第一个数据元素a1,1的存储地址LOC(a1,1 )和每 个数据元素所占用的存储单元k确定后,则该二维数组 中任一数据元素ai,j的存储地址可由下式确定： LOC(ai,j)=LOC(a1,1 )+[(i-1)*n+(j-1)]*k 其中n为列数
同理可推出在以列序为主序的计算机系统中有: LoC(a;j=LOC(a1)+(0-1)m+(1-1)*k 其中m为行数
同理可推出在以列序为主序的计算机系统中有： LOC(ai,j)=LOC(a1,1 )+[(j-1)*m+(i-1)]*k 其中m为行数
例51对二维数组们oata54计算: (1)数组a中的数组元素数目; (2)若数组a的起始地址为2000且每个数组元素长度 为32位(即4个字节),数组元素a3]2的内存地址
例5.1 对二维数组float a[5][4]计算： (1)数组a中的数组元素数目； (2)若数组a的起始地址为2000,且每个数组元素长度 为32位(即4个字节),数组元素a[3][2]的内存地址