2010《数据结构》教案

1、数据结构教案编号：001教学章节开课（课程综述）授课对象教学课型理论课授课形式课堂讲授授课学时1学时教学重点为什么要学习数据结构这门课；如何学习数据结构这门课教学难点如何将学习方法在本课程的学习过程中实际运用教 学 过 程 设 计时间分配1、 简单自我介绍2、 介绍课程性质为什么数据结构课程在教学计划中处于核心地位“练武不练功，到头一场空”，一味在程序设计语言中钻研不会大幅度提高程序设计能力为什么要学习数据结构3、 学习目标从问题的求解过程入手，介绍数据结构的学习目标4、 学习方法和要求强调课外时间的利用、做习题和做实验在本课程中的重要性5、 介绍教材提倡读好书、多读书、会读书，进而强调在当今

2、社会，“文盲不再是目不识丁的人，而是不会学习的人”会学习多半是在大学养成的好习惯6、 介绍网络教学资源介绍精品课程网站，充分利用网络教学资源信息化、网络社会化，资源的检索和利用是一项基本技能15分钟10分钟10分钟5分钟5分钟教学策略 开课前，要激发学生的学习兴趣，老师本身要表现出热爱所教内容，从而感染和影响学生热爱所学的内容，认识到本课程的重要性，产生学习的动力； 开课要交代本课程的教学目标，使学生明确为什么要学习这门课程，通过本课程的学习应该学会些什么，应该获得哪些能力 ； 有些学生由于前导课程C语言学的不好，对这门课产生顾虑，所以，要让学生知道，这门课的教学目标之一就是进一步培养程序设计

3、能力，在这门课程中补语言的知识还来得及。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读 查阅相关学校的考研指导，下载一些数据结构的考研真题，搜索数据结构教学网站，为后续学习做准备； 搜索相关用人单位面试题。教学后记教学感想、学生掌握程度、学生参与情况、意外发现、教学效果、个别疏漏及补救：数据结构教案编号：002教学章节第一章 绪论授课对象教学课型理论课授课形式课堂讲授授课学时4学时教学重点（1）数据结构的基本概念；（2）数据的逻辑结构、存储结构以及二者之间的关系；（3）算法及特点；（4）大O记号表示。教学难点（1）抽象数据类型的定义

4、和使用。 （2）算法的时间复杂度分析。教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合数据结构的起源和发展程序设计的实质数据结构定义、分类数据结构中涉及的概念和术语数据的逻辑结构和存储结构抽象数据类型的定义、定义格式抽象数据类型C语言描述的基本规定算法与程序的定义算法设计的要求问题规模、基本语句算法效率的度量时间复杂度最好、最坏、平均情况的时间性能算法存储空间的度量空间复杂度态度积极主动学习能力 学会定义数据结构和抽象数据类型 学会分析算法的时间复杂度和空间复杂度教 学 过 程 设 计时间分配回忆：为什么要学习数据结构？总结导入新课1.1 数据结构的兴起和发展介绍数据结构

5、课程体系的起源。了解历史专业素养提出问题：程序设计的实质是什么？通过具体实例得出答案介绍数据结构与程序设计的关系。强调数据结构始终是程序设计的基础从发展的观点和应用的观点讨论数据结构的发展1.2 数据结构的研究对象从计算机求解问题的一般过程入手，建立抽象和数据模型的初步概念一、计算机可用于求解数值问题复习：以前用C语言编写数值计算问题的步骤二、计算机可用于求解非数值计算问题图书馆的书目检索系统自动化问题 人机对弈问题多叉路口交通灯管理问题教学计划编排问题通过具体实例总结数据结构的研究对象，注意引申数据元素之间的关系教学提示： 从问题的求解过程入手，理解“数据结构+算法程序”，理解数据结构和算法

6、在问题求解中的作用 数据结构是从非数值问题抽象出来的数据模型，这个阶段的学生还没有抽象和模型的概念，需要补充抽象和模型的相关概念1.3 数据结构的基本概念回忆：根据生活中的实例简单理解什么是数据结构？给出数据的定义，举例说明什么是数据给出数据元素和数据项的定义，根据上一讲的4个例子体会如何界定数据元素，总结数据、数据元素和数据项之间的关系给出数据对象的定义，引入数据结构的定义，从问题求解的角度强调数据结构包含逻辑结构和存储结构两个方面数据结构的图形表示方法给出逻辑结构的定义，重点解释逻辑关系数据结构的形式化定义给出存储结构的定义，重点强调如何表示逻辑关系从数据表示的角度总结逻辑结构和存储结构的

