北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第十一章 高级线性表

数据结构与算法 第十一章高级线性表 任课教员:张铭 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可以如下排列：