数据结构与算法实习.ppt
《数据结构与算法实习.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法实习.ppt(76页珍藏版)》请在三一文库上搜索。
1、数据结构与算法实习,北京大学信息科学技术学院 张 铭 http:/ http:/ 2008.4.20,课程目的,配合“数据结构与算法”主课,提高实际动手能力和程序设计的质量 基本数据结构 线性表(向量、串、栈和队列)、二叉树、树、图等 ADT、STL 综合应用程序 排序、检索、文件、索引等技术 程序设计实践和技巧,课程内容,C+编程技术补充 标准模板库 STL的基本概念 C+流处理 程序设计实践和技巧 风格、设计和实现 界面、排错 测试、性能和可扩展性,基本算法 枚举法、贪心法 递归、回溯、搜索与分支限界 分治法、动态规划 高级数据结构 线性:多维矩阵、稀疏矩阵、广义表、存储管理 树型:字符树
2、、 BestBST、AVL树、伸展树 问题建模 数学建模、软件模型,成绩评定办法,平时:20% 考勤、开卷随堂测试、课堂表现 ACM作业:20% 北大ACM结果、源程序、实习报告 综合上机题:40% 源程序、实习报告 期末考试 20% 有附加题,作业要求,实习课4道大综合实习,6道ACM “诚实代码” 要调试 要提交上机报告,实习课程资源,数据结构实习(计算机和智能专业强化) http:/ http:/ 算法与程序设计自评自测系统 http:/ 2000多道由浅入深设计数据结构与算法程序设计各个知识点的竞赛试题,理论课资源,数据结构与算法(信息学院) http:/ http:/ (公网) 课程
3、答疑 http:/ 注册:1-学号xxx,教材,1. 张铭、赵海燕、王腾蛟、宋国杰,数据结构与算法实验教程,高等教育出版社,2009年 6月。国家级“十一五”规划教材 2. 张铭、王腾蛟、赵海燕,数据结构与算法学习指导与习题解析,高等教育出版社,2008年 6月。 国家级“十一五”规划教材 书号: ISBN 978-70-4-023961 3. 张铭、赵海燕、王腾蛟,数据结构与算法学习指导与习题解析,高等教育出版社,2005年 9月。 国家级“十五”配套教材 书号: ISBN 7-04-017829-X 4. 许卓群、杨冬青、唐世渭、张铭,数据结构与算法,高等教育出版社,2004年7月。 国家
4、级“十五”规划教材,参考教材,1. Brian W.Kernigham 著,裘宗燕 译,程序设计实践,机械工业出版社,2003年9月。 2. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印,2003年1月。 3. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MTI Press. 高等教育出版社影印。 4. Sartaj Sahni, Data Str
5、uctures, Algorithms, and Applications in C+. 机械工业出版社影印版。 5. 数据结构(用面向对象方法与C+语言描述)第2版,殷人昆主编, 清华大学出版社,2007年6月. 清华大学信息学院计算机系、软件学院教材 清华考研第一参考书。 http:/ 程序的境界 界面、排错 测试、性能和可扩展性,风格、设计和实现,风格 文件结构、版式、命名、注释 程序员的素质 程序的境界,设计和实现,问题求解 数学建模、问题建模 数据结构抽象 算法抽象 效率分析 选择能在合理时间内解决预期规模问题的简单算法和数据结构 在一些互相冲突的需求和约束条件之间寻找平衡 反复试验
6、,推倒重来,直至,界面(interface)与排错,用户界面、程序接口 字符界面:菜单型,命令行型 简单、清晰、规范、统一 鲁棒性 排错 注意程序风格(避免全局变量、不用goto) 排错的时间至少跟写程序一样长 不要去怀疑编译器和库函数 读程序,而不是马上去改程序 不要过于依赖debug工具,测试、性能和可扩展性,测试(Testing):用系统的方法来发现程序中可能存在的隐藏的bug 黑盒测试 白盒测试 性能优化 编译、代码、算法优化 可扩展性 软件复用 紧盯标准 平台无关,在总体设计上要注意代码风格、可复用性和可扩展性 在关键段要牺牲上面的内容来追求性能 性能和可扩展性是相互矛盾的,STL中
7、的容器,顺序容器 Sequence Containers 关联容器 Associative Containers,容器 Containers,vector,deque,list,set, multiset map, multimap,STL中的容器,容器适配器,stack,queue,priority_queue,基本算法,问题的状态空间 穷举法 回溯、搜索 贪心法 递归分治 动态规划,八皇后问题,在88格的国际象棋棋盘上摆放8个皇后,使其不能互相攻击 任意两个皇后都不处于同一行、同一列或同一斜线上 问有多少种摆法?,八皇后问题的一个解,穷举法(枚举法),4个皇后各占一行,穷举每一行上可能占有
8、的列 共有44 256种情况 枚举时,可以排除直观不符合条件的情况,减小候选集 有4! 24种情况 最后输出合理的解,穷举法的代价,穷举问题域的所有解,找到所有最佳解 减少穷举次数 穷举的变量 注意穷举的顺序 减少判断每种情况的时间 时间代价最高 问题规模n,搜索空间,总搜索时间是: T= | t,O(n!) = O(nn),O(2n) 指数级时间代价,状态空间,四皇后的解空间树,解空间树,根(root):问题的起点 问题状态(problem states):树中结点 状态空间(state space):由根结点到其它结点的所有路径 解状态(solution states)S:由根到S的路径确
9、定了解空间中的一个元组 答案状态(answer states)S:由根到S的路径确定了这问题的一个解(即,它满足隐式约束条件),回溯法图示,“可行则进,不行则换、换不成则退”。 简化为4皇后问题。搜索过程如下:,四后问题求解,回溯算法,可行则进,不行则换 换不成则退,八皇后问题的表示,棋盘行列、皇后依次编上0, 1,,7号 A0n-10n-1 表示nn棋盘上的格 行号从上至下、列号从左到右依次编号为0, 1,,n-1 八后问题的全部解向量为(x0, x1,,x7)。 xi表示皇后i所处的列数 对任何0i, j8,及ij,有xixj 状态空间缩小为在8! 没有两个皇后在同一斜线上(斜率为1 )
10、重点!,斜率+1,i+j=0, 1, , 14,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,斜率-1,i-j=-7, 6, , 7,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,皇后的控制范围,第i个皇后时,前面几个皇后在各列、各对角线上的占用情况 bool An; / 前0i-1行皇后占用列 bool B2*n-1; / 斜率为+1的对角线 bool C2*n-1; / 斜率为-1, Ci-j+7,试探安排八个皇后,从第0行开始,逐步安排每行皇后。 对第i个皇后,找正确的位置(设为第j列 Aj、Bi+j、Ci-j+7都没有被占用 标记Aj、Bi+j、Ci
11、-j+7为被占用状态 继续安排下一个皇后(第i+1个) 否则,如果找不到合适位置,应该退回(即“回溯”)到第i-1行的皇后,重新安排 前面的安排不太合理,回溯过程,如果8个皇后都排好了,则打印这种方案 为了找到其它方案,应该回溯,重新试探皇后的下一种安排方法 抹掉前面试探留下的标记,即恢复Aj、Bi+j、Ci-j+7为未被占用状态 这种回溯过程将逐步返回 使得各行的皇后都能试探到各种可能的摆法,回溯法的框架,问题的解n元组(x0, x1,,xn-1): void rectry(k) / 初始调rectry(0); 置Xk为第一个可能值; while (Xk可能值没有试完) 设置Xk所涉及的标记
12、; if (X0, X1,Xn-1)是解) 打印一组解; else rectry(k+1); 回溯,抹去Xk涉及的标记; 取下一个可能的Xk值; ,八皇后的递归算法,void queen(int i) int j; for (j=0; jn; j+) if (place(i,j) / 能放置吗 Xi = j; mark(i,j); / 标记(i,j)的影响 if (i n-1) queen(i+1); / 接着试下一个 else print(count); / 打印一个解 erase(i,j); / 回溯,去掉刚才标记 ,四皇后时,函数执行模拟,失败情况下回溯过程模拟: queen(0) 试探
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 实习
链接地址:https://www.31doc.com/p-3185607.html