7、关系结合C语言中学过的数据类型，总结高级语言中的两类数据类型：原子类型和结构类型。在理解数据类型和抽象的基础上，给出抽象数据类型的定义，说明：数据模型 + 一组操作 = ADT抽象数据类型的形式化定义格式抽象数据类型形式化定义举例抽象数据类型的表示与实现结合抽象数据类型的定义说明数据结构的访问接口教学提示： 注意对基本概念的引入和阐述，抓住要点，注意用生活中的实例进行类比 逻辑关系比较抽象、较难理解，通过实例在具体数据模型中理解逻辑关系 抽象数据类型是贯穿课程始终的概念，不要求学生开始就深刻理解，在后续课程中反复应用及强调抽象数据类型的概念1.4 算法及算法分析根据生活中的实例简单理解什么是算

8、法，给出算法的定义结合欧几里德算法，从使用的角度讲解算法的五大特性提出问题：算法设计的要求是什么？从例子判断代码是否为算法 算法 = 程序？指出程序设计的核心是算法分别用自然语言、流程图和C语言描述欧几里德算法，从应用的角度介绍优点、缺点、使用方法、注意事项综合自然语言、流程图和C语言描述欧几里德算法的优缺点，给出伪代码描述，使学生从中理解伪代码描述算法的好处。介绍用C语言中的函数描述算法，强调用伪代码和C描述算法是两种不同级别的抽象，体现了抽象分级的思想课堂练习：用伪代码描述算法教学提示： 要把算法的特性讲透，从应用的角度讲解每一个特性的含义，其用途在于判断一个算法在形式上是否正确 伪代码描

9、述算法较灵活，但是，往往越灵活的知识越不好把握。首先从框架上理解，再通过具体实例掌握基本方法 学生通常都会将书中的算法照搬到计算机中，不能执行还奇怪强调算法是由人（或某种计算模型）来执行的 复习：数据结构和算法的基本概念，引出本讲的教学内容提出问题：什么是算法分析？为什么要进行算法分析？指出算法分析的目的决定了算法分析的方法给出事后度量方法并指出这种方法的局限性，引出事前估算的度量方法根据一个算法实例给出算法分析的方法，注意讲授过程中思维的交换给出问题规模和基本语句的概念，从不同角度讲解大O记号给出几个例子进行分析结合顺序查找算法，分析最好、最坏、平均情况的时间性能简单说明空间复杂度的分析方法

10、算法的存储量包括：1、输入数据所占空间2、程序本身所占空间3、辅助变量所占空间随堂小结：重点：1、熟悉各名词、术语的含义，掌握基本概念 2、理解算法五个要素的确切含义 3、掌握计算语句频度和估算算法时间性能的方法学习方式：理解、记忆、掌握教学提示： 讲授算法分析的重点在于讲授过程中思维的变换，要抓住关键点理顺思路，引导学生跟着思路走 大O记号是本章以及本课程的难点和重点，从不同角度（定义、极限、函数曲线等）深刻理解其根本含义2分钟2分钟5分钟7分钟2分钟2分钟16分钟9分钟=2分钟3分钟5分钟2分钟2分钟8分钟5分钟5分钟1分钟2分钟6分钟4分钟=4分钟10分钟3分钟15分钟4分钟3分钟6分钟

11、=4分钟4分钟3分钟13分钟8分钟5分钟5分钟2分钟教学策略在授课过程中采用多媒体教学，首先还原问题的本来面目提出问题，引导学生积极参与尝试解决问题，在讨论的基础上给出结论讲授教学内容、解决问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读 在数据结构方面，最早的权威著作是Knuth所著的系列丛书计算机程序设计艺术，这套书非常值得一看 许多人致力于计算机科学中的问题求解，实际上这正是该领域吸引人的地方。如何求解问题（曹庆译 中国水利水电出版社）是提高问题求解能力的经典著

12、作 关于抽象数据类型，数据结构与算法（许卓群 高等教育出版社）给出了较深入的讨论 关于如何设计一个好的算法请阅读计算与算法导论（章小莉 电子工业出版社）第2章和第8章 算法分析的方法最初源于Knuth所著的系列丛书计算机程序设计艺术（第三卷）。 关于算法分析较深入的讨论请阅读算法分析导论（冯舜玺 机械工业出版社）教学后记教学感想：学生掌握程度：学生参与情况：意外发现：教学效果：个别疏漏及补救：数据结构教案编号003教学章节第二章 线性表授课对象教学课型理论课授课形式课堂讲授授课学时5学时教学重点（1）顺序存储结构和链式存储结构的基本思想；（2）基于顺序表和单链表基本操作的实现；（3）基于顺序表

