南京邮电大学数据结构A第6章

数据结构A·第6章第6章集合与搜索内容提要1、集合的基本概念2、定义动态集ADT3、集合的表示形式4、顺序搜索5、二分搜索6.1基本概念(a)集合结构(b)线性结构(c)树形结构(d)图状结构图1-2四种基本的结构关系课堂提要第6章集合与搜索6.1基本概念6.2顺序搜索6.3二分搜索集合结构（简称集合）作为一种数据结构，我们将它视为同类型数据元素的汇集。集合的数据元素之间除了“同属于一个集合”的联系之外没有其它关系。一般地，我们假定所讨论的集合不包含相同元素。6.1基本概念6.1.1集合与搜索1.集合（1）基本概念集合：在数学上，集合是不同对象的无序汇集。例如：集合{1,2,3}与{3,2,1}相同。元素：集合的对象。在集合中，每个元素仅出现一次。多重集：元素的无序汇集，其中每个元素可出现一次或多次。无序集：通常用{}表示。例如：多重集{1,1,2,3}与{3,2,1,1}相同，但与集合{1,2.3}不同。有序集：元素的汇集，其中每个元素可以出现一次或多次，并且出现次序是重要的。通常用()表示有序集。例如：(1,2,3)与(3,2,1)不同。6.1基本概念6.1.1集合与搜索1.集合（2）集合的运算数学意义上，集合运算主要有：求集合的并求集合的差求集合的交判断两集合是否相等6.1基本概念6.1.1集合与搜索2.动态集（1）动态集：在数据结构意义上，集合通常是动态的，在集合中可以插入和删除元素，因而称为动态集。（2）集合元素定义templateclassK,classDStructE{operatorK()const{returnkey;}//使元素间的比较视为关键字间的比较Kkey;Ddata;};其中，K称为关键字类型，应为可比较大小的类型。key为关键字：用来标识一个数据元素的某个数据项。6.1基本概念6.1.1集合与搜索3.搜索运算当信息量较少，整个集合元素都存放在内存中，称为表。否则，称为文件。搜索运算是表和文件上的最典型运算。搜索：根据给定的某个值，在表中确定一个关键字值等于给定值的数据元素。6.1基本概念6.1.1集合与搜索4.搜索算法分类按元素是否在内存，分为：内搜索：对表的搜索外搜索：对文件的搜索按关键字的比较情况，分为：基于关键字比较的搜索，此类搜索将在第7章介绍基于计算地址的搜索，此类搜索将在第8章介绍6.1基本概念6.1.2动态集ADTADT6.1动态集抽象数据类型ADTDynamicSet{数据:同类元素的有限汇集，其最大允许长度为MaxSetSize。元素由关键字标识，集合的元素各不相同。运算：Create()：创建一个空集合。Destroy()：撤消一个集合。IsEmpty()：若集合空，则返回true，否则返回false。IsFull()：若集合满，则返回true，否则返回false。Search(x)：在集合中搜索与x的关键字值相同的元素。如果存在该元素，则将其值赋给x，并且函数返回Success；否则返回NotPresent。Insert(x):在集合中搜索与x的关键字相同的元素。若集合中存在该元素，则将其值赋给x，函数返回Duplicate。否则，若集合已满，则函数返回Overflow；若集合未满，则在表中插入值为x的元素，函数返回Success。Remove(x):在集合中搜索与x的关键字值相同的元素。如果存在该元素，则将其值赋给x，并从集合中删除之，函数返回Success；否则返回NotPresent。}6.1基本概念6.1.2动态集ADT程序6.1动态集的C++模板抽象类templateclassTclassDynamicSet{public:virtualResultCodeSearch(T＆x)const=0;virtualResultCodeInsert(T＆x)=0;virtualResultCodeRemove(T＆x)=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;};其中，函数返回类型ResultCode为枚举类型：EnumResultCode{Success,NotPresent,Duplicate,Overflow,Underflow}6.1基本概念6.1.3集合的表示组织集合的方法很多，组织的方法不同，实现搜索等运算的方法也不同，它直接影响运算的效率。集合可以用线性表、搜索树、跳表和散列表表示。6.1基本概念6.1.3集合的表示程序6.2顺序表表示的集合类templateclassTclassListSet:publicDynamicSetT{public:ListSet(intmSize);~ListSet(){delete[]l;}boolIsEmpty()const{returnn==0};boolIsFull()const{returnn==maxSize};ResultCodeSearch(T＆x)const;ResultCodeInsert(T＆x);ResultCodeRemove(T＆x);private:T*l;//指针l指向一个一维数组intmaxSize;intn;……};6.2顺序搜索集合可以用线性表表示。如果线性表中元素已按关键字值的大小次序排列，则称为有序表。否则为无序表。本节将分别讨论无序表和有序表的顺序搜索算法。课堂提要第6章集合与搜索6.1基本概念6.2顺序搜索6.3二分搜索6.2顺序搜索6.2.1无序表的顺序搜索（41，25，28，33，36，15）搜索成功！33（41，25，28，33，36，15）搜索失败！35从头开始检查无序表，将指定元素的关键字x与表中元素的关键字比较，若相等，搜索成功；若搜索完整个表，不存在关键字等于x的元素，则搜索失败。例如，在下表中分别搜索33和35。6.2顺序搜索6.2.1无序表的顺序搜索程序6.3顺序搜索无序表templateclassTResultCodeListSetT::Search(T&x)const{for(inti=0;in;i++)if(l[i]==x){x=l[i];returnSuccess;//搜索成功}returnNotPresent;//搜索失败}6.2顺序搜索6.2.2有序表的顺序搜索（21，25，28，33，36，45）搜索成功！33（21，25，28，33，36，45）搜索失败！35从头开始检查有序表，将指定元素的关键字x与表中元素的关键字比较，若相等，搜索成功；若搜索到某个元素关键字大于x时，搜索失败。例如，在下表中分别搜索33和35。6.2顺序搜索6.2.2有序表的顺序搜索程序6.4顺序搜索有序表constintInfinity=1000;templateclassTResultCodeListSetT::Search(T&x)const{l[n]=Infinity;for(inti=0;l[i]x;i++);//当list[i]的关键字值大于等于//x的关键字值时，退出循环if(l[i]==x){returnSuccess;//搜索成功}returnNotPresent;//搜索失败}6.2顺序搜索6.2.3平均搜索长度分析一个搜索算法的时间复杂度通常分成功搜索以及搜索失败两种情况加以讨论。为了确定一个指定关键字值的记录在表中的位置所需的关键字值之间的比较次数的期望值称为搜索算法的平均搜索长度(averagesearchlengthASL)。6.2顺序搜索6.2.3平均搜索长度1.无序表顺序搜索（1）成功搜索的平均搜索长度计算算法的平均搜索时间，需要给定表中元素ai被搜索的概率pi，假定每个元素的搜索概率是相等的，即pi=1/n，则程序6.3中，搜索成功时的平均搜索长度为（2）搜索失败的平均搜索长度该函数在搜索失败的情况下，总要进行n次关键字值之间的比较。niniSnininASL110211)1(1ASLF=n6.2顺序搜索6.2.3平均搜索长度2.有序表顺序搜索（1）成功搜索的平均搜索长度程序6.4的搜索有序表函数中，搜索成功时的平均搜索长度大致与搜索无序表相同。（2）搜索失败的时间复杂度在搜索失败的情况下，程序6.4的平均搜索长度大约比程序6.3快一倍。niniSnininASL110211)1(1101111(1)12112nnFiinASLiinn6.3二分搜索本节将介绍线性表上的另一种搜索算法：二分搜索。课堂提要第6章集合与搜索6.1基本概念6.2顺序搜索6.3二分搜索6.3二分搜索6.3.1二分搜索算法二分搜索的基本思想是：设有序表（a0,a1,a2,…,an-1），以元素am为划分点，将表分成(a0,a1,a2,…,am-1)和(am+1,…,an-1)两个表。将am的关键字值与x作比较。比较结果有三种可能性：（1)xam:若x在表中，则必在子表（a0,a1,…,am-1）中，此时在该子表内进行二分搜索；（2)x==am:搜索成功；（3)xam:若x在表中，则必在子表（am+1,am+2,…,an-1）中，此时在该子表内进行二分搜索。6.3二分搜索6.3.2对半搜索由分割点的不同，可以得到不同的二分搜索方法。如：对半搜索、一致对半搜索、斐波那契搜索和插值搜索等。对半搜索是二分搜索中的一种，分割点为表的中点元素。若当前搜索的子表为（alow,alow+1,…,ahigh）则i=(low+high)/2其中，i、low和high均为元素在表中的序号，low表示表的左端，high表示表的右端。6.3二分搜索6.3.2对半搜索[Low21303641525466728397]high52对半搜索的例子(1)key=6666[Low]high722130364152546672839721303641525466728397][54搜索成功！21303641525466728397][6601234567896.3二分搜索6.3.2对半搜索[Low21303641525466728397]high52对半搜索的例子(2)key=3535[Low]high302130364152546672839721303641525466728397][36搜索失败！21303641525466728397][01234567896.3二分搜索6.3.2对半搜索程序6.5对半搜索的递归算法templateclassTResultCodeListSetT::Search(T&x)const{inti=BSearch(x,0,n-1);if(i==-1)returnNotPresent;x=l[i];returnSuccess;}templateclassTintListSetT::BSearch(T&x,intlow,inthigh)const{if(low=high){intm=(low+high)/2;//对半分割if(xl[m])returnBSearch(x,low,m-1);elseif(xl[m])returnBSearch(x,m+1,high);elsereturnm;//搜索成功}return-1;//搜索失败}6.3二分搜索6.3.2对半搜索程序6.6对半搜索的迭代算法templateclassTResultCodeListSetT::Search(T&x)const{intm,low=0,high=n-1;while(low=high){m=(low+high)/2;if(xl[m])high=m-1;elseif(xl[m])low=m+1;else{x=l[m];returnSuccess;//搜索成功}}returnNotPresent;//搜索失败}6.3二分搜索6.3.2对半搜索对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过log2n＋1。平均时间复杂度为O(log2n)对于不成功