潍 坊 学 院 教 案课 题绪论课 时2教学目的与要 求1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构间的关系。2.了解抽象数据类型的定义、表示和实现方法。3.熟悉类C语言的书写规范。教学重点与难 点重点：数据、数据元素、数据对象、数据结构、存储结构和抽象数据类型等概念术语的确切含义；难点：理解什么是数据结构，另外存储结构也是个难点。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、介绍学好《数据结构》的意义及方法，激发同学的学习兴趣。另外简要介绍《数据结构》课程的发展背景及新的发展和研究方向。二、引入新内容1.1 什么是数据结构以多个例子引入数据结构的概念：图书馆的书目检索系统自动化问题——线性表计算机和人对奕问题——树多叉路口交通灯的管理问题——图问题引发学生兴趣，用图示加深学生理解和记忆，最后给出简洁明确的总结、定义。1.2 基本概念和术语数据、数据元素、数据对象、数据结构、存储类型、数据类型等。对于几种基本数据结构、存储结构等概念在课件中要给出形象的图示，便于学生理解。1.3 抽象数据类型的表示与实现三、小结四、课后作业：习题1.1 简述下列概念：数据，数据元素，数据类型，数据结构，存储结构，数据类型，抽象数据类型。 授课效果分析总结   课 题算法以及评价标准课 时2教学目的与要 求1.理解算法五个要素的确切含义。2.了解算法设计的要求。3.掌握计算语句频度和估算算法时间复杂度的方法。教学重点与难 点重点：算法的概念、评价标准及从时间和空间角度分析算法的方法。难点：算法的时间复杂度分析。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、回顾上讲要点数据结构基本概念抽象数据类型二、引入新内容1.4 算法和算法分析1.4.1 算法算法的五个重要特性算法的描述1.4.2 算法设计的要求正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量1.4.3 算法效率的度量算法的时间效率算法的渐近时间复杂度语句的频度(应以大量的例子说明算法时间复杂度的概念及其分析、估算方法)1.4.4 算法的存储空间需求三、小结。四、作业习题1.8 (1)(2)(8) 求语句频度和程序段的时间复杂度。补充：(9)i=1;while(i<=n)i=i*3;       难点授课效果分析总结   课 题线性表的类型定义及顺序表示课 时2教学目的与要 求1．了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同存储结构是顺序存储结构和链式存储结构；2. 熟练掌握顺序存储结构的描述方法；3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法教学重点与难 点重点：顺序表的存储结构的描述方法；线性表在顺序存储结构上实现基本操作；难点：顺序表的描述方法及插入、删除等基本操作的实现。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、回顾上讲要点基本概念术语 算法分析二、引入新内容2.1 线性表的类型定义举例阐明线性结构的特点，理解线性表的定义。2.2 线性表的顺序表示和实现2.2.1 线性表的顺序表示——顺序表①定义②特点③实现2.2.2 顺序表上实现的基本操作几个简单的基本操作的实现重点讨论线性表的插入和删除两种运算几个例题顺序表的优缺点分析三、小结。四、作业：题集2.22.11设顺序表a中的数据元素递增有序．试写一算法，将x插入到顺序表的适当位置上，以保持该线性表的有序性。并分析算法的时间复杂度。  授课效果分析总结   课 题线性表的链式表示和实现课 时2教学目的与要 求1．了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同存储结构是顺序存储结构和链式存储结构；2. 熟练掌握链式存储结构的描述方法；3. 熟练掌握在各种链式存储结构上实现线性表基本操作的方法，能在实际应用中选用适当的链表结构。教学重点与难 点重点：链式存储结构的描述方法；线性表在链式存储结构上实现基本操作；难点：各种链表的特点及在其上实现线性表基本操作的方法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体+板书一、新教学内容：2.3 线性表的链式表示和实现线性表链式存储结构的特点2.3.1 单链表单链表的定义和实现核心点：结点结构 注意图示单链表的基本运算：查找、插入、删除算法的实现及算法分析（课件与板书结合）单链表的特点2.3.2 循环链表循环链表的定义循环链表的特点循环链表和单链表上实现基本操作的比较2.3.3 双向链表特点及结点定义插入和删除操作二、小结三、作业：2.1试描述头指针、头结点、起始结点的区别，并说明头指针和头结点的作用。题集2.14： 试写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。题集2.22 试写一算法对带头结点的单链表实现就地逆置。补充题：已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插人表中，使L仍然有序。 授课效果分析总结  课 题静态链表 链表应用举例 习题讲解课 时2教学目的与要 求1.了解静态链表，加深对链表本质的理解；2.熟练掌握在各种链式存储结构上实现线性表基本操作的方法，能在实际应用中选用适当的链表结构。3.能够从时间复杂度和空间复杂度的角度综合比较线性表两种存储结构的不同特点及起适用场合。教学重点与难 点重点：链表的实现及应用；难点：理解、选择和应用链表解决问题。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、复习单链表、循环链表、双链表有关内容。二、引入新内容2.3.4 静态链表什么是静态链表静态链表的实现静态链表算法举例2.4 一元多项式的表示及相加问题分析 一元多项式的表示单链表结点定义运算规则及实现 重在思路2.5 链表小结三、作业：题集 2.31假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。四、本章习题讲评。主要参考书：《数据结构——习题与解析》 李春葆 编著 清华大学出版社《数据结构学练考》 杨明 等编著 清华大学出版社 授课效果分析总结     课 题栈及应用课 时3教学目的与要 求1. 掌握栈这种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法。3. 理解递归算法执行过程中栈的状态变化过程教学重点与难 点知识点：顺序栈、链栈栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体为主一、课前思考题—>引入新内容：二、 3.1 栈3.1.1 栈的定义和基本操作栈的定义 注意图示栈的9种基本操作 ④⑥⑨3.1.2 栈的表示和实现： 顺序栈、链栈顺序栈的实现及基本操作的实现链栈的实现 与顺序栈的不同特点3.2 栈的应用举例1、 函数的嵌套调用3.2.1 数制转换3.2.2 括号匹配的检验3.2.4 行编辑程序3.2.5 迷宫求解3.2.5 表达式求值三、小结四、作业：3.1(1)设有编号为1，2，3的三辆列车，顺序进入一个栈式结构的站台。具体写出这三辆列车开出车站的所有可能的顺序。习题3.3     注意图示授课效果分析总结   课 题队列课 时3教学目的与要 求1. 掌握队列这种抽象数据类型的特点。2. 熟练掌握循环队列和链队列的基本操作实现算法。3．学习如何在求解应用问题中适当地应用栈和队列。教学重点与难 点知识点：循环队列、链队列队列是在程序设计中被广泛使用的一种线性数据结构，因此本节学习重点在于掌握这种结构的特点，以便能在应用问题中正确使用。难点：循环队列；循环队列和链队列的应用。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、 3.4 队列3.4.1 队列的定义和基本操作队列特点：先进先出(FIFO)9种基本操作3.4.2链队列—队列的链式表示和实现链队列空的链队列的判决条件结点定义基本操作的算法描述3.4.2循环队列—队列的顺序表示和实现顺序队列 队头和队尾指针顺序队列存在问题：“假溢出”解决方案：循环队列循环队列及其队满、队空判别条件循环队列的类型说明和基本操作算法描述队列应用举例二、小结三、栈和队列的应用习题讲解四、布置实验一五、作业：1.对于循环向量中的循环队列，如何判断它的空和满？写出求队列长度的公式。题集 3.13 写算法功能。 授课效果分析总结  课 题串课 时2教学目的与要 求1. 熟悉串的七种基本操作的定义。2. 熟练掌握在串的定长存储结构上实现串的各种操作的方法。教学重点与难 点重点：串的基本操作和存储方法；难点：在串的存储结构上实现基本操作。 教 学 过 程主 要 内 容 及 步 骤备 注一、新知识：4.1 串类型的定义（一）、基本概念：串、子串、主串、子串在主串中的位置、两个串相等、串变量和串常量、空格串（二）、串基本操作4.2 串的表示和实现4.2.1 定长顺序存储分配用定长顺序存储表示时串操作的实现:串联接求子串二、小结三、习题讲解四、作业4．1简述下列每对术语的区别： 空串和空格率；串变量和串常量；主串和子串；串名和串值。题集 4.3 4.4 4.5 授课效果分析总结         课 题数组课 时2教学目的与要 求1. 了解数组的两种存储表示方法，并掌握数组在以行优先的存储结构中的地址计算方法。2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。教学重点与难 点重点：数组的顺序存储；矩阵的压缩存储。难点：稀疏矩阵的两种压缩存储方法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、新内容：5.1 数组的定义5.2 数组的顺序表示和实现两种顺序存储方式：行优先顺序列优先顺序数组在顺序存储结构中的地址计算方法5.3 矩阵的压缩存储5.3.1 特殊矩阵1、对称矩阵2、三角矩阵3、三对角矩阵5.3.2 稀疏矩阵二、小结三、作业 〈题集〉p31: 5.1 授课效果分析总结      课 题矩阵、广义表课 时2教学目的与要 求1.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵是进行稀疏矩阵运算采用的存储方法。2.掌握广义表的定义和基本概念。3.掌握广义表的结构特点和存储表示方法，会分解表。教学重点与难 点重点：广义表的定义、结构特点和存储表示方法。难点：稀疏矩阵的两种压缩存储方法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体1.      复习上讲内容；二、新内容：5.3.2 稀疏矩阵稀疏矩阵的压缩存储分析1、三元组顺序表（1）三元组顺序表的类型定义（2）矩阵的转置运算2、带行表的三元组顺序表3.十字链表5.4 广义表的定义一、广义表一般表示形式二、广义表的例子三、广义表的特性5.5 广义表的存储结构三、本章小结四、习题讲解五、布置作业、实验作业：〈题集〉p31: 5.10 授课效果分析总结       课 题树和二叉树课 时2教学目的与要 求1. 熟练掌握二叉树的结构特征，了解相应的证明方法。2. 熟悉二叉树的各种存储结构的特点及适用范围。教学重点与难 点重点: 二叉树的定义和性质；二叉树的存储结构。难点：理解二叉树的性质及其证明。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、新一章：6.1 树的定义和基本术语一、树的定义二、树结构中的一些基本术语6.2 二叉树6.2.1 二叉树的定义定义二叉树与树的最主要的差别二叉树五种基本形态6.2.1 二叉树的性质五个性质满二叉树和完全二叉树的概念6.2.1 二叉树的存储结构1.顺序存储结构2、二叉链表存储结构二、讲解实验注意事项三、作业：习题集 6.1 6.3补充1：试采用顺序存储方法和连接存储方法分别画出习题集p39图示二叉树的存储结构。 授课效果分析总结    课 题遍历二叉树和线索二叉树课 时2教学目的与要 求1. 熟练掌握二叉树的遍历算法。2. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。教学重点与难 点重点：二叉树的遍历。难点：各种遍历策略的递归算法，遍历过程中“栈”的作用和状态；二叉树的线索化过程。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体1.      复习上讲内容二、引入新内容：6.3遍历二叉树和线索二叉树6.3.1 遍历二叉树DLR——先（根）序遍历LDR——中（根）序遍历LRD——后（根）序遍历三种遍历的操作定义和实现例题与练习6.3.2 线索二叉树线索二叉树的定义和实现1.      遍历线索二叉树算法2、二叉树的线索化算法三、布置作业四、实验讲评练习：《题集》6.12作业：《题集》6.14 6.15 6.28补充2：以二叉链表作存储结构，试编写求二叉树深度的算法。 授课效果分析总结      课 题树和森林课 时2教学目的与要 求1. 掌握树的存储结构。2. 熟练掌握树和森林与二叉树的转换方法。3. 掌握树和森林的遍历。教学重点与难 点重点：树的存储结构，树和森林的定义及与二叉树的转换方法。难点：树的存储结构，森林与二叉树的转换方法 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、6.4 树和森林6.4.1 树的存储结构1.双亲表示法2. 孩子表示法3. 孩子兄弟表示法6.4.2 森林土与二叉树的转换1、森林转化成二叉树2、二叉树转换成森林6.4.3 树和森林的遍历两种次序遍历树的方法：1．先根（次序）遍历树2．后根（次序）遍历树森林的两种遍历方法：1、先序遍历森林2、中序遍历森林二、作业讲评三、作业：《题集》6.20 6.21 授课效果分析总结     课 题哈夫曼树及其应用课 时2教学目的与要 求1.      解最优树的性质。2. 掌握建立最优树和哈夫曼编码的方法。教学重点与难 点重点：哈夫曼树的基本概念；建立最优树和哈夫曼编码的方法。难点：建立最优树和哈夫曼编码的方法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体为主一、教学内容：6.6 哈夫曼树及其应用6.6.1 最优二叉树（哈夫曼树）1.      哈夫曼树的基本概念路径、路径长度、树的路径长度结点的带权路径长度、树的带权路径长度、哈夫曼树（最优二叉树）、哈夫曼编码2、哈夫曼树在判定问题中的应用3、如何构造哈夫曼树6.6.2 哈夫曼编码1、哈夫曼编码提出的背景2、构造哈夫曼树和哈夫曼编码的算法3、应用举例二、本章小结三、布置作业 实验讲评作业：〈题集〉6.20（2） 6.21 6.266.42 6.43 6.64 授课效果分析总结        课 题图的定义、术语和存储课 时2教学目的与要 求1、掌握图的定义和术语。2、熟悉图的邻接矩阵和邻接表表示法及其构造算法。了解实际问题的求解效率与采用和种存储结构和算法有密切关系。教学重点与难 点重点：图的定义和术语；图的邻接矩阵表示法和邻接表表示法。难点：图的邻接表表示法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、新一章：7.1 图的定义和术语一、图的定义二、图的基本术语1、顶点2、弧、弧尾、弧头、有向图3、边、无向图4、完全图、有向完全图、稀疏图、稠密图5、权、网6、子图7、邻接点、依附、相关联8、度、入度、出度9、路径、路径长度、回路或环、简单路径10、连通图、连通分量、强连通图、强连通分量、生成树、有向生成树7.2 图的存储结构7.2.1 数组表示法 （邻接矩阵表示）7.2.2 图的邻接表表示法1、 邻接表的结点结构2、邻接表是顶点的向量结构和边（弧）的单链表结构3、邻接表的优缺点二、小结三、作业：《习题集》 7.1 授课效果分析总结  课 题图的存储和遍历课 时2教学目的与要 求1.      熟悉图的十字链表表示法和邻接多重表表示法及其构造算法。了解实际问题的求解效率与采用和种存储结构和算法有密切关系。2、熟练掌握图两种搜索路径的遍历：遍历的逻辑定义、DFS和BFS算法。教学重点与难 点重点：遍历的逻辑定义；难点：深度优先和广度优先算法。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、复习上讲内容二、引入新内容：7.2.3 有向图的十字链表表示法7.2.4 无向图的邻接多重表表示法7.3 图的遍历7.3.1深度优先搜索 DFS什么是深度优先搜索实例模拟算法算法分析7.3.2 广度优先搜索 BFS什么是广度优先搜索实例模拟广度优先搜索算法 使用队列算法分析三、小结四、布置练习和作业作业：《习题集》 7.4 7.5         队列应用的例子 授课效果分析总结     课 题图的连通性课 时2教学目的与要 求理解掌握求解图的连通性问题的方法。教学重点与难 点重点：连通分量的概念及最小生成树的概念；最小生成树的构造方法。难点：最小生成树的构造方法 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、复习上讲内容二、引入新内容：7.4 图的连通性问题7.4.1 无向图的连通分量和生成树1、无向图的连通分量2、深度优先生成树和广度优先生成树3、生成森林4、深度优先生成森林的算法7.4.3 最小生成树1.      问题的提出2、由无向连通网构造最小生成树的方法3、生成最小生成树的普里母（prim）算法4、生成最小生成树的克鲁斯卡尔（kruskal）算法5、算法分析三、小结四、作业《习题集》 7.7    授课效果分析总结    课 题有向无环图及其应用课 时2教学目的与要 求理解有向无环图及其应用：拓扑排序和关键路径。教学重点与难 点重点：拓扑排序难点：拓扑排序 关键路径 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体7.5 有向无环图及其应用1、有向无环图的定义2、有向无环图的应用7.5.1 拓扑排序1、拓扑排序的基本概念2、拓扑排序的方法3、拓扑排序的算法4、拓扑排序算法的分析7.5.2 关键路径1、AOE网2、AOE网研究的问题1.      关键路径的几个术语4、求关键路径的算法5、求关键路径的实例模拟6、求关键路径的算法分析小结作业：《习题集》 7.9 7.10   授课效果分析总结     课 题最短路径课 时2教学目的与要 求目的：掌握两类求最短路径的方法。要求：理解最短路径的含义，掌握求单源最短路径问题的Dijkstra算法的基本思想和时间性能，会应用两类求最短路径的方法求解问题。教学重点与难 点重点：最短路径的求解思路难点：求解最短路径的思路及算法 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体+板书一、新内容：7.6 最短路径提出问题，介绍概念。7.6.1 从某个源点到其余各顶点的最短路径Dijkstra 求最短路径的算法1、Dijkstra 求最短路径的基本思想2、Dijkstra 求最短路径的步骤3、Dijkstra 求最短路径的实例模拟4、Dijkstra 求最短路径的算法5、Dijkstra 求最短路径的算法分析讲解时，首先提出问题，引发学生兴趣，要介绍求解思路形成过程。实例模拟采用板书形式，加强互动。7.6.2 有向图中每对顶点间的最短路径弗洛伊德（floyd）算法：1、弗洛伊德（floyd）算法的基本思想关键：递推公式 板书2、弗洛伊德（floyd）算法的实例模拟3、弗洛伊德（floyd）算法思考问题：路径描述的其它/更优方法？二、小结三、作业：《习题集》 7.11 7.22 板书实例图授课效果分析总结       课 题查找的基本概念和静态查找表课 时2教学目的与要 求1、理解查找的基本概念；2、熟练掌握顺序表和有序表的查找方法。3、熟悉静态查找树的构造方法和查找算法。教学重点与难 点重点：顺序查找、折半查找、索引顺序查找各自的思路与特点。难点：查找思路和算法实现。 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、新篇章：9.0 查找的基本概念9.1 静态查找表9.1.1 顺序表的查找顺序查找：查找过程算法实现查找操作的性能分析平均查找长度9.1.2 有序表的查找折半查找：查找过程适用条件算法实现折半查找的性能分析9.1.3静态树表的查找9.1.4 索引顺序表的查找索引顺序查找：1、分块查找的基本思想2、分块查找的平均查找长度二、几种查找方法的比较三、作业《习题集》9.3 9.9(1)(2) 授课效果分析总结  课 题二叉排序树和平衡二叉树课 时2教学目的与要 求1、熟练掌握二叉排序树的构造方法和查找方法。2、掌握二叉平衡树的维护平衡方法。教学重点与难 点重点:二叉排序树的插入、删除算法和查找方法难点：调平 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、回顾上讲要点二、新内容：9.2 动态查找表9.2.1二叉排序树和平衡二叉树一、二叉排序树及其查找过程：二叉排序树定义二叉排序树的查找、插入、构造、删除查找分析二、平衡二叉树平衡二叉树的定义平衡调整平衡二叉树的插入、构造查找分析三、习题讲解四、作业《习题集》习题9.26 9.9（1）(3)    授课效果分析总结    课 题B-树、B+树和键-树课 时2教学目的与要 求理解B-树、B+树和键-树的特点以及它们的建树过程。教学重点与难 点B-树、B+树和键-树的定义、特点；建树过程教学过程主 要 内 容 及 步 骤备 注一、教学内容：9.2.2 B-树和B+树1.定义：2.查找过程3.查找分析4.插入和删除5. B+树9.2.3 键-树二、本章小结三、作业、习题讲解       授课效果分析总结      课 题哈希表课 时4教学目的与要 求1、熟练掌握哈希表的构造方法。2、深刻理解哈希表与其他结构的表的实质性差别。教学重点与难 点重点：哈希表处理冲突的方法；哈希表的查找及其分析。难点：哈希表处理冲突的方法及其分析 教 学 过 程主 要 内 容 及 步 骤备 注一、新方法：9.3 哈希表9.3.1 哈希表（散列表）的基本概念9.3.2 散列函数的构造方法直接定地址法数字选择法(数字分析法)平方取中法折叠法除留余数法随机数法9.3.3 处理冲突的方法1.      开放地址法2.      再哈希法3.链地址法4.建立一个公共溢出区9.3.4哈希表的查找及其分析二、习题讲解三、作业《习题集》 9.21 授课效果分析总结       课 题插入排序课 时2教学目的与要 求理解掌握插入排序的基本思想、算法特点和排序过程及其时间复杂度分析。教学重点与难 点重点：插入排序的基本思想、算法特点难点：希尔排序 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：板书+多媒体一、第9章作业讲评二、第10章10.1 内部排序概述1、排序的定义2、排序的分类3、稳定排序和不稳定排序4、排序算法的评价10.2 插入排序10.2.1 直接插入排序1、排序原则及过程2、直接插入排序的算法复杂度10.2.2 其它插入排序1.折半插入排序2.2-路插入排序3.表插入排序10.2.3 希尔排序1、希尔排序基本思想2、希尔排序算法3、希尔排序分析三、小结四、作业： 习题 10.1 10.3   授课效果分析总结  课 题交换排序、选择排序课 时2教学目的与要 求理解掌握交换排序、选择排序的基本思想、算法特点和排序过程及其时间复杂度分析。教学重点与难 点重点：快速排序 一趟划分的思想与算法；堆排序。难点：快速排序 堆定义及堆排序 教 学 过 程主 要 内 容 及 步 骤备 注授课形式：多媒体一、插入排序特点二、引入新内容：10.3 交换排序1.起泡排序及其分析a、起泡排序过程b、起泡排序分析2.快速排序a、快速排序的基本概念b、快速排序的实例模拟c、快速排序算法d、快速排序分析10.4 选择排序1.简单选择排序2.树形选择排序3.堆排序a、堆的定义b 、堆排序的基本问题c、调整堆d、建堆e、排序算法f、排序算法分析三、几种排序方法的比较总结四、布置作业《题集》 10.1 10.3 10.12 授课效果分析总结  课 题归并排序课 时2教学目的与要 求1.      理解掌握归并排序的基本思想、算法特点和排序过程。2、分析归并排序的时间复杂度分析。教学重点与难 点重点:归并排序算法思路难点：归并排序算法及分析教学过程主 要 内 容 及 步 骤备 注一、复习上讲内容堆排序过程实例及分析二、作业讲评三、引入新内容10.5 归并排序1、归并排序的基本思想2、归并排序的算法3、二路归并排序的时间复杂度四、习题布置作业 《题集》 10.1 10.3      授课效果分析总结     课 题基数排序课 时2 教学目的与要 求1、理解掌握基数排序的基本思想、算法特点和排序过程及其时间复杂度分析。2、讨论比较各种排序方法。 教学重点与难 点重点：基数排序的思路难点：链式基数排序算法  教 学 过 程主 要 内 容 及 步 骤备 注 授课形式：多媒体一、复习上讲内容二、引入新内容10.6 基数排序10.6.1.多关键字的排序分配排序及实例分配排序方法基数排序10.6.2.链式基数排序1、基数排序的基本思想2、基数排序的实例模拟3、基数排序的算法10.7. 各种排序方法的比较讨论三、本章小结四、习题讲解五、布置作业《题集》 10.1 10.3 10.27    授课效果分析总结     课 题外部排序课 时2教学目的与要 求1、了解外部排序的基本方法，熟悉外部排序的两个阶段和第二个阶段---归并的过程。2、了解败者树的建立过程。教学重点与难 点重点：外部排序的基本方法。难点：外部排序效率分析 教学过程主 要 内 容 及 步 骤备 注一、作业讲评二、引入新内容11.1 外存信息的存取11.2外部排序的方法1、外部排序的两个阶段（1）生成有序归并段（顺串）（2）归并2、外部排序效率分析11.3 多路平衡归并的实现11.4 置换-选择排序11.6 最佳归并树三、布置实验四、作业《题集》 11.1    授课效果分析总结       课 题文件课 时2教学目的与要 求熟悉各类文件（顺序文件、索引文件、直接存取文件、多重表文件和倒排文件）的构造方法及文件操作在其上的实现。教学重点与难 点重点：各类文件的特点及不同适用场合。难点：各类文件的特点。 教学过程主 要 内 容 及 步 骤备 注12.1 文件的基本概念1.      与文件有关的基本术语二、记录的逻辑结构和物理结构三、文件的操作四、文件的物理结构12.2 顺序文件12.3 索引文件12.4 ISAM和VSAM12.5 直接存取文件12.6 多关键字文件多重表文件12.6.2 倒排文件本章小结作业：《题集》 12.1主要参考书：《数据结构——C语言描述》 唐策善 李龙澍 黄刘生 高等教育出版社《数据结构与算法》 齐德昱 清华大学出版社 授课效果分析总结