13、和单链表基本操作的时间性能分析；（4）顺序表和单链表之间的比较。教学难点（1）线性表的抽象数据类型定义；（2）基于单链表的算法设计，尤其是要求算法满足一定的时间性能和空间性能；（3）双链表操作的实现教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合线性表的逻辑结构定义、抽象数据类型定义线性表的基本操作线性表的两种表示方法：顺序存储和链式存储基于顺序表和单链表基本操作的实现基于顺序表和单链表基本操作的时间性能分析顺序表和单链表之间的比较，适用场合稀疏多项式的抽象数据类型定义、表示稀疏多项式加法的实现约瑟夫环问题态度积极主动学习能力 熟练掌握线性表的两种存储结构的表示和其上基本

14、操作的实现； 会用算法的时间复杂度和空间复杂分析方法分析这些操作； 学会用线性这种数据结构解决实际问题并对编写的算法复杂性进行分析教 学 过 程 设 计时间分配复习：数据结构的分类 数据的存储结构总结线性结构的特点，并导入新课指出线性结构的特点2.1 线性表的类型定义通过几个二维表的实例引出线性表的定义给出线性表的定义，注意强调要点，总结线性表的特性给出线性表的抽象数据类型定义，重点讲述基本操作部分。包括：结构初始化操作、结构销毁操作、引用型操作、加工型操作、复杂操作。注意结合算法实例讲解。利用线性表实现集合的并、集合的无重复并，线性表的合并2.2 线性表的顺序表示和实现顺序表给出顺序表的存储

15、示意图，强调存储要点，总结存储特点复习存储地址的有关内容，给出顺序表的随机存取特性顺序存储的地址计算方法顺序表存储结构的定义教学提示： 有关线性表的内容比较简单，学生容易掌握，但要透彻理解并不容易 把线性表定义的讲透，通过线性表定义的讲授方法，向学生渗透一种理解基本概念的方法问题分解、抓住要点、引申 通过线性表抽象数据类型进一步理解抽象数据类型的三个视图（使用视图、设计视图、实现视图），理解其模块化思想，掌握其使用方法，并为后续内容做铺垫 在授课过程中要复习C语言的相关知识，复习遵循的原则是“实用至上”，从应用的角度复习，注意凝练，切忌“多而杂”线性表的基本操作在顺序表中的实现与复杂度分析，注

16、意结合算法实例讲解。例子：初始化、建立、插入、递增插入、递减插入、删除、按位查找、按值查找，给出执行过程，再写出算法总结顺序表的优缺点教学提示： 对于顺序表的算法（插入、删除）要讲过程、讲思路、讲方法，注意培养抽象思维能力和逻辑思维能力，这是本课程技能培养方面的教学目的23 线性表的链接存储结构及实现由顺序表的缺点引出链接存储结构根据一个实例给出线性表链接存储的实际内存状态，复习C语言中指针的有关知识，抽象出单链表的存储示意图给出单链表的存储结构定义及C语言描述区分指针变量和结点变量，说明头指针、尾标志和头结点给出单链表的按位查找算法，总结单链表算法的设计模式设计单链表的插入算法，分析时间性能

17、比较带头结点和不带头结点的单链表上的插入操作给出单链表的删除算法，注意分析边界情况给出单链表建立算法中的头插法和尾插法提出问题：如何在连续存储区实现链接存储？引出静态链表给出静态链表的定义，总结静态链表存储结构的优缺点通过图示理解静态链表的插入和删除操作的执行过程提出问题：将数组和指针结合起来存储线性表会怎样？引出间接寻址通过图示理解间接寻址存储结构上如何实现插入和删除操作，并与顺序表的插入和删除操作做比较24 顺序表和单链表的比较将顺序表和单链表进行比较，总结比较存储结构的方法25 线性表的其它存储方法提出问题：在单链表中如何找某结点的前驱？从而引出循环链表将循环链表的插入算法与单链表的插入

