资源描述：
《归并排序、桶排序分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ZhangXiSchoolofComputerScience,BUPTCH7SearchOutlineSearchTableSequentialSearchBinarySearchIndexingSearchBinarySearchTreesBinarysearchtreeAVLtreeB-TreeHashTableWhatishashingHashFunctionCollisionResolutionOpenAddressingRehashingSeparateChainingAnalysisofHashingSearchTabl
2、eSearchTable:Asetofthesametypeofdataelements.Key:Thevalueofdataiteminthedataelement.Itisusedtoidentifythedataelements.PrimaryKeyandSecondKey.Attributes:(1)Thereisnofixedrelationshipbetweentheelements.(2)Anyrelationshipcanbedefinedonthesetforoperationconvenience.SearchT
3、ableSearchBasedonthesearchvalueofkey,findouttheelementwhosekeyvalueisthesameassearchvalue.Itreturnsthepositionoftheelementlocatedin.Operationsonsearchtable(1)Searchagivenelementinthesearchtable;(2)Getattributesofagivenelement;(3)Insertanelementintothesearchtable;(4)Del
4、eteanelementfromthesearchtable.Staticsearchtable:OnlydosearchonthesearchtableDynamicsearchtable:Needdosearch,insertionanddeletiononthesearchtableSearchTableBasicconceptsGiven:Distinctkeysk1,k2,…,knandcollectionTofnrecordsoftheform((k1,I1),(k2,I2),…,(kn,In))whereIjisthe
5、informationassociatedwithkeykjfor1<=j<=n.SearchProblem:ForkeyvalueK,locatetherecord(kj,Ij)inTsuchthatkj=K.Searchingisasystematicmethodforlocatingtherecord(s)withkeyvaluekj=K.Successfulvs.UnsuccessfulAsuccessfulsearchisoneinwhicharecordwithkeykj=Kisfound.Anunsuccessfuls
6、earchisoneinwhichnorecordwithkj=Kisfound(andpresumablynosuchrecordexists).Weoftenaskhowmanytimesonekeyiscomparedwithanotherduringasearch.Thisgivesusagoodmeasureofthetotalamountofworkthatthealgorithmwilldo.ApproachestoSearchSequentialandlistmethods(lists,tables,arrays).
7、Treeindexingmethods.Directaccessbykeyvalue(hashing)SearchComparisonCalculationSearchLinearSearchTreeSearchHashSearchOutlineSearchTableSequentialSearchBinarySearchIndexingSearchBinarySearchTreesBinarysearchtreeAVLtreeB-TreeHashTableWhatishashingHashFunctionCollisionReso
8、lutionOpenAddressingRehashingSeparateChainingAnalysisofHashing#defineLIST_SIZE20typedefstruct{KeyTypekey;OtherTypeoth
