高中信息技术算法与程序设计分册4.4查找教案.pdfVIP

高中信息技术算法与程序设计分册4.4查找教案

一、教材

教材：中国科大版秦锋主编《数据结构》

参考书：清华大学版严蔚敏等《数据结构》

二、教学目标

通过对本章的学习，使学生掌握教科书中所列出的排序算法的差

不多思想，熟练掌握顺序查找、折半查找、分块查找算法，并能熟练

地设计类似的算法；掌握二叉排序树的查找、插入算法，理解二叉序

树的删除、B-树和B+树；掌握哈希查找的差不多思想，并能设计简

单的算法。

三、课时

5—6学时

四、重点难点

顺序查找、折半查找、二叉排序树的查找与插入、哈希查找应作

为本章的重点，而B-树、B+树尽管比较难，但并不是本章的重点。

五、教学内容与过程组织

8、1差不多概念

一

〔这节是为后面几节做预备的，因此要把本章中所用到概

念及几个名词介绍清晰。〕

1、先介绍查找的概念

〔如：在辞典中查找一个单词，在电话号码簿中查找一个电

话号码等〕

2．再介绍以下名词

记录、关键字、查找表、查找成功与失败、静态查找与动

动态查找、平均查找长度〔必要时，可一个简单例子〕。

3、为了本章讲授方便，要介绍清晰查找表记录的格式定义。

8、2线性表的查找

1、顺序查找

该算法比较简单，简单地介绍一下差不多思想即可。

让学生自己学出算法，并进行分析，找出查找成功时的平均

查找长度和查找不成功时的平均查找长度。之后，老师可对算法

做一介绍，并分析。

可不要因为该算法太简单，而忽视了它！顺序查找算法有【三】

四种写法，执行时间相差好几倍呢！不妨给出几个算法让学生讨

论。其中有假设干设计技巧，教科书中的“监视哨”确实是其中

之一。

2．折半查找

先介绍一下顺序查找的适应对象：顺序查找是对无序表操作的，

假设是有序表呢？显然，用顺序查找就不合适了。举一例子，介

绍一下折半查找的差不多思想〔所以要在黑板上进行〕。

通过那个例子，学生们大都理解了。下面给出算法，并讲解。

在讲解算法时，要讲清晰以下几点：

〔1〕比较的对象为“中间”元素，但并不是绝对的。

(2)上下界的修正问题。

（3）在一个表中查找时，在同一个区间内，不管查找的关

键字是什么，比较的对象是相同的。

在讲第〔3〕点时，能够通过例子详细介绍，讲完之后，判

定树就出来了。通过判定树，使学生加深对查找路径和查找长度

的理解。〔这一段也要在黑板上讲〕

讲完折半查找后，可用半小时的时间介绍一下斐波那契查找、插值查

找的差不多思想。

3、分块查找

先介绍一下顺序查找和折半查找的优缺点，之后，给出一种

折衷的查找方法，即分快查找。有了前面两种查找方法的基础，

分块查找的思想和分析就简单多了。

用15分钟的时间，对以上三种查找方法做一简单总结。

8、3树表查找

首先，向学生介绍以下事实：以上三种查找算法是对固定长度的

表进行操作的，假如在查找过程中，又有插入或删除操作时，记录的

移动是相当费时的，这确实是静态查找的缺点。

针对以上问题，引出动态查找的概念，进行下面的内容。

1、二叉排序树

先給出二叉排序树的定义，并举例说明；再介绍在二叉排序树上

查找和插入算法的差不多思想；最后，给出二叉排序树的结构定义。

由于二叉排序树的查找和插入算法比较简单，如今，可直截了当进入

查找和插入算法的讲解了。

〔1〕二叉排序树的查找算法

想必学生们差不多比较熟练地掌握了二叉树遍历算法了，因此，

能够要求学生当场写出算法，并进行复杂性分析。

学生做完以后，老师要讲二叉排序树的性质：假设对二叉排序树

进行中序遍历，输出的结果是一个有序序列。因此，在二叉排序树上

查找时，类似于折半查找。

对该算法的分析，可在后面进行，以引出平衡二叉树。

〔2〕二叉排序树的插入和生成算法

在二叉排序树上插入结点和二叉排序树的生成算法实际上是同

一个算法，因此，只介绍插入算法即可。

先介绍结点的插入规那么