《数据结构》课程PPT教学课件（2015）第5章 数组

《数据结构》 第五章数组

《 数据结构》 第五章 数组

数据结构 第五章 数组 5.1数组的定义 5.2 :数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1特殊矩阵 5.3.2稀疏矩阵

数据结构 第五章 数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵

数据结构 数组可看成是一种特殊的线性表，其特殊在于，表 中的元素本身也是一种线性表。 5.1数组的定义 多维数组是向量（一维数组）的推广。 例如，二维数组： aoo a01. a0,n-1 Amn a10 a11 a1,n-1 am-1,0am-1,1.am-1,n-1 数组的抽象类型定义参见P90

数据结构 数组可看成是一种特殊的线性表，其特殊在于，表 中的元素本身也是一种线性表。 5.1 数组的定义 多维数组是向量（一维数组）的推广。 例如，二维数组： a00 a01 . a0,n-1 a10 a11 . a1,n-1 . . . . am-1,0 am-1,1 . am-1,n-1 Amn = 数组的抽象类型定义参见P90

数据结构 在C语言中，一个二维数组类型可以定义为其分量类 型为一维数组类型的一维数组类型，也就是说， typedef ElemType Array2[m][n]; 等价于： typedef ElemType Array1[n]; typedef Array1 Array2[m]; 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组的基本 操作只有存取元素和修改元素值的操作

数据结构 在C语言中，一个二维数组类型可以定义为其分量类 型为一维数组类型的一维数组类型，也就是说， typedef ElemType Array2[m][n]; 等价于： typedef ElemType Array1[n]; typedef Array1 Array2[m]; 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组的基本 操作只有存取元素和修改元素值的操作

数据结构 5.2数组的顺序表示和实观 由于计算机的内存结构是一维的，因此用一维内 存来表示多维数组，就必须按某种次序将数组元 素排成一个序列，然后将这个线性序列存放在存 储器中。 又由于对数组一般不做插入和删除操作，也就是 说，数组一旦建立，结构中的元素个数和元素间 的关系就不再发生变化。因此，一般都是采用顺 序存储的方法来表示数组。 通常有两种顺序存储方式： 低下标优先 高下标优先

数据结构 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内 存来表示多维数组，就必须按某种次序将数组元 素排成一个序列，然后将这个线性序列存放在存 储器中。 又由于对数组一般不做插入和删除操作，也就是 说，数组一旦建立，结构中的元素个数和元素间 的关系就不再发生变化。因此，一般都是采用顺 序存储的方法来表示数组。 通常有两种顺序存储方式： 低下标优先 高下标优先

数据结构 对二维数组而言： ()以行序为主序一一将数组元素按行排列，第引+1个行 向量紧接在第个行向量后面。 在C语言中，数组就是按行优先顺序存储的。 (2)以列序为主序一一将数组元素按列排列，第1+1个列 向量紧接在第个列向量后面。 在FORTRAN语言中，数组就是按列优先顺序存储的。 只要知道开始结点的存放地址（即基地址)，维数和 每维的上、下界，以及每个数组元素所占用的单元 数，就可以将数组元素的存放地址表示为其下标的 线性函数。因此，数组中的任一元素可以在相同的 时间内存取，即顺序存储的数组是一个随机存取结 构

数据结构 对二维数组而言： ⑴以行序为主序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。 在C语言中，数组就是按行优先顺序存储的。 ⑵以列序为主序——将数组元素按列排列，第i+1个列 向量紧接在第i个列向量后面。 在FORTRAN语言中，数组就是按列优先顺序存储的。 只要知道开始结点的存放地址（即基地址），维数和 每维的上、下界，以及每个数组元素所占用的单元 数，就可以将数组元素的存放地址表示为其下标的 线性函数。因此，数组中的任一元素可以在相同的 时间内存取，即顺序存储的数组是一个随机存取结 构

数据结构 数组元素存储地址的计算： 一维数组 0 1 23456789 35 27491860547783 4102 ixl L0C(i)=L0C(i-1)+I=a+i*1

数据结构 一维数组 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l 数组元素存储地址的计算：

数据结构 二维数组 a00 a01. a0,n-1 Amn a10 a11 n a1,n-1 ■■■ aaa am-1,0am-1,1mam-1,n-1 行优洗LOC（i,j) =a+(i*n+j)米1

数据结构 二维数组 行优先 LOC ( i, j ) = α + ( i * n + j ) * l a00 a01 . a0,n-1 a10 a11 . a1,n-1 . . . . am-1,0 am-1,1 . am-1,n-1 Amn =

数据结构 n维数组 各维元素个数为b1,b2,b3,vbn 下标为j1,j方，j3,jn的数组元素的存储地址： LOC (j j2.jn)=a+ (j1*b2*b3*.*bn+j2*b3*b4*.*bn +.+jn-*bn +in)*1 最后的公式参见P93

数据结构 LOC ( j1, j2, .,jn ) = α + ( j1*b2*b3*.*bn + j2*b3*b4*.*bn + .+ jn-1*bn + jn ) * l 各维元素个数为 b1 , b2 , b3 , ., bn 下标为 j1 , jj , j3 , ., jn 的数组元素的存储地址： 最后的公式参见P93 n维数组

数据结构 5.3矩阵的压缩存储 高级语言编制程序时，常将一个矩阵描述为一个二 维数组。这种存储表示可以对元素随机存取，各种 矩阵运算也非常简单。 矩阵中非零元素呈某种规律分布或者矩阵中出现大 量的零元素的情况下，存储空间大量浪费。 当一个矩阵中的元素有很多都是零时，零元素的个 数远大于非零元素，则称该矩阵为稀疏矩阵。 矩阵的压缩存储一一为多个相同的非零元素只分配 一个存储空间：对零元素不分配空间

数据结构 5.3 矩阵的压缩存储 高级语言编制程序时，常将一个矩阵描述为一个二 维数组。这种存储表示可以对元素随机存取，各种 矩阵运算也非常简单。 矩阵中非零元素呈某种规律分布或者矩阵中出现大 量的零元素的情况下，存储空间大量浪费。 当一个矩阵中的元素有很多都是零时，零元素的个 数远大于非零元素，则称该矩阵为稀疏矩阵。 矩阵的压缩存储——为多个相同的非零元素只分配 一个存储空间；对零元素不分配空间