数据结构-Python语言描述教案.docx

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

1、教案授课时数2教学目的：1 .介绍数据结构的基本概念（P2）2 .算法的描述（P8）和算法时间复杂度（P10）空间复杂度（P10）3 .要求了解本章介绍的各种基本概念和术语，是全书的基础。教学内容（课程导入）一数据结构数据结构基本概念：指的是相互之间存在着一种或者多种关系的数据元素的集合，也叫数据元素类，是数据的一个自己，数据元素是数据对象的一个实例。数据的逻辑结构可分为四类：1）集合2）线性结构3）树形结构4）图形结构P3【图1.2】数据的存储结构可分为四类：1）顺序存储结构2）链式存储结构3）索引存储结构4）散列存储结构数据操作：1）创建操作2）插入创造3）删除创造4）查找创造5）修改操作

2、6）遍历操作7）销毁操作数据类型：是一组性质相同的值的集合和定义在此集合上的一组操作的总称。数据抽象：数据抽象指“定义和实现相分离”，即将一个类型的数据及其上的操作的逻辑含义和具体实现相分离，只考虑执行什么操作，而不考虑怎样实现这些操作。抽象数据类型:抽象数据类型是从问题的数学模型中抽象出来的逻辑结构定义在逻辑结构上的一组操作，进描述了数据的特性和数据操作的语法规则，隐藏了数据的存储结构和操作的实现细节。P6【例1.2】二算法：算法的定义：算法是有穷规则的集合，其规则确定一个解决某一特定类型问题的指令序列，其中每一条指令表示计算机的一个或者多个操作。算法必须满足五个特性：1）有穷性2）确定性3

3、）可行性4）有输入5）有输出算法建立在数据结构上，对数据结构的操作需要使用算法来描述。算法设计依赖于数据的逻辑结构，算法实现依赖于数据的存储结构。算法描述：算法可以采用1）自然语言2）程序设计语言3）伪代码多种语言来描述P9【例1.3】三算法分析算法分析是主要是通过某种方法讨论算法的复杂度，评价算法的效率，以便在解决实际问题时根据实际情况和算法的优缺点对算法进行取舍。四算法的时间复杂度是指算法的执行时间虽问题规模的变化而变化的趋势，反映算法执行时间的长短。执行时间是用算法编写的程序在计算机上运行的时间，他是算法中涉及的所有的基本运算的执行时间之和。通常采用算法的渐进分析中的大O表示作为算法时间

4、复杂度的渐进度量值，称为算法的渐进时间复杂度。循环语句的时间代价一般可用一下3条原则进行分析：1）一个循环的时间代价=循环次数每次执行的基本指令数目。2）多个并列的循环的时间代价=每个循环的时间代价之和。3）多层嵌套循环的时间代价=每层循环的时间代价值积。五算法的时间/空间复杂度.算法分析举例书本P11【例1.4】本章节的教学重点、难点：1 .重点是数据结构的基本概念2 .难点是时间复杂度分析教学方法、教学手段：1 .介绍到算法概念2 .算法分析和举例使用教具：计算机和投影仪作业、讨论题、思考题:P12讲授章节第二章线性表授课时数7教学目的：1.介绍线性表的基本概念（P15）和各种存储表示方法

5、（P16-18）2.定义在逻辑结构上的各种基本运算及在存储结构上如何实现这些基本运算（P18-22）。3.要求在这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。教学内容（讲授提纲）一线性表线性表的Python抽象类的实现方法主要有以下两种1）基于顺序存储的实现2）基于链式存储的实现。二线性表的顺序存储定义：是把线性表中的所有元素按照其逻辑顺序依次存储到计算机的内存单元中指定存储位置开始的一块连续的存储空间中，成为顺序表。P17图2.2特点：1）在线性表中逻辑上相邻的元素在物理存储位置上也同样相邻。2）可按照数据元素的位序号

6、进行随机存取。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个数据元素之后的数据元素都向前移动一个存储

