《数据结构》 第五章
《 数据结构》 第五章
数据结构 第五章数组 5.1数组的定义 52数组的顺序表示和实现 53矩阵的压缩存储 53.1特殊矩阵 532稀疏矩阵
数据结构 tjm 第五章 数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵
数据结构 数组可看成是一种特殊的线性表,其特殊在于,表 中的元素本身也是一种线性表。 51勤组的定义 多维数组是向量(一维数组)的推广 例如,二维数组: G 00 01 0n-1 10 11 ■■■ G 1,n-1 mn ■■■ m-1,0 ■■ 数组的抽象类型定义参见P90
数据结构 tjm 数组可看成是一种特殊的线性表，其特殊在于，表 中的元素本身也是一种线性表。 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]i 等价于 ypedef ElemType Array[; typedef Array 1 Array2[m]i 数组一旦被定义,它的维数和维界就不再改变。 因此,除了结构的初始化和销毁之外,数组的基本 操作只有存取元素和修改元素值的操作
数据结构 tjm 在C语言中，一个二维数组类型可以定义为其分量类 型为一维数组类型的一维数组类型，也就是说， typedef ElemType Array2[m][n]; 等价于： typedef ElemType Array1[n]; typedef Array1 Array2[m]; 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组的基本 操作只有存取元素和修改元素值的操作
数据结构 52数组的顺序表示和兴现 由于计算机的内存结构是一维的,因此用一维内 存来表示多维数组,就必须按某种次序将数组元 素排成一个序列,然后将这个线性序列存放在存 储器中。 又由于对数组一般不做插入和删除操作,也就是 说,数组一旦建立,结构中的元素个数和元素间 的关系就不再发生变化。因此,一般都是采用顺 序存储的方法来表示数组。 通常有两种顺序存储方式: 低下标优先 高下标优先
数据结构 tjm 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内 存来表示多维数组，就必须按某种次序将数组元 素排成一个序列，然后将这个线性序列存放在存 储器中。 又由于对数组一般不做插入和删除操作，也就是 说，数组一旦建立，结构中的元素个数和元素间 的关系就不再发生变化。因此，一般都是采用顺 序存储的方法来表示数组。 通常有两种顺序存储方式： 低下标优先 高下标优先
数据结构 对二维数组而言 ()以行序为主序一一将数组元素按行排列,第+1个行 向量紧接在第个行向量后面。 在C语言中,数组就是按行优先顺序存储的。 (2)以列序为主序一一将数组元素按列排列,第+1个列 向量紧接在第个列向量后面。 在 FORTRAN语言中,数组就是按列优先顺序存储的。 只要知道开始结点的存放地址(即基地址),维数和 每维的上、下界,以及每个数组元素所占用的单元 数,就可以将数组元素的存放地址表示为其下标的 线性函数。因此,数组中的任一元素可以在相同的 时间内存取,即顺序存储的数组是一个随机存取结
数据结构 tjm 对二维数组而言： ⑴以行序为主序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。 在C语言中，数组就是按行优先顺序存储的。 ⑵以列序为主序——将数组元素按列排列，第i+1个列 向量紧接在第i个列向量后面。 在FORTRAN语言中，数组就是按列优先顺序存储的。 只要知道开始结点的存放地址（即基地址），维数和 每维的上、下界，以及每个数组元素所占用的单元 数，就可以将数组元素的存放地址表示为其下标的 线性函数。因此，数组中的任一元素可以在相同的 时间内存取，即顺序存储的数组是一个随机存取结 构
数据结构 数组元素存储地址的计算: 35274918605477834102 LOC (i)=LOC(i-1)+I=a+i*
数据结构 tjm 一维数组 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l 数组元素存储地址的计算：
数据结构 二维数组 aoo ao1 0n-1 10 11a1,n-1 am-1,0am-11am-1n-1 行优先Loc(bj) =a+(i*n+i)*I
数据结构 tjm 二维数组 行优先 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 =
数据结构 各维元素个数为b1,b2/b3wbn 下标为九方J3…j的数组元素的存储地址 Loc(yj2…in)=q+ (j1*b2*b3*物bn+力2*b3*b4*,*bn +in-1*bn+in)*l 最后的公式参见P93
数据结构 tjm 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矩阵的压缩存储 高级语言编制程序时,常将一个矩阵描述为一个 维数组。这种存储表示可以对元素随机存取,各种 矩阵运算也非常简单。 矩阵中非器元素呈某种规视律分布或者矩阵中出现大 量的零元素的情况下,存储空间大量浪费。 当一个矩阵中的元素有很多都是零时,零元素的个 数远大于非零元素,则称该矩阵为稀疏矩阵。 矩阵的压缩存储一一为多个相同的非零元素只分配 一个存储空间;对零元素不分配空间
数据结构 tjm 5.3 矩阵的压缩存储 高级语言编制程序时，常将一个矩阵描述为一个二 维数组。这种存储表示可以对元素随机存取，各种 矩阵运算也非常简单。 矩阵中非零元素呈某种规律分布或者矩阵中出现大 量的零元素的情况下，存储空间大量浪费。 当一个矩阵中的元素有很多都是零时，零元素的个 数远大于非零元素，则称该矩阵为稀疏矩阵。 矩阵的压缩存储——为多个相同的非零元素只分配 一个存储空间；对零元素不分配空间