数据结构-Python语言描述教案.pdf
教 案讲授章节授课时数教学目的：1.介绍数据结构的基本概念（P2）第 1 章 绪论22.算法的描述(P8)和算法时间复杂度(P10)空间复杂度(P10)3.要求了解本章介绍的各种基本概念和术语，是全书的基础。教 学 内 容（课程导入）一一 数据结构数据结构数据结构基本概念：指的是相互之间存在着一种或者多种关系的数据元素的集合，也叫数据元素类，是数据的一个自己，数据元素是数据对象的一个实例。数据的逻辑结构可分为四类：1）集合 2）线性结构 3）树形结构 4）图形结构P3【图1.2】数据的存储结构可分为四类：1）顺序存储结构 2）链式存储结构 3）索引存储结构 4）散列存储结构数据操作：1）创建操作 2）插入创造 3）删除创造 4）查找创造 5）修改操作 6）遍历操作 7）销毁操作数据类型：是一组性质相同的值的集合和定义在此集合上的一组操作的总称。数据抽象：数据抽象指“定义和实现相分离”，即将一个类型的数据及其上的操作的逻辑含义和具体实现相分离，只考虑执行什么操作，而不考虑怎样实现这些操作。抽象数据类型：抽象数据类型是从问题的数学模型中抽象出来的逻辑结构定义在逻辑结构上的一组操作，进描述了数据的特性和数据操作的语法规则，隐藏了数据的存储结构和操作的实现细节。P6【例 1.2】二二 算法算法：算法的定义：算法是有穷规则的集合，其规则确定一个解决某一特定类型问题的指令序列，其中每一条指令表示计算机的一个或者多个操作。算法必须满足五个特性：1）有穷性 2）确定性 3）可行性 4）有输入 5）有输出算法建立在数据结构上，对数据结构的操作需要使用算法来描述。算法设计依赖于数据的逻辑结构，算法实现依赖于数据的存储结构。算法描述：算法可以采用 1）自然语言 2）程序设计语言 3）伪代码 多种语言来描述P9【例 1.3】三三 算法分析算法分析算法分析是主要是通过某种方法讨论算法的复杂度，评价算法的效率，以便在解决实际问题时根据实际情况和算法的优缺点对算法进行取舍。四四 算法的时间复杂度算法的时间复杂度是指算法的执行时间虽问题规模的变化而变化的趋势，反映算法执行时间的长短。执行时间是用算法编写的程序在计算机上运行的时间，他是算法中涉及的所有的基本运算的执行时间之和。通常采用算法的渐进分析中的大 O 表示作为算法时间复杂度的渐进度量值，称为算法的渐进时间复杂度。循环语句的时间代价一般可用一下3 条原则进行分析：1）一个循环的时间代价=循环次数每次执行的基本指令数目。2）多个并列的循环的时间代价=每个循环的时间代价之和。3）多层嵌套循环的时间代价=每层循环的时间代价值积。五五 算法的时间算法的时间/空间复杂度空间复杂度.算法分析举例书本P11【例 1.4】本章节的教学重点、难点：1.重点是数据结构的基本概念2.难点是时间复杂度分析教学方法、教学手段：1.介绍到算法概念2.算法分析和举例使用教具：计算机和投影仪作业、讨论题、思考题：P12讲授章节授课时数教学目的：第二章 线性表71.介绍线性表的基本概念（P15）和各种存储表示方法(P16-18)2.定义在逻 辑结构 上的各种 基本运 算及在 存储结构 上如何 实现这 些基本运 算(P18-22)。3.要求在这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。教 学 内 容（讲授提纲）一一 线性表线性表线性表的 Python 抽象类的实现方法主要有以下两种1）基于顺序存储的实现 2）基于链式存储的实现。二二 线性表的顺序存储线性表的顺序存储定义：是把线性表中的所有元素按照其逻辑顺序依次存储到计算机的内存单元中指定存储位置开始的一块连续的存储空间中，成为顺序表。P17 图 2.2特点：1)在线性表中逻辑上相邻的元素在物理存储位置上也同样相邻。2)可按照数据元素的位序号进行随机存取。3)进行插入，杀出操作需要移动大量的数据元素。4)需要进行存储空间的预先分配，可能会造成空间浪费，但存储密度较高描述：P17插入操作：P19 图 2.3 主要步骤为：判断顺序表的存储空间是否已满，若已满则抛出异常。1）判断参数 i 的值是否满足 0=i=curLen，若不满足则抛出异常。2）将插入位置及其之后的所有数据元素后移一个存储位置。3）在位置 i 出插入新的数据元素 x。4）在插入位置及其新的数据元素。5）表长加 1.P19【算法 2.1】删除操作P20 图 2.4 主要步骤为：1）判断参数 i 是否满足 i=i=curLen-1,若不满足则抛出异常。2）将第 i 个数据元素之后的数据元素都向前移动一个存储单元。3）表长减 1.P20【算法 2.2】查找操作主要步骤为将 x 与顺序表中的每一个数据元素的值进行比较，若相等，则返回该数据元素的位置；若比较结束未找到等值的数据元素，返回-1.P21【算法 2.3】【例 2.3】P22【例 2.4】三三 线性表的链式存储和实现线性表的链式存储和实现采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据元素。逻辑上相邻的数据元素在屋里位置上不一定相邻，必须采用附加欣喜表示数据元素之间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息-数据域，而且包含元素之间的逻辑关系的信息，即逻辑上相邻结点地址的指针域。单链表单链表指结点中只包含一个指针域的链表，指针域中储存着指向后继结点的指针。P22图 2.5、2.6查找操作其主要步骤为将 x 与单链表中的每一个数据元素的数据域进行比较，若想等，则返回该数据元素在单链表中的位置；若比较结束未找到等值的数据元素，返回-1.P24【算法 2.4】【算法 2.5】插入操作主要步骤如下：1）查找到插入位置的前驱结点，即第i-1 个结点。2）创建数据域值为 x 的新节点。3）修改前去结点的指针域为指向新节点的指针，新结点的指针域位指向原第i 个结点的指针。P25【算法 2.6】【算法 2.7】删除操作主要步骤如下1）判断单链表是否为空。2）查找待删除结点的前驱结点。3）修改前驱结点的指针域为待删除结点的指针域。P26【算法 2.8】单链表的建立操作1)头插法 P26【算法 2.9】2)尾插法 P27【算法 2.10】本章节的教学重点、难点本章重点是熟练掌握顺序表(P17-21)和单链表(P22-27)上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章学到的基本知识设计有效算法与线性表相关的应用问题。教学方法、教学手段：1.开始到顺序表中各种操作实现2.顺序表算法钟）使用教具：计算机和投影仪作业、讨论题、思考题：P28-30讲授章节授课时数教学目的：1.介绍栈（P31）和队列(P37)的逻辑结构定义2.两种顺序结构上如何实现栈(P32-36)和队列(P38-46)的基本运算。第三章 栈63.要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。教 学 内 容（讲授提纲）一一 栈栈栈的概念：栈是一种特殊的线性表，其插入，删除操作只能在表的尾部进行。在栈中允许进行插入，删除操作的一端称为栈顶，另一端称为栈底。在栈a0，a1，a2，an-1中 a0 成为占地元素，an-1 成为栈顶元素。通常，栈的插入叫做入栈，站的删除操作交出栈。栈的抽象数据 Python 接口包含了栈的主要基本操作，如果要使用这个接口还需要具体的类来实现。栈的 Python 接口的实现方法主要有以下两种：1）基于顺序存储的实现，为顺序栈；2）基于链式存储的实现，为链栈。顺序栈顺序栈基本操作的实现入栈操作(P33 图 3.1)1）判断顺序栈是否为满，若满则抛出异常。2）将 x 存入 top 所指的存储单元位置。3）Top 加 1.P33【算法 3.1】P33【算法 3.2】P34【例 3.1】链栈链栈的存储结构：P34 图 3.3链栈基本操作的实现1）入栈操作，主要步骤如下1)改造购书值域为 x 的新结点。2)改变新结点和首结点指针域，是新结点成为新的栈顶顶点。链栈进行入栈操作后的状态棉花如图P36 3.4 所示P36【算法 3.3】2）出栈操作，主要步骤如下1）判断链栈是否为空，若空则返回null。2）修改 top 指针域的值，返回被删结点的数据域值。链栈进行出栈操作后的状态变化如图3.5 所示 P40P36【算法 3.4】【例 3.2】P37【例 3.3】【例 3.4】二二 队列队列队列的基本概念队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。通常，队列的插入操作交入队，队列的删除操作叫出队。没有数据元素的队列称为空队列。队列的抽象数据 Python 接口包含了队列的主要的基本操作，如果要使用这个接口，还需要具体的类来实现。队列的Python 抽象类的实现方法主要有以下两种：1）基于顺序存储的实现，为顺序队列。2）基于链式存储的实现，为链队列。顺序队列顺序队列的存储结构与顺序栈类似，可用数组实现，因为入队和出队操作分别在对为和对手进行，所以增加变量 front 来只是队首元素的位置，rear 指示队尾元素的下一个存储单元的位置。顺序队列进行入队操作的状态变化如 P39 图 3.7 进行出对操作后的状态变化P37 图 3.8顺序队列之所以会出现“假溢出”（P40 图 3.9）现象是因为顺序队列的存储单元没有重复使用机制，为了解决顺序队列因数组下标越界而应起的“溢出”问题，课将顺序序列的首位项链，形成循环顺序队列。循环顺序队列进行入队和出对操作后状态变化如P40 图 3.10 P41【例 3.5】【例 3.6】链队列是单链表实现，由于入队和出对分别在队尾和队首进行，不存在在队列的任意位置进行插入和删除的情况，所以不需要设置头结点，只需要将指针front 和 rear 分别指向对手节点和对为节点，每个节点的指针域指向其后继结点即可。P42 图 3.12 所示为链队列进行入队操作的状态变化。本章节的教学重点、难点：本章重点是掌握栈(P31-36)和队列(P37-44)在两种存储结构上实现的基本运算.教学方法、教学手段：1栈的基本概念和顺序栈2链栈、中缀表达式求值使用教具：计算机和投影仪作业、讨论题、思考题：P47、48、49讲授章节授课时数第四章 串和数组5教学目的：1.本章主要是介绍串的基本概念（P50）2.数据类型定义(P50)3.串的存储结构，基本操作实现和应用等(P51)。4.介绍多维数组的逻辑结构特征及存储方式（P60-61），特殊矩阵和稀疏矩阵的压缩存储方法(P61-64)。教 学 内 容（讲授提纲）一一 串串串的概念：字符串也叫串，是有字符组成的有限序列，是一种常用的非数值数据。串的逻辑结构是线性表，串是一种特殊的线性表，其每个数据元素都是一个字符。穿的操作特点与线性表不同，主要是对字串进行操作，通过采用顺序存储结构存储。串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决定。字符串的抽象数据类型 Python 抽象类包含了串的主要基本操作，如果要使用这个接口，还需要具体的类来实现。串的Python 抽象类的实现方法主要有以下两点：1）基于顺序存储的实现，为顺序串；2）基于链式存储的实现，为链串。顺序串顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具有独特的不同雨线性表的操作，属于特殊类型的线性表。如 P51 图 4.1顺序串基本操作的实现1）求子串操作；P53【算法 4.1】2）插入操作 主要步骤如下：1）判断参数 i 是否 0=i=n，若不满足，则抛出异常。2）重新分配存储空间为 n+m，m 为插入的字符串 str 的长度。3）将第 i 个及之后的数据元素向后移动m 个存储单元。4）将 str 插入到字符串从 i 开始的位置。3）删除操作 P54【算法 4.2】【算法 4.3】4)连接操作5）比较操作 主要步骤如下：1）确定需要比较的字符的个数n 为两个字符串长度的较小值。2）从下标 0 至 n-1 依次进行比较 P54-55【算法 4.4】【例 4.1】链串的两种存储结构 P55 图 4.2串的匹配模式串的模式匹配也叫查找定位，指的是在当前串中的寻找模式串的过程，主要的模式匹配算法有 Brute-Force 算法和 KMP 算法。Brute-Force 算法是从主串的第一个字符开始和模式串的第一个字符进行比较，若想等，则继续比较后续字符；否则从主串的第二个字符开始重新和模式串进行比较。以此类推，知道模式串的每个字符一次与朱传的字符相等，匹配成功。P56【算法 4.5】KMP 算法Kmp 算法的主要思想是当某次匹配失败时主串的开始标位置不会推推，而是利用部分字符匹配的结果将模式串向右移动较远的距离后再继续进行比较。Kmp 模式匹配算法分析K 值的计算 P57【算法 4.6】Kmp 算法步骤1）计算模式穿的 next函数值2）I 为主串的比较字符位序号，j 为模式串的比较字符位序号。当字符相等时，i，j 分别加 1 后继续比较；否则 i 的值不变，j=nextj,继续比较。3）重复步骤 2），直到 j 等于模式串的长度是匹配成功，否则匹配失败。P58【算法 4.7】【例 4.2】【例 4.3】二二 数组数组数组是 n 个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在地质连续的存储单元中，是顺序存储的随机存储结构。数组元素在数组中的位置成为数组元素的下标，用户通过下标可以访问相应的数组元素。数组的下标的个数是数组的维数，具有一个下标的数组叫一维数组，具有两个下标的数组叫二维数组。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。数组的特性数组元素被存放在一组地址连续的存储单元里，并且每个数据元素的大小相同，故只要已知首地址和每个数据元素占用的内存单元大小即可求出数组中任意数据元素的存储地址。数组的遍历对二维数组进行遍历操作有两种次序，即行主序和列主序。P61【例 4.4】三三 特殊矩阵的压缩存储特殊矩阵的压缩存储在科学技术和工程计算的许多领域，矩阵是数值分析问题研究的对象。本章将以特殊矩阵为例介绍矩阵的压缩存储。矩阵采用二维数组进行存储，至少占用m x n 个存储单元。三角矩阵的压缩存储线性压缩存储使用三角形的二维数组压缩存储对称矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储1.稀疏矩阵的非零元素三元组 P64【算法 4.8】矩阵元素的行号，列号和元素值称为钙元素的三元组。2.稀疏矩阵的十字链表存储 P64【例 4.5】本章节的教学重点、难点：1中缀表达式转成前缀、后缀表达式，并对两种表达式求值。2用递归解决的问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的，掌握典型问题的算法。将递归算法转为非递归算法，特别是尾递归的消除。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P65、P66，P67讲授章节授课时数教学目的：1.介绍树的定义（P68）2.二叉树的定义和性质(69)3.存储结构(P71)4.遍历及算法和应用（P72-79）第五章 树形结构75.哈夫曼树及哈夫曼编码(P79-83)等内容。教 学 内 容（讲授提纲）一一 树树树的概念树是数据元素之间具有层次关系的非线性结构，是由 n 个结点构成的有限集合，结点数为 0 的树叫空树。树必须满足：1）有且仅有一个被称为根的结点。2）其余结点可分为 m 个互不相交的有限集合，每个集合又构成一棵树，叫根结点的子树。树的表示方法有很多种，如树形表示法，文氏图表示法，凹入图表示法和广义表表示法。见 68图 5.1 图 5.2树的术语 P69 需熟悉二叉树二叉树的基本概念1）普通二叉树2）满二叉树3）完全二叉树二叉树的性质有五个性质 P70 5.2.2、P70-71【例 5.1】【例 5.2】二叉树的存储结构二叉树的顺序存储结构：是指将二叉树的各个结点存放在一组地址连续的存储单元中，所有结点按结点序号进行顺序存储。可以利用 5.2.2 节总的性质 5 将二叉树的结点排成线性序列，将节点存放在下标为对应编号的数组元素中。示意图 P71 图 5.5二叉树的链式存储结构：是指将二叉树的各个结点随机存放在存储空间中，二叉树的各结点间的逻辑关系由指针确定。二叉树的链式存储结构又分为 P72【图 5.6】1）二叉链式存储结构2）三叉链式存储结构二叉树链式存储结构的结点类的描述二叉树类的描述二叉树的遍历二叉树的遍历方法二叉树通常可划分为三个部分，即根结点，左子树和右子树。根据3 个部分的访问顺序不同，可将二叉树的遍历方法分为：P73【图 5.7】1）层次遍历2）P73 先序遍历【算法 5.1】3）P73 中序遍历【算法 5.2】4）P73 后序遍历【算法 5.3】二叉树遍历操作实现的递归算法二叉树遍历操作实现的非递归算法将递归算法转换成非递归算法使用临时便利保存中间结果，用循环结构代替递归过程利用栈保存中间结果1）P74 先序遍历【算法 5.4】2）P74 中序遍历【算法 5.5】3）P75 后序遍历【算法 5.6】4）P75 层次遍历【算法 5.7】二叉树遍历算法的应用二叉树上的查找算法 P76【算法 5.8】统计二叉树的结点个数的算法 P77【算法 5.9】二叉树的深度 P77【算法 5.10】二叉树的建立 P79【例 5.3】【图 5.9】1）由中序和先序遍历序列建立二叉树 P78【图 5.8】【算法 5.11】2）由标明空子树的先序遍历序列创建二叉树 P79【算法 5.12】二二 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码哈夫曼树的基本概念1 结点间的路径2 节点的路径长度3 结点的权4 节点的带权路径长度5 树的带权路径长度6 最优二叉树哈夫曼树的构造 P81【图 5.10】P80【例 5.4】构造哈夫曼树和哈夫曼编码的类的描述构造哈夫曼树需要从子结点到父结点的操作，译码是需要从父结点到子结点的操作，所以为了提高算法的效率将哈夫曼树的结点设计为三叉链式存储结构。构造哈夫曼树 P82【算法 5.13】求哈夫曼编码 P82【算法 5.14】P83【例 5.5】三三 树和森林树和森林树的存储结构 1 树的父母孩子链表 2 树的父母孩子兄弟链表树的遍历规则树的孩子有限遍历规则有两种1）树的先序遍历2）树的后序遍历树的遍历规则也是递归的本章节的教学重点、难点：重点掌握二叉树的遍历算法及其与有关应用（P76-79）难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P84、P85、P86讲授章节授课时数教学目的：1.主要介绍图的基本概念（P87）2.抽象数据类型定义和存储结构(P89-96),遍历方法（P97-P101）3.介绍最小生成树的基本概念和算法(P102-104)第六章 图74.最短路径的相关算法(P104-107)，拓扑排序的概念和实现方法(P107-110)。教 学 内 容（讲授提纲）一一 图概述图概述图的概念无向边有向边零图无向图有向图完全图 P88【图 6.1 6.2 6.3】稠密图子图生成子图邻接点顶点的度路径回路连通图连通分量强连通图强连通分量生成树和生成森林网图的抽象数据类型描述二二 图的存储结构图的存储结构邻接矩阵1.图的邻接矩阵的存储结构2.图的邻接矩阵类的基本操作的实现1）图的创建【P90 算法 6.1 P916.2 6.3 P91 6.4】（创建无/有向图，创建无/有向网）2）顶点的定位 P92【算法 6.5】3）查找第一个邻接点 P92【算法 6.6】4）查找下一个邻接点 P92【算法 6.7】3.邻接矩阵表示图的性能分析 P93【例 6.1】邻接表1.图的邻接表存储结构2.图的邻接表的基本操作的实现1）图的创建【算法 P956.8 6.9 P96 6.10 6.11】（创建无/有向图，创建无/有向网）2）在图中插入边节点 P96【算法 6.12】3）查找第一个邻接点 P96【算法 6.13】4）查找下一个邻接点三三 图的遍历图的遍历图的遍历概念图的遍历方式分为1.广度优先搜索图的广度优先搜索遵循“先被访问的顶点，其邻接点先被访问”的规则 P98【算法6.14】2.深度优先搜索P99【算法 6.15】【例 6.2】P100【例 6.3】P100-101【例 6.4】【例 6.5】四四 最小生成树最小生成树在一个网的所有生成树中权值总和最少的生成树称为最小代价生成树，简称为最小生成树，最小生成树不一定唯一，需要满足以下三条准则1）只能使用图中的边构造最小生成树2）具有 n 个顶点和 n-1 条边3）不能使用产生回路的边。产生最小生成树的算法主要有两种Krusakl 算法Prim 算法P104【例 6.6】五五 最短路径最短路径最短路径的求解问题主要分为两类1.求某个顶点到其余顶点的最短路径2.求任意两个顶点间的最短路径六六 拓扑排序和关键路径拓扑排序和关键路径拓扑排序主要步骤1).在 AOV 网中选择一个没有前去的顶点并输出2).在 AOV 网中删除该顶点以及从它出发的弧3).重复 1.2 直到 AOV 网为空，或者剩余子图中不存在没有前驱的顶点，此时说明 AOV网中存在环。P108【算法 6.16 6.17】关键路径由于 AOE 网中某些活动可以并行进行，故完成整个工程的最短时间即从源点到汇点的最长路径的长度，这条路径被称为关键路径，构成关键路径的弧即为关键活动 P109-110【算法 6.18 6.19】本章节的教学重点、难点：要求学生在熟悉这些内容的基础上重点掌握图的存储结构和图的两种遍历算法(P89-101)本章难点是求最小生成树的算法(P102-104)最短路径(P104-106)拓扑排序和关键路径算法(P107-110)。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P111、P112讲授章节授课时数教学目的：第七章 排序71.本章目的是介绍五类内部排序方法的基本思想2.排序过程3.算法实现4.时间和空间性能的分析以及各种排序方法的比较和选择。教 学 内 容（讲授提纲）一一 排序概述排序概述排序的基本概念是指将一组数据按照关键字值的大小（递增或递减）次序进行排列。排序是线性表，二叉树等数据结构的一种基本操作。排序算法的性能评价通常从时间复杂度和空间复杂度两个方面评价排序算法的性能待排序的记录和顺序表的类描述二二 插入排序插入排序直接插入排序1 直接插入算法的实现 P114【图 7.1】【算法 7.1】2 算法性能分析1.时间复杂度2.空间复杂度3.算法稳定性希尔排序1.希尔排序算法的实现 P115【图 7.2】【算法 7.2】2.算法性能分析1.时间复杂度2.空间复杂度3.算法稳定性三三 交换排序交换排序冒泡排序1.冒泡算法的实现 P116【图 7.3】【算法 7.3】2.算法性能分析1.时间复杂度2.空间复杂度3.算法稳定性快速排序1.快速排序算法的实现 P118【图 7.4 7.5】P119【算法 7.4】2.算法性能分析 P120【例 7.1】1.时间复杂度2.空间复杂度3.算法稳定性四四 选择排序选择排序直接选择排序1.直接选择排序算法的实现 P121【图 7.6】【算法 7.5】2.算法性能分析1.时间复杂度2.空间复杂度3.算法稳定性堆排序1.堆的定义是利用完全二叉树特性的一种选择排序2.用筛选法调整堆在进行堆排序的过程中，当堆顶元素和堆中的最后一个元素交换位置后根结点和其子结点的关键字值不再满足堆的含义，需要进行调整。3.堆排序 P123【算法 7.7】4.算法性能分析 P123【例 7.2】1.时间复杂度2.空间复杂度3.算法稳定性五五 归并程序归并程序1.两个相邻有序序列归并 P124【算法 7.8】2.一趟归并排序 P125【算法 7.9】3.二路归并排序 P125【算法 7.10】算法性能分析 P125【例 7.3】1.时间复杂度2.空间复杂度3.算法稳定性本章节的教学重点、难点：要求学生在熟悉这些内容的基础上重点掌握冒泡排序（P117）快速排序（P118）堆排序(P123)归并排序(P124)的基本思想及排序过程。本章的难点是四个排序算法的实现。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P128，129讲授章节授课时数教学目的：1.介绍查找的基本概念（P130）2.顺序查找(P131)二分查找(P131)等查找的原理和实现方法和性能分析3.二叉排序树的算法应用（P133-136）第八章 查找74.平衡二叉树(P136)哈希表的概念(P139)及结构定义(P140)。教 学 内 容（讲授提纲）一一 查找的基本概念查找的基本概念查找就是在由一组记录组成的集合中寻找属性值符合特定条件的数据元素查找表就是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的灵活的数据结构给定值与关键字值的比较次数的期望值也被称为平均查找长度二二 静态表查找静态表查找顺序查找1.顺序查找算法的实现 P131【算法 8.1】2.算法性能分析二分查找1.二分查找算法的实现 P131-132【算法 8.2】【图 8.1】2.算法性能分析分块查找将线性表分成若干份，块之间是有序的，快中的元素不一定有序，将每块中最大的关键字值按块的顺序建立索引顺序表，在查找是首先通过索引顺序表确定待查找元素可能在的块，然后在块中寻找该元素。三三 动态表查找动态表查找二叉排序树查找1.二叉排序树的概念 P133【图 8.3】【例 8.1】2.二叉排序树查找算法的实现 P134【算法 8.3】3.二叉排序树插入算法的实现P134【算法 8.4】4.二叉排序树删除算法的实现 P135【算法 8.5】平衡二叉树1.平衡二叉树的概念：平衡二叉树是左右子树深度只差的绝对值小于2 并且左右子树均为平衡二叉树的树。2.平衡二叉树的实现 P138【例 8.3】1.LL 型平衡旋转（单向右旋）P137【图 8.7】2.RR 型平衡旋转（单向左旋）P137【图 8.8】3.LR 型平衡旋转（先左旋后右旋）P138【图 8.9】4.RL 型平衡旋转（先右旋后左旋）P138【图 8.10】B-树和 B+树1.B-的概念2.B+的概念四四 哈希表查找哈希表查找（略讲）（略讲）哈希表的概念哈希函数解决冲突的方法本章节的教学重点、难点：要求学生在熟悉这些内容的基础上掌握线顺序查找(P131)二分查找(P131)分块查找算法(P132)理解二叉排序树的基本概念和作用(P133)掌握二叉排序树的查找，插入和删除等操作算法(P133-136)了解平衡二叉树的基本概念和保持平衡性的调整规则(P137-139)。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P145，146