7、单元。3）表长减1, P20【算法2.2】查找操作主要步骤为将x与顺序表中的每一个数据元素的值进行比较，若相等，则返回该数据元素的位置；若比较结束未找到等值的数据元素，返回-1.P21【算法2.3】【例2.3】P22【例2.4】三线性表的链式存储和实现采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据元素。逻辑上相邻的数据元素在屋里位置上不一定相邻，必须采用附加欣喜表示数据元素之间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息-数据域，而且包含元素之间的逻辑关系的信息，即逻辑上相邻结点地址的指针域。单链表单链表指结点中只包含一个指针域的链表，指针域中储存着指向

8、后继结点的指针。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

9、）头插法P26【算法2.9】2）尾插法P27【算法2.10】本章节的教学重点、难点本章重点是熟练掌握顺序表（P17-21）和单链表（P22-27）上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章学到的基本知识设计有效算法与线性表相关的应用问题。教学方法、教学手段：1 .开始到顺序表中各种操作实现2 .顺序表算法钟）使用教具：计算机和投影仪作业、讨论题、思考题：P28-30g -* * 14 第三章栈讲授章节授课时数教学目的:1 .介绍栈（P31）和队列（P37）的逻辑结构定义2 .两种顺序结构上如何实现栈（P32-36）和队列（P38-46）的基本运算。3 .要求在掌握栈和队列的特

10、点的基础上，懂得在什么样的情况下能够使用栈或队列。教学内容（讲授提纲）一栈栈的概念：栈是一种特殊的线性表，其插入，删除操作只能在表的尾部进行。在栈中允许进行插入，删除操作的一端称为栈顶，另一端称为栈底。在栈a0，a1, a2,，an-1中a0成为占地元素，an-1成为栈顶元素。通常，栈的插入叫做入栈，站的删除操作交出栈。栈的抽象数据Python接口包含了栈的主要基本操作，如果要使用这个接口还需要具体的类来实现。栈的Python接口的实现方法主要有以下两种：1）基于顺序存储的实现，为顺序栈；2）基于链式存储的实现，为链栈。顺序栈顺序栈基本操作的实现入栈操作（P33图3.1）1）判断顺序栈是否为满

11、，若满则抛出异常。2）将乂存入top所指的存储单元位置。3）Top加1. P33【算法3.1P33【算法3.2P34【例3.1】链栈链栈的存储结构：P34图3.3链栈基本操作的实现1）入栈操作，主要步骤如下1）改造购书值域为x的新结点。2）改变新结点和首结点指针域，是新结点成为新的栈顶顶点。链栈进行入栈操作后的状态棉花如图P363.4所示P36【算法3.3】2）出栈操作，主要步骤如下1）判断链栈是否为空，若空则返回null。2）修改top指针域的值，返回被删结点的数据域值。链栈进行出栈操作后的状态变化如图3.5所示P40P36【算法3.4】【例3.2P37【例3.3】【例3.4】二队列队列的基

12、本概念队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。通常，队列的插入操作交入队，队列的删除操作叫出队。没有数据元素的队列称为空队列。队列的抽象数据Python接口包含了队列的主要的基本操作，如果要使用这个接口，还需要具体的类来实现。队列的Python抽象类的实现方法主要有以下两种：1）基于顺序存储的实现，为顺序队列。2）基于链式存储的实现，为链队列。顺序队列顺序队列的存储结构与顺序栈类似，可用数组实现，因为入队和出队操作分别在对为和对手进行，所以增加变量front来只是队首元素的位置，rear指示队尾元素的下一个存储单元的位置。顺序队列进行入队操作的状态变化如P

13、39图3.7进行出对操作后的状态变化 P37图3.8顺序队列之所以会出现“假溢出”(P40图3.9)现象是因为顺序队列的存储单元没有重复使用机制，为了解决顺序队列因数组下标越界而应起的“溢出”问题，课将顺序序列的首位项链，形成循环顺序队列。循环顺序队列进行入队和出对操作后状态变化如P40图3.10 P41【例3.5】【例3.6】链队列是单链表实现，由于入队和出对分别在队尾和队首进行，不存在在队列的任意位置进行插入和删除的情况，所以不需要设置头结点，只需要将指针front和rear分别指向对手节点和对为节点，每个节点的指针域指向其后继结点即可。P42图3.12所示为链队列进行入队操作的状态变化。

