数据结构课程知识体系和教学实践.ppt

《数据结构课程知识体系和教学实践.ppt》由会员分享，可在线阅读，更多相关《数据结构课程知识体系和教学实践.ppt（34页珍藏版）》请在三一办公上搜索。

1、数据结构课程知识体系和教学实践,张 铭,北京大学信息科学与技术学院http:/山东烟台师范学院 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.教学策略,北京大学信息学院 版权所有，转载或翻印必究 Page 13,数据结构课程的主要内容,理论算法的数学基础算法的时间和空间度量抽象排序、检索等重要问题类的有

4、效算法重要数据结构技术设计算法的选择、实现和测试,北京大学信息学院 版权所有，转载或翻印必究 Page 14,教学目的,“数据结构算法程序”把数据结构和算法理论与编程实践相结合能够在实际的工程实践中灵活地予以应用培养数据抽象的能力 提高程序设计的质量,北京大学信息学院 版权所有，转载或翻印必究 Page 15,二、教学实践,1.教学目的2.教材编写3.教学策略,北京大学信息学院 版权所有，转载或翻印必究 Page 16,教材编写,许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年 7月。ISBN 7-04-014616-9。张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习

5、题解析，高等教育出版社，2004年 9月。ISBN 7-04-017829-X。,北京大学信息学院 版权所有，转载或翻印必究 Page 17,数据结构与算法,C+模板,抽象数据类型(ADT)第1章概论数据结构的定义抽象数据类型基本的算法分析技术第2-6章从逻辑结构的角度系统地介绍各种基本数据结构线性表、字符串、二叉树、树和图,北京大学信息学院 版权所有，转载或翻印必究 Page 18,第7章 内排序第8章 文件与外排序第9章 检索第10章 索引第11章 高级线性结构第12章 高级树形结构Patricia树、伸展树，k-d树、PR四分树、R*树,北京大学信息学院 版权所有，转载或翻印必究 Pag

6、e 19,数据结构与算法学习指导与习题详解,第1-12章，涵盖了主教材的基本内容主教材重要的数据结构和算法知识点、学习重点和难点 习题详解第13章上机报告ACM竞赛：穷举、回溯、分治、搜索、DP实习报告要求和样例 第14章为考试题及其解答2004年秋季学期的期中、期末考题和答案1999-2005年北大研究生入学考试,北京大学信息学院 版权所有，转载或翻印必究 Page 20,习题详解,212道习题、53道上机题题意分析、边界处理提示典型解法（算法描述）算法代价分析典型错误170道新习题，40道新上机题,北京大学信息学院 版权所有，转载或翻印必究 Page 21,二、教学实践,1.教学目的2.教

7、材编写3.教学策略,北京大学信息学院 版权所有，转载或翻印必究 Page 22,（1）启发式教学,数学特性抽象数据类型不同的存储方法不同存储方法的可能算法结合算法分析来讨论各种存储方法和算法的利弊，摒弃不适宜的方法,北京大学信息学院 版权所有，转载或翻印必究 Page 23,（2）引进新理论技术,“搜索引擎”中的数据结构技术图搜索排序索引技术,北京大学信息学院 版权所有，转载或翻印必究 Page 24,（3）加强实践环节的训练,数据结构与算法，3学分/周3学时每周布置6道书面作业或小程序实习数据结构与算法实习，2学分/周2学时 一个学期8道ACM竞赛题6道综合上机实习题上机实习时间，120小时

8、/学生,北京大学信息学院 版权所有，转载或翻印必究 Page 25,（4）新教育技术,建立了高质量的课程网站 http:/50多小时rm（全程录像）标准C+模板编写的可执行的源程序代码9209代码总行数，非注释行7498习题和上机题及其参考答案 BBS讨论版(2005年7月28日数据)2244名注册会员，653个问题，1863回帖 助教讲答,北京大学信息学院 版权所有，转载或翻印必究 Page 26,北京大学信息学院 版权所有，转载或翻印必究 Page 27,每章内容,概述、前测知识点详解动画习题解、新习题电子教案pdf、视频扩展资源参考网站、论文、讲义,北京大学信息学院 版权所有，转载或翻印

9、必究 Page 28,（5）严格要求，教书育人,每一届都布置全新作业“诚实代码”助教严格检查,北京大学信息学院 版权所有，转载或翻印必究 Page 29,教学实施,1.教师面授重点难点讲解（30%）2.学生利用网络课件和网络资源自学（40%）3.课后作业和小组协作（课上和课下）（20%）4.助教网络答疑和网络讨论（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:/,