数据结构查找ppt课件.ppt

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

1、数据结构第九章查找内容提要静态查找表9.1动态查找表9.2哈希表9.3基本要求（1）掌握静态查找表的顺序表的查找、有序表的折半查找、静态树表查找（最优查找树）、索引顺序表的查找方法。（2）掌握动态查找表的二叉排序树、B_树和B+树的概念和构造方法。（3）掌握哈希表方法处理思想和过程。重点各种查找方法的处理过程难点各种查找方法的计算问题基本要求、重点、难点查找表(SearchTable)：同一类型的数据元素的集合。静态查找表(StaticSearchTable)：查询某个元素、检索指定元素的属性。动态查找表(D

2、ynamicSearchTable)：查找后插入、删除。关键字(Key)：可以唯一标识一个数据元素或记录的数据项的值。第九章查找查找，检索(Searching)：给出一个key值，在含有若干个结点的序列中找出它。查找成功—当某个元素的key值等于给定值K，返回该元素的位置。查找失败—所有元素的key值均不等于给定值K，返回表示失败的标志。第九章查找平均查找长度AverageSearchLength：nnASL=pici可简化为：ASL=1/ncii=1i=1n为结点个数，pi是查找第i个结点的概率，且pi

3、=1/n，，即各结点的查找概率相等。ci是找到第i个结点时与key值进行的比较次数。第九章查找npi=1i=1典型的关键字类型说明和定义类型说明typedeffloatKeyType;//实型typedefintKeyType;//整型typedefcharKeyType;//字符型类型定义typedefstruct{KeyTypekey;//关键字域……//其它域}SElemType;9.1静态表查找静态查找表的抽象数据类型ADTStaticsearchTable{数据对象D：具有同一特性和类型的元素的集

4、合、可唯一标识数据元素的关键字。数据关系R：数据集合基本操作P：create(&ST,n)//构造查找表destroy(&ST)//销毁查找表search(ST,ch)//查找表中指定元素Traverse(ST,visit())//遍历表}ADTStaticsearchTable9.1.1顺序表的查找顺序表(SequentialList)：线性表的顺序存储结构用数组A[MaxSize]表示元素类型为ElemType，关键字key域的类型为KeyType9.1.1顺序表查找顺序查找，线性查找Sequential

5、Search：一种最基本和最简单的查找方法。从表中的第一个元素开始，顺序扫描。将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。对于表中记录的关键字是无序的表，只能采用这种方法。静态查找表的顺序存储结构typedefstruct{ElemTypeelem;intlength;}SSTable;顺序查找intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;i

6、--)returni;}顺序查找intSeqsch1(ElemTypeA[],intn,KeyTypeK){A[n].key=K;∥设置岗哨for(inti=0;;i++)if(A[i].key==K)break;if(i

7、多查找n次，不成功时的查找次数为n+1。此时的查找概率为Pi=1/(2n)nASLss=1/(2n)∑(n-i+1)+1/2(n+1)i=1=3/4(n+1)9.1.2有序表的查找有序表：关键字有序，即表中的各元素按关键字的值有序(升序或降序)存放。二分查找，折半查找(BinarySearch)：在有序表中进行，先确定表的中点位置，再通过比较确定下一步在哪一个半区查找。假设指针low和high分别指示待查元素所在区间的下界和上界，指针mid指示区间的中间位置，mid=(low+high)/2(1)若key

8、=r[mid].key，成功，否则：(2)若kr[mid].key,则low=mid+1，重复(1)；直到查找成功查找不成功时:low>high。基本思想查找2112345678910110513192137566475808892lowhighmidhighmidlowmid例如：已知11个数据元素的有序表：{05,13,19