《数据结构(C#语言描述)》第07章查找.ppt

第7章查找《数据结构(C#语言描述)》配套PPT引入《数据结构(C#语言描述)》配套PPT查找是计算机应用中最常用的操作之一,也是许多程序中最耗时间的一部分。因而,查找方法的优劣对系统的运行效率影响极大。本章讨论各种查找算法,并通过对它们的分析来比较各种查找方法的优劣。《数据结构(C#语言描述)》配套PPT查找和查找表1查找是指在数据元素集合中查找满足某种条件的数据元素的过程。例如在学生成绩表中查找某一学生的成绩;在字典中查找某个字等等。用于查找的数据元素集合就称为查找表,查找表由同一类型的数据元素组成。《数据结构(C#语言描述)》配套PPT关键字是数据元素中某个数据项。能惟一标识数据元素的关键字称为主关键字。不能惟一标识数据元素的关键字称为次关键字。关键字、主关键字、《数据结构(C#语言描述)》配套PPT静态查找和动态查找3若在查找的同时对表做修改运算(如插入和删除),则称这类查找为动态查找,否则为静态查找。静态查找在查找过程中查找表本身不发生变化,而动态查找在查找过程中查找表可能会发生变化。《数据结构(C#语言描述)》配套PPT若整个查找过程全部在内存中进行,则称为内查找;若在查找过程中还需要访问外存,则称为外查找。《数据结构(C#语言描述)》配套PPT顺序查找又称线性查找(SequentialSearch),是一种最简单、最基本的静态查找方法。其基本思想是:从表的一端开始,顺序扫描整个线性表,依次将扫描到的结点关键字与给定值K进行比较,若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字值等于K的结点,则查找失败。《数据结构(C#语言描述)》配套PPT顺序查找所用时间跟查找关键字K在表中的位置有关。顺序表查找的时间复杂度为O(n)。顺序查找的优点是算法简单,且对表的结构无任何要求,无论是用顺序表还是用链表存放记录,也无论记录之间是否按关键字有序存放,它同样适用。顺序查找的缺点是查找效率低,因此当在较大规模数据中进行查找时,不宜采用顺序查找。《数据结构(C#语言描述)》配套PPT二分查找又称折半查找(BinarySearch),是一种效率较高的静态查找方法。二分查找要求查找表用顺序存储结构存放,且各数据元素按关键字有序(升序或降序)排列,并且要求查找表使用线性表的顺序存储结构。也就是说,二分查找只适用于对有序顺序表进行查找。《数据结构(C#语言描述)》**********lowhighmid28101321查找关键字为51的数据元素576269low=0,high=9,mid=(0+9)/2=4low=5,high=9,mid=(5+9)/2=7,mid=(5+6)/2=5low=5,high=6low=6,high=6,mid=(6+6)/2=636