线性表的查找技术教案

《线性表的查找技术教案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性表的查找技术教学目标：理解顺序查找和二分查找的基本思想。教学重点顺序查找和折半查找的思想、算法。教学难点折半查找的思想和算法。授课方法讲授、示例教学安排1课时教学手段板书、课件教学过程教学环节教学内容教师活动学生活动导入新课日常生活举例引入查找的概念。导入学生思考查找的基本概念顺序查找顺序表查找的基本概念查找是在具有相同类型的记录构成的集合屮找出满足给定条件的记录。为了便于讨论，把查找条件限制为“匹配”，即查找关键码等于给定值的记录。查找分为静态查找和动态查找。静态查找通常采用顺序查找和折半查找。在线性表中进行的查找通常属于静态查找。一、顺序查找顺

2、序查找，又称线性查找，主要用在线性结构中进行查找。若表中有n个对象，则顺序查找从表的一端开始，用各对象的关键码与给定值k进行比较，直到找到与其值相等的对象，则查找成功，给出该对象在表中的位置。若整个表都己检测完仍未找到关键码与k相等的对•象，则查找失败。给出失败信息。（1）、顺序表按值查找讲述思考按值查找intserch(intr[],intn,intk){inti;for(i=0;i<=n;i++)if(r[i]==k)returni+1;//下标为i的元素等于x,返回其序号i+1顺序表的顺序查找(演示)(2)、顺序表的顺序查找(演示)0123456

3、789K10152461235409855哨兵展示课件思考并理解查找方向顺序查找算法(3)、顺序查找算法intSeqSearchl(intr[],intn,intk){r[0]二k;i=n;while(r[i]!=k)i；returni;}二分查找二、二分查找(折半查找)现在有50个小圆球，其大小、颜色等完全相同，其中有一个小球比其它49个小球重5克，现给你一天平(无具体刻度)，要求将该小于找出来，我们应该怎么办？提出一个问题思考解决这个问题的方法二分查找的步骤有序表：以递增(或递减)顺序排列的表。基本思想：给定值k与中间位置的记录的关键字比较，若相等

4、则查找成功；若给定值大于中间位置记录的关键字值，则在表的后半部分继续二分查找；否则在表的前半部分进行二分查找，直至查找成功或不成功。(1)、二分查找的步骤：(1)计算中间位置mid=(low+high)/2取整。(2)k与R[mid]比较return0;//退出循环，说明查找失败1826324552668091LA二分査找的示例若k=RLmidJ则查找成功；若kR[mid],则low=mid+l,转(3)。(3)若1owWhigh,则重复(1)否则：查找不成功，结束。(2).1)、第1步二分查找的示

5、例：用二分査找法在顺序表中査找关键字为80的纪录!1826324552668091lowmid解释查找的过查稈一了着过步曲跟找一步high52668091▲▲midhighlow8091ttlowI4highmid查找成功2)、查找关键字为10的纪录!第1步26324552668091fmidlowhighII*26324552668091fhighlowmid1826324552668091highlowrmidlow二分查找算法总结high此时，high二T,low=0,high

6、nsearch(elcmtyper[],intn,int.key){intlow,high,mid;low=0;high=n-l;whi1e(1ow<=high){mid=(1ow+high)/2;if(key==r[mid].key)returnmid;elseif(key>r[mid],key)low=mid+l;elsehigh二midT;}return-1;}作业布置：给定11个数据元素的有序表(2,3,10,15,25,28,29,30,35,40),采用折半查找，试问：若查找给定值为20的元素，将依次与表屮哪些元素比较？前面一节课我们学习了

7、顺序查找，如果查找的数据较多或频繁进行查找，顺序查找效率会比较低，而使用二分法查找则可以提高查找的效率。而二分法查找的数据是有序的，怎样让一组无序的数据变成有序的，便于我们通过二分法查找呢，下节课我们将一起来探讨这一问题。结布课作总并置后业记住老师布置的作业，课后认真作答