18、算法作比较讲述例子：将单循环链表倒置或逆置。提出问题：在头指针批示的循环链表中，如何查找开始结点和终端结点？引出带尾指针的循环链表提出问题：如何快速求得某结点的前驱？引出双链表通过图示理解双链表的插入和删除操作，写出算法教学提示： 熟练使用指针是学好单链表的基本前提，首先需要复习指针的有关内容 在精讲单链表查找算法的基础上，总结单链表算法的设计模式 单链表算法设计的关键是多练 静态链表和间接寻址是顺序存储和链接存储相结合的产物，要引申各存储结构之间的关系 循环链表和双链表是单链表的变形 存储结构的设计是个很灵活的过程，本讲的重点在于种存储结构的设计思想，要把灵活的思想讲出来2.6 线性表的应用

19、举例A 一元多项式的表示及相加给出一元多项式的数学表示形式和线性表表示形式提出这种表示形式不适合表示稀疏多项式给出一元稀疏多项式的数学表示形式和线性表表示形式抽象数据类型一元多项式的定义，存储结构的选取分析一元多项式的链式存储结构定义基本操作的算法实现和复杂性分析，包括单个多项式的创建、两个多项式相加等B 约瑟夫环给出约瑟夫环问题的描述，介绍该问题的起源运行一个实例，从逻辑上理解约瑟夫环问题的求解过程，抽象出数据模型复习顺序表存储结构，考虑用顺序存储结构实现约瑟夫环问题，设计具体的存储结构，设计算法实现求解复习单链表存储结构，考虑用单链表存储结构实现约瑟夫环问题，设计具体的存储结构，设计算法实

20、现求解C 其它应用教学提示： 一元多项式问题、约瑟夫环问题，等等，是对本章教学效果的检验，考查学生是否掌握了线性表及其存储结构，是否能在实际问题中设计合适的存储结构和算法实现问题求解 通过一元多项式问题、约瑟夫环问题等进一步理解数据结构和算法在问题求解中的重要地位，认识到数据结构课程的重要性，引起学生的学习兴趣，为后续课程的学习奠定基础 算法设计的关键是多练，留下几个例子在课堂进行练习，或作为作业，然后再讲评本章小结主要内容：1、 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性结构称为顺序表，用后者

21、表示的线性表称为链表。2、 熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现算法。3、 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。难点：线性表抽象数据类型的理解，顺序表、链表基本操作的实现算法，基本时间复杂度分析方法和空间复杂度分析方法的掌握。学习方式：理解、记忆、掌握3分钟3分钟6分钟5分钟10分钟2分钟8分钟4分钟2分钟2分钟=40分钟5分钟=5分钟7分钟5分钟5分钟5分钟5分钟5分钟4分钟4分钟=8分钟10分钟4分钟10分钟5分钟8分钟=15分钟15分钟15分钟教学策略在授课过程中采用多媒体教学，首先还原问题的本来面目提出问题，引导学生

22、积极参与尝试解决问题，在讨论的基础上给出结论讲授教学内容、解决问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读 关于线性表的定义有二元组、三元组、五元组，请参阅相关资料 顺序表、单链表的实现方法在种资料中不尽相同，请参阅相关内容 线性表的间接寻址存储结构在各教材中的介绍都较少。 约瑟夫环问题有很多种变形，上网查找约瑟夫环及其变形问题的解决方法，要求写一份约瑟夫环问题的相关作业教学后记教学感想：学生掌握程度：学生参与情况：意外发现：教学效果：个别疏漏及补救：数据结构教案

23、编号004教学章节第三章 栈和队列授课对象教学课型理论课授课形式课堂讲授授课学时4学时教学重点（1）栈和队列的操作特性；（2）栈和队列基本操作的实现。教学难点（1）两栈共享共间的实现； （2）循环队列的组织及队空和队满的判定条件。教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合栈的抽象数据类型定义、表示和实现栈的基本操作算法和复杂性分析顺序栈及实现链栈及实现顺序栈和链栈的比较栈的递归实现原理、算法执行过程中栈的状态变化利用栈编写递归程序两栈共享空间队列的抽象数据类型定义栈与队列的比较顺序队列的假溢出现象队列的链式表示和顺序表示循环队列队列的基本操作算法和复杂性分析态度积极

