国家级精品课程—《数据结构与算法》 第12章高级数据结构 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:张铭 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：张铭 ©版权所有，转载或翻印必究 第12章 高级数据结构
主要内容 今12.1多维数组 122广义表和存储管理 12.3Trie结构和Parc树对 14改进的二又搜索树 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 12.1 多维数组 ◼ 12.2 广义表和存储管理 ◼ 12.3 Trie结构和Patricia树 ◼ 12.4 改进的二叉搜索树
121多维数组 基本概念 数组的空间结构 中数组的存储 中数组的声明 今用数组表示特殊矩阵 中稀疏矩阵 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 12.1 多维数组 ◼ 基本概念 ◼ 数组的空间结构 ◼ 数组的存储 ◼ 数组的声明 ◼ 用数组表示特殊矩阵 ◼ 稀疏矩阵
基本概念 数组( Array)是数量和元素类型固定的有序 序列 口静态数组必须在定义它的时候指定其大小和类 型 口动态数组可以在程序运行才分配内存空间 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 基本概念 ◼ 数组（Array）是数量和元素类型固定的有序 序列 ❑ 静态数组必须在定义它的时候指定其大小和类 型 ❑ 动态数组可以在程序运行才分配内存空间
基本概念(续) 多维数组( Multi-array)是向量的扩充 口向量的向量就组成了多维数组 可以表示为: ELEM ALcl. d,].d].[cn .d,] ac;和d是各维下标的下界和上界。所以其元素 个数为: ∏I(d1-c;+1) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 基本概念（续） ◼ 多维数组（Multi-array）是向量的扩充 ❑ 向量的向量就组成了多维数组 ❑ 可以表示为： ELEM A[c1 ..d1 ][c2 ..d2 ]…[cn ..dn ] ❑ ci和di是各维下标的下界和上界。所以其元素 个数为： = − + n i i i d c 1 ( 1)
数组的空间结构 d1=3d2=5d3=5 d1 d2 a2|12 a[2||3]l3 二维数组 三维数组 d1[1.3],d2[1..5],d3[1..5]分别为3个维 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 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个维
数组的存储 内存是一维的,所以数组的存储也只能是一维 的 口以行为主序(也称为“行优先”) 口以列为主序(也称为“列优先”) X= 456 789 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 数组的存储 ◼ 内存是一维的，所以数组的存储也只能是一维 的 ❑ 以行为主序（也称为“行优先”） ❑ 以列为主序（也称为“列优先”） X= 1 2 3 4 5 6 7 8 9
Pascal的行优先存储 a11a12a13a14a15a1n a21a22a23a24a25 a2. a31a32a33a34a35 an a41a42a43a44a45.|a4n am1 am2 am3 am4 am5 mn “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 Pascal的行优先存储 a11 a12 a13 a14 a15 … a1n am1 am2 am3 am4 am5 … amn a21 a22 a23 a24 a25 … a2n a31 a32 a33 a34 a35 … a3n a41 a42 a43 a44 a45 … a4n … … … … … … …
FORTRANI的列优先存储 ex a11a12a13a14a15 ain alla 22|a 23a24a25 a 2 a31a32a33a34a35 an a41a42a43a44a45 an am1 am3 am4 am5 mn “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 FORTRAN的列优先存储 am2 am3 am4 am5 … amn … a2n a32 a33 a34 a35 … a3n a42 a43 a44 a45 … a4n am1 a31 a41 … … … … … … … a11 a12 a13 a14 a15 … a1n a21 a22 a23 a24 a25 next
CC++、 Pasca行优先 口先排最右的下标 口从右向左 口最后最左的下标 例如对于三维数组a1k1.m,1.m的元 素a可以如下排列: “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ C/C++、 Pascal行优先 ❑ 先排最右的下标 ❑ 从右向左 ❑ 最后最左的下标 ◼ 例如对于三维数组a[1..k,1..m,1..n]的元 素axyz可以如下排列：