数据结构章节程知识体系和教学实践

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