2010数据结构教案.docx

《2010数据结构教案.docx》由会员分享，可在线阅读，更多相关《2010数据结构教案.docx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、计算中进展了很多和零值的运算，遇到除法，还需判别除数是否为零。提出问题：解决稀疏矩阵存储问题的思路是什么？学生答复后，总结出以下原则：1、尽可能少存或不存零元素；2、尽可能削减没有实际意义的运算；3、操作便利原则（尽可能快地找到与下标值(i,j)对应的元素，尽可能快地找到同一行或同一列的非零元素）给出矩阵压缩存储的根本思想介绍特别矩阵的定义、种类依据对称矩阵的特点给出压缩存储方法，得出寻址方法依据三角矩阵的特点给出压缩存储方法，得出寻址方法依据对角矩阵的特点给出压缩存储方法，得出寻址方法复习线