数据结构与算法 第十一章高级线性表 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第十一章 高级线性表 任课教员:张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有,转载或翻印必究
主要内容 411.1多维数组 411.2广义表 411.3存储管理技术 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 2 主要内容 11.1 多维数组 11.2 广义表 11.3 存储管理技术
11.1多维数组 基本概念 ●数组的空间结构 ●数组的存储 金数组的声明 令用数组表示特殊矩阵 稀疏矩阵 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 3 11.1 多维数组 基本概念 数组的空间结构 数组的空间结构 数组的存储 数组的声明 用数组表示特殊矩阵 稀疏矩阵
基本概念 数组( Array)是数量和元素类型固定的 有序序列 静态数组必须在定义它的时候指定其 大小和类型 n动态数组可以在程序运行才分配内存 空间 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 4 基本概念 数组(Array)是数量和元素类型固定的 )是数量和元素类型固定的 有序序列 静态数组必须在定义它的时候指定其 静态数组必须在定义它的时候指定其 大小和类型 动态数组可以在程序运行才分配内存 动态数组可以在程序运行才分配内存 空间
基本概念(续) 多维数组( Multi- array)是向量的扩充 向量的向量就组成了多维数组 可以表示为: ELEM ALCr.d,]Lc2.d2 I.[cn.,,I ac1和d是各维下标的下界和上界。所以其元 素个数为: 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 5 基本概念(续) 多维数组(Multi-array)是向量的扩充 向量的向量就组成了多维数组 向量的向量就组成了多维数组 可以表示为: ELEM A[c ELEM A[c1..d1][c2..d2]…[cn..dn] ci和di是各维下标的下界和上界。所以其元 是各维下标的下界和上界。所以其元 素个数为: ∏ = − + n i i i d c 1 ( 1)
数组的空间结构 dl=3,d2=5,d3=5 d1 d2 d1 国田 a[2|33l 二维数组 三维数组 d1[1.3],d2[1..5],d3[1..5]分别为3个维 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 6 数组的空间结构 数组的空间结构 d1=3,d2=5,d3=5 d1 d2 a[2][2] d1 d2 d3 a[2][3][3] 二维数组 三维数组 d1[1..3],d2[1..5],d3[1..5]分别为3个维
数组的存储 内存是一维的,所以数组的存储也只能 是一维的 以行为主序(也称为“行优先”) 以列为主序(也称为“列优先”) 123 47 58 6 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 7 数组的存储 内存是一维的,所以数组的存储也只能 是一维的 以行为主序(也称为“行优先”) 以列为主序(也称为“列优先”) X= 1 2 3 4 5 6 7 8 9
C/C+、 Pasca1行优先 先排最右的下标 从右向左 最后最左的下标 例如对于三维数组 a[1..k,1.m,1.n]的元素ay可以 如下排列: 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 8 C/C++、 Pascal行优先 先排最右的下标 从右向左 最后最左的下标 例如对于三维数组 a[1..k,1..m,1..n]的元素axyz可以 如下排列:
Pasca1语言的行优先存储 12 a alln a11a122a123…。a12n a 211 a 213 a 21n a 221222 a。 223 a 2m1 a a a k11 k12 a kIn a k21 a a km1 a1 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 9 Pascal语言的行优先存储 语言的行优先存储 a111 a112 a113 … a11n a121 a122 a123 … a12n ………………………… a1m1 a1m2 a1m3 … a1mn a211 a212 a213 … a21n a221 a222 a223 … a22n ………………………… a2m1 a2m2 a2m3 … a2mn ┇ ak11 ak12 ak13 … ak1n ak21 ak22 ak23 … ak2n ………………………… akm1 akm2 akm3 … akmn 12 3 n C 1 2 m 2 2 2 2 2 2 2 2 2 2 2 2
FORTRAN列优先 先排最左的下标 从左向右 最后最右的下标 ■例如对于三维数组a[1..k,1..m, 1.n]的元素a可以如下排列: 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 10
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 10 FORTRAN列优先 先排最左的下标 从左向右 最后最右的下标 例如对于三维数组a[1..k, 1..m, 1..n]的元素axyz可以如下排列: