北京大学：《数据结构与算法》课程教学资源（实验班讲义）第一章 概论

数据结构与算法 张铭 http://db.pku.edu.cn/mzhang/ds/ 北京大学信息科学与技术学院 数据结构与算法"教学小组 2007年9月10日 版权所有,转载或翻印必究

数据结构与算法 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法 ”教学小组 2007 年 9 月10 日 ©版权所有，转载或翻印必究

教学目的 “数据结构+算法=程序” 基本数据结构的ADT及其应用 合理组织数据,有效表示数据,有效处 理数据 算法的设计分析技术 抽象能力 问题——数据——算法 提高程序设计的质量 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 2

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 教学目的… „ “数据结构＋算法＝程序” „ 基本数据结构的ADT及其应用 „ 合理组织数据, 有效表示数据, 有效处 理数据 „ 算法的设计分析技术 „ 抽象能力 „ 问题——数据——算法 „ 提高程序设计的质量

课程的主要内容 理论 n算法的数学基础 算法的时间和空间度量 抽象 排序、检索等重要问题类的有效算法 重要数据结构技术 设计 算法的选择、实现和测试 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 3

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 课程的主要内容 „ 理论 „ 算法的数学基础 „ 算法的时间和空间度量 „ 抽象 „ 排序、检索等重要问题类的有效算法 „ 重要数据结构技术 „ 设计 „ 算法的选择、实现和测试

实习课目的 配合“数据结构与算法”主课,提高实际动 手能力和程序设计的质量 基本数据结构 a线性表(向量、串、栈和队列)、二叉树、 树、图等 ADT、sTL 综合应用程序 排序、检索、文件、索引等技术 程序设计实践和技巧 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 4

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 实习课目的 配合“数据结构与算法”主课，提高实际动 手能力和程序设计的质量 „ 基本数据结构 „ 线性表(向量、串、栈和队列)、二叉树、 树、图等 „ ADT、STL „ 综合应用程序 „ 排序、检索、文件、索引等技术 „ 程序设计实践和技巧

实习课程内容(1/2) C++编程技术补充 标准模板库STL的基本概念 ■C++流处理 程序设计实践和技巧 风格、设计和实现 界面、排错 n测试、性能和可扩展性 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 5

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 实习课程内容(1/2) „ C++编程技术补充 „ 标准模板库 STL的基本概念 „ C++流处理 „ 程序设计实践和技巧 „ 风格、设计和实现 „ 界面、排错 „ 测试、性能和可扩展性

实习课程内容(2/2) 基本算法 枚举法、贪心法 ■递归、回溯、搜索与分支限界 分治法、动态规划 问题建模 数学建模、软件模型 数据结构的应用 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 6

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 实习课程内容(2/2) „ 基本算法 „ 枚举法、贪心法 „ 递归、回溯、搜索与分支限界 „ 分治法、动态规划 „ 问题建模 „ 数学建模、软件模型 „ 数据结构的应用

主题 组长组员 面向对象技术 毛琛吴迪 STL和c+ 钱昊巨程 调试和测试技术 赖博彦陈学轩丁羽 陈醒王瑞超 递归和回溯 王子琪谭裕韦 图、搜索、剪枝 姚金宇黄柏彤陈琪 动态规划 杨涛金鑫李昂周 金果 算法优化 李森贾由 数学建模技术 汪瑜婧雷涛罗睿醉 王尧 数据结构与算法的应用陈志杰冯熙铉张策 北京大学信

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 数据结构与算法的应用 陈志杰 冯熙铉 张策 雷涛 罗睿辞 王尧 数学建模技术 汪瑜婧 算法优化 李森 贾由 金鑫 李昂 周 金果 动态规划 杨涛 图、搜索、剪枝 姚金宇 黄柏彤 陈琪 递归和回溯 王子琪 谭裕韦 陈学轩 丁羽 陈醒 王瑞超 调试和测试技术 赖博彦 STL和C++ 钱昊 巨程 面向对象技术 毛琛 吴迪 主题 组长 组员

实习课程进度(1/2) 9月12日第一周数据结构与算法实习简介 9月19日第二周算法(一):穷举法 9月26日第三周算法(二):回溯法 10月3日第四周国庆放假 10月10日第五周算法(三):贪心法,算法优化 10月17日第六周程序设计实践(一):风格、设计 和实现,面向对象技术 10月24日第七周程序设计实践(二):STL的基本 概念和常用容器 10月31日第八周算法(四):分治法 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 8

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 实习课程进度(1/2) „ 9月12日 第一周 数据结构与算法实习简介 „ 9月19日 第二周 算法（一）：穷举法 „ 9月26日 第三周 算法（二）：回溯法 „ 10月3日 第四周 国庆放假 „ 10月10日 第五周 算法（三）：贪心法, 算法优化 „ 10月17日 第六周 程序设计实践（一）：风格、设计 和实现，面向对象技术 „ 10月24日 第七周 程序设计实践（二）：STL的基本 概念和常用容器 „ 10月31日 第八周 算法（四）：分治法

实习课程进度(2/2) 11月7日第九周算法(五):动态规划 11月14日第十周习题讨论,布置大实习,讨 论项目管理 11月21日第十一周程序设计实践(三):界 面和排错 11月28日第十二周程序设计实践(四):测 试、性能和可扩展性 12月5日第十三周问题建模专题讨论 12月12日第十四周图的应用 12月19日第十五周数据结构应用 12月26日第十六周上机题讲评,期末总复习 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必究 Page 9

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 实习课程进度(2/2) „ 11 月 7日 第九周 算法（五）：动态规划 „ 11 月14日 第十周 习题讨论，布置大实习，讨 论项目管理 „ 11 月21日 第十一周 程序设计实践（三）：界 面和排错 „ 11 月28日 第十二周 程序设计实践（四）：测 试、性能和可扩展性 „ 12 月 5日 第十三周 问题建模专题讨论 „ 12 月12日 第十四周 图的应用 „ 12 月19日 第十五周 数据结构应用 „ 12 月26日 第十六周 上机题讲评，期末总复习

主课教学考核 期中20 期末20% 高级数据结构20 平时(考勤+课堂)20% 书面作业、上机作业15% 态度59 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 主课教学考核 „ 期中20 % „ 期末20 % „ 高级数据结构20% „ 平时(考勤+课堂)20 % „ 书面作业、上机作业15 % „ 态度5%