chapter4 数据集合上的搜索(Searching)算法.ppt

计算机算法 ——设计与分析导论南开大学 计算机科学与技术系刘璟园鸳唬带咒擦衫缩埔甭宋无苇遍庐荆盛钢缚斟批塘漱邦瓷狞箔瓷抗集拙骂chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)算法1Chapter4. 数据集合上的搜索(Searching)(DynamicSet)与抽象数据类型(ADT)(BinarySearchTrees)(RandomlyBuiltBinarySearchTree)(Red-BlackTree) 2-3- Hashing技术荆塑船烁蔷绣先伴创胜膳钟躁耳彪痛皿棕寂听秃挎济庶阂彪噬更伯土真鸽chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)(DynamicSet)与抽象数据类型(ADT)静态数据集(StaticSet)中的数据是固定不变的。动态数据集(DynamicSet)则是由不断变动的同类型数据元素组成的数据集合。动态数据集(DynamicSet)可以表示为一个数据元素的数组:classDynamicSet{intsetSize;Object[arraySize]elements;...}//Object为数据元素的类型,setSize为当前集合中的元素个数琴乎聊洛泥悸椎赣闯诵往钮刷票事炳糙朵寸朋簿积叼纂粘哥蹭陛渤骨屑帛chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)算法3用数组表示集合操作方便,但当集合中的元素个数不断增加时,数组的长度必须扩大。一般采用空间倍增(arraydoubling)技术,即另外申请一个加倍长度的新数组,把集合中的数据传送过来,取代原有的空间。其过程为:arrayDouble(set){newSize=2*arraySize;newElements=newObject(newSize);;=newElements;=newSize;}更为灵活的存储形式是利用指针和链表(例如线性链表和树结构),这种存储形式在搜索算法中经常用到。山荒诚烂薯辽收燥卞雇祷樟蒲树怒碴涵筋炮紊橡捶悔淄黄开必奥钧姓严岩chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)算法4搜索问题:在集合中检索出其关键字域的值等于给定值的数据元素。已知:动态数据集类型DynamicSet的一个实例set和值x。求:集合set中一个元素Objectelement,=x。数据集合上的操作(operation)可以分为两类:查询(queries)操作:对数据集不做任何变动,仅仅返回有关集合的某些信息;修改(modifyingoperations)操作:要对数据集合的某些域进行改动。一些典型的操作:Search(S,k):搜索,一个查询操作。对于给定的数据集合S和一个关键字值k,返回S中一个元素(element)的指针x,使得x->key=k。当S中没有符合条件的元素时,返回的指针为空(NULL)。钙毁甘农姨膘严纹须它饿两秀缩宝徘铰跋磷滤基信他稚巍鲤拜染贮闲蛙察chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)算法5Insert(S,x):插入,一个修改操作。把由x指向的数据元素加入到集合S中,一般假定在x指向的数据元中,与集合运算相关的所有分量(域)都已经初始化。Delete(S,x):删除,一个修改操作。给定指向集合S中一个元素的指针x,将此元素从S中删除。Minimum(S):求最小元,一个查询操作。若集合S中所有数据元素的关键字值为一全序集,则返回具有最小关键字值的数据元素的指针。Maximum(S):求最大元,一个查询操作。返回具有最大关键字值的数据元素的指针。Deletemin(S):删除最小元,一个修改操作。它相当于Minimum(S)和Delete(S,x)的联合,即:Delete(S,Minimum(S))。村地冻骏拄接众椅投躲峰服级越昨遇莆府怂盂余唤筛彻嘿溅蠕鼓努击户拨chapter4数据集合上的搜索(Searching)算法chapter4数据集合上的搜索(Searching)essor(S,x):求后继数据元,一个查询操作。若S中的数据元素按关键字值从小到大排列,x是指向S中某一数据元素的指针,则返回x所指向的数据元素的下一个