14、本章节的教学重点、难点：本章重点是掌握栈(P31-36)和队列(P37-44)在两种存储结构上实现的基本运算.教学方法、教学手段：1.栈的基本概念和顺序栈2.链栈、中缀表达式求值使用教具：计算机和投影仪作业、讨论题、思考题：P47、48、49讲授章节第四章串和数组授课时数5教学目的：1 .本章主要是介绍串的基本概念（P50）2 .数据类型定义（P50）3 .串的存储结构，基本操作实现和应用等（P51）。4 .介绍多维数组的逻辑结构特征及存储方式（P60-61），特殊矩阵和稀疏矩阵的压缩存储方法（P61-64）。教学内容（讲授提纲）一串串的概念：字符串也叫串，是有字符组成的有限序列，是一种常用的

15、非数值数据。串的逻辑结构是线性表，串是一种特殊的线性表，其每个数据元素都是一个字符。穿的操作特点与线性表不同，主要是对字串进行操作，通过采用顺序存储结构存储。串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决定。字符串的抽象数据类型Python抽象类包含了串的主要基本操作，如果要使用这个接口，还需要具体的类来实现。串的Python抽象类的实现方法主要有以下两点：1）基于顺序存储的实现，为顺序串；2）基于链式存储的实现，为链串。顺序串顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具有独特的不同雨线性表的操作，属于特殊类型的线性表。如P51图4.1顺

16、序串基本操作的实现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串的匹配模式串的模式匹配也叫查找定位，指的是在当前串中的寻找模式串的过程，

17、主要的模式匹配算法有Brute-Force算法和KMP算法。Brute-Force 算法是从主串的第一个字符开始和模式串的第一个字符进行比较，若想等，则继续比较后续字符；否则从主串的第二个字符开始重新和模式串进行比较。以此类推，知道模式串的每个字符一次与朱传的字符相等，匹配成功。P56【算法4.5】KMP算法Kmp算法的主要思想是当某次匹配失败时主串的开始标位置不会推推，而是利用部分字符匹配的结果将模式串向右移动较远的距离后再继续进行比较。Kmp模式匹配算法分析K值的计算P57【算法4.6】Kmp算法步骤1）计算模式穿的next 函数值2）I为主串的比较字符位序号，j为模式串的比较字符位序号。

18、当字符相等时，i， j分别加1后继续比较；否则i的值不变，j=nextj,继续比较。3）重复步骤2），直到j等于模式串的长度是匹配成功，否则匹配失败。P58【算法4.7】【例4.2】【例4.3】二数组数组是n个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在地质连续的存储单元中，是顺序存储的随机存储结构。数组元素在数组中的位置成为数组元素的下标，用户通过下标可以访问相应的数组元素。数组的下标的个数是数组的维数，具有一个下标的数组叫一维数组，具有两个下标的数组叫二维数组。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。数组的特性数组元素被存放在一组地址连续的存储单元里，并且每个

19、数据元素的大小相同，故只要已知首地址和每个数据元素占用的内存单元大小即可求出数组中任意数据元素的存储地址。数组的遍历对二维数组进行遍历操作有两种次序，即行主序和列主序。P61【例4.4】三特殊矩阵的压缩存储在科学技术和工程计算的许多领域，矩阵是数值分析问题研究的对象。本章将以特殊矩阵为例介绍矩阵的压缩存储。矩阵采用二维数组进行存储，至少占用m x n个存储单元。三角矩阵的压缩存储线性压缩存储使用三角形的二维数组压缩存储对称矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储1 .稀疏矩阵的非零元素三元组 P64【算法4.8】矩阵元素的行号，列号和元素值称为钙元素的三元组。2 .稀疏矩阵的十字链表

20、存储P64【例4.5】本章节的教学重点、难点：1 .中缀表达式转成前缀、后缀表达式，并对两种表达式求值。2 .用递归解决的问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的，掌握典型问题的算法。将递归算法转为非递归算法，特别是尾递归的消除。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P65、 P66， P67讲授章节第五章树形结构授课时数7教学目的：1 .介绍树的定义(P68)2 .二叉树的定义和性质(69)3 .存储结构(P71)4 .遍历及算法和应用(P72-79)5 .哈夫曼树及哈夫曼编码(P79-83)等内容。教学内容(讲授提纲)一树树的概念树是数

