《数据结构A》第06章课件.ppt

1、6.1基本概念基本概念6.2顺序搜索顺序搜索6.3二分搜索二分搜索6.1.1集集合合在在数数学学上上，是是不不同同对对象象的的无无序序汇汇集集 ，集集合合的的对对象象称称为为元元素素或或成成员员，每每个个元元素素仅仅出出现现一一 是是元元素素的的无无序序汇汇集，集，其其中，中，每每个个元元素素可可出出现现一一次次或或多多次。次。例例如，如，多多重重集集 1,1,1,1,2,2,3 3 与与 1,1,2,2,3,3,11相相同，同，但但与与 1,1,2,2,33不不同。同。通通常常用用大大括括号号表表示示。一一个个是是元元素素的的汇汇集，集，其其中，中，每每个个元元素素可可以以出出现现一一次次或

2、或多多次，次，并并且且它它们们的的出出现现次次序序是是重重要要的的（如如同同向向量量一一样）样）。通通常常用用圆圆括括号号表表示示有有序序集，集，例例如，如，（2 2，1 1，3 3）。多多重重集集无无序序集集有有序序集集 （简称（简称集合集合）作为一种数据结构，我）作为一种数据结构，我们将它视为同类型数据元素的们将它视为同类型数据元素的。集合的数据。集合的数据元素之间除了元素之间除了“同属于一个集合同属于一个集合”的联系之外没的联系之外没有其它关系。一般地，我们假定所讨论的集合不有其它关系。一般地，我们假定所讨论的集合不包含相同元素。数据结构意义上的集合通常是动包含相同元素。数据结构意义上的

3、集合通常是动态的，在集合中可以插入和删除元素，因而被称态的，在集合中可以插入和删除元素，因而被称为为 。元素类型元素类型templatestructEoperatorK()constreturnkey;Kkey;Ddata;其中，其中，K和和D是用户定义的数据类型，是用户定义的数据类型，K被称为被称为关键字类型关键字类型，key是关键字，我们要求类型是关键字，我们要求类型K是是C/C+语言允许的，可以比较大小的类型。除关键语言允许的，可以比较大小的类型。除关键字外的其它数据项归入字外的其它数据项归入data域部分，域部分，D可以是简单可以是简单类型，也可以是结构类型。类型，也可以是结构类型。关

4、键字关键字是用以标识一个数据元素的某个数据项。是用以标识一个数据元素的某个数据项。若此关键字可以惟一标识一个元素，则称此关键若此关键字可以惟一标识一个元素，则称此关键字字为为主关键字主关键字。集合中，不同数据元素有不同的主。集合中，不同数据元素有不同的主关键字值。关键字值。称可用以识别若干数据元素的关键字为称可用以识别若干数据元素的关键字为次关键字次关键字。当数据元素是初等数据类型时，其关键字值即数据当数据元素是初等数据类型时，其关键字值即数据元素值。元素值。在本章讨论中，若非特殊说明，都假定被搜索的在本章讨论中，若非特殊说明，都假定被搜索的关键字为主关键字。关键字为主关键字。搜索搜索：根据给

5、定的某个值，在表中确定一个关键字值：根据给定的某个值，在表中确定一个关键字值等于给定值的数据元素，若表中存在这样的元素，则等于给定值的数据元素，若表中存在这样的元素，则称称搜索成功搜索成功，搜索结果可以返回整个数据元素，也可，搜索结果可以返回整个数据元素，也可指示该元素在表中的地址；若表中不存在关键字值等指示该元素在表中的地址；若表中不存在关键字值等于给定值的元素，则称于给定值的元素，则称搜索不成功搜索不成功（也称（也称搜索失败搜索失败）。）。搜索算法分类搜索算法分类 搜索算法可以按元素是否全部在内存分为：搜索算法可以按元素是否全部在内存分为：内搜内搜索索 和和外搜索外搜索。我们将对表的搜索称

6、为。我们将对表的搜索称为内搜索内搜索，而对文，而对文件的搜索称为件的搜索称为外搜索外搜索。如果一个搜索算法只是单纯搜索一个元素，称为如果一个搜索算法只是单纯搜索一个元素，称为静态搜索静态搜索，如果在搜索不成功时，需将被搜索的元素，如果在搜索不成功时，需将被搜索的元素插入表中，这样的搜索被称为插入表中，这样的搜索被称为动态搜索动态搜索，这种将搜索，这种将搜索和插入结合起来的算法常称为和插入结合起来的算法常称为符号表算法符号表算法，被编译程，被编译程序用于构造标识符表。序用于构造标识符表。搜索算法还可以根据算法中是否以关键字值间的比搜索算法还可以根据算法中是否以关键字值间的比较为基础，或由关键字值

