《数据结构课程知识体系和教学实践.ppt》由会员分享，可在线阅读，更多相关《数据结构课程知识体系和教学实践.ppt（34页珍藏版）》请在三一文库上搜索。
1、数据结构课程 知识体系和教学实践,张 铭,北京大学信息科学与技术学院 http:/ 2005年高等学校计算机系列课程教师培训暨教学研讨会 山东烟台师范学院 2005年8月,北京大学信息学院 版权所有，转载或翻印必究 Page 2,内容提要,一、知识体系 二、教学实践 三、教学案例,北京大学信息学院 版权所有，转载或翻印必究 Page 3,一、知识体系,1.数据的定义 2.算法的效率问题 3.抽象数据类型,北京大学信息学院 版权所有，转载或翻印必究 Page 4,1. 数据结构的定义,数据的逻辑结构 数据的存储结构 数据的运算,北京大学信息学院 版权所有，转载或翻印必究 Page 5,常见的逻
2、辑关系,线性结构 树形结构 图结构 文件结构 图树二叉树线性表,北京大学信息学院 版权所有，转载或翻印必究 Page 6,常见的存储方法,顺序方法 链接方法 索引方法（线性、树形 ） 散列方法,北京大学信息学院 版权所有，转载或翻印必究 Page 7,运算,建立、清除数据结构 插入一个新数据元素 删除、修改某个数据元素 排序 检索,北京大学信息学院 版权所有，转载或翻印必究 Page 8,一、知识体系,1.数据的定义 2.算法的效率问题 3.抽象数据类型,北京大学信息学院 版权所有，转载或翻印必究 Page 9,算法效率的基本问题权衡,对于给定的一类问题 算法需要多少存储空间和时间？ 最好算法
3、的最坏情况是什么？ 平均来说，算法的运行好到何种程度？ 算法一般化到何种程度？ 什么情况下，最好的算法是什么？ 算法分析技术,北京大学信息学院 版权所有，转载或翻印必究 Page 10,一、知识体系,1.数据的定义 2.算法的效率问题 3.抽象数据类型,北京大学信息学院 版权所有，转载或翻印必究 Page 11,抽象数据类型ADT,抽象数据类型是定义了一组运算的数学模型 把数据结构的存储与实现细节剥离 在适当的抽象层次上考虑程序的结构和算法 封装和信息隐蔽,北京大学信息学院 版权所有，转载或翻印必究 Page 12,二、教学实践,1. 教学目的 2. 教材编写 3. 教学策略,北京大学信息学院
4、 版权所有，转载或翻印必究 Page 13,数据结构课程的主要内容,理论 算法的数学基础 算法的时间和空间度量 抽象 排序、检索等重要问题类的有效算法 重要数据结构技术 设计 算法的选择、实现和测试,北京大学信息学院 版权所有，转载或翻印必究 Page 14,教学目的,“数据结构算法程序” 把数据结构和算法理论与编程实践相结合 能够在实际的工程实践中灵活地予以应用 培养数据抽象的能力 提高程序设计的质量,北京大学信息学院 版权所有，转载或翻印必究 Page 15,二、教学实践,1. 教学目的 2. 教材编写 3. 教学策略,北京大学信息学院 版权所有，转载或翻印必究 Page 16,教材编写,
5、许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年 7月。ISBN 7-04-014616-9。 张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2004年 9月。ISBN 7-04-017829-X。,北京大学信息学院 版权所有，转载或翻印必究 Page 17,数据结构与算法,C+模板, 抽象数据类型(ADT) 第1章概论 数据结构的定义 抽象数据类型 基本的算法分析技术 第2-6章 从逻辑结构的角度系统地介绍各种基本数据结构 线性表、字符串、二叉树、树和图,北京大学信息学院 版权所有，转载或翻印必究 Page 18,第7章 内排序 第8章 文件
6、与外排序 第9章 检索 第10章 索引 第11章 高级线性结构 第12章 高级树形结构 Patricia树、伸展树，k-d树、PR四分树、R*树,北京大学信息学院 版权所有，转载或翻印必究 Page 19,数据结构与算法学习指导与习题详解,第1-12章，涵盖了主教材的基本内容 主教材重要的数据结构和算法知识点、学习重点和难点 习题详解 第13章上机报告 ACM竞赛：穷举、回溯、分治、搜索、DP 实习报告要求和样例 第14章为考试题及其解答 2004年秋季学期的期中、期末考题和答案 1999-2005年北大研究生入学考试,北京大学信息学院 版权所有，转载或翻印必究 Page 20,习题详解,21
7、2道习题、53道上机题 题意分析、边界处理提示 典型解法（算法描述） 算法代价分析 典型错误 170道新习题，40道新上机题,北京大学信息学院 版权所有，转载或翻印必究 Page 21,二、教学实践,1. 教学目的 2. 教材编写 3. 教学策略,北京大学信息学院 版权所有，转载或翻印必究 Page 22,（1）启发式教学,数学特性 抽象数据类型 不同的存储方法 不同存储方法的可能算法 结合算法分析来讨论各种存储方法和算法的利弊，摒弃不适宜的方法,北京大学信息学院 版权所有，转载或翻印必究 Page 23,（2）引进新理论技术,“搜索引擎”中的数据结构技术 图搜索 排序 索引技术,北京大学信息
8、学院 版权所有，转载或翻印必究 Page 24,（3）加强实践环节的训练,数据结构与算法， 3学分/周3学时 每周布置6道书面作业或小程序实习 数据结构与算法实习，2学分/周2学时 一个学期8道ACM竞赛题 6道综合上机实习题 上机实习时间，120小时/学生,北京大学信息学院 版权所有，转载或翻印必究 Page 25,（4）新教育技术,建立了高质量的课程网站 http:/ 1500ppt, 50多小时rm（全程录像） 标准C+模板编写的可执行的源程序代码 9209代码总行数，非注释行7498 习题和上机题及其参考答案 BBS讨论版(2005年7月28日数据) 2244名注册会员，653个问题，
9、1863回帖 助教讲答,北京大学信息学院 版权所有，转载或翻印必究 Page 26,北京大学信息学院 版权所有，转载或翻印必究 Page 27,每章内容,概述、前测 知识点详解 动画 习题解、新习题 电子教案 pdf、视频 扩展资源 参考网站、论文、讲义,北京大学信息学院 版权所有，转载或翻印必究 Page 28,（5）严格要求，教书育人,每一届都布置全新作业 “诚实代码” 助教严格检查,北京大学信息学院 版权所有，转载或翻印必究 Page 29,教学实施,1. 教师面授重点难点讲解（30%） 2. 学生利用网络课件和网络资源自学（40%） 3. 课后作业和小组协作（课上和课下）（20%） 4
10、. 助教网络答疑和网络讨论（10%） 5. 重点难点时间放在网络自学及教师面授讲解上。,北京大学信息学院 版权所有，转载或翻印必究 Page 30,主课教学评价,1. 平时(书面作业、课堂测试)：20% 2. 上机实习(+实习报告)：15% 3. 期中考试：20% 4. 期末考试：40% 5. 考勤和态度：5%,北京大学信息学院 版权所有，转载或翻印必究 Page 31,实习课教学评价,平时(考勤+开卷随堂测试课堂表现)占30% 上机题（源程序实习报告）70%,北京大学信息学院 版权所有，转载或翻印必究 Page 32,1线性表；2二叉树；3树；4图；5散列与检索；6排序；7索引；8高级数据结构。,学生对知识点的认识,北京大学信息学院 版权所有，转载或翻印必究 Page 33,学生评估,专业内容游刃有余、知识拓展广 课堂效率高、实例丰富 学生实践机会多 课程增长了知识和能力 动手以及思考能力得到很大锻炼,北京大学信息学院 版权所有，转载或翻印必究 Page 34,谢谢！,教学案例 vs 案例教学 http:/ 联系张铭：,