第十一章高级线性表 任课教员:张铭 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