数据结构单元7查找课件.pptVIP

数据结构国家教学资源库建设项目

数据结构教学目标【知识目标】?了解查找的基本概念?掌握顺序查找的基本思想、算法实现和查找效率分析?掌握二分查找的基本思想、算法实现和查找效率分析?掌握分块查找的基本思想、算法实现和查找效率分析?掌握二叉查找树的插入、删除、建树和查找算法及时间性能?掌握哈希查找方法、哈希函数的构造和解决冲突的方法【能力目标】?具有选择恰当的查询算法解决实际问题的能力单元7查找

数据结构引例描述——高校最低录取分数线查询该系统用于学生、学生家长和其他人员查询各高校的最低录取分数线，为他们的了解高校录取情况、做出正确的选择和决策提供有必要的信息。该系统有以下六项功能：（1）按考生分数查询高校信息；（2）按给定分数查询一定范围内的高校信息，包括：查询录取分数线比给定分数高（包括相等）的高校信息和录取分数线比给定分数低（包括相等）的高校信息；（3）按给定的分数范围查询高校信息；（4）能够添加高校信息；（5）为用户提供系统帮助，以便更好的使用系统；（6）安全退出本系统。演示执行单元7查找

数据结构知识储备7.1查找的基本概念一、基本概念1．查找定义给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。2．动态查找表和静态查找表若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。否则称之为静态查找表。3．内查找和外查找若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。单元7查找

数据结构4．平均查找长度（AverageSearchLength）ASL查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义：即ASL等于每个结点的查找概率pi与比较次数ci的乘积的和。其中：（1）n是结点的个数；（2）p是查找第i个结点的概率。若不特别声明，认为每个i结点的查找概率相等，即p=p=…=p=1/n；l2n（3）c是找到第i个结点所需进行的比较次数。i单元7查找

数据结构7.2静态查找一、顺序查找（sequentialsearch）#defineN20typedefintKeyType;//关键字字段类型定义顺序查找又称线性查找，是最基本的查找方法之一。顺typedefcharOtherdataType;//非关键字字段类型定义序查找既适用于顺序表，也适用于链表。typedefstruct1．基本思想{KeyTypekey;从表的一端开始，顺序扫描线性表，依次按给定值kx与OtherdataTypedata;关键字（Key）进行比较，若相等，则查找成功，并给出数}NodeType;据元素在表中的位置；若整个表查找完毕，仍未找到与kx相typedefNodeTypeSeqList[N+1];//0号单元用作监视哨同的关键字，则查找失败，给出失败信息。2．基于顺序结构的顺序查找算法的类型描述单元7查找

数据结构3．具体算法4．算法分析（1）算法中监视哨R[0]的作用intSeqSearch(SeqlistR,KeyTypeK)为了在for循环中省去判定防止下标越界的条件i≥1，从而{//在顺序表R[1...n]中查找关键字为K的结点节省比较的int时i;间。（2）成功时的顺序查找的平均查找长度R[0].key=K;//设置哨兵在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长for(i=n;R[i].key!=K;i--);//从表后往前找度为(n+…+2+1)/n=(n+1)/2，即查找成功时的平均比较次数约returni;//若i为0，表示查找失败，否则R[i]是要找为表长的一半，若K值不在表中，则须进行n+1次比较之后才的结点能确}定查找失败。（3）顺序查找的优缺点优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。单元7查找

数据结构二、二分查找（binarysearch）1．二分查找：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2．二分查找的基本思想设R[low...high]是当前的查找区间。（1）首先确定该区间的中点位置：mid=[(low+high)/2];（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，