国家级精品课程—《数据结构与算法》 第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)