数据结构第7章 查找ppt课件.ppt

《数据结构第7章 查找ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找7.1基本概念7.2静态查找7.3动态查找表7.4哈希法查找7.1基本概念列表：由同一类型的数据元素(或记录)构成的集合，可利用任意数据结构实现。关键字：数据元素某个数据项的值，用它可以标识列表中的一个或一组数据元素。主关键字：唯一标识列表中的一个数据元素，否则为次关键字。当数据元素仅有一个数据项时,数据元素值就是关键字。查找：在一个给定的数据结构中，根据给定的条件查找满足条件的数据元素。不同的数据结构采用不同的查找方法，查找的效率直接影响数据处理的效率。查找的结果：查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。静态查找(staticsearc

2、h)在查找过程中，查找表本身的结构不发生变化，只确定是否存在数据元素的关键字值与给定的关键值相等或找出此数据元素的属性。动态查找(dynamicsearch)在查找过程中，查找表本身的结构将发生变化，包括插入元素(查找不成功时，在查找表中插入关键字为给定值的记录)或删除元素(查找成功时，将查找表中关键字为给定值的记录删除。（查找算法在查找成功时）平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值。对于长度为n的列表，查找成功时的平均查找长度为：ASL=P1C1+P2C2+…+PnCn其中Pi为查找列表中第i个数据元素的概率，Ci为找到列

3、表中第i个数据元素时，已经进行过的关键字比较次数。7.2静态查找7.2.1顺序查找从表最后一个记录开始，逐个向前进行记录关键字和给定值的比较，相等，查找成功；不等，比较下一个记录；思想:直至第一个记录，若均不等，则查找不成功。存储结构可为顺序结构，也可为链式结构。顺序结构的数据类型定义：#defineLIST_SIZE20typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;typedefstruct{RecordTyper[LIST_SIZE+1];/*r[0]为工作单元*/intlength;}Recor

4、dList;【不设置监视哨的顺序查找法】intSeqSearch(RecordListl，KeyTypek)/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)returni;elsereturn0;}循环条件i>=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。01234567（a）初态40803060102025(b)K=80(returni=4)804080306010202501234567(c)K=90(returni=0)012345679

5、040803060102025顺序查找的算法：【设置监视哨的顺序查找法】intSearch_seq(RecordListl,KeyTypek){i=l.length;l.r(0).key=k;while(l.r(i).key!=k)i--;/*从表尾往前查*/returni;}监视哨使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：ASL==

6、)1(21)1(1111+=+-=åå==ninnCnniniiå=niiiCP12.7.2折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。设查找表中记录的关键字{4，8，12，15，21，32，38，41，55，67，78，90}分三种情况：1）若中间项的值等于x，则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。用折半查找法查找4、70的具体过程，其中mid=(low+hi

7、gh)/2，当high