新版数据结构教案.doc

信息学院课程教案五邑大学信息学院数据结构教案20072008年度 第二学期 课 程 名 称 数据结构 课 程 主 讲 人 白明、金旺春 课程所属教研室 软件工程、计算机科学与技术 课程类型及学时 理论课（含实验）、72学时 授课教材版本 数据结构（C+版） 清华大学出版社 授 课 班 级 计算机科学与技术2006级1班、2班 网络工程2006级1班 软件工程2006级1班 授 课 日 期 2008年3月7月五邑大学信息学院 制二七年一月教学专题开课1-1教学专题开课课程综述授课学时 1学时（50分钟）教学章节 组织授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点 为什么要学习数据结构这门课以及如何学习教学难点 认识课程，找到学好课程的方法教学内容和教学过程课程引入：介绍数据结构课程在教学计划中的位置5分钟1 课程性质：核心地位2 课程学习目标（1） 学习知识角度（2） 培养能力角度3 介绍教材：主教材和与之配套的辅助教材4 介绍参考文献资料：多角度、全方位学习5 介绍网络教学资源：6 学习方法及要求（1） 坚持上课（2） 学会读书：预习+复习+拓展（3） 认真作业和实验（4） 下载课件、演示系统，提高记忆效率（5） 理解知识+自主实践7考核要求：作业+考勤+实验+自主实践（期中考核）+期末考试5分钟15分钟3分钟3分钟5分钟10分钟2分钟课程总结：下定决心、树立信心、坚持恒心、改革创新2分钟教学提示1开课要精彩，激发兴趣，认识重要性2明确课程目标：学些什么，达到的目标3需要具备的基本知识，对基础差的同学多鼓励从现在做起=追赶超出4为什么学，怎样学，如何学好5考研思考题课后导读 你对你所学的专业了解多少？你对学习这门课应该如何准备？在数据结构方面，最早的权威性著作是Knuth所著的系列丛书计算机程序设计艺术，这套书非常值得一看教学后记教学专题数据结构的研究对象1-2教学专题数据结构的兴起和发展授课学时 1学时（50分钟）教学章节 11 、12授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点 抽象与数据类型；数据结构的研究对象教学难点 数据结构与类的对应关系教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 程序设计的性质 数据结构的起源和发展 数据结构与程序设计的关系 计算机求解问题的一般过程 数据结构的研究对象教学过程课程引入：介绍数据结构课程体系的起源。了解历史专业素养3分钟1 提出问题：程序设计的实质是什么？通过具体实例得出答案2 介绍数据结构与程序设计的关系，强调数据结构始终是程序设计的基础，强调从面向对象角度看待数据结构3 从发展的观点和应用的观点讨论数据结构的发展4 从计算机求解问题的一般过程入手，建立抽象和数据模型的初步概念5 通过具体实例总结数据结构的研究对象，注意引申数据元素之间的关系3分钟5分钟12分钟3分钟15分钟10分钟课程总结：数据结构研究的对象是非数值计算问题2分钟教学提示1从问题求解过程入手，理解“数据结构+算法=程序”，理解数据结构和算法在问题求解中的作用2通过结构化程序和面向对象程序对比，从框架上理解为什么将数据结构从结构化发展到面向对象3数据结构是从非数值问题抽象出来的数据模型，这个阶段的学生还没有抽象和模型的概念，需要补充抽象和模型的相关知识媒体使用 多媒体课件：Kunth的照片及介绍；用动画辅助解释基本概念 教学网络平台：相关教学材料思考题课后导读 在数据结构方面，最早的权威性著作是Knuth所著的系列丛书计算机程序设计艺术，这套书非常值得一看许多人致力于计算机科学中的问题求解，实际上这正是该领域吸引人的地方。如何求解问题（曹宏庆.中国水电出版社）是提高问题求解能力的经典著作教学后记教学专题数据结构的基本概念2-30教学专题数据结构的基本概念授课学时 1.4学时（70分钟）教学章节 1.3授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点数据结构及相关概念；数据的逻辑结构和存储结构之间的关系教学难点 数据元素；逻辑关系；抽象数据类型教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 数据、数据项、数据对象 数据元素 数据结构 数据的逻辑结构 数据的存储结构 逻辑结构和存储结构之间的关系 数据结构的访问接口 抽象数据类型 教学过程课程引入：根据生活中的实例简单理解什么是数据结构3分钟1 给出数据的定义，举例说明什么是数据2 给出数据元素和数据项的定义，根据上一讲得个例子体会如何界定数据元素，总结数据、数据元素、数据项之间的关系3 给出数据结构的定义，从问题求解的角度强调数据结构包含逻辑结构和存储结构两个方面4 给出逻辑结构的定义重点解释逻辑关系5 给出存储结构的定义，重点强调如何表示逻辑关系6 从数据表示的角度总结逻辑结构和存储结构的关系7 在理解数据类型抽象的基础上，给出抽象数据类型的定义，说明：数据模型+一组操作=ADT8 结合抽象数据类型的定义说明数据结构的访问接口5分钟 8分钟6 分钟10分钟15分钟5分钟10分钟5 分钟课程总结：数据的逻辑结构、存储结构及其相互关系3分钟教学提示1注意对基本概念的引入和阐述，抓住要点，注意用生活中的实例进行类比逻辑2关系较抽象、较难理解，通过实例在具体数据模型中理解逻辑关系3抽象数据类型是贯穿课程始终的概念，不要求学生开始就深刻理解，在后续的课程中反复应用抽象数据类型的三个视图同心圆式的教学方法媒体使用 多媒体课件：用动画实现存储结构；用动画辅助解释基本概念 教学网络平台：相关教学材料思考题课后导读美William Ford, William Topp著,刘卫东，沈官林译，数据结构C+语言描述，清华大学出版社,第3章抽象数据类型和类和第7章形式数据类型教学后记教学专题算法的基本概念3-1+30教学专题算法的基本概念授课学时 1.6 学时（80分钟）教学章节 1.3授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点算法的定义及特性；伪代码描述算法教学难点 算法的特性；伪代码描述算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 算法及算法的特性 算法和程序的关系 算法的描述方法自然语言算法的描述方法程序流程图算法的描述方法程序设计语言算法的描述方法伪代码 用C+语言中的函数描述算法教学过程课程引入：根据生活中的实例简单理解什么是算法5分钟1给出算法的定义，从使用的角度讲解算法的特性2提出问题：算法=程序？指出程序设计的核心是算法3分别用自然语言、程序设计流程图和C+语言举例描述算法，从应用角度介绍优点、缺点、使用方法、注意事项4综合自然语言、程序设计流程图和C+语言描述算法的优缺点，给出伪代码描述，反映伪代码描述的优势5介绍用C+语言中的函数描述算法，强调用伪代码和C+描述算法是两种抽象级别，体现了抽象分级的思想6课堂练习用伪代码描述算法10分钟5分钟20分钟12分钟15分钟8分钟课程总结：算法的定义和描述方法；算法与程序的关系5分钟教学提示1算法特性要讲清楚透彻，从应用的角度讲解每一个特性的含义，其用途在于判断一个算法在形式上是否正确2伪代码描述算法比较灵活，但掌握存在难度，应先从框架上理解，再通过事例掌握基本方法3强调算法的作用，是不能直接执行的媒体使用 多媒体课件：用动画辅助解释基本概念 教学网络平台：相关教学材料思考题课后导读计算与算法导论章小莉等译，电子工业出版社。关于如何设计一个好的算法请阅读第2章和第8章教学后记教学专题算法及算法分析3-2教学专题算法及算法分析授课学时 1学时（50分钟）教学章节 14授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点用大O记号表示算法的时间教学难点 算法分析的方法；用大O记号表示算法的时间性能教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 度量算法效率的方法事后度量度量算法效率的方法事前估算 算法分析的目的问题规模、基本语句大O记号估算算法时间复杂度的基本方法 最好、最坏、平均情况时间性能教学过程课程引入：通过复习数据结构和算法的基本概念引出本讲内容5分钟1提出问题：什么是算法分析？为什么要进行算法分析？指出算法分析的目的决定了算法分析的方法2给出事后度量方法并指出该方法的局限性，引出事前估算的度量方法3根据一个算法实例给出算法分析的方法4给出问题规模和基本语句概念，从不同角度讲解大O记号5结合顺序查找算法，分析最好、最坏、平均情况的时间性能6说明空间复杂度的分析方法5分钟3分钟15分钟10分钟5分钟5分钟课程总结：算法分析的事前估算方法；用大O记号表示算法的时间性能2分钟教学提示1注意讲授算法分析过程中的思维变换2深刻理解大O记号的含义媒体使用 多媒体课件：用动画给出算法分析方法的过程；再用板书总结 教学网络平台：相关教学材料思考题课后导读 算法分析导论冯舜玺译，机械工业出版社。关于算法分析较深入的讨论见第1章算法分析概述教学后记教学专题线性表（一）4教学专题1线性表的逻辑结构 2线性表的顺序存储结构授课学时 2学时（100分钟）教学章节 21、22授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点线性表的定义；线性表的逻辑特征；顺序表的存储特点；顺序表的基本操作教学难点 线性表的抽象数据类型定义；用伪代码描述算法，描述顺序表的基本操作教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 线性表的定义 线性表的逻辑特征 线性表的抽象数据类型定义线性表的基本操作顺序表的存储特点顺序表类顺序表的基本操作 顺序表的插入、删除操作的时间性能 顺序表的优缺点教学过程课程引入：通过几个二维表的实例3分钟1给出线性表的定义，总结线性表的逻辑特性2复习ADT的三个视图（定义视图、设计视图、实现视图）3给出线性表的抽象数据类型定义4给出顺序表的存储示意图，总结存储特点5复习存储地址的有关内容，给出顺序表的随机存取特性6顺序表类的声明、构造函数、析构函数7给出顺序表插入操作的执行过程，写出伪代码，再写出C+描述8分析插入算法的时间性能，总结算法分析的一般步骤9对于顺序表的删除操作，给出必要的提示，要求学生自行完成10给出顺序表的查找操作的执行过程和算法11总结顺序表的优缺点10 分钟5分钟7分钟10 分钟10 分钟15 分钟15 分钟5分钟3分钟7分钟5分钟课程总结：线性表的逻辑结构；顺序表的存储特点和基本操作5分钟教学提示1线性表的定义要讲清楚透彻，向学生渗透一种理解概念的方法问题分析、抓住要点、引申理解2通过线性表抽象数据类型进一步理解抽象数据类型的三个视图，理解模块化思想，掌握其使用方法3从实用角度出发复习C+语言相关知识4对于顺序表的基本操作算法，要讲思路、讲方法、讲过程，注意培养抽象思维能力和逻辑思维能力。媒体使用 多媒体课件：用动画辅助解释基本概念和模拟顺序表类的基本操作的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构（C语言版）严蔚敏编著，清华大学出版社。参阅相关章节：关于线性表的定义采用二元组的形式数据结构与算法齐德昱编著，清华大学出版社。参阅相关章节：注意顺序表的实现与本教材不同教学后记教学专题线性表（二）5教学专题线性表的链接存储结构及实现授课学时 2学时（100分钟）教学章节 23、24授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点单链表的存储特点；单链表的基本操作的算法及时间性能教学难点 单链表查找、插入和删除算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 单链表的存储要点及存储特点 单链表类 单链表的顺序存取特性单链表的插入、删除操作单链表插入、删除操作的时间性能单链表类的构造函数和析构函数顺序表和单链表的比较教学过程课程引入：通过分析顺序表的缺点引出链接存储结构5分钟1根据一个实例给出线性表链接存储的实际内存状态，复习C+语言中指针的相关知识，抽象出单链表的存储结构示意图2区分指针变量和结点变量，说明头指针、头结点和尾指针3给出单链表类的声明，引申单链表类与顺序表类的关系4给出单链表查找的算法，总结单链表算法的设计模式5设计单链表的插入算法，分析时间性能6比较带头结点和不带头结点的单链表上的插入操作7设计单链表的删除算法，注意分析边界情况8对单链表类的构造函数，给出头插法和尾插法的算法9对单链表类的析构函数，给出必要的提示，要求学生自行完成20 分钟10 分钟 5 分钟10 分钟15 分钟10 分钟5 分钟12 分钟3分钟课程总结：将顺序表和单链表进行比较，总结并比较存储结构及实现方 法5分钟教学提示1熟练使用指针是学好单链表的基本前提2单链表算法设计的关键是多练，安排一节习题课是非常必要的，如果学时较紧，至少通过课堂对相关作业进行点评媒体使用 多媒体课件：用动画模拟单链表各种操作的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构与算法齐德昱编著，清华大学出版社。参阅相关章节：注意单链表表的实现与本教材不同教学后记教学专题线性表（三）6教学专题 1线性表的其它存储方法 2线性表的应用举例授课学时 2学时（100分钟）教学章节 25及课后思考题和习题授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点循环链表、双链表 教学难点 双链表的基本操作教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 循环链表的存储结构 循环链表的操作 双链表的存储结构双链表的基本操作 静态链表的存储结构 静态链表的操作间接寻址存储结构 约瑟夫环问题描述 设计算法求解约瑟夫环问题教学过程课程引入：通过提出问题：在单链表中如何查找某结点的前驱？2分钟1将循环链表的插入算法与单链表的插入算法进行比较2在有头结点的循环链表中，如何查找第1个结点和最后1个结点，引出带尾指针的循环链表3如何更快速得到某结点的前驱（空间换时间），引出双链表4通过图示理解双链表的插入和删除操作，给出算法5如何通过连续存储实现连接关系，引出静态链表6通过图示理解静态链表的插入和删除操作过程7提出问题：将数组和指针结合起来存储线性表会怎样？引出间接寻址8通过图示理解间接存储结构上如何实现插入和删除操作，并与顺序表进行比较9给出约瑟夫环问题的描述，介绍该问题的起源10从逻辑上理解约瑟夫环问题的求解过程11分别用顺序存储结构和单链表存储结构实现约瑟夫环问题12其它问题或习题举例 8 分钟5 分钟5 分钟10 分钟 5 分钟15 分钟 5 分钟5 分钟5 分钟5 分钟20分钟5 分钟课程总结：线性表的各种逻辑结构；线性表的存储特点和基本操作5分钟教学提示1循环链表和双链表是单链表的变形2静态链表和间接寻址是顺序存储和连接存储相结合的产物3重点在于灵活设计各种存储结构的思想4通过例题检验学生掌握线性表及其存储结构的教学效果。媒体使用 多媒体课件：用动画模拟算法和示例的执行过程，用动画辅助解释基本概念 教学网络平台：相关教学材料思考题课后导读数据结构C+实现穆淮扣等编著，科学出版社。参阅相关章节：关于双链表的实现 上网查找约瑟夫环及其变形问题的解决方法，完成关于该问题的课程作业教学后记教学专题栈7教学专题 栈授课学时 2学时（100分钟）教学章节 31、341授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点栈的操作特性、顺序栈及实现、链栈及实现教学难点 两栈共享空间教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 栈的定义及操作特性 栈的抽象数据类型定义 顺序栈及实现两栈共享空间链栈及实现顺序栈和链栈的比较顺序栈应用举例教学过程课程引入：通过复习线性表的插入和删除操作引出栈5分钟1给出栈的定义，通过实例说明栈的操作特性2根据顺序栈存储示意图给出入栈和出栈算法，分析时间性能。总结：顺序栈算法是顺序表算法的简化3如何提高栈空间的利用率？引出两栈共享空间算法4复习单链表，如何改造成链栈？5根据链栈存储示意图给出入栈和出栈算法，分析时间性能。总结：链栈算法是单链表算法的简化6回顾顺序表和单链表的比较方法，引导学生得出顺序栈和链栈的比较结果7给出递归的定义，结合具体实例说明递归是一种描述问题和解决问题的基本方法8递归问题举例9给出描述递归函数运行轨迹的图示方法，强调递归的层次10总结递归函数，强调注意事项10 分钟15 分钟25 分钟 2 分钟15 分钟 3 分钟5 分钟 5 分钟5分钟5分钟课程总结：栈的操作特性；栈的基本操作和栈的应用5分钟教学提示1栈是计算机技术及程序设计中常用的数据结构之一，熟练掌握对后续学习有益2根据生活实例深刻理解栈的操作特性，并与线性表进行比较3从实用角度出发复习C+语言递归知识4通过递归函数的运行轨迹，引导学生理解递归的调用层次以及实参和形参的结合方法，及程序运行过程中工作栈的变化 媒体使用 多媒体课件：用动画辅助解释基本概念和模拟各操作的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构与算法齐德昱编著，清华大学出版社。参阅相关章节：注意用抽象类和继承类实现栈数据结构刘大友等编著，高等教育出版社，相关章节对递归和汉诺塔问题进行了较深入的介绍教学后记教学专题队列8教学专题 队列授课学时 2学时（100分钟）教学章节 32、342授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点队列的操作特性、循环队列及实现、链队列及实现教学难点 循环队列的存储方法及队空和队满的判断教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 队列的定义及操作特性 队列的抽象数据类型定义 顺序队列的假溢出现象循环队列及实现链队列及实现循环队列和链队列的比较队列的应用举例教学过程课程引入：通过复习线性表和栈的插入、删除操作引出栈5 分钟1给出队列的定义，通过实例说明队列的操作特性2如何存储？引出队列的顺序存储和链接存储3假溢出问题？改造顺序表，得出循环队列的存储方法4如何判断队空和队满？分析各种解决方案5如何改造单链表实现队列的链接存储6链式队列的出队算法需注意边界情况（判断队空）7引导学生比较循环队列和链式队列8队列问题应用举例10 分钟 5 分钟25 分钟15 分钟10 分钟15 分钟 5 分钟5 分钟课程总结：队列的操作特性；队列的基本操作和队列的应用5分钟教学提示1队列是程序设计中常用的数据结构之一，熟练掌握对后续学习有益2根据生活实例深刻理解队列的操作特性，并与线性表和栈进行比较3通过循环队列的引入过程启发学生的逻辑思维能力 媒体使用 多媒体课件：用动画辅助解释基本概念和模拟各操作的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构与算法齐德昱编著，清华大学出版社。参阅相关章节：注意用抽象类和继承类实现队列教学后记教学专题串9教学专题 串授课学时 2学时（100分钟）教学章节 33、343授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点串的定义及基本操作、BF算法、KMP算法教学难点 模式匹配算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 串的定义及基本概念 串的抽象数据类型定义 串的基本操作串的存储结构BF算法KMP算法求匹配失效数组next 教学过程课程引入：通过给出串的定义，并与线性表进行比较5 分钟1介绍串的基本概念，补充字符集的相关知识2给出串的ADT定义，分析串的基本操作和特点3如何改造顺序表，实现串的顺序存储，并引出串的压缩和非压缩存储4如何改造链表，实现串的链接存储，分析各种解决方案5给出BF算法的基本思想，运行实例和BF算法6分析BF算法效率低的原因，引出KMP算法 7根据部分匹配特征，给出失效数组next的求解方法8给出KMP算法，简单分析KMP算法的时间性能10 分钟 5 分钟10 分钟 5 分钟20 分钟10 分钟25 分钟5 分钟课程总结：串的特性；模式匹配算法5分钟教学提示1由于学时原因，本专题只要求理解，但需强调串的基本操作2KMP算法的技巧性很强，需要注意讲授方法媒体使用 多媒体课件：用动画模拟各算法的动态执行过程 教学网络平台：相关教学材料思考题课后导读算法设计与分析王红梅编著，清华大学出版社。参阅相关章节：注意KMP算法的技巧性教学后记教学专题数组及矩阵的压缩存储10+25教学专题 数组及矩阵的压缩存储授课学时 25学时（125分钟）教学章节 41、42授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点二维数组的寻址方法、对称矩阵的寻址方法、稀疏矩阵的压缩存储方法教学难点 数组的存储与寻址、稀疏矩阵压缩存储后转置操作的实现教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 数组的抽象数据类型定义 二维数组的存储方法及寻址 矩阵压缩存储的基本思想特殊矩阵和稀疏矩阵的概念特殊矩阵压缩存储及寻址稀疏矩阵的三元组顺序表稀疏矩阵的转置运算教学过程课程引入：通过复习C+语言的数组定义，并与线性表进行比较3 分钟1给出数组的基本操作和ADT定义2复习顺序表和链表的优缺点，得出数组的顺序存储结构3画出行优先存储二维数组的示意图，给出存储方法与寻址方法4引导学生仿照行优先，画出列优先存储二维数组的示意图，给出存储方法与寻址方法，并引申出n维(n2)数组的存储方法5从矩阵的应用背景出发，给出矩阵压缩存储的基本思想6根据对称矩阵的特点给出压缩存储方法和寻址方法7根据三角矩阵的特点给出压缩存储方法和寻址方法8给出稀疏矩阵的三元组表的存储方法9根据实例画出三元组顺序表的存储示意图，定义存储结构10根据稀疏矩阵转置算法I 的基本思想运行实例，写出算法11分析转置算法I 的缺点，引出转置算法II ，运行实例，根据算法的执行过程，涉及辅助数据结构，写出转置算法II。12由三元组顺序表的缺点引出十字链表，划出存储示意图 5 分钟 3 分钟10 分钟 7 分钟 5 分钟15 分钟 5 分钟6 分钟6 分钟20 分钟30 分钟5 分钟课程总结：数组的寻址方法；特殊矩阵的存储与寻址方法5 分钟教学提示1深入剖析二维数组的内部实现，从根本上理解数组的寻址方法2对于特殊矩阵压缩后的寻址，重点讲方法，灵活掌握存储结构的设计方法3稀疏矩阵压缩存储后转置算法的讲授思路：给出基本思想运行实例伪代码描述C+描述，重点讲设计过程 媒体使用 多媒体课件：用动画模拟稀疏矩阵转置算法的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：包含更复杂的稀疏矩阵十字链表类的定义和实现教学后记教学专题广义表及数组应用举例11-25教学专题 广义表及数组应用举例授课学时 15学时（75分钟）教学章节 43、44授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点广义表的定义及基本概念、广义表的存储方法教学难点 广义表的存储结构、广义表及本操作的实现教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 广义表的定义及基本概念 广义表的抽象数据类型定义 广义表的存储结构广义表基本操作的实现数组应用举例教学过程课程引入：通过给出广义表的定义，将其与线性表进行比较3 分钟1通过给出几个广义的例子，给出广义表的ADT定义2提问题：广义表可以顺序存储吗？采用链接存储结构结点能统一吗？引出头尾表示法3画出头尾表示法存储示意图，分析其优缺点4结合存储示意图，给出基本操作的实现5数组应用举例 5 分钟 5 分钟 10 分钟18 分钟30 分钟课程总结：广义表的逻辑结构、存储结构及实现 4 分钟教学提示1注意概念讲授的准确性2应遵循链接存储的基本思想讲解广义表的存储结构3通过例子讲解数组的正确运用 媒体使用 多媒体课件：用动画辅助解释基本概念，展示广义表的存储结构 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：包含广义表的其他存储方法和广义表的遍历算法教学后记教学专题树的逻辑结构和存储结构12教学专题 树的逻辑结构和存储结构授课学时 2学时（100分钟）教学章节 51、52授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点树的定义和基本术语、树的遍历操作、树的存储表示法教学难点树的遍历操作、树的孩子链表示法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 树的定义 树的基本术语 树的抽象数据类型定义树的遍历操作树的双亲表示法树的孩子链表示法树的孩子兄弟表示法教学过程课程引入：举例现实中的非线性问题有些是树形结构，如何解决？3 分钟1给出树的定义，在与线性表定义比较的基础上，注重理解树的逻辑特征2结合实例分类讲授树的基本术语3理解什么是遍历，重点讲清访问的含义和遍历次序4由树的组成得到前序和后序遍历，由树的层次特征得到层序遍历5树的遍历操作定义采用递归方法，（树结构本身具有递归特性），相应问题的求解也常用递归方法6结合树的实例练习各种遍历方法7从如何表示树的逻辑关系引出树的存储结构8从双亲角度考虑分析结点间的逻辑关系，画出双亲存储示意图9从孩子角度考虑给出多重链表解决方案，分析缺点及原因，引出孩子链表表示法，分析结点间的逻辑关系10将双亲表示和孩子表示结合，形成双亲孩子表示法11观察任意一棵树，某结点的第1个孩子和右兄弟都具有惟一性，引出孩子兄弟表示法12根据实例画出孩子兄弟存储示意图，分析结点间的逻辑关系 5 分钟 25 分钟 4 分钟 2 分钟 8 分钟 3 分钟5 分钟10 分钟15 分钟2 分钟3 分钟10 分钟课程总结：树的逻辑结构；树的存储结构5 分钟教学提示1介绍树结构在计算机软件系统中的应用2从逻辑上理解遍历操作的执行过程，再探讨基于存储结构的实现3注意树的各种存储结构中体现的结点间的逻辑关系 媒体使用 多媒体课件：用动画模拟树的遍历过程，展示树的存储过程，辅助解释树的基本术语和基本方法 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：给出了树遍历操作的具体实现及树的其它存储方法计算机程序设计艺术Knuth著 第4卷第4册，生成所有可能的树教学后记教学专题二叉树的逻辑结构13教学专题 二叉树的逻辑结构授课学时 2学时（100分钟）教学章节 53授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点二叉树的定义、二叉树的性质、二叉树的遍历操作教学难点二叉树性质的证明、二叉树的遍历操作教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 二叉树的定义 二叉树的基本形态 几种特殊的二叉树二叉树的性质二叉树的抽象数据类型定义二叉树的遍历操作教学过程课程引入：通过分析一般树的存储问题，提出二叉树3 分钟1给出二叉树的定义，注重强调二叉树和树是两种不同的树结构2根据二叉树的定义得出二叉树的基本形态3给出斜树、满二叉树、完全二叉树的定义，说明其特点4给出并证明二叉树的性质5给出二叉树的ADT定义6复习树的遍历，给出遍历二叉树的定义7由二叉树的组成得到前、中、后三种遍历次序，由树的层次特征得到层序遍历8给出遍历次序的操作定义9已知一棵二叉树的前序序列和中序序列，如何构造惟一一棵二叉树？给出构造过程 5 分钟5 分钟15 分钟25 分钟 5 分钟 5 分钟 7 分钟15 分钟10 分钟课程总结：二叉树的性质；二叉树的遍历5 分钟教学提示1强调二叉树不是树的特例，二叉树和树是两种不同的树结构2基于二叉链表的二叉树的遍历的递归思想媒体使用 多媒体课件：用动画模拟二叉树的遍历过程，辅助解释二叉树的基本概念 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：给出了有关扩充二叉树及其性质教学后记教学专题二叉树的存储结构及实现14教学专题 二叉树的存储结构及实现授课学时 2学时（100分钟）教学章节 541、543授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点二叉链表存储结构、二叉树遍历算法教学难点 二叉树遍历算法的递归与非递归实现教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 二叉树的顺序存储结构 二叉链表存储结构 二叉树遍历算法的递归实现二叉树前序、中序遍历的非递归实现二叉树后序遍历的非递归实现二叉树的构造算法三叉链表及其静态链表形式教学过程课程引入：通过分析二叉树结点间的逻辑关系，如何解决存储问题？5 分钟1给出二叉树的顺序存储方法，分析缺点，确定适用情况2复习单链表结点结构，给出二叉链表的结点结构3根据二叉树的ADT定义，给出二叉链表类4根据二叉树的前序遍历操作定义，给出前序遍历的递归算法，引导学生写出中序和后序遍历的算法5根据前序遍历的递归算法，引出前序遍历的非递归算法6分析中、后序遍历的执行过程，非递归算法要求学生课后完成7分析层序遍历的执行过程，写出层序遍历算法8给出扩展二叉树的定义，给出构造函数9提问题：如何从二叉链表中快速查找双亲？引出三叉链表10 分钟 5 分钟 5 分钟10 分钟20 分钟10 分钟10 分钟15 分钟 5 分钟课程总结：二叉树的存储结构、二叉树遍历算法的递归与非递归实现 5 分钟教学提示1二叉树的顺序存储的适用情况，用存储位置表示逻辑关系2二叉链表存储结构如何体现结点间的逻辑关系，递归遍历过程3在深入剖析二叉树遍历算法执行过程的基础上，给出非递归遍历算法 媒体使用 多媒体课件：用动画模拟二叉树遍历算法的执行过程 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：给出了树遍历操作的具体实现及树的其它存储方法教学后记教学专题树、森林与二叉树间的转换、应用举例15教学专题1树、森林与二叉树间的转换2二叉树与树的应用举例授课学时 2学时（100分钟）教学章节 55、56授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点树和二叉树之间的转换、Huffman树的构造方法、Huffman编码方法教学难点 二叉树转换为树、Huffman算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 树转换为二叉树 森林转换为二叉树 二叉树转换为树或森林树、森林与二叉树转换的形式化描述森林的遍历Huffman树的定义Huffman树的构造方法Huffman树的构造算法Huffman编码与解码的方法Huffman编码算法树的应用举例教学过程课程引入：通过给出树和二叉树转换的目的2 分钟1画出一棵树的孩子兄弟表示法存储示意图和对应二叉树的二叉链表存储示意图，引出树和二叉树转换的媒介和基本方法2强调森林是树的集合，观察树转换为二叉树的特点，得出森林转换为二叉树的方法3树和二叉树转换是互逆的，给出二叉树转换为树或森林的方法4复习树的遍历方法，给出森林的遍历方法5结合具体实例介绍Huffman树的相关概念，重点解释权值6观察Huffman树的特点，给出Huffman算法的基本思想，运行构造Huffman树的过程7设计Huffman树的存储结构，给出算法的伪代码描述及C+描述8介绍等长编码和不等长编码，通过实例强调在设计不等长编码时，必须考虑解码的惟一性，引出前缀码9分析Huffman编码算法的关键问题，具体实现由学生课后完成10给出树的应用实例的问题描述和分析，具体实现由学生课后完成10 分钟 5 分钟 5 分钟 3 分钟5 分钟10 分钟20 分钟5 分钟5 分钟7 分钟20 分钟课程总结：二叉树与树和森林的关系；Huffman树的构造和Huffman编码的要点3 分钟教学提示1以二叉链表为媒介，导出树或森林与二叉树之间的关系2通过Huffman树的构造解决Huffman编码问题媒体使用 多媒体课件：用动画模拟树和二叉树的转换过程，用动画解析Huffman算法的动态执行过程，辅助解释基本概念 教学网络平台：相关教学材料思考题课后导读数据结构与算法许卓群编著，高等教育出版社。参阅相关章节：给出了Huffman编码是前缀编码以及Huffman编码是最短前缀编码的证明教学后记教学专题图的逻辑结构16教学专题图的逻辑结构授课学时 2学时（100分钟）教学章节 61授课对象 计算机学科各专业本科生教学类型 理论课授课形式 课堂讲授教学重点图的定义及基本术语、图的遍历操作教学难点图的遍历操作教学内容和教学目标知识点学习要求了解理解掌握熟练掌握 图的定义 图的基本术语 图的抽象数据类型定义图的深度优先遍历图的广度优先遍历教学过程课程引入：举例现实中的非线性问题有些是图形结构，如何解决？2 分钟1给出图的定义，注意与线性结构、树结构进行比较2通过具体实例介绍图的基本术语3通过复习遍历等相关概念，提出图的遍历要解决哪些关键问题4给出深度优先遍历的思想，通过实例分析深度优先遍历过程中工作栈的状态变化，给出算法的伪代码描述5给出深度优先遍历的思想，通过实例分析深度优先遍历过程中工作栈的状态变化，给出算法的伪代码描述5 分钟45分钟10 分钟20 分钟15 分钟课程总结：图的深度、广度优先遍历方法，两者之间的区别 3 分钟教学提示1注意几种数据结构之间的比较2重点从逻辑上搞清图遍历的思想和遍历过程媒体使用 多媒体课件：用动画模