数据结构与算法_第九章ppt课件.ppt

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

1、第9章查找查找的基本概念静态查找表动态查找表哈希表主要知识点查找的基本概念查找表：同一类型数据元素构成的集合。(集合则无相同元素)查找:查询关键字是否在(数据元素集合）表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找，不改变数据元素集合内的数据元素动态查找:既查找，又改变（增减）集合内的数据元素静态查找表:静态查找时构造的查找表动态查找表:动态查找时构造的查找表平均查找长度:查找过程所需进

2、行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。9.1静态查找表静态查找表主要有三种结构：顺序表有序顺序表索引顺序表静态查找表的顺序存储结构：typedefstruct{ElemType*elem;//数据元素存储空间基址，0号单元留空intlength/*表长度*/}SSTable;typedefintKeyType;typedefchar*InfoType;定义要查找数据元素的结构体为：typedefstruct{KeyTypekey;/*关键字域*/InfoTypeoth

3、erinfo;/*其他域*/}ElemType;9.1.1顺序表顺序查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回0。查找函数设计如下：intSearch_Seq(SSTableST,KeyTypekey){//算法9.1//在顺序表ST中顺序查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。inti=0;ST.elem[0].key=key;//"哨兵"for(i=ST.lengt

4、h;ST.elem[i].key!=key;--i);//从后往前找returni;//找不到时，i为0}//Search_Seq利用监视哨的算法。思考：监视哨作用？算法分析(顺序表)查找成功时的平均查找长度ASL成功为：ASL=PiCi=1/n*(n-i+1)=(n+1)/2(约表长的一半)查找失败时的平均查找长度ASL失败显然为n+19.1.2有序表的查找有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。一、有序表的顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同二、二分查找（又称折半查找）算法的基本思想：先给数据排序（一般按升序排好），形成有序表

5、，然后再将key与正中元素相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。查找215131921375664758088921234567891011MidHighLow5131921375664758088921234567891011MidHighLow5131921375664758088921234567891011MidHighLow(a)查找成功示例算法示例如图(a)，(b)所示。查找71-5131723384656657881921234567891011MidHi

6、ghLow-5131723384656657881921234567891011MidHighLow-5131723384656657881921234567891011MidHighLow-5131723384656657881921234567891011MidHighLow(b)查找不成功示例二分查找算法如下：intSearch_Bin(SSTableST,KeyTypekey){//算法9.2//在有序表ST中折半查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。intlow,high,mid;low=1;high=ST.leng

7、th;//置区间初值while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search_Bin算法分析查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示：◆根结点就是第一次进行比较的