数据结构教案第八章

安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第八章查找课时2教学目的与要求熟练掌握顺序表有序表的查找方法，静态查找树的构造方法和查找算法，重点、难点重点：查找的基本概念和一些基本术语，顺序查找课型电脑＋理论教学方法投影、讨论、版书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、查找的基本概念前言：查找，也称检索。在我们日常生活中，随处可见查找的实例，例如查找某人的地址，电话号码，查某单位20岁以上职工等，都属于查找范畴。1、关键字定义：是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址，电话号码、成绩等关键字，但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素（每个考生考号是唯一的，不能相同的）我们将能唯一标识一个数据元素的关键字、称为主关键字，而其它关键字可称为辅助关键字或从关键字。有了以上定义，可以为查找定义。教学过程设计(续表)查找：就是给定的值，在一个点中查找出其关键字等于给定值的数据元素，若表中有这样的元素称查找成功的，此时，查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的或称查找是失败的，可给出相应的提示。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，用ASL表示。任务二：线性表的查找1．顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。2．顺序查找算法实现structnode{…;intkey;//key为关键字，类型设定为整型};typedefstructnodeNODE;intseq_search(NODEarrry[],intn,intk)//在表中查找关键字值{inti;为Ｋ的元素,n是表的长度for(i=0;in&&array[i].key!=k;i++);//从表尾开始向前扫描if(in)returni;elseretur(-1);}3.顺序查找性能分析顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。复习思考题作业上机任务案例分析：对于一个学生信息表，我们可以查找学生的姓名，年龄，成绩等等。我们可以用上面介绍的顺序查找方法。参考文献课后记（或归纳小结）本次课程就介绍这里结束，总结本次的内容；课后学生要好好把这次上的内容好好复习一下，然后预习下一次的内容，下一次我们介绍以上所述关系的具体描述安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第八章查找课时2教学目的与要求理解查找树和折半折半查找的关系。掌握二叉排序树的构造方法、查找方法和哈希表的构造方法。重点、难点重点：二分法查找（折半查找）难点：分块查找课型电脑＋理论教学方法投影、讨论、版书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）复习上一次的内容：1、查找内容：2、顺序查找：3、顺序查找的思想和算法：要求学生回答（接上一次课的序号）任务三：二分查找1.二分查找的基本思想二分查找，也称折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序)。不妨假设表中元素为升序排列。二分查找的基本思想是：首先将待查值K与有序表array[0]到array[n-1]的中点mid上的关键字array[mid].key进行比较，若相等，则查找成功；否则，若教学过程设计(续表)array[mid].keyk，则在array[mid+1]到array[n-1]中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。intbin_search(NODEarray[],intn,intk){intlow=0,hig=n-1,mid;while(low=hig){mid=(low+hig)/2;//取区间中点if(array[mid].key==k)return(mid);//查找成功if(array[mid].keyk)hig=mid-1;//在左子区间中查找elselow=mid+1;}//在右子区间中查找return(-1);}//查找失败例如，假设给定有序表中关键字为05,13,19,21,37,56,64,74,80,88,92将查找K=21和K=85的情况描述为图8-1及图8-2形式。012345678910012345678910012345678910[0513192137566474808892]lowhig(a)初始情形012345678910[0513192137]566474808892lowhigmid(b)经过一次比较后的情形[0513192137]566474808892(c)经过二次比较后的情形(array[mid].key=19)lowmidhig图8-1查找K=21的示意图教学过程设计(续表)012345678910012345678910012345678910012345678910012345678910051319[2137]566474808892(d)经过三次比较后的情形(array[mid].key=21)midlowhig图8-1查找K=21的示意图(查找成功)[0513192137566474808892]lowhig(a)初始情形012345678910051319213756[6474808892]midlowhig(b)经过一次比较后的情形051319213756[6474808892]lowmidhig(c)经过二次比较后的情形051319213756647480[8892]lowmidhig(d)经过三次比较后的情形3.二分查找的性能分析为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，图8-1给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树见图8-3。从图8-3可知，查找21的过程是从根到结点3的路径，查找85,应在结点9的左子树上,但其左子树为空,故失败。二叉树第K层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。则二分查找的时间复杂度为O(log2n)。任务四：分块查找分块查找1.分块查找的思想分块查找是顺序查找的一种改进方法，又称索引顺序查找，具体实现如下：将一个主表分成n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。typedefstruct{intkey;…;}NODE;typedefstruct{intkey,pos;}INDEX;40327658910图8-3具有11个关键字序列的二分查找判定树140327658910图8-3具有11个关键字序列的二分查找判定树1例如，给定关键字序列如下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3，即将该序列分成3个子表，每个子表有6个元素，则得到的主表和索引表如图所示。分块查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38,则先在索引表中按顺序比较，因为22k48，则可确定38应该在第二块中，从第二块的第一个记录array[6]顺序查起.分块查找的时间复杂度是O（m+n)m是块长度，n是索引表长度。224886061222121389203342443824486058744986535386497458604824384442332098131222126086422复习思考题作业上机任务案例分析：对于一个学生信息表，我们可以查找学生的姓名，年龄，成绩等等。我们可以用上面介绍的折半查找和分块查找方法。参考文献课后记（或归纳小结）本次课程就介绍这里结束，总结本次的内容；课后学生要好好把这次上的内容好好复习一下，然后预习下一次的内容，下一次我们介绍以上所述关系的具体描述安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第八章查找课时2教学目的与要求本节主要介绍了二叉排序树和平衡二叉树重点、难点重点：二叉排序树难点：平衡二叉树课型电脑＋理论教学方法投影、讨论、版书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）复习上一次的内容：4、折半查找：5、分块查找：6、折半查找的思想和算法：要求学生回答（接上一次课的序号）任务三：树表的查找二叉排序树查找1．什么是二叉排序树二叉排序树（BinarySortingTree），它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：(1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字；(3)左、右子树本身又都是一棵二叉排序树。教学过程设计(续表)2．二叉排序树的数据类型描述和第六章类似，可以用一个二叉链表来描述一棵二叉排序树，具体为：structnode{intkey;//代表关键字…structnode*lch,*rch;//代表左、右孩子};4．二叉排序树上的查找（1）二叉排序树的查找思想若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。（2）二叉排序树查找的算法实现NODE*search(intk,NODE*root)//在以root为根指针的二叉排序树中查找关键值为x的结点{NODE*p;p=root;while(p!==NULL){if(p-key==k)return(p);//查找成功elseif(p-keyk)p=p-lch;//进入左子树查找elsep=p-rch;//进入右子树查找}return(NULL);}5．二叉排序树查找的性能分析在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。任务四：平衡二叉树查找1．平衡二叉树的概念平衡二叉树(balancedbinarytree)是由阿德尔森一维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balancefactor)。也就