《数据结构》课程教学资源：第五章 数组和稀疏矩阵

第5章数组和稀炬阵 51数组 52稀流矩阵 本章小结

1 第5章 数组和稀疏矩阵 5.1 数组 5.2 稀疏矩阵 本章小结

51数组 数组的定义 数组是n(n>1个相同类型数据元素a1a2y,lan 构成的有限序列,且该有限序列存储在一块地址连 续的内存单元中 2维数组:A(a12…,1,a)随机存取 12 ■■■■■■ ■■■■■■ 设每个数据元素占用k个存储单元则任一数据元 素的存储地址LOC(a就可由以下公式求出: LOC(a=LOC(a)+(D)*(0≤≤n) 2

2 5.1 数组 数组是n(n＞1)个相同类型数据元素a1 ,a2 ,…,an 构成的有限序列,且该有限序列存储在一块地址连 续的内存单元中。 a1 a2 … … ai … … an 设每个数据元素占用k个存储单元,则任一数据元 素ai的存储地址LOC(ai )就可由以下公式求出： LOC(ai )=LOC(a1 )+(i-1)*k (0≤i≤n) 随机存取 数组的定义： 一维数组：An=(a1 a2 … ai … an )

二维数组: am-1,0am-11 可以看成是由m个行向量组成的线性表,即数组可表 示为:Am=(a02a12,a2…,n1) 其中:Q1=(al0 i09i°°ui°9ui,n 每个数据元素相当于一个一维数组 同样地,也可以将数组看成是由n个列向量组成的 3线性表

3 二维数组：                 = − − − − − −  1,0 1,1 1, 1 10 11 1, 1 00 01 0, 1 ... ... ... ... ... ... ... ... ... ... ... m m m n n n m n a a a a a a a a a A ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 可以看成是由m个行向量组成的线性表，即数组可表 示为： 同样地，也可以将数组看成是由n个列向量组成的 线性表。 每个数据元素αi相当于一个一维数组。 ( , ,..., ,..., ) Am = 0 1 i  m−1 其中： ( , ,..., ,..., ) 0 1 , −1 = i ai ai aij ai n 

, n n×n 从逻辑角度来看:数组中的每个元素a均属于两 个向量:第術上的行向量和第列上的列向量。除周 边元素外,每个元素均有两个直接前驱和两个直接 后继 4

4                 = + − + − −  ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 1, , 1 , , 1 1, 00 01 0, 1 i j i j i j i j i j n m n a a a a a a a a A 从逻辑角度来看：数组中的每个元素aij均属于两 个向量：第i行上的行向量和第j列上的列向量。除周 边元素外，每个元素均有两个直接前驱和两个直接 后继

维数组 m维数组An0n1…看作二维数组的推广,其 每个元素均属于m个向量,即受到m个关系的约 束,最多可以有m个直接前驱和m个直接后继

5 • m维数组 看作二维数组的推广，其 每个元素均属于m个向量，即受到m个关系的约 束，最多可以有m个直接前驱和m个直接后继。 M维数组： 0 1 m − 1 A n n … n

数组的特点 1.数组中的数据元素数据固定。一旦定义了 个数组,其数据元素数目不再有增减的变化 2.数组中的数据元素具有相同的数据类型。 3.数组中的每个数据元素都和一组惟一的下标 值对应。 4.数组是一种随机存储结构。可随机存取数组 海中的任意数据元素。 6

6 1. 数组中的数据元素数据固定。一旦定义了一 个数组，其数据元素数目不再有增减的变化。 2. 数组中的数据元素具有相同的数据类型。 3. 数组中的每个数据元素都和一组惟一的下标 值对应。 4. 数组是一种随机存储结构。可随机存取数组 中的任意数据元素。 数组的特点：

数组的基本运算 1.给定下标,存取相应的数据元素。 2.给定下标,修改相应的数据元素。 对于不作删除和插入操 作的数据,应该采用哪种 类型的物理结构呢? 7

7 1. 给定下标，存取相应的数据元素。 2. 给定下标，修改相应的数据元素。 数组的基本运算： 对于不作删除和插入操 作的数据，应该采用哪种 类型的物理结构呢？

数组的存李储:(采用顺序存储结构 一维数组:An=(a1a2 Loc(ai=Loc(a+(i-1)*k 其中:Loc(a1)是a1的存储地址 表示每个数据元素占用的存储单元 多维数组:Amxn 计算机内存:一维结构 数组结构:多维结构 次序约定 以伤序为主序的存方式 以列房为主序的存储方式

8 计算机内存：一维结构 数组结构：多维结构 次序约定 以行序为主序的存储方式 以列序为主序的存储方式 数组的存储：（采用顺序存储结构） 一维数组：An=(a1 a2 … ai … an ) Loc(ai )=Loc(a1 )+ (i-1)*k 其中： Loc(a1 )是a1的存储地址 k表示每个数据元素占用的存储单元 多维数组：Amⅹn

K 以行序为主序存放 a01 n a 0,n-1 a 10 00a01…a0n 12 10 a 11 a 1,n-1 a 1,n-1 am-1,0am1,1 m-1,n-1 n-1.0 m-1,1 Loc( aii=Loc(aoo)+(i*n+j)K mn a m-1,n-1 9

9 a00 a01 …….. a0,n-1 a10 a11 …….. a1,n-1 am-1,0 am-1,1 … am-1,n-1 …………………. 以行序为主序存放 am-1,n-1 …….. am-1,1 am-1,0 ………. a1,n-1 …….. a12 a10 a0,n-1 ……. a01 0 a00 1 n-1 m*n-1 n K Loc( aij)=Loc(a00)+(i*n+j)*K

以列序为主序存放 10 am-1,0 01 0,n-1 11 a 10 a ll···· a 1,n-1 m-1,0am-1,1··am-1,n-1 a0,n-1 Loc(ai=Loc(aoo)+( m+i)K a 1,n-1 mn a m-1,n-1 10

10 以列序为主序存放 0 1 m-1 m*n-1 m am-1,n-1 …….. a1,n-1 a0,n-1 ………. am-1,1 …….. a11 a01 am-1,0 ……. a10 a00 a00 a01 …….. a0,n-1 a10 a11 …….. a1,n-1 am-1,0 am-1,1 ……am-1,n-1 …………………… Loc(aij)=Loc(a00)+ (j*m+i)*K K