7、直接计算元素地址，分为较为基础，或由关键字值直接计算元素地址，分为和和，本章和，本章和第第9 9章的搜索属于前者，第章的搜索属于前者，第1010章的散列表搜索属于后者章的散列表搜索属于后者 6.1.2 动态集动态集ADT 同同类类元元素素的的有有限限汇汇集，集，其其最最大大允允许许长长度度为为MaxSetSize。元元素素由由关关键键字字标标识，识，集集合合的的元元素素各各不不相相同。同。Create();创创建建一一个个空空集集合。合。Destroy()：撤撤消消一一个个集集合。合。IsEmpty():若若集集合合为为空，空，则则返返回回true，否否则则返返回回false。IsFull()

8、:若若集集合合满，满，则则返返回回true，否否则则返返回回false。运运算：算：在表中搜索与在表中搜索与x的关键字值相同的元素。的关键字值相同的元素。如果存在该元素，则将其值赋给如果存在该元素，则将其值赋给x，并且函数返回，并且函数返回Success；否则返回；否则返回NotPresent。在表中搜索与在表中搜索与x的关键字值相同的元素。的关键字值相同的元素。若表中存在该元素，则将其值赋给若表中存在该元素，则将其值赋给x，函数返回，函数返回Duplicate。否则，若表已满，则函数返回。否则，若表已满，则函数返回Overflow；若表未满，则在表中插入值为；若表未满，则在表中插入值为x的元

9、素，的元素，函数返回函数返回Success。在表中搜索与在表中搜索与x的关键字值相同的元素。的关键字值相同的元素。如果存在该元素，则将其值赋给如果存在该元素，则将其值赋给x，并从表中删除，并从表中删除之，函数返回之，函数返回Success；否则返回；否则返回NotPresent。Underflow,Overflow,Success,Duplicate,NotPresent,.;virtualResultCodeSearch(T&x)const=0;virtualResultCodeInsert(T&x)=0;virtualResultCodeRemove(T&x)=0;virtualboolI

10、sEmpty()const=0;virtualboolIsFull()const=0;6.1.3集合的表示集合的表示templateclassListSet:publicDynamicSetpublic:ListSet(intmSize);ListSet()deletel;boolIsEmpty()constreturnn=0;boolIsFull()constreturnn=maxSize;ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);private:T*l;/指针指针l指向一个一维数组指向一个一

11、维数组intmaxSize;intn;6.2.1 无序表的顺序搜索无序表的顺序搜索templateResultCodeListSet:Search(T&x)constfor(inti=0;in;i+)if(li=x)x=li;returnSuccess;/搜搜索索成成功功returnNotPresent;/搜搜索索失失败败6.2.2有有序序templateResultCodeListSet:Search(T&x)constfor(inti=0;i+)if(li=x)x=li;returnSuccess;/搜索成功搜索成功returnNotPresent;/搜索失败搜索失败6.2.3 平平 搜搜

12、索索中中所所需需的的关关键键字字值值之之间间的的比比较较次次数数的的期期望望值，值，被被称称为为搜搜索索算算法法的的(a av ve er ra ag ge e s se ea ar rc ch h l le en ng gt th h A AS SL)L)。平平均均搜搜索索长长度度求成功搜索的平均搜索长度，需要给定表求成功搜索的平均搜索长度，需要给定表中元素中元素a ai i被搜索的概率被搜索的概率p pi i。设表长为。设表长为n n，假，假定每个元素的搜索概率是相等的，即定每个元素的搜索概率是相等的，即p pi i=1/n=1/n，则程序则程序6.3 6.3 在搜索成功时的平均搜索长度在

