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

教学目的 “数据结构十算法=程序 数据结构与算法 基本数据结构的ADT及其应用 理组织数据,有效表示数据,有效处 张铭 http:/db.pku.edu.cn/mzhang/ds/ 算法的设计分析技术 北京大学信息科学与技术考 抽象能力 数据结构与算法教学小组 ■问题—数据——算法 2007年9月10日 提高程序设计的质量 ⊙版权所有,转蒙或印必兜 北大息_张铭写 课程的主要内容 实习课目的 论 配合“数据结构与算法”主课,提高实际动 算法的数学基础 手能力和程序设计的质量 算法的时间和空间度量 ■基本数据结构 线性表向量、串、栈和队列)、二叉树、 排序、检索等盒要问题类的有效算法 ADT、STL 黛要数据结构技术 ■综合应用程序 设计 排序、检索、文件、索引等技术 算法的选择、实现和测试 程序设计实践和技巧 北大影_歌张写 权质有轨国邮究 真大_息 张铭编写 有,神剑究 实习课程内容(1/2) 实习课程内容(2/2) ■C++编程技术补充 基本算法 标准模板库STL的基本概念 ■枚举法、贪心法 C++流处理 递归、回溯、搜索与分支限界 程序设计实践和技巧 分治法、动态规划 ■风格、设计和实现 ■问题建模 界面、排错 数学建模、软件模型 测试、性能和可扩展性 m数据结构的应用 北大张写 权所有轨康■命邮 盒大带张铭写

1 数据结构与算法 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 2007年9月10日 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 教学目的… „ “数据结构＋算法＝程序” „ 基本数据结构的ADT及其应用 „ 合理组织数据, 有效表示数据, 有效处 理数据 „ 算法的设计分析技术 „ 抽象能力 „ 问题——数据——算法 „ 提高程序设计的质量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 课程的主要内容 „ 理论 „ 算法的数学基础 „ 算法的时间和空间度量 „ 抽象 „ 排序、检索等重要问题类的有效算法 „ 重要数据结构技术 „ 设计 „ 算法的选择、实现和测试 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 实习课目的 配合“数据结构与算法”主课，提高实际动 手能力和程序设计的质量 „ 基本数据结构 „ 线性表(向量、串、栈和队列)、二叉树、 树、图等 „ ADT、STL „ 综合应用程序 „ 排序、检索、文件、索引等技术 „ 程序设计实践和技巧 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 实习课程内容(1/2) „ C++编程技术补充 „ 标准模板库 STL的基本概念 „ C++流处理 „ 程序设计实践和技巧 „ 风格、设计和实现 „ 界面、排错 „ 测试、性能和可扩展性 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 实习课程内容(2/2) „ 基本算法 „ 枚举法、贪心法 „ 递归、回溯、搜索与分支限界 „ 分治法、动态规划 „ 问题建模 „ 数学建模、软件模型 „ 数据结构的应用

