北京大学：《数据结构与算法》课程教学资源（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 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

主要内容 11.1多维数组 11.2广义表 11.3存储管理技术 北京大学信息学院 @版权所有,转载或翻印必究 Page 2

北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 11.1 多维数组 ◼ 11.2 广义表 ◼ 11.3 存储管理技术

11.1多维数组 数组( Array)是数量和元素类型固定的有序序列 静态数组必须在定义它的时候指定其大小和类型 动态数组可以在程序运行才分配内存空间 多维数组(Muti- array)是向量的扩充 向量的向量就组成了多维数组 可以表示为 ELEM ALC.d,][c2. 21.[cn.dn] ac1和d1是各维下标的下界和上界。所以其元素个数为: ∏I(d-c1+1) 北京大学信息学院 @版权所有,转载或翻印必究 Page 3

北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 11.1 多维数组 ◼ 数组（Array）是数量和元素类型固定的有序序列 ◼ 静态数组必须在定义它的时候指定其大小和类型 ◼ 动态数组可以在程序运行才分配内存空间 ◼ 多维数组（Multi-array）是向量的扩充 ◼ 向量的向量就组成了多维数组 ◼ 可以表示为： ELEM A[c1 ..d1 ][c2 ..d2 ]…[cn ..dn ] ◼ ci和di是各维下标的下界和上界。所以其元素个数为： = − + n i i i d c 1 ( 1)

数组的空间结构 dB d=3.d=5d3=5 d a[2][2] a[2][3I3] 左边是二维数组的空间结构,右边是三维数组的空间结 构,d1[1..3],d2[1..5],d3[1..5分别为3个维。 北京大学信息学院 @版权所有,转载或翻印必究 Page 4

北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 数组的空间结构 左边是二维数组的空间结构，右边是三维数组的空间结 构，d1[1..3],d2[1..5],d3[1..5]分别为3个维

数组的存储 内存是一维的,所以数组的存储也只能是一维的 以行为主序(也称为“行优先”) 以列为主序(也称为“列优先”) 个3×3的数组X的行优先表示 456 789 ■内存中的存放是:1,2,3,4,5,6,7,8,9 北京大学信息学院 @版权所有,转载或翻印必究 Page 5

北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 数组的存储 ◼ 内存是一维的，所以数组的存储也只能是一维的 ◼ 以行为主序（也称为“行优先”） ◼ 以列为主序（也称为“列优先”） ◼ 一个3 × 3的数组X的行优先表示： ◼ 内存中的存放是：1，2，3，4，5，6，7，8，9 X= 1 2 3 4 5 6 7 8 9

数组的存储(续) 个二维m×n数组中元素X[(第第j列 元素)的内存地址可以这样来计算: X[0][o](数组首地址)+(nxij)×元素的长度 (如C+中int型为4字节 ■例如,我们已知一个数组的A[0][0]元素在内 存的644的位置,假设元素的长度为8,那么我 们就可以求得其他任意元素A[x]y]的位置, 为644+1en×(n×x+y)。 例如,n=m=3,由上面公式得到A2]3]元素的 地址:644+8×(3×2+2)=708 北京大学信息学院 @版权所有,转载或翻印必究 Page 6

北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 数组的存储（续） ◼ 一个二维m × n数组中元素X[i][j]（第i行第j列 元素）的内存地址可以这样来计算： ◼ X[0][0]（数组首地址）+（n×i+j）× 元素的长度 （如C++中int型为4字节） ◼ 例如，我们已知一个数组的A[0][0]元素在内 存的644的位置，假设元素的长度为8，那么我 们就可以求得其他任意元素A[x][y]的位置， 为644+len×(n×x + y)。 ◼ 例如，n = m = 3，由上面公式得到A[2][3]元素的 地址：644 + 8×（3×2+2）= 708

Pascal语言的存储实现是接行优 先处理的,先排最右的下标,从 右向左,最后最左的下标。 例如对于三维数组 a[1..k,1.m,1.n的元素a可 以如下排列: 北京大学信息学院 @版权所有,转载或翻印必究 Page 7

北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 ◼ Pascal语言的存储实现是按行优 先处理的，先排最右的下标，从 右向左，最后最左的下标。 ◼ 例如对于三维数组 a[1..k,1..m,1..n]的元素axyz可 以如下排列：

Pascal语言的行优先存储 1118112a113 a 121 122 123 ain aiml aim2 a1m3 n a211a212a 213a 21n a 221a222a223 22n a2m1 a2m2 a2m3 2mn akl ak12 ak13 kln ak21 ak22 ak23 k2n akm1 akm2 akm3 kmn 北京大学信息学院 @版权所有,转载或翻印必究 Page 8

北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 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

FORTRAN语言采用列优先存储。 先排最左的下标,从左向右, 最后最右的下标。 例如对于三维数组a[1.k, 1.m,1.n]的元素a可以如 下排列: 北京大学信息学院 @版权所有,转载或翻印必究 Page 9

北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 ◼ FORTRAN语言采用列优先存储。 先排最左的下标，从左向右， 最后最右的下标。 ◼ 例如对于三维数组a[1..k, 1..m, 1..n]的元素axyz可以如 下排列：

FORTRAN语言的列优先存储 111 211 311 k11 121a21a32 ax21 a a a ' km1 a112a212a312 ak12 122 a 222 a322 a k22 ●00●00●00000●000 1m2 a 2m2 3m2 a km2 a aln akin 22n a 32n k 2n amn 3 akon 北京大学信息学院 版权所有,转载或翻印必究 Page 10

北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 FORTRAN语言的列优先存储 a111 a211 a311 … ak11 a121 a221 a321 … ak21 ………………………… a1m1 a2m1 a3m1 … akm1 a112 a212 a312 … ak12 a122 a222 a322 … ak22 ………………………… a1m2 a2m2 a3m2 … akm2 ┇ a11n a21n a31n … ak1n a12n a22n a32n … ak2n ………………………… a1mn a2mn a3mn … akmn