13、搜索成功时的平均搜索长度为：为：21nin1)1i(n1ASLn1i1n0iS 设有序表为（设有序表为（a a0 0,a,a1 1,a,an n1 1），通常可以假），通常可以假定待查元素的值位于定待查元素的值位于a a0 0之前，之前，a a0 0与与a a1 1之间，之间，a a1 1与与a a2 2之间之间,a an-2n-2与与a an n1 1之间以及之间以及 a an n1 1之后之后的共的共n+1n+1个区间内的概率是相等的。程序个区间内的概率是相等的。程序6.4搜索失败的平均搜索长度为：搜索失败的平均搜索长度为：22ni1n11)1i(1n11ASL1n1in0iF 6.3 二

14、分搜索二分搜索 6.3.1 二分搜索算法二分搜索算法 设有一个长度为设有一个长度为n的有序表：的有序表：要求在表中搜索与给定元素要求在表中搜索与给定元素x有相同关键字值的元素有相同关键字值的元素。若若n=0，则显然搜索失败；若，则显然搜索失败；若n0，则可将有序表分解，则可将有序表分解成若干个子表，最简单的做法是分成两个子表。成若干个子表，最简单的做法是分成两个子表。以元素以元素am为划分点，将表分成如下两个子表：为划分点，将表分成如下两个子表：将将am的关键字值与指定元素的关键字值与指定元素x的关键字值作比较，比的关键字值作比较，比较结果有三种可能性：较结果有三种可能性：（续）（续）（1 1

15、）当）当xaxam时，若与时，若与x相同关键字值的元素在相同关键字值的元素在表中，则必定在子表（表中，则必定在子表（am+1,am+2,an1）中，可）中，可以在该子表中继续进行搜索。以在该子表中继续进行搜索。对半搜索的例子对半搜索的例子：“”=”=low,“”=highlow,“”=high(1)key=66key=66，搜索成功，搜索成功21 30 36 41 21 30 36 41 5252 54 66 72 83 97 54 66 72 83 97 21 30 36 41 52 54 66 21 30 36 41 52 54 66 7272 83 97 83 97 21 30 36 4

16、1 52 21 30 36 41 52 5454 66 72 83 97 66 72 83 97 21 30 36 41 52 54 21 30 36 41 52 54 6666 72 83 97 72 83 97(2)key=35key=35，搜索失败，搜索失败21 30 36 41 21 30 36 41 5252 54 66 72 83 97 54 66 72 83 9721 21 3030 36 41 52 54 66 72 83 97 36 41 52 54 66 72 83 97 21 30 21 30 3636 41 52 54 66 72 83 97 41 52 54 66 7

17、2 83 97 21 3036 41 52 54 66 72 83 97 21 3036 41 52 54 66 72 83 97私有函数私有函数BSearch定义如下：定义如下：intListSet:BSearch(T&x,intlow,inthigh)const在范围为在范围为low,high的表中搜索与的表中搜索与x有相同关键有相同关键字值的元素；如果存在该元素，则函数返回该字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回元素在表中的位置，否则函数返回1，表示搜，表示搜索失败。索失败。templateintListSet:BSearch(T&x,intlow,int

18、high)constif(low=high)intm=(low+high)/2;/对半分割对半分割if(xlm)returnBSearch(x,m+1,high);elsereturnm;/搜索成功搜索成功return-1;/搜索失败搜索失败templateResultCodeListSet:Search(T&x)constinti=BSearch(x,0,n-1);if(i=-1)returnNotPresent;x=li;returnSuccess;templateResultCodeListSet:Search(T&x)constintm,low=0,high=n-1;while(low

19、=high)m=(low+high)/2;if(xlm)low=m+1;elsex=lm;returnSuccess;/搜索成功搜索成功returnNotPresent;/搜索失败搜索失败6.3.3（1）指定元素）指定元素x的关键字值与表中元素的关键字值与表中元素的关键的关键字值之间的一次字值之间的一次，表现为二叉判定树中表现为二叉判定树中的一个的一个，用一个圆形结点表示，并用，用一个圆形结点表示，并用标标识。如果识。如果x=lm，则算法在该结点处成功终止。，则算法在该结点处成功终止。（2）二叉判定树的二叉判定树的，代表算法中首先与，代表算法中首先与x比比较的元素较的元素lm，用，用m标识。标

20、识。（3）是当是当xlm时时,算算法接下去与法接下去与x比较的元素下标。比较的元素下标。（4）如果根据算法，在）如果根据算法，在x与与lm比较之后有比较之后有，且，且算法终止，那么，结点算法终止，那么，结点m的左孩子用一个的左孩子用一个表表示，结点标号为示，结点标号为。反之，在。反之，在x与与lm比较之后有比较之后有，且算法终止，那么，结点，且算法终止，那么，结点m的右孩子用一个的右孩子用一个方形结点表示，结点标号为方形结点表示，结点标号为。方形结点称为。方形结点称为。换句话说，如果算法在方形结点换句话说，如果算法在方形结点m处终止，这意味着：处终止，这意味着：（a）当）当0 mn-1时，时，

21、lmxlm+1之间；之间；（b）当）当m=-1时，时，xln-1。（5）从根结点到每个内结点的一条路径代表成功搜索从根结点到每个内结点的一条路径代表成功搜索的一条比较路径。如果搜索成功，则算法在内结点处的一条比较路径。如果搜索成功，则算法在内结点处终止，否则算法在外结点处终止。终止，否则算法在外结点处终止。对半搜索算法在成功搜索的情况下，对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过关键字值之间的比较次数不超过 log2n+1。对于不成功的搜索，算法需要作对于不成功的搜索，算法需要作 log2n 或或 log2n+1次比较。次比较。由定理由定理6.1容易知道，容易知道，（1）对半

22、搜索算法的）对半搜索算法的分别为分别为，（2）为为。对半搜索算法在搜索成功时的对半搜索算法在搜索成功时的为为O(log2n)。对于成功搜索，假定查找表中任何一个元对于成功搜索，假定查找表中任何一个元素的概率是相等的，为素的概率是相等的，为。对于失败搜索，假定待查元素对于失败搜索，假定待查元素x的值落在的值落在区间（区间（lm，lm+1），），0 mn-1，区间，区间xln-1，总共，总共n+1个区间中的个区间中的概率是相等的。概率是相等的。那么，那么，这里，这里，I是二叉判定树的内路径长度，是二叉判定树的内路径长度，E是是外路径长度。从定理外路径长度。从定理71可知，可知，E=I+2n，因此，因此，定理得证。定理得证。