主题 组长组员 面向对象技术 毛琛吴迪 钱昊巨程 实习课程进度(1/2 调试和测试技术 赖博彦陈学轩丁羽 陈醒王瑞超 9月12日第一周数据结构与算法实习简介 9月19日第二周算法(一):穷举法 递归和回溯 9月26日 周算法(二):回溯法 图、搜索、剪枝姚金字黄柏彤陈琪 10月3日第四周国庆放 10月10日第五周算法(三):贪心法,算法优 动态规划 杨涛金鑫李昂周 日第六周程序设计实践(一):风格 金果 算法优化 李森贾由 和2用*覆序设计实政(=),5的源本 数学建模技术 汪瑜雷涛罗睿辞 10月31日第八周算法(四):分治法 王尧 改据续控与算法的应用陈志态冯黑张 北大息_张铭写 实习课程进度(2/2) 主课教学考核 11月7日第九周算法(五):动态规划 第十周习题讨论,布置大实习,讨 期中20% 期末20% 11月21日第十一周程序设计实践(三):界 高级数据结构20% 震性序设计实践(四):测 平时(考勤+课堂)20% 12月5日第十三周问题建模专题讨论 书面作业、上机作业15 12月12日第十四周图的应用 态度5% 12月19日第十五周数据结构应用 ■12月26日第十六周上机题讲评,期末总复习 北大影_歌张写 权质有轨国邮究 真大影张帖写 叔新有,量究 考勤 作业要求 不要迟到早退、旷课 1.主课只有书面作业(每周4道) ◆有事提前请假 我保证本次作业由我本人独立完成, ■中请“课堂免修”(自学)? 不需要调试 ◆同样交作业、上机题、考试 ■2.实习课3道大综合实习,7道AcM ◆不建议 ■“诚实代码 学习需要环境 要调 ◆考勤措施:随堂小测试 ■要提交上机报告 北真大学张铭编写 聊张帖写 权新有,究

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 数据结构与算法的应用 陈志杰 冯熙铉 张策 雷涛 罗睿辞 王尧 数学建模技术 汪瑜婧 算法优化 李森 贾由 金鑫 李昂 周 金果 动态规划 杨涛 图、搜索、剪枝 姚金宇 黄柏彤 陈琪 递归和回溯 王子琪 谭裕韦 陈学轩 丁羽 陈醒 王瑞超 调试和测试技术 赖博彦 STL和C++ 钱昊 巨程 面向对象技术 毛琛 吴迪 主题 组长 组员 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 实习课程进度(1/2) „ 9月12日 第一周 数据结构与算法实习简介 „ 9月19日 第二周 算法（一）：穷举法 „ 9月26日 第三周 算法（二）：回溯法 „ 10月3日 第四周 国庆放假 „ 10月10日 第五周 算法（三）：贪心法, 算法优化 „ 10月17日 第六周 程序设计实践（一）：风格、设计 和实现，面向对象技术 „ 10月24日 第七周 程序设计实践（二）：STL的基本 概念和常用容器 „ 10月31日 第八周 算法（四）：分治法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 实习课程进度(2/2) „ 11月7日 第九周 算法（五）：动态规划 „ 11月14日 第十周 习题讨论，布置大实习，讨 论项目管理 „ 11月21日 第十一周 程序设计实践（三）：界 面和排错 „ 11月28日 第十二周 程序设计实践（四）：测 试、性能和可扩展性 „ 12月5日 第十三周 问题建模专题讨论 „ 12月12日 第十四周 图的应用 „ 12月19日 第十五周 数据结构应用 „ 12月26日 第十六周 上机题讲评，期末总复习 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 主课教学考核 „ 期中20 % „ 期末20 % „ 高级数据结构20% „ 平时(考勤+课堂)20 % „ 书面作业、上机作业15 % „ 态度5% 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 考 勤 „ 不要迟到早退、旷课 ‹有事提前请假 „ 申请“课堂免修”（自学）？ ‹同样交作业、上机题、考试 ‹不建议 ‹学习需要环境 ‹考勤措施：随堂小测试 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 作业要求 „ 1. 主课只有书面作业(每周4道) „ “我保证本次作业由我本人独立完成， 没有抄袭他人作业” „ 不需要调试 „ 2. 实习课3道大综合实习，7道ACM „ “诚实代码” „ 要调试 „ 要提交上机报告

按时提交作业,严禁抄袭 作业提交期限的说明 每周第一次课课间交书面作业(或之前 ftp提交电子版) 1.有利于助教及时批改、讲解 计分标准10分,期末加权。规则: 2.有利于同学及时讨论复习 1.准时提交,满分可达10分(个别加 分) 2.延迟3天之内提交,满分可达7分; ■破例申请—要在 deadline前提出 3.延迟7天之内提交,满分可达3分 1.个别有困难的同学 4.7天之后提交或不交,得分-5分。 2.生病或事假 5.抄袭得-20分。 举位▲张倍墙写 北大单张铭写 叔新有,命邮 诚信 书面作业提交要求 ■端正学习态度、调动学习兴趣 写学号、名字 ◆提倡讨论,但严禁抄袭 写“XX保证没有抄袭他人作业”的诚实 ◆可以讨论思路 保证 ◆但要亲自动手实现 写算法分析、注释 现抄袭,严肃查处 注意算法格式(层次嵌套、不同功能块 效密馩和棼抄部喜杏或上机题计 留空) ◆以后的作业题会得到重点检查 否则,计零分或根据抄袭情况倒扣分 北真大脆张写 叔新有,量究 学习过程中的问题 学习过程中的问题 ■问题1:进度快,听不懂 问题2:算法思想能懂,但代码不懂 别人是牛人,自己是菜鸟 没有入门,经验不够 同学发言听不懂 建议:多读代码 ■建议:主动学习 先弄懂思想,再看代 建立信心我是精英,我能行 预习—聪明鸟先飞 再总皓算法的主 ,物例检测边界—具体 提问式学习——量疑、创新 经典算法代码不仅要恒,还要自己能写出来 复习—总结、提高、实践应用 不是背,是用自己的风格写 以考题的形式来看书,做习题 对经典算法的灵活 售改问题条件,仿写 北真大学张铭编写 聊张帖写 权新有,究

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 按时提交作业，严禁抄袭 „ 每周第一次课课间交书面作业(或之前 ftp提交电子版) „ 计分标准10分，期末加权。规则： 1. 准时提交，满分可达10分（个别加 分）； 2. 延迟3天之内提交，满分可达7分； 3. 延迟7天之内提交，满分可达3分； 4. 7天之后提交或不交，得分 - 5分。 5. 抄袭得 – 20分。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 作业提交期限的说明 „ 1. 有利于助教及时批改、讲解 „ 2. 有利于同学及时讨论复习 „ 破例申请——要在deadline前提出 „ 1. 个别有困难的同学 „ 2. 生病或事假 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 诚 信 „端正学习态度、调动学习兴趣 ‹提倡讨论，但严禁抄袭 ‹可以讨论思路 ‹但要亲自动手实现 ‹发现抄袭，严肃查处 ‹抄袭者和被抄袭者本次作业或上机题计 双倍倒扣分，即得 - 20分 ‹以后的作业题会得到重点检查 ‹严重的期评将给予不及格处理 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 书面作业提交要求 „ 写学号、名字 „ 写“XX保证没有抄袭他人作业”的诚实 保证。 „ 写算法分析、注释 „ 注意算法格式(层次嵌套、不同功能块 之间留空) „ 否则，计零分或根据抄袭情况倒扣分。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 学习过程中的问题 „ 问题1：进度快，听不懂 „ 别人是牛人，自己是菜鸟 „ 同学发言听不懂 „ 建议：主动学习 „ 建立信心——我是精英，我能行 „ 预习——聪明鸟先飞 „ 提问式学习——置疑、创新 „ 复习——总结、提高、实践应用 „ 以考题的形式来看书，做习题 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 学习过程中的问题 „ 问题2：算法思想能懂，但代码不懂 „ 还没有入门，经验不够 „ 建议：多读代码 „ 先弄懂思想，再看代码 „ 抽象——具体——抽象 „ 弄懂算法的大框架——抽象 „ 要多用实例走几遍，特例检测边界——具体 „ 再总结算法的主要功能块——抽象 „ 经典算法代码不仅要懂，还要自己能写出来 „ 不是背，是用自己的风格重写 „ 对经典算法的灵活 „ 修改问题条件，仿写

学习过程中的问题 学习过程中的问题 ■问题3:编写的算法质量不高 数学模型建立 问题4:不能独立完成作业 质上是散学思能力,抽像能力 抄同学的——作弊 不深入考虑,就问—没有收获 理不周到 有思想写不出代码 n翻书,照着代码修改—考试有问题 ■建议;多写代码 建议:独立完成作业 事先想明白算法思想 先看一遍敦材、或讲义 编写结构清晰的程序 顺序、条件选 不懂的地方找同学请教,或看视频 不要过于依赖拿 还不懂,在bbs上提问,或找责任助教 举位▲张倍墙写 北大单张铭写 叔新有,命邮 学习过程中的问题 学习过程中的问题 ■问题5:不好意思与同学交流 问题6:不善于利用资源 怕打搅 课程网站、课程讨论bbs 怕抄袭嫌疑 助教、同学 建议:主动交流、普于交流 推荐作业 ■沟通、交流是雪要的情商 ■建议:高效调动资源 增进感情、为将来的合作打基础 多看参考资源 能加深对问题的理解,提高作业质量 多请教、讨论 只要不直接看答案,思想类似不会构成抄袭 推荐作业 重要前提:一定要自己先思考,否则效率低 研究复习大纲 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 课程资源 实验班资源 数据结构与算法(信息学院 .httpldbpku.edu.cn/mzhang/ds/ .http://db.pku.edu.cn/mzhang/ds/honor 数据结构实习(计算机和智能专业强化) ■实验班作业提交 .http:ldbpku.edu.cn/mzhang/ds/shixi/i ftp:dshonordsoZhonor@fusiongrids.cn ■课程答疑 用户名: ds honor .http:Idbcs.pku.edu.cn/mzhang/ds/bbs/ 密码:ds07 honor ◆注册:h学号Xxx 北真大学张铭编写 聊张帖写 权新有,究

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 学习过程中的问题 „ 问题3：编写的算法质量不高 „ 数学模型建立不了 „ 本质上是数学思维能力，抽象能力 „ 递归思想 „ 边界处理不周到 „ 有思想写不出代码 „ 建议：多写代码 „ 事先想明白算法思想 „ 编写结构清晰的程序 „ 顺序、条件选择、循环、函数 „ 不要过于依赖编译器 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 学习过程中的问题 „ 问题4：不能独立完成作业 „ 抄同学的——作弊 „ 不深入考虑，就问——没有收获 „ 翻书，照着代码修改——考试有问题 „ 建议：独立完成作业 „ 先看一遍教材、或讲义 „ 不懂的地方找同学请教，或看视频 „ 还不懂，在bbs上提问，或找责任助教 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 学习过程中的问题 „ 问题5：不好意思与同学交流 „ 怕打搅 „ 怕抄袭嫌疑 „ 建议：主动交流、善于交流 „ 沟通、交流是重要的情商 „ 增进感情、为将来的合作打基础 „ 能加深对问题的理解，提高作业质量 „ 只要不直接看答案，思想类似不会构成抄袭 „ 重要前提：一定要自己先思考，否则效率低 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 学习过程中的问题 „ 问题6：不善于利用资源 „ 课程网站、课程讨论bbs „ 助教、同学 „ 推荐作业 „ 建议：高效调动资源 „ 多看参考资源 „ 多请教、讨论 „ 推荐作业 „ 研究复习大纲 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 课程资源 „ 数据结构与算法（信息学院） ‹ http://db.pku.edu.cn/mzhang/DS/ „ 数据结构实习（计算机和智能专业强化） ‹ http://db.pku.edu.cn/mzhang/DS/shixi/i ndex.htm „ 课程答疑 ‹ http://db.cs.pku.edu.cn/mzhang/ds/bbs/ ‹ 注册：h-学号xxx 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 实验班资源 „ http://db.pku.edu.cn/mzhang/ds/honor „实验班作业提交 ftp://ds_honor:ds07honor@fusion.grids.cn „ 用户名: ds_honor „ 密码: ds07honor

教材 参考书目 ■许卓群、杨冬青、唐世渭、张 ■张铭、刘晓丹译,《数据结构与算法分 铭,《数据结构与算法》,高等 析》(C++第二版、Java版),电子工业 教育出版社,2004年7月。 出版社,2002年。(用1998年的第 ■张铭、赵海燕、王腾蛟,《数据 版也可以,也可以直接用英文原版) 结构与算法一一学习指导与习题 ■许卓群,《数据结构》,高等教育出版 社,1988。 解 高等教育出版社, 2005年10月 举位▲张倍墙写 北大单张铭写 叔新有,命邮 教学参考书 教学参考书(续) Donald e Knuth, The Art of Computer rogramming, Addison Wesley. vol 1 跌与昆+努结华大图鞋 vol3.国防工业出版社影印。(苏运霖译 Thomas H Cormen charles e Leiserson 德径〈等桉; c++ donald L. Rivest, Clifford Stein 育出版 production to Algorithms, MIT Press. 5 等教育出版社影印 蔚 和语言版 哥据结+笑学图社1 (Data Structure with 大学出版社 严蔚敏,《数据结构题集》,清华大学 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 主课助教 第一章概论 ■王位春:学院课程总助教 ■为竹么县啪习教据构 13810026968 ■么是教据施构 ■黄燕京 吴定明 抗法的兮性及分 ■的敦度量 ■邢国峰(实习课总助教 拇枘的辑和评价 总綰 北真大学张铭编写 聊张帖写 权新有,究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 教材 „ 许卓群、杨冬青、唐世渭、张 铭，《数据结构与算法》，高等 教育出版社， 2004年 7月。 „ 张铭、赵海燕、王腾蛟，《数据 结构与算法－－学习指导与习题 解析》，高等教育出版社， 2005年 10月。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 参考书目 „ 张铭、刘晓丹译, 《数据结构与算法分 析》(C++第二版、Java版)，电子工业 出版社，2002年。（用1998年的第一 版也可以，也可以直接用英文原版） „ 许卓群，《数据结构》，高等教育出版 社，1988。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 教学参考书 „ Donald E. Knuth, The Art of Computer Programming, Addison Wesley. Vol. 1， Vol 3. 国防工业出版社影印。（苏运霖译） „ Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press. 高 等教育出版社影印。 „ William Ford，《Data Structure with C++》，清华大学出版社 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 教学参考书(续) „ 殷人昆，《数据结构——用面向对象方 法与C++描述》，清华大学出版社， 1999。 „ 张乃孝，裘宗燕，《数据结构——C++ 与面向对象的途径》，高等教育出版 社，2001。 „ 严蔚敏，《数据结构》 第二版(Pascal 和语言版都可以)，清华大学出版社。 „ 严蔚敏，《数据结构题集》，清华大学 出版社 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 主课助教 „ 王位春：学院课程总助教 „ 13810026968 „ 黄燕京 „ 吴定明 „ 邢国峰(实习课总助教) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 第一章 概论 „ 为什么要学习数据结构 „ 什么是数据结构 „ 抽象数据类型 „ 算法的特性及分类 „ 算法的效率度量 „ 数据结构的选择和评价 „ 总结