24、主动学习能力 熟练掌握栈和队列这两种抽象数据类型的特点，并能在应用问题中正确选择使用哪种数据结构； 熟练掌握栈和队列这两种结构的顺序表示和链式表示，会应用它们的基本操作算法，学会分析算法的时间复杂性和空间复杂性； 理解递归算法的执行原理； 理解两栈共享空间的含义。教 学 过 程 设 计时间分配复习：线性表的插入和删除操作提出问题：1、什么是线性结构？2、你见过餐馆中一叠叠的盘子吗？如果它们是按1,2,n的次序往上叠的，那么使用时候的次序应该是怎样的呢？3、在日常生活中，我们去买火车票，我们经常要做的事情是什么？总结导入新课受限的线性表31 栈给出栈的定义，通过实例说明栈的操作特性，给出栈的抽象

25、类型根据顺序栈存储示意图写出入栈和出栈算法，分析时间性能基本操作算法实现与分析提出问题：如何存储具有相同数据类型的两个栈？对解决方案进行分析，引出并实现两栈共享空间复习：单链表的相关知识提出问题：如何改造单链表形成链栈？给出链栈的存储方案根据链栈存储示意图写出入栈和出栈算法，分析时间性能回顾顺序表和单链表的比较方法，引导学生自己得出顺序栈和链栈的比较结果教学提示： 栈是程序设计中常常用到的一种数据结构，栈的研究历史比较长，也比较成熟。 熟练掌握并学会使用栈对后面的学习十分有益 注意将栈与线性表进行比较，根据生活中的实例深刻理解栈的操作特性 多准备一些栈的应用实例，如果学时有多，给出栈在计算机软

26、件系统的一些应用实例32 栈的应用列举算法实例、分析算法的复杂性提出问题：如何用C语言编写一个嵌套调用程序？举例说明。学生回答：指出嵌套与递归的区别与联系嵌套既可以自己调用自己，也可以调用别人；递归程序只能是自己调用自己。总结导入新课用栈实现递归的原理33 栈与递归的实现结合例子说明，函数调用之前系统完成的工作简介结合例子说明，调用返回之前系统完成的工作简介给出递归的定义，结合具体实例说明递归是一种描述问题和解决问题的基本方法结合求n!、求斐波那契数列等问题的过程，讨论递归的两个基本要素解释汉诺塔问题，说明其递归求解过程，给出求解汉诺塔问题的递归算法给出描述递归函数运行轨迹的图示方法，画出汉诺

27、塔算法的运行轨迹，强调递归的层次说明递归函数内部执行过程，画出汉诺塔算法执行过程中工作栈的变化状态总结递归函数，强调注意事项递归算法和非递归算法的转换方法教学提示： 递归是一个比较难理解的技术，学生不容易掌握 通过递归函数的运行轨迹让学生理解递归的调用层次以及实参和形参的结合方法，通过递归函数运行中工作栈的变化深入剖析递归算法的内部执行过程34 队列复习：线性表的插入和删除操作，栈的相关操作，引出队列给出队列的定义，通过实例说明队列的操作特性，给出队列抽象数据类型的定义队列的分类：一端进、另一端出的队列；双端队列用图示意说明队列的特点提出问题：如何存储队列？引出队列的顺序存储结构和链接存储结构

28、改造顺序表，得出循环队列的存储方法提出问题：如何判断循环队列的队空和队满？分析各种方案。在解决了循环队列的 关键问题后，基本操作的实现略讲提出问题：如何改造单链表实现队列的链接存储？引出链队列的存储方法链队列的出队算法要注意边界情况，其他基本操作的实现可以略讲引导学生比较循环队列和链队列队列的应用举例教学提示： 队列是程序设计中常常用到的一种数据结构，学会使用队列对后面的学习十分有益 注意将队列与线性表、栈做比较，根据生活中的实例深刻理解队列的操作特点 注意通过循环队列的引入过程启发学生的逻辑思维能力本章小结线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；

29、栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：1. 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。2. 用途不同：线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、操作系统作业调度和简化设计等。3分钟2分钟8分钟12分钟5分钟15分钟=3分钟12分钟3分钟8分钟3分钟5分钟5分钟6分钟=6分钟6分钟6分钟2分钟5分钟4分钟10分钟6分钟=3分钟15分钟10分钟5分钟6分钟2分钟4分钟教学策略在授课过程中采

30、用多媒体教学，首先还原问题的本来面目提出问题，引导学生积极参与尝试解决问题，在讨论的基础上给出结论讲授教学内容、解决问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读 回顾C语言中学过的函数嵌套调用，深入理解函数调用时系统的工作 关于栈与队列的实现，数据结构与算法（齐德昱编著 清华大学出版社）中有用面向对象方法实现的 在数据结构（刘大友等 高等教育出版社）中对递归和汉诺塔问题进行了更深入的介绍教学后记教学感想：学生掌握程度：学生参与情况：意外发现：教学效果：个别疏漏及补

