数据结构（c语言描述） 教学课件 作者 库波 第8章 查找.ppt

数据结构(C#)主编: 、查找的相关概念查找是计算机科学中研究的重要研究课题之一,在计算机应用系统中,在查找方面所花费的时间占系统运行总时间的25%,所以查找算法的合理应用,对系统的运行效率影响非常大。所谓查找(Search),就是在某一个数据表中,查找给定的数据是否能在数据表中找到。(Key)。查找得到的记录(Record),每个数据项称为字段(Segment)或域(Field)。被查找的数据表称为查找表(SearchTable)。我们对查找表如果只进行查找操作,那么此类查找表称为静态查找表(StaticSearchTable)。我们如果对查找表进行插入和删除操作,那么此类查找表称为动态查找表(DynamicSearchTable)。在进行查找时,如果顺利找到某条记录,说明查找时成功的,否则查找失败。顺序查找(SequnceSearch)又称线性查找(LinearSearch),在查找表中,逐个查询各条记录,直到找到与关键字相符的记录为止,查询成功;如果整个查找表都查询完了,还没有找到与关键字相符的记录,查询失败。顺序查找概念例:假设有一组数据{3,5,8,23,57,2},顺序的存放在数组Arr[i]中。现给定一个关键字57,查询数组中是否能找到57。顺序查找算法顺序查找的基本思路是:假设有n个记录,存放在数组Arr中,其中,第i个记录的值为Arr[i],将给定的关键字x与数组中的记录逐个比较,如果找到要查询记录,则查找成功,并标出记录在表中的位置;否则,查找失败,给出失败提示。顺序查找算法的实现见教材。折半查找折半查找(BinarySearch)又称为二分查找,跟顺序查找有所区别,顺序查找是从第一个记录开始逐个查找,并比较是否找到关键字,而折半查找是要先确定待查找记录的范围,然后逐步缩小查找范围,直到找到记录或找不到记录为止。折半查找思路:折半查找的基本思路是,先将按照从小到大的顺序排序的有序表,用数组Arr来保存,用n来记录数组元素的个数,用Arr[0]来存放查找的关键字x,用low记录有序表中的第一个元素的位置,用high记录有序表中的最后一个元素的位置;再取中间位置的序号m=(n+1)/2,相应记录的值为Arr[m],将给定的关键字x与Arr[m]比较;比较后会得到三种结果:(1)x<Arr[m],由于有序表中的元素是从小到大排序的,如果x存在的话,就在有序表的左边。这样,查找的范围就缩小一半了,再继续对左半部分查找;(2)x==Arr[m],查找成功;(3)x>Arr[m],由于有序表中的元素是从小到大排序的,如果x存在的话,就在有序表的右边。这样,查找的范围就缩小一半了,再继续对右半部分查找。重复上述过程,查找区间不断折半,当最后只剩下一个记录,而此记录不是要找的记录,查找失败。由于查找范围不断缩小,查找速度明显快于顺序查找。例:假设有一组有序的数据{4,6,9,24,25,32,75,95},顺序的存放在数组Arr[i]中。现给定一个关键字6,使用折半查找方法查询数组中是否能找到6。