数据结构课程知识体系和教学实践课件市公开课一等奖百校联赛特等奖课件.pptx

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