数据结构与算法实习 课程目的 (一)概论 配合“数据结构与算法”主课,提高实际动 能力和程序设计的 ●基本数据结构 北京大学信息科学技术学院 ·线性表向量、串、栈和队列)、二又树、 张铭 ADT、STL zhang@db.pku.edu.cn 综合应用程序 排序、检索、文件、索引等技术 tp: db. pku. edu. cn/zhang/ds/shixi 20079.12 程序设计实践和技巧 课程内容 ●C++编程技术补充 ●基本算法 标准模板库STL的基本概念 枚举法、贪心法 C++流处理 ●程序设计实践和技巧 递归、回溯、搜索与分支限界 分治法、动态规划 风格、设计和实现 界面、排错 ●问题建模 测试、性能和可扩展性 数学建模、软件模型 成绩评定办法考勤 平时:20% ●可以申请自学,必须写出书面申请 考勤、开卷随堂测试、课堂表现 ·AcM作业:20% ◆自学的同学可以不来听课 北大AcM结果、源程序、实习报告 ◆同样交作业、上机题、考试 ●综合上机题:40% 实习课也不要迟到早退、旷课 源程序、实习报告 ◆有事提前请假 期末考试20% ◆1/3旷课得不到学分 ●有附加题 任何一项表现突出都可以*+ 分 ◆“不及格
1 数据结构与算法实习 （一）概论 北京大学信息科学技术学院 张 铭 mzhang@db.pku.edu.cn http://db.pku.edu.cn/mzhang/ds/shixi/ 2007.9.12 课程目的 配合“数据结构与算法”主课，提高实际动 手能力和程序设计的质量 z 基本数据结构 z 线性表(向量、串、栈和队列)、二叉树、 树、图等 z ADT、STL z 综合应用程序 z 排序、检索、文件、索引等技术 z 程序设计实践和技巧 课程内容 z C++编程技术补充 z 标准模板库 STL的基本概念 z C++流处理 z 程序设计实践和技巧 z 风格、设计和实现 z 界面、排错 z 测试、性能和可扩展性 z 基本算法 z 枚举法、贪心法 z 递归、回溯、搜索与分支限界 z 分治法、动态规划 z问题建模 z 数学建模、软件模型 成绩评定办法 z 平时：20% z 考勤、开卷随堂测试、课堂表现 z ACM作业：20% z 北大ACM结果、源程序、实习报告 z 综合上机题：40% z 源程序、实习报告 z 期末考试 20% z 有附加题 任何一项表现突出都可以 +++分 考 勤 z 可以申请自学，必须写出书面申请 自学的同学可以不来听课 同样交作业、上机题、考试 z 实习课也不要迟到早退、旷课 有事提前请假 1/3旷课得不到学分 “不及格
作业要求 上机题编程风格 实习课3道大综合实习,7道 ACM 诚实代码保证 “诚实代码” 内部文档要求 ●要调试 ●过程代码要求 ●要提交上机报告 ●面向对象的代码要求 按时提交作业,严禁抄袭 诚信 ftp提交电子版 端正学习态度、调动学习兴趣 计分标准10分,期末加权。规则: ◆提倡讨论,但严禁抄袭 ◆可以讨论思路 准时提交,满分可达10分(个别加 ◆但要亲自动手实现 分) ◆发现抄袭,严肃查处 2.延迟3天之内提交,满分可达7分; 3.延迟7天之内提交,满分可达3分 ◆掏翥芬和諮麥翥夯次作业或上机题计双倍 4.7天之后提交或不交,得分-5分 ◆以后的作业题会得到重点检查 抄袭得-20分 ◆严重的期评将给予不及格处理 上机题提交要求 课程资源 打包后 建议命名式 ·数据结构与算法(信息学院) .http:/ldb.pku.edu.cn/mzhang/ds/ 包中须含有: ·数据结构实习〔计算机和智能专业强化) ·1. readme. txt文件 程序运行环境、编译运行步骤、程序功能等 课程谷 ·2诚实代码保证、源程序以及相关的项目和 .http:/db.cs.pku.edu.cn/mzhang/ds/bbs/ 资源文 足够注释 ◆注册:h学号xx或其他班要求的 偺查源文性的时件取J要的w 课作业提交 orojidsoLproi@fusion grids,cn ·3.上机实习总结报告
2 作业要求 z实习课3道大综合实习，7道 ACM z“诚实代码” z要调试 z要提交上机报告 上机题编程风格 z诚实代码保证 z内部文档要求 z过程代码要求 z面向对象的代码要求 按时提交作业，严禁抄袭 z ftp提交电子版 z 计分标准10分，期末加权。规则： 1. 准时提交，满分可达10分（个别加 分）； 2. 延迟3天之内提交，满分可达7分； 3. 延迟7天之内提交，满分可达3分； 4. 7天之后提交或不交，得分 - 5分； 5. 抄袭得 – 20分。 诚 信 z端正学习态度、调动学习兴趣 提倡讨论，但严禁抄袭 可以讨论思路 但要亲自动手实现 发现抄袭，严肃查处 抄袭者和被抄袭者本次作业或上机题计双倍 倒扣分，即得 - 20分 以后的作业题会得到重点检查 严重的期评将给予不及格处理 上机题提交要求 z 打包后提交，建议命名式： z 00308096张宁1.zip 包中须含有： z 1. readme.txt文件 z 程序运行环境、编译运行步骤、程序功能等 z 2. 诚实代码保证、源程序以及相关的项目和 资源文件、足够注释 z 例如，VC++中的.dsw, .dsp文件，rc目录中的 图像资源文件；Jbuilder中的.jpr或.jpx文件，特 殊的Java包等等 z 3. 上机实习总结报告 课程资源 z 数据结构与算法（信息学院） http://db.pku.edu.cn/mzhang/DS/ z 数据结构实习（计算机和智能专业强化） http://db.pku.edu.cn/mzhang/DS/shixi/ z 课程答疑 http://db.cs.pku.edu.cn/mzhang/ds/bbs/ 在实习版块 注册：h-学号xxx 或 其他班要求的 z 实习课作业提交 ftp://ds_proj:ds07proj@fusion.grids.cn
教材 ·1张铭 ,《数据结构与算法 Charles eleiserson 社, 04-017829 熟尊章蹂、螽尊膏出社:额。4 据结 評实肌蕾薨3年猾骨 叠设第素丢a防击 ·4.M.H. Alsuwaiyel, 版社影 酸狂骑夯3年打潸计与分析),清华大学出 于φ大竽备法引年1计与分 助教 主题 组长组员 面向对象技术 毛泵吴迪 ·邢国 实习总助教 sTL和c++ 钱昊巨程 调试和测试技术 赖博彦陈学轩丁羽 ·Te:13146717633;82179629 陈醒王瑞超 归和回溯 王子琪谭裕韦 张阜东 图、搜索、剪枝姚金宇黄柏影陈琪 ·哈立久 动态规划 杨涛金鑫李昂周金果 算法优化 李森贾由 王位亭—学院 数学建模技术汪瑜婧雷涛罗睿辞 数据结构与算法应用陈志杰冯熙铉张策 实习课程进度W鱻 实习课程进度(2/2) ·9月12日第一周数据结构与算法实习简介—张铭 ·9月19日 周算法(一):穷举法 ·11月7日第九周算法(五):动 算法(二):回测 态规划—张阜东 10月10日第五周算法(三):贪心法,算法优化一刘 ·11月14日第十周习题讨论,布置 ·10月 表漫序法实(),凤格,设计和实 大实习,讨论项目管理——陈长城 ·层甭七厘珠 设计实践(二):STL的基本概念 ·11月21日第十一周程序设计实践 ·10月31日第八周算法(四):分治法陈长城 (三):界面和排错——王栋 ·11月28日第十二周程序设计实践 (加),洲性能和可把屈性
3 教材 z 1. 张铭、赵海燕、王腾蛟，《数据结构与算法 －－学习指导与习题解析》，高等教育出版 社，2005年 9月。ISBN 7-04-017829-X。 z 2. 许卓群、杨冬青、唐世渭、张铭，《数据结 构与算法》，高等教育出版社，2004年7月。 z 3. Brian W.Kernigham 著，裘宗燕 译，《程 序设计实践》，机械工业出版社，2003年9月。 z 4. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影 印，2003年1月。 z 5. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5 月。 z 6. Donald E.Knuth 著，苏运霖 译，《计算机 程序设计艺术，第1卷基本算法》，国防工业出 版社，2002年。 z 7. 王晓东，《算法设计与分析》，清华大学出 版社，2003年1月。 z 8. 卢开澄，《计算机算法导引——设计与分 析》，清华大学出版社，1996年11月。 助教 z 邢国峰——实习总助教 z Email: holdenxing@gmail.com z Tel:13146717633;82179629. z 陈长城 z 刘培 z 张阜东 z 王栋 z 喻立久 z 杨宇 z 高壮 z 王位春——学院总助教 数据结构与算法应用 陈志杰 冯熙铉 张策 数学建模技术 汪瑜婧 雷涛 罗睿辞 算法优化 李森 贾由 动态规划 杨涛 金鑫 李昂 周金果 图、搜索、剪枝 姚金宇 黄柏彤 陈琪 递归和回溯 王子琪 谭裕韦 陈学轩 丁羽 陈醒 王瑞超 调试和测试技术 赖博彦 STL和C++ 钱昊 巨程 面向对象技术 毛琛 吴迪 主题 组长 组员 实习课程进度(1/2) z 9月12日 第一周 数据结构与算法实习简介——张铭 z 9月19日 第二周 算法（一）：穷举法——张铭 z 9月26日 第三周 算法（二）：回溯法——张铭 z 10月3日 第四周 国庆放假 z 10月10日 第五周 算法（三）：贪心法, 算法优化——刘 培 z 10月17日 第六周 程序设计实践（一）：风格、设计和实 现，面向对象技术——高壮 z 10月24日 第七周 程序设计实践（二）：STL的基本概念 和常用容器——张阜东 z 10月31日 第八周 算法（四）：分治法——陈长城 实习课程进度(2/2) z 11月7日 第九周 算法（五）：动 态规划——张阜东 z 11月14日 第十周 习题讨论，布置 大实习，讨论项目管理——陈长城 z 11月21日 第十一周 程序设计实践 （三）：界面和排错——王栋 z 11月28日 第十二周 程序设计实践 （四）：测试、性能和可扩展性—
程序设计实践和技巧|「风格、设计和实现 ●风格、设计和实现 风格 ●程序的境界 ●文件结构、版式、命名、注释. ●界面、排错 程序员的素质 ●程序的境界 ●测试、性能和可扩展性 设计和实现 界面( (interface)与排错 问题求解 ●用户界面、程序接口 ·数学建模、问题建模 字符界面:菜单型,命令行型 ·数据结构抽象 ·简单、清晰、规范、统 棒性 效率分析 排错 禱鞏獯辯聽沟解决预期规模间恩的 注意程序风格(避免全局变量、不用 互相冲突的需求和约束条件之间寻 ·排错的时间至少跟写程序一样长 不要去怀疑编译器和库函数 反复试验,推倒重来,直至 读程序,而不是马上去改程序 ·不要过于依赖 debug工具 测试、性能和可扩展性 霾禧狂的矚的用系统的方法发现程序中 ●在总体设计上要注意代码风格、 黑盒测试 可复用性和可扩展性 白盒测试 性能优化 ●在关键段要牺牲上面的内容来追 ·编译、代码、算法优化 可扩展性 求性能 ·敦件复用 ●性能和可扩展性是相互矛盾的 ·紧町标准 平台无关
4 程序设计实践和技巧 z风格、设计和实现 z程序的境界 z界面、排错 z测试、性能和可扩展性 风格、设计和实现 z风格 z 文件结构、版式、命名、注释…… z 程序员的素质 z 程序的境界 设计和实现 z 问题求解 z 数学建模、问题建模 z 数据结构抽象 z 算法抽象 z 效率分析 z 选择能在合理时间内解决预期规模问题的 简单算法和数据结构 z 在一些互相冲突的需求和约束条件之间寻 找平衡 z 反复试验，推倒重来，直至…… 界面(interface)与排错 z 用户界面、程序接口 z 字符界面：菜单型，命令行型 z 简单、清晰、规范、统一 z 鲁棒性 z 排错 z 注意程序风格（避免全局变量、不用 goto……） z 排错的时间至少跟写程序一样长 z 不要去怀疑编译器和库函数 z 读程序，而不是马上去改程序 z 不要过于依赖debug工具 测试、性能和可扩展性 z 测试(Testing)：用系统的方法来发现程序中可 能存在的隐藏的bug z 黑盒测试 z 白盒测试 z 性能优化 z 编译、代码、算法优化 z 可扩展性 z 软件复用 z 紧盯标准 z 平台无关 z在总体设计上要注意代码风格、 可复用性和可扩展性 z在关键段要牺牲上面的内容来追 求性能 z 性能和可扩展性是相互矛盾的
sTL中的容器「sTL中的容器 °8°8 顺序容器 vector deque[ list stack queue priority 关联容器 ueue et. multiset map, multimap 容器适配器 容器 Containers 基本算法 八皇后问题 问题的状态空间 ●在8×8格的国际象棋棋盘上摆 ●穷举法 放8个皇后,使其不能互相攻击 回溯、搜索 任意两个皇后都不处于同一行、 贪心法 同一列或同一斜线上 递归分治 ●问有多少种摆法? 动态规划 八皇后问题的一个解 四皇后的解空间树 Q @@的@的@的的回 324 0@ g@8
5 STL中的容器 顺序容器 关联容器 容器 Containers vector deque list set, multiset map, multimap STL中的容器 容器适配器 stack queue priority _queue 基本算法 z问题的状态空间 z穷举法 z回溯、搜索 z贪心法 z递归分治 z动态规划 八皇后问题 z在8×8格的国际象棋棋盘上摆 放8个皇后，使其不能互相攻击 z 任意两个皇后都不处于同一行、 同一列或同一斜线上 z问有多少种摆法？ 八皇后问题的一个解 Q Q Q Q Q Q Q Q 四皇后的解空间树