数据结构案例教程课件：查找.pptx

查找

人们在日常生活中经常需要查找某个人或某个单位的电话号码，要求实现一个简单的通讯录查询系统，根据用户输入的信息（例如姓名）进行快速查询。计算机的出现使信息查询更加快捷、方便、准确。导学问题：

8.1知识学习——查找的基本概念查找的术语查找表。由具有同一类型的数据元素（或记录）组成的集合。关键字。是记录中某个项或组合项的值，用它可以标识一个记录。能唯一确定一个记录的关键字，称为主关键字；而不能唯一确定一个记录的关键字，称为次关键字。查找。是指按给定的某个值k，在查找表中查找关键字为给定值k的记录。

8.1知识学习——查找的基本概念查找算法的性能查找算法时间性能通过关键码的比较次数来度量。关键码的比较次数与哪些因素有关呢？⑴算法；⑵问题规模；⑶待查关键码在查找集合中的位置；⑷查找频率。查找频率与算法无关，取决于具体应用。

8.1知识学习——查找的基本概念查找算法的性能平均查找长度：查找算法进行的关键码的比较次数的数学期望值。计算公式为：其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。ASL?==niiicp1

8.1知识学习——查找的基本概念查找技术静态查找：不涉及插入和删除操作的查找。静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找：涉及插入和删除操作的查找。动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。

8.1知识学习8.1.2顺序表查找1）顺序查找基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。

intSeqSearch(intr[],intn,intk){ inti=0; while(inr[i]!=k)i++; if(in)returni; elsereturn-1;}

基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。101524612354098550123456789i例：查找k＝35iii哨兵35查找方向改进的顺序查找

intSeqSearch2(intr[],intn,intk){ inti=0; r[n]=k; while(r[i]!=k) i++; if(in)returni; elsereturn-1;}ASL==?=niicp1?+-=niiinp1)1(i=(n+1)/2=O(n)改进的顺序查找

顺序查找的缺点：平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。顺序查找的优点：算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。

8.1.2顺序表查找2）折半查找使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

例：查找值为23的过程low=0high=13mid=6high=5mid=23223192301234567891011125131921232932353742464956low=0low=3high=5mid=423=23

例：查找值为23的过程low=0high=13mid=6high=5mid=23222192201234567891011125131921232932353742464956low=0low=3high=5mid=4mid=32322low=3high=32122low=4high=3Lowhigh

intBiSearch(intr[