31、救：数据结构教案编号005教学章节第四章 串授课对象教学课型理论课授课形式课堂讲授授课学时2学时教学重点（1）串的数据类型定义；（2）串的三种存储表示；（3）串的模式匹配算法教学难点改进的模式匹配KMP 算法教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合串的定义及基本概念串的抽象数据类型串的基本运算的实现串的存储结构串的模式匹配算法态度积极主动学习能力使用C语言提供的串操作函数构造与串相关的算法，解决简单的应用问题教 学 过 程 设 计时间分配提出问题：结合C语言程序设计谈谈自己对串类型的认识？字符串的应用范围如何？要有效地实现字符串的处理，如何设计其存储结构？结合程序

32、设计的实践，启发学生串应具备哪些基本操作？总结导入新课4.1 串的逻辑结构给出串的定义，在与线性表比较的基础上，总结串的特性介绍串的基本概念，补充字符集的相关知识，强调只有一个字的符串与字符的区别给出串的抽象数据类型定义，分析串的基本操作的特点，从抽象数据类型的三要素（数据对象、数据关系、基本操作）分别介绍串。对于串的基本操作，重点放在每种操作的初始条件和操作结果的介绍上，并注意结合C语言中相应的函数进行应用举例4.2 串的表示和实现提出问题：如何改造数组实现串的顺序存储？引出顺序串的压缩存储和非压缩存储提出问题：如何改造链表实现串的链接存储？引出链串的压缩存储和非压缩存储，引入存储密度的定义

33、结合实际串的块链存储表示，鼓励学生在课外实现一个文字编辑系统。在整个文本编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即同一行的串用定长结构（如80个字符），行与行之间用指针联接。4.3 串的模式匹配算法提出问题：很多软件中，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。如何实现查找算法？给出BF算法的基本思想，运行实例，写出BF算法分析BF算法的时间复杂度再次运行实例，分析BF算法效率低的原因，引出KMP算法（在此之前可以先引入首尾匹配算法：先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符）根据部分匹配的特征，

34、得出失效数组next的求解方法，通过具体实例进一步理解next数组的求解方法给出KMP算法，粗略分析KMP算法的时间性能提出问题：特殊情况的next函数的改进算法教学提示： 对于串的基本操作，只要求理解，但要强调串的基本操作的实现是训练程序设计能力与技巧的一个很好的内容 首尾匹配法在教材上没有，引导学生对算法进行改进 KMP算法的技巧性很强，学生如果能真正学懂这个算法，将会极大地增强学习兴趣，同时对教师的思维能力和表达能力也是一个挑战2分钟13分钟10分钟7分钟2分钟1分钟1分钟15分钟5分钟15分钟3分钟15分钟教学策略在授课过程中采用多媒体教学，首先还原问题的本来面目提出问题，引导学生积极

35、参与尝试解决问题，在讨论的基础上给出结论讲授教学内容、解决问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读KMP算法非常巧妙，求匹配失效数组next的算法更是巧上加巧，更深入的内容请参见算法设计与分析（王红梅编著 清华大学出版社）教学后记教学感想：学生掌握程度：学生参与情况：意外发现：教学效果：个别疏漏及补救：数据结构教案编号006教学章节第五章 数组和广义表授课对象教学课型理论课授课形式课堂讲授授课学时4学时教学重点（1）数组的寻址方法；（2）特殊矩阵、稀疏矩阵的压

36、缩存储方法；（3）广义表中求表头和表尾的方法教学难点（1）广义表的存储结构；（2）稀疏矩阵压缩存储转置方法；教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合数组的抽象数据类型定义数组的顺序表示和实现稀疏矩阵的压缩存储广义表的类型定义广义表的表示方法广义表操作的递归函数态度积极主动学习能力熟练掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表概念教 学 过 程 设 计时间分配引入：几乎所有的程序设计语言中都有数组类型，本课程将以抽象数据类型的形式讨论数组的定义和实现。导入新课5.1 数组的定义给出数组的定义，将数组与线性表进行比较提出问题：在数

