资源描述：
《计算机算法导论_第11章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IntroductiontoAlgorithmsIIIDataStructuresDynamicSetsnDynamicSets:Differentfrommathematicalset,thesetsmanipulatedbyalgorithmscangrow,shrink,orotherwisechangeovertime.nAlgorithmsmayrequireseveraldifferenttypesofoperationstobeperformedonsets.qDictionary:Adynamicsetthato
2、nlysupportstheabilitytoinsertelementsinto,deleteelementsfrom,andtestmembershipinaset.2ElementsofadynamicsetnTypically,eachelementisrepresentedbyanobject.qAnobject=Key+satellitedatanSomedynamicsetspresupposethatthekeysaredrawnfromatotallyorderedset3Operationsondynamic
3、setsnQueries:simplyreturninformationaboutthesetqSEARCH(S,k),returnsapointerxtoanelementinSsuchthatkey[x]=k,orNILifnosuchelementbelongstoS.qMINIMUM(S),returnsapointertotheelementofSwiththesmallestkey.qMAXIMUM(S),returnsapointertotheelementofSwiththelargestkey.qSUCCESS
4、OR(S,x),returnsapointertothenextlargerelementinS,orNILifxisthemaximumelement.qPREDECESSOR(S,x),returnsapointertothenextsmallerelementinS,orNILifxistheminimumelement.nModifyingoperations:changetheset.qINSERT(S,x),augmentsthesetSwiththeelementpointedtobyx.qDELETE(S,x),
5、givenapointerxtoanelementinthesetS,removesxfromS.4OverviewnThetimetakentoexecuteasetoperationisusuallymeasuredintermsofthesizeoftheset.nNextfewlectureswillfocusondatastructuresratherthanstraightalgorithms1.Chapter10presentstheessentialsofworkingwithsimpledatastructur
6、essuchasstacks,queues,linkedlists,androotedtrees.2.Chapter11introduceshashtables,whichsupportthedictionaryoperationsINSERT,DELETE,andSEARCH.3.Chapter12Binarysearchtrees4.Chapter13Red-blacktrees,avariantofbinarysearchtrees5.Chapter14,augmentred-blacktreestosupportoper
7、ationsotherthanthebasicones511HashTableHashTablesnMotivation:symboltablesqAcompilerusesasymboltabletorelatesymbolstoassociateddatanSymbols:variablenames,procedurenames,etc.nAssociateddata:memorylocation,callgraph,etc.qForasymboltable(alsocalledadictionary),wecareabou
8、tsearch,insertion,anddeletionqTypicallydon’tcareaboutsortedorder7Symbol-tableproblemnThestructurewewilluseisahashtableqSupportsallt