21、据元素之间具有层次关系的非线性结构，是由n个结点构成的有限集合，结点数为0的树叫空树。树必须满足：1）有且仅有一个被称为根的结点。2）其余结点可分为m个互不相交的有限集合，每个集合又构成一棵树，叫根结点的子树。树的表示方法有很多种，如树形表示法，文氏图表示法，凹入图表示法和广义表表示法。见68图5.1图5.2树的术语P69需熟悉二叉树二叉树的基本概念1）普通二叉树2）满二叉树3）完全二叉树二叉树的性质有五个性质P705.2.2、P70-71【例5.1】【例5.2】二叉树的存储结构二叉树的顺序存储结构:是指将二叉树的各个结点存放在一组地址连续的存储单元中，所有结点按结点序号进行顺序存储。可以利用

22、5.2.2节总的性质5将二叉树的结点排成线性序列，将节点存放在下标为对应编号的数组元素中。示意图P71图5.5二叉树的链式存储结构：是指将二叉树的各个结点随机存放在存储空间中，二叉树的各结点间的逻辑关系由指针确定。二叉树的链式存储结构又分为P72【图5.61）二叉链式存储结构2）三叉链式存储结构二叉树链式存储结构的结点类的描述二叉树类的描述二叉树的遍历二叉树的遍历方法二叉树通常可划分为三个部分，即根结点，左子树和右子树。根据3个部分的访问顺序不同，可将二叉树的遍历方法分为：P73【图5.71)层次遍历2) P73先序遍历【算法5.13) P73中序遍历【算法5.24) P73后序遍历【算法5.

23、3二叉树遍历操作实现的递归算法二叉树遍历操作实现的非递归算法将递归算法转换成非递归算法使用临时便利保存中间结果，用循环结构代替递归过程利用栈保存中间结果1) P74先序遍历【算法5.42) P74中序遍历【算法5.53) P75后序遍历【算法5.64) P75层次遍历【算法5.7二叉树遍历算法的应用二叉树上的查找算法P76【算法5.8统计二叉树的结点个数的算法P77【算法5.9二叉树的深度 P77【算法5.10二叉树的建立P79【例5.3图5.91)由中序和先序遍历序列建立二叉树P78【图5.8【算法5.112)由标明空子树的先序遍历序列创建二叉树P79【算法5.12二哈夫曼树及哈夫曼编码哈夫

24、曼树的基本概念1结点间的路径2节点的路径长度3结点的权4节点的带权路径长度5树的带权路径长度6最优二叉树哈夫曼树的构造P81【图5.10】P80【例5.4】构造哈夫曼树和哈夫曼编码的类的描述构造哈夫曼树需要从子结点到父结点的操作，译码是需要从父结点到子结点的操作，所以为了提高算法的效率将哈夫曼树的结点设计为三叉链式存储结构。构造哈夫曼树P82【算法5.13】求哈夫曼编码P82【算法5.14P83【例5.5】三树和森林树的存储结构1树的父母孩子链表2树的父母孩子兄弟链表树的遍历规则树的孩子有限遍历规则有两种1）树的先序遍历2）树的后序遍历树的遍历规则也是递归的本章节的教学重点、难点：重点掌握二叉

25、树的遍历算法及其与有关应用（P76-79）难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P84、 P85、 P86讲授章节第六章图授课时数教学目的：1 .主要介绍图的基本概念(P87)2 .抽象数据类型定义和存储结构(P89-96)，遍历方法(P97-P101)3 .介绍最小生成树的基本概念和算法(P102-104)4 .最短路径的相关算法(P104-107)，拓扑排序的概念和实现方法(P107-n0)。教学内容(讲授提纲)一图概述图的概念 无向边 有向边 零图 无向图 有向图 完全图P88【图6.