37、组中插入或删除一个元素有意义吗？给出数组的基本操作，给出数组的抽象类型定义（注意从抽象数据类型的三要素分别介绍数组）结合PPT课件介绍数组的4种基本操作，重点放在每种基本操作的初始条件和操作结果的介绍上，并结合C语言中相应的函数进行应用举例。5.2 数组的顺序存储与实现复习顺序表和链表的优缺点，得出数组的顺序存储结构画出行优先存储二维数组的示意图，给出存储方法与寻址方法得出结论：数组元素的存储位置是其下标的线性函数引导学生仿照行优先画出列优先存储二维数组的示意图，给出存储方法与寻址方法由二维数组的存储方法引申了n维(n2)数组的存储方法教学提示： 学生在程序设计语言中已经接触过数组了，本讲重点

38、讲授二维数组的存储结构和寻址方法，深入剖析二维数组的内部实现，使学生对数组的使用不仅知其然，而且知其所以然 对于二维数组的寻址，重点讲方法，而不要讲公式、背公式，只有从根本上理解了寻址方法，才能解决任意数组下标的寻址问题。 详略得当，精讲二维数组的行优先存储及寻址方法，略讲二维数组列优先存储寻址，通过做练习题检验学生的掌握程度。5.3 矩阵的压缩存储基本概念描述：稀疏因子、稀疏矩阵提出问题：使用前面介绍的存储方法存储稀疏矩阵会还来什么问题？学生思考回答后，总结得出以下结论：1、零元素占了很大空间；2、计算中进行了很多和零值的运算，遇到除法，还需判别除数是否为零。提出问题：解决稀疏矩阵存储问题的

39、思路是什么？学生回答后，总结出以下原则：1、尽可能少存或不存零元素；2、尽可能减少没有实际意义的运算；3、操作方便原则（尽可能快地找到与下标值(i,j)对应的元素，尽可能快地找到同一行或同一列的非零元素）给出矩阵压缩存储的基本思想介绍特殊矩阵的定义、种类根据对称矩阵的特点给出压缩存储方法，得出寻址方法根据三角矩阵的特点给出压缩存储方法，得出寻址方法根据对角矩阵的特点给出压缩存储方法，得出寻址方法复习线性表的存储结构，得出随机稀疏矩阵的压缩存储方法：三元组顺序表、行逻辑联接的顺序表、十字链表根据实例画出三元组顺序表存储示意图，定义存储结构三元组顺序表应用举例：矩阵转置根据稀疏矩阵转置算法I的基本

40、思想运行实例，写出算法分析转置算法I的缺点，引出转置算法II，运行实例，根据算法的执行过程，设计辅助数据结构，写出转置算法II由三元组顺序表的缺点引出十字链表，画出存储示意图教学提示： 对于特殊矩阵压缩存储后的寻址，重点讲方法，只有理解了寻址方法才能应用此方法解决其他类似问题。稀疏矩阵压缩存储的设计思想较灵活，要通过分析过程灵活掌握存储结构设计的方法。 稀疏矩阵压缩存储后转置算法的讲授思路：给出基本思想运行实例伪代码描述C语言描述，重点讲设计过程54 广义表建立认识：广义表是线性表的推广，广泛应用于人工智能等领域的表处理语言LISP给出广义表的定义，将广义表与线性表做比较，将广义表与数组做比较

41、给出几个广义表的例子，从抽象数据类型的三要素（数据对象、数据关系、基本操作）分别介绍广义表引导学生进一步理解广义表是递归定义的线性结构；广义表是一个多层次的线性结构结合实例分析广义表的结构特点提出问题：广义表可以顺序存储吗？采用链接存储结构存储广义表，其结点如何统一？引出头尾表示法画出头尾表示法存储示意图，体会这种存储结构的优缺点结合存储示意图，给出基本操作的实现教学提示： 注意表头、一尾概念的讲授，学生常常不以准确理解这两个概念 广义表的存储结构较复杂，但仍遵循链接存储的基本思想。讲授思路为：由广义表结构上的特性出发，回顾顺序存储和链接存储的基本思想，结合表头、表尾操作，得出具体的存储方法

42、在定义广义表存储结构之前，要适当复习C语言中的联合体类型5.5 数组的应用举例幻方给出幻方的定义，介绍幻方的起源及其在组合学的地位探讨幻方的特性，介绍研究幻方的书籍和网站给出左上行法构造幻方的规则，通过3阶幻方理解构造过程复习有关求模运算，写出左上行构造幻方的算法求3阶幻方的数量教学提示： 幻方是一个古老的智力游戏，对于一个幻方实例（如3阶幻方），大部分学生可以给出一个解答，但没有深究其中蕴涵的数学问题和数学道理 作为与数学有都会内在联系的计算机科学，需要计算机从业者具有良好的数学基础和数学思维方式，通过娱乐数学，使人在游戏中启迪思维、开阔视野、锻炼思维能力 本讲的主要目的不是传授一种构造幻方

