课程教案 - 西南财经大学天府学院

课程教案 - 西南财经大学天府学院 西南财经大学天府学院 教 案 课程名称: 数据结构 西南财经大学天府学院教务处制 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:1 章节 第1章第1、2、3、4节 授课方式 课堂讲授、课堂讨论 教 (1)了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容; 学 (2)掌握数据结构的基本概念; 目 (3)实现算法描述和简单的算法分析。 的 教 (1)数据结构的基本概念; 学 (2)数据的逻辑结构、存储结构以及二者之间的关系; 重 (3)算法及特点。 点 教 学 (1)抽象数据类型的定义和使用。 难 (2)算法的时间复杂度分析。 点 时间 教 学 过 程 分配 1. 介绍数据结构课程体系的起源。了解历史——专业素养 2. 提出问题:程序设计的实质是什么,通过具体实例得出，介绍数据结构与程序设计的20 关系。强调数据结构始终是程序设计的基础，从发展的观点和应用的观点讨论数据结构的25 发展，从问题的求解过程入手，理解“数据结构+算法,程序”，理解数据结构和算法在问 题求解中的作用，数据结构是从非数值问题抽象出来的数据模型，这个阶段的学生还没有 抽象和模型的概念，需要补充抽象和模型的相关概念 3. 数据结构的基本概念。给出数据的定义，举例说明什么是数据，给出数据元素和数据项的 定义，根据上一讲的4个例子体会如何界定数据元素，数据、数据元素和数据项之间15 的关系给出数据对象的定义，引入数据结构的定义。 4. 数据的逻辑结构、存储结构以及二者之间的关系。从问题求解的角度强调数据结构包含逻 辑结构和存储结构两个方面，数据结构的图形表示方法，给出逻辑结构的定义，重点解释 逻辑关系，数据结构的形式化定义。 5. 同学们讨论抽象数据类型。 30 6. 算法及算法分析，根据生活中的实例简单理解什么是算法，给出算法的定义，结合欧几里90 德算法，从使用的角度讲解算法的五大特性分别用自然语言、流程图和C语言描述欧几里 德算法，从应用的角度介绍优点、缺点、使用方法、注意事项综合自然语言、流程图和C 语言描述欧几里德算法的优缺点，给出伪代码描述，使学生从中理解伪代码描述算法的好 处。介绍用C语言中的函数描述算法，强调用伪代码和C描述算法是两种不同级别的抽象， 体现了抽象分级的思想。 7. 讲授算法的时间复杂度分析并布置练习题 作 业 讨论抽象数据类型和算法时间复杂度的分析。 布 置 第2页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 课 重点:1、熟悉各名词、术语的含义，掌握基本概念 后 2、理解算法五个要素的确切含义 总 3、掌握计算语句频度和估算算法时间性能的方法 结 学习方式:理解、记忆、掌握 第3页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:2 章节 第2章第1、2、3、4节 授课方式 课堂讲授、项目实验 教 (1)熟练掌握线性表的两种存储结构的表示和基本操作的实现; 学 (2)掌握算法的时间复杂度和空间复杂分析方法; 目 (3)具备用线性表数据结构解决实际问题的能力。 的 教 (1)顺序存储结构和链式存储结构的基本思想; 学 (2)基于顺序表和单链表基本操作的实现; 重 (3)基于顺序表和单链表基本操作的时间性能分析; 点 (4)顺序表和单链表之间的比较。 教 (1)线性表的抽象数据类型定义; 学 (2)基于单链表的算法设计，尤其是要求算法满足一定的时间性能和空间性能; 难 (3)循环链表和双链表操作的实现。 点 时间 教 学 过 程 分配 1、 线性表的类型定义: 45 通过几个二维表的实例引出线性表的定义 给出线性表的定义，注意强调要点，总结线性表的特性 给出线性表的抽象数据类型定义，重点讲述基本操作部分。包括:结构初始化操作、结 构销毁操作、引用型操作、加工型操作、复杂操作。注意结合算法实例讲解。 2、 线性表的顺序表示和实现——顺序表 45 给出顺序表的存储示意图，强调存储要点，总结存储特点; 复习存储地址的有关内容，给出顺序表的随机存取特性; 顺序存储的地址计算方法; 顺序表存储结构的定义。 3、 线性表的链接存储结构及实现 45 由顺序表的缺点引出链接存储结构，根据一个实例给出线性表链接存储的实际内存状态， 复习C语言中指针的有关知识，抽象出单链表的存储示意图，给出单链表的存储结构定义及C 语言描述，区分指针变量和结点变量，说明头指针、尾标志和头结点，给出单链表的按位查 找算法，总结单链表算法的设计模式，设计单链表的插入算法，分析时间性能，比较带头结 点和不带头结点的单链表上的插入操作，给出单链表的删除算法，注意分析边界情况，给出 单链表建立算法中的头插法和尾插法。 4、 线性表的其它存储方法 45 提出问题:在单链表中如何找某结点的前驱,从而引出循环链表。 将循环链表的插入算法与单链表的插入算法作比较 讲述例子:将单循环链表倒置或逆置。 提出问题:在头指针批示的循环链表中，如何查找开始结点和终端结点,引出带尾指针 的循环链表 提出问题:如何快速求得某结点的前驱,引出双链表 第4页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 通过图示理解双链表的插入和删除操作，写出算法 作 业 用顺序表分别实现简易学生管理系统 布 用链表实现简易学生管理系统 置 课 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生积极参与后 ——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决问题，最后采用课件总 进行算法的动态演示，加大课堂信息量，提高教学效率。 结 第5页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:3 章节 第2章第5节 第3章 第1、2节 授课方式 课堂讲授、项目实验 教 学 (1)熟练掌握栈这种抽象数据类型的特点，并能在应用问题中正确选择使用数据结构; 目 (2)熟练掌握栈这种结构的顺序表示和链式表示，会应用它的基本操作算法。 的 教 学 (1)栈的操作特性; 重 (2)栈的基本操作的实现。 点 教 学 两栈共享共间的实现。 难 点 时间 教 学 过 程 分配 1、 综合实例——文具店货品管理系统实现,指导学生结合线性表算法代码实现文具店货品管45 理 2、 栈的定义及其操作:给出栈的定义，通过实例说明栈的操作特性，给出栈的抽象类型，根45 据顺序栈存储示意图写出入栈和出栈算法，分析时间性能，基本操作算法实现与分析栈是 程序设计中常常用到的一种数据结构，栈的研究历史比较长，也比较成熟。熟练掌握并学 会使用栈对后面的学习十分有益，注意将栈与线性表进行比较，根据生活中的实例深刻理 解栈的操作特性，多准备一些栈的应用实例，如果学时有多，给出栈在计算机软件系统的 一些应用实例。 3、 顺序栈: 45 列举算法实例、分析算法的复杂性 提出问题:如何用C语言编写一个嵌套调用程序,举例说明。 学生回答:指出嵌套与递归的区别与联系——嵌套既可以自己调用自己，也可以调用别 人;递归程序只能是自己调用自己。 总结导入新课——用栈实现递归的原理 4、 链栈主要讲解内容:栈的操作特性和基本操作的实现。 45 结合例子说明，函数调用之前系统完成的工作简介; 结合例子说明，调用返回之前系统完成的工作简介; 给出递归的定义，结合具体实例说明递归是一种描述问题和解决问题的基本方法; 结合求n!、求斐波那契数列等问题的过程，讨论递归的两个基本要素; 释汉诺塔问题，说明其递归求解过程，给出求解汉诺塔问题的递归算法。 作 业 项目实现:文具店的货品管理 布 项目实现:数值转换 置 第6页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 课 线性表、栈的异同点: 后 相同点:逻辑结构相同，都是线性的;都可以用顺序存储或链表存储;栈是特殊的线性表，总 即受限的线性表(只是对插入、删除运算加以限制)。 结 第7页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:4 课堂讲授、项目实验、章节 第 3章 第4、5、6、7、8节 授课方式 课堂讨论 教 学 (1)熟练掌握队列这种抽象数据类型的特点，并能在应用问题中正确选择使用数据结构; 目 (2)熟练掌握队列这种结构的顺序表示和链式表示，会应用它的基本操作算法。 的 教 学 (1)队列的操作特性; 重 (2)队列基本操作的实现。 点 教 学 循环队列的组织及队空和队满的判定条件。 难 点 时间 教 学 过 程 分配 1. 复习:线性表的插入和删除操作，栈的相关操作，引出队列给出队列的定义，通过实例说15 明队列的操作特性，给出队列抽象数据类型的定义队列的分类:一端进、另一端出的队列; 双端队列用图示意说明队列的特点。 2. 第四节:队列的定义及其操作 30 提出问题:如何存储队列,引出队列的顺序存储结构和链接存储结构 改造顺序表，得出循环队列的存储方法 提出问题:如何判断循环队列的队空和队满,分析各种。在解决了循环队列的 关 键问题后，基本操作的实现略讲 提出问题:如何改造单链表实现队列的链接存储,引出链队列的存储方法 链队列的出队算法要注意边界情况，其他基本操作的实现可以略讲 引导学生比较循环队列和链队列 队列的应用举例 3. 栈与队列的应用 45 45 4. 同学们讨论输入输出缓冲区 45 5. 同学们代码实现停车场管理 作 业 讨论:输入输出缓冲区 布 项目实现:停车场管理 置 第8页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 线性表、栈、队的不同点: 运算规则不同: 课 • 线性表为随机存取; 后 • 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO; 总 • 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 结 用途不同:线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、操作系统作业调度和简化设计等。 第9页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:5 章节 第4 章 第1、2、3、4、5节 授课方式 课堂讲授、项目实验 教 学 具备使用C语言提供的串操作函数构造与串相关的算法，解决简单的应用问题的能力。 目 的 教 (1)串的数据类型定义; 学 (2)串的顺序和链式存储表示; 重 (3)串的模式匹配算法。 点 教 学 串的模式匹配算法。 难 点 时间 教 学 过 程 分配 提出问题:结合C语言程序设计谈谈自己对串类型的认识, 10 字符串的应用范围如何, 要有效地实现字符串的处理，如何设计其存储结构, 结合程序设计的实践，启发学生串应具备哪些基本操作, 总结导入新课 1. 串的基本概念及其操作 35 给出串的定义，在与线性表比较的基础上，总结串的特性;介绍串的基本概念，补充字 符集的相关知识，强调只有一个字的符串与字符的区别;给出串的抽象数据类型定义，分析 串的基本操作的特点，从抽象数据类型的三要素(数据对象、数据关系、基本操作)分别介 绍串。对于串的基本操作，重点放在每种操作的初始条件和操作结果的介绍上，并注意结合C 语言中相应的函数进行应用举例。 2. 串的顺序存储结构和链式存储结构 35 提出问题:如何改造数组实现串的顺序存储,引出顺序串的压缩存储和非压缩存储 提出问题:如何改造链表实现串的链接存储,引出链串的压缩存储和非压缩存储，引入存储 密度的定义;结合实际串的块链存储表示，鼓励学生在课外实现一个文字编辑系统。在整个 文本编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。 即同一行的串用定长结构(如80个字符)，行与行之间用指针联接。 3. 串的模式匹配 55 提出问题:很多软件中，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。如何实 现查找算法, 给出BF算法的基本思想，运行实例，写出BF算法; 分析BF算法的时间复杂度; 再次运行实例，分析BF算法效率低的原因，引出KMP算法(在此之前可以先引入首尾匹配算 法:先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二 第10页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 个到第n-1个字符); 根据部分匹配的特征，得出失效数组next的求解方法，通过具体实例进一步理解next数组 的求解方法; 给出KMP算法，粗略分析KMP算法的时间性能。 提出问题:特殊情况的next函数的改进算法。 4. 综合实例——简易文本编辑软件 45 作 业 项目实现:简易文本编辑软件 布 置 课 对于串的基本操作，只要求理解，但要强调串的基本操作的实现是训练程序设计能力与技巧后 的一个很好的内容;首尾匹配法在教材上没有，引导学生对算法进行改进KMP算法的技巧性总 很强，学生如果能真正学懂这个算法，将会极大地增强学习兴趣，同时对教师的思维能力和结 表达能力也是一个挑战。 第11页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:6 章节 第 5 章 第1、2、3、4、5、6节 授课方式 课堂讲授、项目实验 教 学 (1)熟练掌握多维数组的逻辑结构特征及其存储方式; 目 (2)掌握特殊矩阵和稀疏矩阵的压缩存储方法及广义表概念。 的 教 (1)数组的寻址方法; 学 (2)特殊矩阵、稀疏矩阵的压缩存储方法; 重 (3)广义表中求表头和表尾的方法。 点 教 学 (1)广义表的存储结构; 难 (2)稀疏矩阵压缩存储转置方法。 点 时间 教 学 过 程 分配 第一节:数组的基本概念、寻址方法及其操作 10 给出数组的定义，将数组与线性表进行比较 提出问题:在数组中插入或删除一个元素有意义吗,给出数组的基本操作，给出数组的 抽象类型定义(注意从抽象数据类型的三要素分别介绍数组) 结合PPT课件介绍数组的4种基本操作，重点放在每种基本操作的初始条件和操作结果 的介绍上，并结合C语言中相应的函数进行应用举例。 第二节:数组的顺序存储 15 复习顺序表和链表的优缺点，得出数组的顺序存储结构 画出行优先存储二维数组的示意图，给出存储方法与寻址方法 得出结论:数组元素的存储位置是其下标的线性函数 引导学生仿照行优先画出列优先存储二维数组的示意图，给出存储方法与寻址方法 由二维数组的存储方法引申了n维(n>2)数组的存储方法 第三节:特殊矩阵及其压缩存储 45 基本概念描述:稀疏因子、稀疏矩阵 提出问题:使用前面介绍的存储方法存储稀疏矩阵会还来什么问题, 学生思考回答后，总结得出以下结论: 1、零元素占了很大空间; 2、计算中进行了很多和零值的运算，遇到除法，还需判别除数是否为零。 提出问题:解决稀疏矩阵存储问题的思路是什么, 学生回答后，总结出以下原则: 1、尽可能少存或不存零元素; 2、尽可能减少没有实际意义的运算; 3、操作方便原则(尽可能快地找到与下标值(i,j)对应的元素，尽可能快地找到同一行 或同一列的非零元素) 第12页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 第四节:稀疏矩阵 20 建立认识:广义表是线性表的推广，广泛应用于人工智能等领域的表处理语言LISP 给出广义表的定义，将广义表与线性表做比较，将广义表与数组做比较 给出几个广义表的例子，从抽象数据类型的三要素(数据对象、数据关系、基本操作) 分别介绍广义表 引导学生进一步理解广义表是递归定义的线性结构;广义表是一个多层次的线性结构 结合实例分析广义表的结构特点 提出问题:广义表可以顺序存储吗,采用链接存储结构存储广义表，其结点如何统一, 引出头尾表示法 画出头尾表示法存储示意图，体会这种存储结构的优缺点 结合存储示意图，给出基本操作的实现 第五节:广义表 15 主要讲解内容:数组的寻址方法，广义表、特殊矩阵、稀疏矩阵的压缩存储方法，广义表中 求表头和表尾的方法，稀疏矩阵压缩存储转置方法。 第六节:综合实例—n阶魔方 30 作 业 项目实现:n阶魔方 布 置 了解数组的类型定义及其在高级语言中实现的方法。 课 数组的特点是一种多维的线性结构，并只进行存取或修改某个元素的值，因此它只需要采用 后 顺序存储结构。 总 介绍了稀疏矩阵的三种表示方法。至于在具体应用问题中采用哪一种表示法这取决于该矩阵 结 主要进行什么样的运算。 广义表是一种递归定义的线性结构，因此它兼有线性结构和层次结构的特点。 第13页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:7 章节 第6章 第1、2节 授课方式 课堂讲授、课堂讨论 教 学 (1)掌握树与二叉树的抽象数据类型定义和实现; 目 (2)编程实现二叉树的遍历。 的 教 (1)二叉树的性质; 学 (2)二叉树和树的存储表示; 重 (3)二叉树的遍历及算法实现。 点 教 学 (1)二叉树遍历算法的非递归实现; 难 (2)基于二叉树的遍历实现二叉树的其它操作。 点 时间 教 学 过 程 分配 举例:客观世界广泛存在树形结构，它是一类重要的非线性数据结构 30 策略:启发学生列举客观世界的树形结构，从而认识研究该结构的重要性 第一节:树 60 给出树的定义，在与线性表定义比较的基础上，抓住要点，深刻理解树的逻辑特征 结合实例，分类讲授树的基本术语 给出树的ADT定义，简单介绍树的3类基本操作(查找类、插入类、删除类) 介绍树的几种常见表示方法 小结:将树结构和线性结构从逻辑结构上做比较(利用课件列表对比，加深学生对两种 结构的理解) 第二节:二叉树 45 主要讲解内容:二叉树的性质;二叉树和树的存储表示;二叉树的遍历及算法实现;树 与二叉树的转换关系 给出二叉树的定义，强调二叉树和树是两种树结构 根据二叉树的定义得出二叉树的基本形态 介绍几种特殊形式的二叉树，说明其特点 给出并证明二叉树的性质，做习题进一步理解二叉树的性质 介绍二叉树顺序存储表示，利用课件举例说明二叉树的顺序存储表示 介绍二叉树的4种链式存储方法:二叉链表、三叉链表、双亲链表、线索链表 遍历二叉树 45 给出遍历的定义 根据二叉树的先序遍历操作定义，写出先序遍历的递归算法，引导学生写出中序和后序 遍历的递归算法 对三种遍历算法进行比较 遍历算法的应用举例:统计二叉树中叶子结点的个数(先序遍历)、求二叉树的深度(后 第14页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 序遍历)、复制二叉树(后序遍历)、建立二叉树的存储结构 重新讨论先序遍历递归算法，写出先序遍历的非递归算法 提出问题:已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树,通过例 子给出构造过程 分析层序遍历的执行过程，写出层序遍历算法 作 业 讨论:已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树,通过例子给出构 布 造过程。 置 课 树结构中的数据元素之间存在着“一对多”的关系，它为计算机应用中出现的具有层次关系 后 的数据，提供了自然的表示方法。 总 二叉树是和树不同的另一种树型结构。 结 二叉树的几个重要特性应该熟练掌握的 第15页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:8 课堂讲授、项目实验、章节 第6章 第3、4、5节 授课方式 课堂讨论 教 学 (1)了解树、森林与二叉树的关系; 目 (2)实现哈夫曼树及其应用。 的 教 学 (1)树、二叉树与森林的转换关系; 重 (2)哈夫曼树及应用。 点 教 学 哈夫曼编码算法。 难 点 时间 教 学 过 程 分配 第三节:森林 45 结合前面讲述的树的概念，引入树的三种存储结构 从双亲的角度考虑，引出双亲表示法，根据实例画出双亲存储示意图，分析如何表示结 点之间的逻辑关系 从孩子的角度考虑，给出多重链表解决方案，分析缺点及原因，引出孩子链表表示法 给出孩子链表表示法，根据实例画出孩子链表存储示意图，分析如何表示结点之间的逻 辑关系 观察任意一棵树，某结点的第一个孩子是唯一的，某结点的右兄弟是唯一的，得出孩子 兄弟表示法 根据实例画出孩子-兄弟存储示意图，分析如何表示结点之间的逻辑关系 第四节:哈夫曼树及其应用 45 结合具体实例介绍哈夫曼树的相关概念，重点解释权值 利用课件演示，观察哈夫曼树的特点，给出哈夫曼算法的基本思想，运行一个实例构造 哈夫曼树 重新考察哈夫曼树的构造过程，总结要点 哈夫曼树的应用实例简介 介绍等长编码和不等长编码，通过实例强调在设计不等长编码时，必须考虑解码的唯一 性，引出前缀编码 给出用哈夫曼构造最短的不等长编码的方法，通过实例解释编码与解码过程，体会树的 带权路径长度的含义 分析哈夫曼编码与解码算法的关键问题，由学生课后完成算法。 第五节:综合实例——高校社团管理 90 第16页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 作 业 讨论:分析哈夫曼编码与解码算法的关键问题，由学生课后完成算法。 布 项目实现:高校社团管理 置 课 后 哈夫曼树和哈夫曼编码的构造方法。 总 结 第17页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:9 章节 五一放假 授课方式 教 学 目 的 教 学 重 点 教 学 难 点 时间 教 学 过 程 分配 作 业 布 置 课 后 总 结 第18页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:10 章节 第 7章 第1、2、3、4、5、6节 授课方式 课堂讲授、课堂讨论 教 学 具备利用深度优先搜索、广度优先搜索解决简单应用问题的能力。 目 的 教 (1)图的基本术语; 学 (2)图的各种存储表示; 重 (3)图的两种遍历的思想及算法; 点 (4)图的各种应用。 教 (1)最小生成树算法; 学 (2)最短路径算法; 难 (3)拓扑排序算法; 点 (4)关键路径算法。 时间 教 学 过 程 分配 提出问题:结合日常生活中有关图的例子，如著名的哥尼斯堡七桥问题、学生坐火车时路线15 的选择等提出问题，即图的应用范围如何,如何存储图,如何实现常见的对图的操作,学生 回答后，总结并导入新课 第一节:图的基本概念 30 给出图的定义，注意与线性结构、树结构进行比较 结合实例，讲授图的基本术语 回顾线性表的序号、树的编号，给出图中顶点的编号方法 给出图的ADT定义，简单介绍图的基本操作 第二节:图的存储结构 45 由图存储需要解决的关键问题引出图的各种存储结构 给出邻接矩阵存储思想及表示，画出有向图、无向图和网图的邻接矩阵存储示意图 根据无向图的邻接矩阵存储示意图，分析基本操作的实现 根据有向图的邻接矩阵存储示意图，分析基本操作的实现 根据网图的邻接矩阵存储示意图，分析基本操作的实现 总结邻接矩阵存储表示的特点 给出邻接表的存储思想及实现，画出有向图、无向图和网图的邻接表存储示意图 根据无向图的邻接表存储示意图，分析基本操作的实现 根据有向图的邻接表存储示意图，分析基本操作的实现 根据网图的邻接表存储示意图，分析基本操作的实现 第三节:图的遍历 30 复习二叉树的遍历，理解访问的含义以及遍历的次序 提出问题:图的遍历要解决哪些关键问题 给出深度优先遍历的思想，通过实例分析深度优先遍历过程中工作栈的状态变化，给出 算法的C语言实现 第19页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 给出广度优先遍历的思想，通过实例分析广度优先遍历过程中工作栈的状态变化，给出 算法的C语言实现 第四节:最小生成树 15 第五节:最短路径 45 举例说明在网图和非网图中最短路径的含义 给出Dijkstra算法的基本思想，将其转化为形式化描述 运行一个实例，展示Dijkstra算法的求解过程 考察Dijkstra算法的求解过程，设计数据结构，给出算法的伪代码描述，给出算法的C 语言实现 给出Floyd算法的基本思想，将其转化为形式描述 设计Floyd算法的数据结构，写出迭代公式 运行一个实例，展示Floyd算法的求解过程，写出Floyd算法的C代码 第六节:拓扑排序和关键路径 作 业 讨论:图的两种遍历的思想及算法。 布 置 图的基本术语在本科生的教材中大同小异，更深入的介绍请参见《图论简明教程》(Frd Buckley 著 李慧霸译 清华大学出版社) 课 深度优先遍历图的性质和广度优先遍历图的性质请参见《数据结构与算法》(齐德昱 清华大后 学出版社) 总 拓扑排序算法的其它讨论参见《数据结构与算法》(许卓群 清华大学出版社)“某路径为关键结 路径的充分必要条件是其上的活动均为关键活动”的证明请参见《数据结构与算法》(齐德昱 清华大学出版社) 第20页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:11 章节 第 7章 第4节 第8章 第1、2节 授课方式 课堂讲授、项目实验 教 (1)掌握查找的基本概念; 学 (2)程序实现各种查找算法; 目 (3)掌握散列查找的应用。 的 教 学 (1)查找的基本概念; 重 (2)顺序查找的过程及性能分析; 点 教 学 静态查找和动态查找的概念。 难 点 时间 教 学 过 程 分配 80 第七节:综合实例——故宫导游咨询 10 提出问题:(1)在日常生活中，人们几乎每天都要进行“查找”工作，如在电话号码簿中查 找“某人”的电话号码;在字典中查找“某个词”的含义等到。这里的“电话号码簿”和“字 典”都可视为一张查找表。 (2)在各种系统软件和应用软件中，查找表也是一种常见的结构之一，如编译程序中符号表、 信息处理系统中信息表等。 第一节:查找的基本概念 45 给出查找的定义，说明查找所基于的数据结构是集合 结合实例，给出关键码的有关概念 给出静态查找和动态查找的概念，说明适用情况 给出查找结构的概念，引申:数据结构+算法=程序 提出问题:关键码的比较次数与哪些因素有关,给出衡量查找算法性能的方法 第二节:顺序查找 45 静态查找和动态查找是本章的两条主线，因此，本讲要使学生深刻理解这两个概念 从逻辑上说，查找所基于的数据结构是集合，即查找集合中的记录之间没有关系，但是 为了获得较高的查找性能，存储时可以将查找集合组织成表、树等查找结构 主要讲解内容:顺序查找的过程及性能分析。 第21页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 作 业 项目实现:故宫导游咨询 布 置 课 查找表即为集合结构，表中记录之间本不存在约束条件，但为了提高查找速度，在计算机后 中构建查找表时，应人为地在记录的关键字之间加上某些约束条件，即以其它结构表示之。总 由于查找过程中的主要操作是关键字和给定值进行比较，因此以一次查找所需进行的比较结 次数的期望值作为查找方法效率的衡量标准，称之谓平均查找长度。 第22页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:12 章节 第 8 章 第3、4、5、6节 授课方式 课堂讲授 教 (1)掌握查找的基本概念; 学 (2)程序实现各种查找算法; 目 (3)掌握散列查找的应用。 的 教 (1)折半查找的过程及性能分析; 学 (2)二叉排序树的构造及查找方法; 重 (3)平衡二叉树的调整方法; 点 (4)各种查找技术的时间性能及对比。 教 学 (1)二叉排序树的删除操作; 难 (2)平衡二叉树的调整方法。 点 时间 教 学 过 程 分配 第三节:折半查找 30 设置哨兵，运行实例，分别考察在查找成功和查找不成功的情况下哨兵所起的作用 写出改进的顺序查找算法，并与改进前的算法进行比较 分析顺序查找技术的优缺点、适用情况 给出折半查找的基本思想，运行实例，写出折半查找的非递归算法 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功情况下的查找性能 提出问题:折半查找的分割点位于查找区间的中间，有没有其他分割办法,引出斐波那 契查找和插值查找 提出问题:黄金分割法, 第四节:分块查找 15 主要讲解内容:折半和分块查找的过程及性能分析。 第五节:二叉排序树 90 提出问题:对一个大型的查找集合进行动态查找，应如何存储这个查找集合呢,引出树 表和二叉排序树 给出二叉排序树的定义，说明构造二叉排序树的根本目的 给出二叉排序树的存储结构，注意与二叉链表做比较 根据在二叉排序树上进行查找的实例，给出二叉排序树的查找算法，分析性能 给出在二叉排序树上插入一个结点的方法，利用课件运行实例，写出算法 考察构造二叉排序树与插入结点的关系，运行实例，写出构造二叉排序树的算法 提出问题:在二叉排序树上删除一个结点，其含义是什么,考虑被删除结点的各种可能 情况，由简到难解决问题 将二叉排序查找与折半查找进行比较 由二叉排序树的查找性能引出平衡二叉树 给出平衡二叉树和平衡因子的概念，理解平衡的含义 第23页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 给出最小不平衡子树的概念主寻找方法，为后续内容做铺垫 给出构造平衡二叉树的基本思想，说明这种调整方法能以最小代价获得平衡二叉排序树 通过实例引出平衡调整的关键:扁担原理和旋转优先原则 介绍平衡调整的四种情况，注意对称情况 最后通过一个课堂练习，进一步掌握平衡二叉树的调整方法 第六节:哈希表 45 主要讲解内容:二叉排序树的构造及查找方法;各种查找技术的时间性能及对比。 作 业 对比各种查找方式的特点及应用。 布 置 课 在本章中介绍了查找表的三类存储表示方法:顺序表、树表和哈希表。这里的顺序表指的是后 顺序存储结构，包括有序表和索引顺序表，因此主要用于表示静态查找表，树表包括静态查总 找树、二叉查找树和二叉平衡树，树表和哈希表主要用于表示动态查找表。 结 第24页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:13 章节 第8章 第7节 第9章 第1、2、3节 授课方式 课堂讲授、项目实验 (1)了解排序的定义和各种排序算法的特点; 教 (2)熟悉各种排序方法的基本思想及其算法; 学 (3)掌握各种排序方法的时间复杂性分析方法，能从“关键字的比较次数”分析排序算法的 目 平均情况和最坏情况的时间性能; 的 (4)理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序方法必须是稳 定的。 (1)各种排序算法的基本思想; 教 (2)各种排序算法的执行过程; 学 (3)各种排序算法的设计; 重 (4)各种排序算法的时间复杂度的分析; 点 (5)各种排序算法之间的比较。 教 学 使用排序算法解决实际问题。 难 点 时间 教 学 过 程 分配 综合实例——十大流行歌手排行榜 90 概述 根据生活中的例子简单理解排序，理解排序的主要目的 给出排序的定义，抓住要点充分理解排序定义的内涵 给出几种排序分类的方法 结合具体实例，解释排序算法的稳定性 给出单键排序和多键排序的概念，说是它们本质上对应一种操作——单键排序 提出问题:基于比较的内排序，其基本操作是什么,结合实例说明 10 结合实例说明排序算法的辅助空间 第一节:排序的基本概念 10 , 排序是数据处理中经常使用的一种基本操作，要熟练掌握各种排序算法 , 排序的概念是本讲的重点，通过分析概念的要点将概念讲透，引导学生掌握正确理解概 念的方法，这是会学习的一个标志 , 通常学生不容易理解排序算法的稳定性，要通过实例进行讲解，并说明排序算法的稳定 性取决于算法，在一定条件下是可以转化的 第二节:插入排序 30 给出直接插入排序的基本思想，结合图例和生活中的例子解释其基本思想 根据基本思想提出直接插入排序算法的关键问题 运行实例，在每一趟排序中进一步提出问题并解决问题 根据上述关键问题的解决方法设计出算法，最后给出完整的C语言代码 分析最好、最坏、平均情况下的时间复杂度 分析空间复杂度和算法的稳定性 第25页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 分析算法的优缺点，得出算法的适用情况 提出问题:如何改进直接插入排序,引出折半插入排序 第三节:交换排序 30 给出起泡排序算法的基本思想，强调比较的是相邻记录 根据基本思想运行实例，引导学生提出起泡排序算法需要解决的关键问题 带着关键问题重新运行实例，在每一趟排序中进一步提出问题并解决问题 将关键问题的解决文宗写出算法，最后给出完整的起泡排序算法。注意思维方式:算法 是从里层向外层写的 分析最好、最坏、平均情况下的时间性能 分析空间性能和算法的稳定性 将起泡算法的时间性能与直接插入算法做比较 提出问题:如何改进起泡排序, 主要讲解内容:插入和交换排序算法的基本思想、执行过程、设计、时间复杂度的分析。 10 作 业 项目实现:十大流行歌手排行榜 布 置 课 后 在程序设计中，充分发挥小组优势完成项目，同时也体会到小组合作的重要性与必要性。 总 结 第26页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:14 章节 第 9 章 第 4、5、6、7节 授课方式 课堂讲授、课堂讨论 (1)了解排序的定义和各种排序算法的特点; 教 (2)熟悉各种排序方法的基本思想及其算法; 学 (3)掌握各种排序方法的时间复杂性分析方法，能从“关键字的比较次数”分析排序算法的 目 平均情况和最坏情况的时间性能; 的 (4)理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序方法必须是稳 定的。 (1)各种排序算法的基本思想; 教 (2)各种排序算法的执行过程; 学 (3)各种排序算法的设计; 重 (4)各种排序算法的时间复杂度的分析; 点 (5)各种排序算法之间的比较。 教 学 (1)快速排序、堆排序、归并排序等算法的设计; 难 (2)快速排序算法的时间复杂度的分析。 点 时间 教 学 过 程 分配 第四节:选择排序 20 给出简单选择排序的基本思想。引导学生根据基本思想提出简单选择排序算法需解决的 关键问题 带着关键问题运行实例，在每一趟排序中进一步提出并解决问题 将关键问题的解决方法写出算法，写出简单选择排序算法 分析简单选择排序算法执行过程中记录的比较次数和移动次数，得到算法的时间性能 分析空间复杂度，分析算法的稳定性 分析简单选择排序算法的优缺点，给出适用情况 第五节:归并排序 20 结合现实生活中的排队解释归并的含义 给出二路归并排序的基本思想，运行一个实例，在理解二路归并排序的基础上，提出二 路归并排序需解决的关键问题 再次运行归并排序实例，重点考察如何实现一次归并，写出一次归并算法 再次运行归并排序实例，重点考察如何实现一趟归并，分析各种归并情况，写出一趟归 并算法 写出归并算法的非递归算法，分析时间性能和空间性能 体会归并排序的分治思想，写出归并排序的递归算法 将递归算法和非递归算法进行比较，给出结论 第六节:基数排序 20 结合例子，讲解多关键字排序的基本思想、算法和复杂性分析 给出链式基数排序的基本思想、算法和复杂性分析 第七节:各种排序方法的比较 30 第27页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 指出排序算法各有优缺点，难以得出哪个最好、哪个最坏的结论，因此，排序方法的选 用应该根据具体情况而定 给出选择排序算法时需要考虑的各种综合因素 对各种排序算法的时间性能列表进行比较 对各种排序算法的空间性能列表进行比较 对排序算法的稳定性进行分类 对排序算法的简单性进行分类 待排序记录个数(即问题规模)对排序算法时间性能的影响进行分类 待排序记录本身信息量对排序算法时间性能的影响列表进行比较 给出一些具体实例，说明如何选择排序算法 作 业 讨论:各种排序算法之间的比较。 布 置 课 首先给出选择排序算法的综合考虑因素，再将所有排序算法的每一种因素列表进行比较。提后 醒学生注意:将相关或不相关的知识放在一起，常常会有意外的发现引导学生掌握在各种情总 况下，灵活选择合适的排序算法的方法，达到活学活用的教学目的。 结 第28页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:15 章节 小组项目(通讯录) 授课方式 课堂讨论 (1)熟练利用数据结构各种算法思想设计程序; 教 (2)掌握C语言基本语法; 学 (3)加深对数据结构课程所学内容的进一步理解和巩固; 目 (4)加深对结构化课程设计思想的理解，并设计合理的模块化结构; 的 (5)提高程序开发功能，能运用合理的控制流程编写清晰高效的程序; (6)培养分析问题、解决问题的能力。 教 (1)分析程序的功能要求，划分程序功能模块; 学 (2)定义数据结构; 重 (3)画系统流程图; 点 (4)链表的使用。 教 学 画系统流程图。 难 点 时间 教 学 过 程 分配 项目要求: 随着社会发展，时代的前进，人与人的交往越来越密切，通讯成为当代社会发展必不可 少的一大服务业，目前在我国较为有影响力的通讯产业有中国移动、中国联通、中国电 信等，它们的产生给人们生活、交往带来极大的便利，通讯录由此而生，方便了同学、 亲戚朋友的交往。说到通讯录，从字面意思来看，即通讯的记录，方便人们的交往，在 我看来，通讯录的主要意义也就在于有助于人与人之间的通讯，便捷地找到自己想找到 的人,其实通讯录无处不在,根据需要设计本程序。 (一)分析程序的功能要求，划分程序功能模块。 20 一个简单的通讯录系统应具有以下功能: 1、通讯录成员的输入(输入通讯录成员的个数由用户自己决定，当在“请输入姓名”后 面输入为空时，结束输入) 2、通讯录成员的删除(输入要删除成员的姓名，当此成员存在通讯录中，即可删除此成 员，若是输入的姓名未能找到，系统会提示“没有此人信息”。) 3、浏览通讯录(显示通讯录中所有成员的信息，成员的信息有姓名、地址、邮编、电话、 QQ。) 4、查找通讯录中某些成员(输入要查找成员的姓名，显示要查找成员的所有信息。) 5、对通讯录中的所有信息的保存(将通讯录中的所有信息保存在mylist文件中，方便 用户的操作。) 6、对通讯录某些成员进行修改(输入需要修改成员的姓名，输入其正确的信息。) 7、系统清屏(当屏幕内容过多时，清屏。) 8、退出通讯录(完成通讯录的所有操作，退出系统。) (二)画出系统流程图。 20 第29页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE (三)代码的编写。 30 1、定义数据结构: 数据结构如此定义:姓名、性别、地址由字符组成，最大字符数分别为 10个，2个和16个;邮编、电话、QQ由数字字符组成，最在字符数分别为6个，11个 和9个;当输入的输的字符超过上面所规定的最大字符数时，系统会提示“输入字符太 长，请重新输入”。 2、实现各个功能子函数 (四)程序的功能调试。 20 作 业 对系统进行功能测试，如有问题则找出原因并解决。 布 置 课 后 在程序设计中，充分发挥小组优势完成项目，同时也体会到小组合作的重要性与必要性。 总 结 第30页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:16 章节 小组项目(学生信息管理系统) 授课方式 课堂讨论 (1)熟练利用数据结构各种算法思想设计程序; 教 (2)掌握C语言基本语法; 学 (3)加深对数据结构课程所学内容的进一步理解和巩固; 目 (4)加深对结构化课程设计思想的理解，并设计合理的模块化结构; 的 (5)提高程序开发功能，能运用合理的控制流程编写清晰高效的程序; (6)培养分析问题、解决问题的能力。 教 (1)分析程序的功能要求，划分程序功能模块; 学 (2)定义数据结构; 重 (3)画系统流程图; 点 (4)双链表的使用。 教 学 (1)画系统流程图; 难 (2)双链表的使用。 点 时间 教 学 过 程 分配 项目要求: 1、用c语言编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。 2、具体要求: 建立一个4个学生的信息登记表，每个学生的信息包括:学号，姓名，和3门课程的成 绩(FOX,C,ENGLISH)。 程序运行时显示一个简单的菜单，例如: (1)信息输入(INPUT) (2)总分统计(COUNT) (3)总分排序(SORT) (4)查询(QUERY) 其中: (1)对4个学生的信息进行输入; (2)对每个学生的3门课程统计总分; (3)对4个学生的总分按降序排序并显示出来; (4)查询输入一个学号后，显示出该学生的有关信息; (一)分析程序的功能要求，划分程序功能模块。 40 1、信息输入 2、总分统计 3、总分排序 4、查询 (二)画出系统流程图。 40 (三)代码的编写。 60 第31页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 1、定义数据结构 2、实现各个功能子函数。 (四)程序的功能调试。 40 在程序中设断点，可以找到程序流程错误。实际上，断点的功能远非如此，不但可以拦 截程序流程错误，也可以拦截数据错误。当然，这需要一些辅助手段。当数据出错后，我们 希望能够在最快时间内，让程序停下来，这样才能有效查出是哪一段程序出了问题。有些调 试环境本身可以捕捉数据错误，并产生断点中断。这当然最好不过。但是我们现在用的大多 数调试软件本身不提供这种捕捉功能，那么就需要我们自己来制造条件了。回到程序中来， 假设我们要监控的那个值，正常值域为0~9;那么我们可以写一段测试代码，判断数值是否>9， 根据判断结果执行两个分支，并在那条错误的分支路径上设置断点。如果数据没有出错，程 序会一直运行;直到数据错误发生，断点会自动停下来。我们可以把这段测试程序，插入在 我们担心出错的地方，然后我们就可以守株待兔了。 作 业 对系统进行功能测试，如有问题则找出原因并解决。 布 置 课 后 在程序设计中，充分发挥小组优势完成项目，同时也体会到小组合作的重要性与必要性。 总 结 第32页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 教 案 编号:17 章节 项目答辩 授课方式 项目实现 教 学 (1)总结项目过程中的成功与失败经验; 目 (2)培养分析问题、解决问题的能力。 的 教 学 (1)检验学生小组项目成果; 重 (2)小组成员自我风采展示。 点 教 学 能否在规定时间内完成小组成果的展示，并较为清楚的表达，是否符合项目的前期要求。 难 点 时间 教 学 过 程 分配 项目要求: 随着社会发展，时代的前进，人与人的交往越来越密切，通讯成为当代社会发展必不可 少的一大服务业，目前在我国较为有影响力的通讯产业有中国移动、中国联通、中国电 信等，它们的产生给人们生活、交往带来极大的便利，通讯录由此而生，方便了同学、 亲戚朋友的交往。说到通讯录，从字面意思来看，即通讯的记录，方便人们的交往，在 我看来，通讯录的主要意义也就在于有助于人与人之间的通讯，便捷地找到自己想找到 的人,其实通讯录无处不在,根据需要设计本程序。 (一)项目展示; 30 (二)项目小组成员答辩: 60 I、分析程序的功能要求及程序各功能模块实现。 1、通讯录成员的输入 2、通讯录成员的删除 3、浏览通讯录 4、查找通讯录中某些成员 5、对通讯录中的所有信息的保存 6、对通讯录某些成员进行修改 7、系统清屏 8、退出通讯录 II、所遇到的问题，你是怎样解决这些问题的, III、体会收获及建议 通过答辩综合判断，项目小组同学的设计结构是否合理，是否能对课程设计内容进 行全面、系统的总结，并能用理论知识对课程设计所涉及的问题加以深入分析，是否收 集并综合利用了足够的资料，独立运用所学知识的能力如何，独立分析问题和解决问题 的能力如何，是否有自己的创新之处。答辩时对该设计项目过程的把握程度如何，回答 第33页 共34页 西南财经大学天府学院教案 TIANFU COLLEGE OF SWUFE 问题思路是否清晰，陈述相关程序时是否语言流利。 (三)答辩完成后完成错误或不足部分，完善相关提交资料。 90 作 业 答辩完成后继续完善相关提交资料。 布 置 课 通过一学期的学习，最后的小组项目答辩是各小组成员展示小组项目成果的一次很好的机会，后 很多小组通过分工协作最终完成了项目，大家反应虽然在过程中遇到很多问题，但是通过自总 己的努力将一个个的问题解决，收获很大，并且也提升了自己的学生自信心和学习兴趣，是结 一次很好的锻炼。 第34页 共34页