26、16.26.3】 稠密图 子图 生成子图 邻接点 顶点的度 路径 回路 连通图 连通分量 强连通图 强连通分量 生成树和生成森林 网图的抽象数据类型描述二图的存储结构邻接矩阵1 .图的邻接矩阵的存储结构2 .图的邻接矩阵类的基本操作的实现1）图的创建【P90算法6.1 P916.26.3 P916.4】（创建无/有向图，创建无/有向网）2）顶点的定位P92【算法6.5】3）查找第一个邻接点P92【算法6.6】4）查找下一个邻接点P92【算法6.7】3 .邻接矩阵表示图的性能分析P93【例6.1】邻接表1 .图的邻接表存储结构2 .图的邻接表的基本操作的实现1）图的创建【算法P956.86.9

27、P966,106.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个顶点和

28、n-1条边3）不能使用产生回路的边。产生最小生成树的算法主要有两种Krusakl 算法Prim算法P104【例6.6】五最短路径最短路径的求解问题主要分为两类1 .求某个顶点到其余顶点的最短路径2 .求任意两个顶点间的最短路径六拓扑排序和关键路径拓扑排序主要步骤1) .在AOV网中选择一个没有前去的顶点并输出2) .在AOV网中删除该顶点以及从它出发的弧3) .重复1.2直到AOV网为空，或者剩余子图中不存在没有前驱的顶点，此时说明AOV 网中存在环。P108【算法6.166.17关键路径由于AOE网中某些活动可以并行进行，故完成整个工程的最短时间即从源点到汇点的最长路径的长度，这条路径被称为

29、关键路径，构成关键路径的弧即为关键活动P109-110【算法6.186.19本章节的教学重点、难点：要求学生在熟悉这些内容的基础上重点掌握图的存储结构和图的两种遍历算/P89-101)本章难点是求最小生成树的算法(P102-104)最短路径(P104-106)拓扑排序和关键路径算法(P107-n。)。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P111、 P112讲授章节第七章排序授课时数教学目的:1 .本章目的是介绍五类内部排序方法的基本思想2 .排序过程3 .算法实现4 .时间和空间性能的分析以及各种排序方法的比较和选择。教学内容（讲授提纲）一排序概述排序的基本概念是

30、指将一组数据按照关键字值的大小（递增或递减）次序进行排列。排序是线性表，二叉树等数据结构的一种基本操作。排序算法的性能评价通常从时间复杂度和空间复杂度两个方面评价排序算法的性能待排序的记录和顺序表的类描述二插入排序直接插入排序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.

31、 算法稳定性快速排序1 .快速排序算法的实现P118【图7.47.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.

32、 时间复杂度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讲授章节第八章查找授课时数7教学目的：1 .介绍查找的基本概念

33、(P130)2 .顺序查找(P131)二分查找(P131)等查找的原理和实现方法和性能分析3 .二叉排序树的算法应用(P133T36)4 .平衡二叉树136)哈希表的概念(P139)及结构定义(P140)。教学内容(讲授提纲)一查找的基本概念查找就是在由一组记录组成的集合中寻找属性值符合特定条件的数据元素查找表就是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的灵活的数据结构给定值与关键字值的比较次数的期望值也被称为平均查找长度二静态表查找顺序查找1 .顺序查找算法的实现P131【算法8.1】2 .算法性能分析二分查找1.二分查找算法的实现P131-132【算法8.2】【图8.1】

34、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. 11

35、型平衡旋转（单向右旋）P137【图8.7】2. RR型平衡旋转（单向左旋）P137【图8.8】3. LR型平衡旋转（先左旋后右旋）P138【图8.9】4. RL型平衡旋转（先右旋后左旋）P138【图8.10B-树和B+树1. B-的概念2. B+的概念四哈希表查找（略讲）哈希表的概念哈希函数解决冲突的方法本章节的教学重点、难点：要求学生在熟悉这些内容的基础上掌握线顺序查找(P131)二分查找(P131)分块查找算法(P132)理解二叉排序树的基本概念和作用(P133)掌握二叉排序树的查找，插入和删除等操作算法133-136)了解平衡二叉树的基本概念和保持平衡性的调整规则(P137-139)。教学方法、教学手段：使用教具：计算机和投影仪作业、讨论题、思考题：P145，146