43、的方法，而是通过课堂的讲授引起学生的兴趣，从而自发地广泛查阅资料，探索诸如此类的智力游戏本章小结 了解数组的类型定义及其在高级语言中实现的方法。 数组的特点是一种多维的线性结构，并只进行存取或修改某个元素的值，因此它只需要采用顺序存储结构。 介绍了稀疏矩阵的三种表示方法。至于在具体应用问题中采用哪一种表示法这取决于该矩阵主要进行什么样的运算。 广义表是一种递归定义的线性结构，因此它兼有线性结构和层次结构的特点。2分钟2分钟5分钟7分钟2分钟2分钟16分钟9分钟=2分钟3分钟5分钟2分钟2分钟8分钟5分钟5分钟1分钟2分钟9分钟1分钟=4分钟10分钟3分钟15分钟4分钟3分钟6分钟=4分钟4分钟

44、3分钟13分钟8分钟5分钟5分钟2分钟教学策略在授课过程中采用多媒体教学，首先还原问题的本来面目提出问题，引导学生积极参与尝试解决问题，在讨论的基础上给出结论讲授教学内容、解决问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。教学方法与教学手段教学方法：导入，配合图形、实例讲解，提问、讨论教学手段：PPT课件，板书，动画演示课后导读关于多维数组、稀疏矩阵十字链表、广义表的其它存储方法等内容更深入的讨论请参见数据结构与算法（许卓群 高等教育出版社）教学后记教学感想：学生掌握程度：学生参与情况：意外发现：教学效果：个别疏漏及补救：数据结构教案编号007教学章节第六章 树和二叉树授

45、课对象教学课型理论课授课形式课堂讲授授课学时10学时教学重点（1）二叉树的性质；（2）二叉树和树的存储表示；（3）二叉树的遍历及算法实现；（4）树与二叉树的转换关系；（5）哈夫曼树及应用。教学难点（1）二叉树遍历算法的非递归实现；（2）基于二叉树的遍历实现二叉树的其它操作；（3）线索二叉树；（4）树的基本操作的实现。教学内容和教学目标知 识 点学 习 要 求识记理解熟练掌握应用分析综合树的类型定义二叉树的类型定义二叉树的存储结构二叉树的遍历线索二叉树树和森林的表示方法树和森林的遍历哈夫曼树与哈夫曼编码态度积极主动学习能力树与二叉树的抽象数据类型定义和实现，二叉树的遍历与线索二叉树，树、森林与二

46、叉树的关系，哈夫曼树及其应用。教 学 过 程 设 计时间分配举例：客观世界广泛存在树形结构，它是一类重要的非线性数据结构策略：启发学生列举客观世界的树形结构，从而认识研究该结构的重要性 6.1 树的定义和基本术语给出树的定义，在与线性表定义比较的基础上，抓住要点，深刻理解树的逻辑特征结合实例，分类讲授树的基本术语给出树的ADT定义，简单介绍树的3类基本操作（查找类、插入类、删除类）介绍树的几种常见表示方法小结：将树结构和线性结构从逻辑结构上做比较（利用课件列表对比，加深学生对两种结构的理解）教学提示： 树结构在计算机软件系统中的应用较多，比较直观的有操作系统中的文件组织、软件界面中的多级下拉菜

47、单；另外，比较典型的应用还有描述递归执行过程的递归树、描述判定过程的判定树、编译程序中进行语法检查的语法树等。 注意从应用的角度以具体实例引起学生对本章的重视6.2 二叉树给出二叉树的定义，强调二叉树和树是两种树结构根据二叉树的定义得出二叉树的基本形态介绍几种特殊形式的二叉树，说明其特点给出并证明二叉树的性质，做习题进一步理解二叉树的性质介绍二叉树顺序存储表示，利用课件举例说明二叉树的顺序存储表示介绍二叉树的4种链式存储方法：二叉链表、三叉链表、双亲链表、线索链表教学提示： 强调树和二叉树是两种不同的树结构，二叉树不是树的特例，这是本讲较难理解的知识点，通过对比定义、正面总结、举反例说明等方法讲解 通过二叉树性质的证明引申计算机学科常