数据结构教案第八章 - 图文

安徽新华电脑专修学院课堂教学教案

（电脑应用课使用）

课程名称 教 材 授课内容 数据结构 教学对象 数据结构（C语言） 新华软工专业 第八章 查找 课 时 2 教学目的 与要求 熟练掌握顺序表有序表的查找方法，静态查找树的构造方法和查找算法， 重点、难点 重点：查找的基本概念和一些基本术语，顺序查找 课 型 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 电脑＋理论 教学方法 投影、讨论、版书 任务一、 查找的基本概念 前言： 查找，也称检索。在我们日常生活中，随处可见查找的实例，例如查找某人的地址，电话号码，查某单位20岁以上职工等，都属于查找范畴。 1、关键字定义： 是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。 例如， 描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址，电话号码、成绩等关键字，但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素（每个考生考号是唯一的，不能相同的） 我们将能唯一标识一个数据元素的关键字、称为主关键字，而其它关键字可称为辅助关键字或从关键字。 有了以上定义，可以为查找定义。 查找： 就是给定的值，在一个点中查找出其关键字等于给定值的数据元素，若表中有这样的元素称查找成功的，此时，查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的或称查找是失败的，可给出相应的提示。 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，用ASL表示。 任务二：线性表的查找 1．顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。 2．顺序查找算法实现 struct node { …; int key; //key为关键字，类型设定为整型 }; typedef struct node NODE; int seq_search (NODE arrry[ ],int n,int k) //在表中查找关键字值 { int i; 为Ｋ的元素, n是表的长度 for (i=0; i

案例分析： 复习思考题 对于一个学生信息表，我们 可以查找学生的姓名，年龄，作 业 成绩等等。我们可以用上面介绍的顺序查找方法。 上机任务 参考文献 本次课程就介绍这里结束，总结本次的内容；课后学生要好好把课后记 这次上的内容好好复习一下，然后预习下一次的内容，下一次我（或归纳小们介绍以上所述关系的具体描述 结）

安徽新华电脑专修学院课堂教学教案

（电脑应用课使用）

课程名称 教 材 授课内容 数据结构 教学对象 数据结构（C语言） 新华软工专业 第八章 查找 课 时 2 教学目的 与要求 理解查找树和折半折半查找的关系。掌握二叉排序树的构造方法、查找方法和哈希表的构造方法。 重点：二分法查找（折半查找） 重点、难点 难点：分块查找 课 型 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 电脑＋理论 教学方法 投影、讨论、版书 复习上一次的内容： 1、查找内容： 2、顺序查找： 3、顺序查找的思想和算法：要求学生回答 （接上一次课的序号） 任务三：二分查找 1.二分查找的基本思想 二分查找，也称折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序)。不妨假设表中元素为升序排列。二分查找的基本思想是：首先将待查值K与有序表array[0]到array[n-1]的中点mid上的关键字array[mid].key进行比较，若相等，则查找成功；否则，若