北京大学：《数据结构与算法》实习实验教程（PPT课件讲稿）概论

数据结构与算法实习 概论 北京大学信息科学技术学院 主讲:张铭、郝丹 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

●●● ●●● ●●●●● 核心内容 ●●●● ●●●●● ●基本算法 ●枚举法、贪心法 ●递归、回溯、搜索与分支限界 ●分治法、动态规划 ●问题建模 ●数学建模、软件模型

核心内容 ⚫ 基本算法 ⚫ 枚举法、贪心法 ⚫ 递归、回溯、搜索与分支限界 ⚫ 分治法、动态规划 ⚫问题建模 ⚫ 数学建模、软件模型

●●● 补充内容 ●●● ●●●●● ●●●● ●●●●● ●C++编程技术补充 ●标准模板库STL的基本概念 C++流处理 ●程序设计实践和技巧 ●风格、设计和实现 ●界面、排错 ●测试、性能和可扩展性

补充内容 ⚫ C++编程技术补充 ⚫ 标准模板库 STL的基本概念 ⚫ C++流处理 ⚫ 程序设计实践和技巧 ⚫ 风格、设计和实现 ⚫ 界面、排错 ⚫ 测试、性能和可扩展性

●●● 进度安排(可调顺序) ●●●●● ●●●● ●●●●● ●1.第一周数据结构与算法实习简介 ●2.第二周算法(一):穷举法、贪心法 ●3.第三周程序设计实践(一):风格、设计和 实现 ●4.第四周算法(二):回溯法、搜索问题 ●5.第五周国庆放假 ●6.第六周习题课 ●7.第七周算法(三):分治法 ●8.第八周程序设计实践(二):项目设计案例

进度安排（可调顺序） ⚫ 1. 第一周 数据结构与算法实习简介 ⚫ 2. 第二周 算法（一）：穷举法、贪心法 ⚫ 3. 第三周 程序设计实践（一）：风格、设计和 实现 ⚫ 4. 第四周 算法（二）：回溯法、搜索问题 ⚫ 5. 第五周 国庆放假 ⚫ 6. 第六周 习题课 ⚫ 7. 第七周 算法（三）：分治法 ⚫ 8. 第八周 程序设计实践（二）：项目设计案例

●●● ●●●●● ●●●● ●●●0● ●9.第九周算法(四):数据结构与算法技巧 ●10.第十周特邀校友讲座 ●11.第十一周算法(五):动态规划 12.第十二周程序设计实践(三):界面、排错 测试 ●13.第十三周习题课 ●14.第十四周图的应用、算法优化 15.第十五周问题建模专题讨论 ●16.第十六周习题课,大实习设计和项目展示

⚫ 9. 第九周 算法（四）：数据结构与算法技巧 ⚫ 10. 第十周 特邀校友讲座 ⚫ 11. 第十一周 算法（五）：动态规划 ⚫ 12. 第十二周 程序设计实践（三）：界面、排错 、测试 ⚫ 13. 第十三周 习题课 ⚫ 14. 第十四周 图的应用、算法优化 ⚫ 15. 第十五周 问题建模专题讨论 ⚫ 16. 第十六周 习题课，大实习设计和项目展示

●●● ●●●●● 成绩评定办法 ●●●● ●●●0● 平时:5% 开卷随堂测试、课堂表现、团队合作 ACM作业:15% ●北大AcM结果、源程序、实习报告 ●POJ机考:30% 源程序、实习报告 ●综合上机题:30% 源程序、实习报告 ●期末考试20%

成绩评定办法 ⚫ 平时：5% ⚫ 开卷随堂测试、课堂表现、团队合作 ⚫ ACM作业：15% ⚫ 北大ACM结果、源程序、实习报告 ⚫ POJ机考：30% ⚫ 源程序、实习报告 ⚫ 综合上机题：30% ⚫ 源程序、实习报告 ⚫ 期末考试 20%