数据结构与算法实习 概论 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang lat] net.pku.edu. cn http:/wwwjpk.pkuedu.cn/pkujpk/courselsiiglshixil 2011.8 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验 教程》(国家十一五规划教材),高教社2011年1月
数据结构与算法实习 概论 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验 教程》（国家十一五规划教材），高教社2011年1月
Mcb信息处理人工智能 广义表、集合、搜 图形图像 矩阵散列、排序 索树及各种有向图 队列、栈、图、矩阵、 索引、检索 空间索引树、检索 数据库概论 操作系统 线性表、多链表、、队列、存储管理表、 编译原理 排序及B+索引树 排序及目录树 字符串、栈、散 列表及语法树 算法分析与设计数据结构与算法实习 数据结构与算法 程序设计实习 概率统计 计算概论集合论与郾论
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 数据结构与算法实习 数据结构与算法 算法分析与设计 计算概论 图形图像 队列、栈、图、矩阵、 空间索引树、检索 数据库概论 线性表、多链表、 排序及B+索引树 编译原理 字符串、栈、散 列表及语法树 操作系统 队列、存储管理表、 排序及目录树 人工智能 广义表、集合、搜 索树及各种有向图 Web信息处理 队列、图、字符、 矩阵散列、排序、 索引、检索 概率统计 程序设计实习 集合论与图论
数据结构与算法体系图 前沿应用:后缀树、 XML DOM树、搜索引擎… 抽象数据类型ADT 算法分析 时空折衷 基础: 逻辑 算 存 理论抽象 线性(表、栈、排序:插入、分治 顺序、链接、 队列、串) 快速、堆、基数 散列、索引 树(二叉树、森 检索:二分、散列 内存、外存 林) 图(有向、无 向、DAG) 索引:BST、B+ 外排序 B+树,倒排 设 许、扩展研究 外排序,广义表,稀矩阵,字符树 Patricia树,AVL,红黑树,伸展树
索引： BST、B+ 扩展研究: 逻辑 运算 存储 线性（表、栈、 队列、串） 树(二叉树、森 林) 图（有向、无 向、DAG） 排序：插入、分治 、快速、堆、基数 检索: 二分、散列 内存、外存 外排序 B+树，倒排 理 论 前沿应用： 后缀树、 XML DOM树、搜索引擎…... 数据结构与算法体系图 抽象数据类型ADT 算法分析 时空折衷 抽 象 设 计 顺序、链接、 散列、索引 外排序，广义表，稀疏矩阵，字符树， Patricia树，AVL， 红黑树，伸展树 …… 基础:
●●● 课程目的 ●●●●● ●●●● ●●●0● 配合“数据结构与算法”主课,提高实际 动手能力和程序设计的质量 ●基本数据结构 ●线性表(向量、串、栈和队列)、二叉树、 树、图等 ADT、STL ●综合应用程序 ●排序、检索、文件、索引等技术 ●程序设计实践和技巧
课程目的 配合“数据结构与算法”主课，提高实际 动手能力和程序设计的质量 ⚫ 基本数据结构 ⚫ 线性表(向量、串、栈和队列)、二叉树、 树、图等 ⚫ ADT、STL ⚫ 综合应用程序 ⚫ 排序、检索、文件、索引等技术 ⚫ 程序设计实践和技巧
●●● ●●●●● 数据结构的逻辑组织 ●●●● ●●●●● ●逻辑结构描述数据元素之间的关系 ●线性结构 0②③④③⊙ ●线性表(表,栈,队列,串等) 非线性结构 ●树(二叉树, Huffman树,二叉搜索树等) ●图(有向图,无向图等)
数据结构的逻辑组织 ⚫ 逻辑结构描述数据元素之间的关系 ⚫ 线性结构 ⚫ 线性表（表，栈，队列，串等） ⚫ 非线性结构 ⚫ 树（二叉树，Huffman树，二叉搜索树等） ⚫ 图（有向图，无向图等） 4 5 6 2 3 1 1 2 3 4 5 6 1 2 3 5 4 6