,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,7,章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL,中的静态表,1第7章 集合与静态查找表 集合的基本概念,2,集合的基本概念,集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。,在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值,集合的主要运算：,查找某一元素是否存在,将集合中的元素按照它的唯一标识排序,2集合的基本概念集合中的数据元素除了属于同一集合之外，没有任,3,集合的存储,任何容器都能存储集合,常用的表示形式是借鉴于线性表或树,唯一一个仅适合于存储和处理集合的数据结构是散列表,3集合的存储任何容器都能存储集合,4,第,7,章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL,中的静态表,4第7章 集合与静态查找表 集合的基本概念,5,查找的基本概念,用于查找的集合称之为查找表,查找表的分类：,静态查找表,动态查找表。,内部查找,外部查找,5查找的基本概念用于查找的集合称之为查找表,6,静态查找表的存储,静态查找表可以用顺序表存储。如,C+,的标准模板库中的类模板,vector,，或第二章中定义的,seqList,查找函数应该是一个函数模板。模板参数是数据元素的类型。,6静态查找表的存储静态查找表可以用顺序表存储。如C+的标,7,第,7,章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL,中的静态表,7第7章 集合与静态查找表 集合的基本概念,8,无序表的查找,无序表：数组中的元素是无序的,无序表的查找：毫无选择只能做线性的顺序查找,template,int seqSearch(vector&data,const Type&x),data0=x;,for(int i=data.size()+1;x!=datai;-i);,return i;,8无序表的查找无序表：数组中的元素是无序的template,9,第,7,章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL,中的静态表,9第7章 集合与静态查找表 集合的基本概念,10,有序表的查找,顺序查找,二分查找,插值查找,分块查找,10有序表的查找顺序查找,11,顺序查找,与无序表的顺序查找类似，只是当被查元素在表中不存在时，不需要查到表尾,template,int seqSearch(vector&data,const Type&x),data0=x;,for(int i=data.size()+1;x datai;-i);,if(i=0|x!=datai)return 0;else,return i;,11顺序查找与无序表的顺序查找类似，只是当被查元素在表中不存,12,有序表的查找,顺序查找,二分查找,插值查找,分块查找,12有序表的查找顺序查找,13,二分查找,每次检查待查数据中排在最中间的那个元素,如中间元素等于要查找的元素，则查找完成,否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。,13二分查找每次检查待查数据中排在最中间的那个元素,14,查找,x=8,0,1,2,mid=4,但,key=9 10,向左,key,4,8,9,10,11,13,19,3,4,5,6,7,high=7,low=1,0,1,2,mid=2,找到,key,4,8,9,10,11,13,19,3,4,5,6,7,high=7,low=1,14查找 x=8012mid=4 但 key=9 10,15,template,int binarySearch(const vector&data,const Type&x),int low=1,high=data.size()+1,mid;,while(low=high)/,查找区间存在,mid=(low+high)/2;/,计算中间位置,if(x=datamid)return mid;,if(x datamid)high=mid-1;,else low=mid+1;,return 0;,15template,16,有序表的查找,顺序查找,二分查找,插值查找,分块查找,16有序表的查找顺序查找,17,插值查找,适用于知道数据的大致分布情况,查找位置的估计,缺点：计算量大,17插值查找适用于知道数据的大致分布情况,18,插值查找适用情况,访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。,这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的,18插值查找适用情况访问一个数据元素必须比一个典型的指令费时,19,有序表的查找,顺序查找,二分查找,插值查找,分块查找,19有序表的查找顺序查找,20,分块查找,分块查找也称为索引顺序块的查找。,它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。,20分块查找分块查找也称为索引顺序块的查找。,21,块内最大关键字,17,44,60,块起始地址,0,6,14,3,6,9,10,14,17,19,23,34,37,39,40,42,44,46,48,51,58,60,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,查找由两个阶段组成：查找索引和查找块,21块内最大关键字174460块起始地址06143691,22,第,7,章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL,中的静态表,22第7章 集合与静态查找表 集合的基本概念,23,STL,中的静态表,对应于顺序查找和二分查找，,C+,的标准模板库中提供两个模板函数：,find,和,binary_search,。这两个函数模板都位于标准库,algorithm,中,find,函数顺序查找一个序列,find,有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。,函数有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。,find,函数的返回值是一个迭代器对象，指出了被查找的元素在容器中的位置。,23STL中的静态表对应于顺序查找和二分查找，C+的标准模,24,binary_search,binary_search,函数用二分查找的方式查找一个有序序列。,它也有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。,函数也有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。,函数的返回值是,bool,类型的，指出了被查找的元素在容器中是否存在。如果存在，返回,true,，否则，返回,false,。,24binary_searchbinary_search函数,25,应用实例,#include,#include,#include,using namespace std;,int main(),int a=2,4,7,8,10,12,13,15,16,19,20;,vector v;,vector:iterator itr;,for(int i=0;i11;+i)v.push_back(ai);,if(binary_search(v.begin(),v.end(),13),cout 13,存在,n;,else cout 13,不存在,n;,itr=find(v.begin(),v.end(),13);,cout *itr endl;,return 0;,25应用实例#include,26,总结,本章介绍了集合关系的基本概念，以及集合类型的数据结构中的基本操作。,针对静态的集合，介绍了查找操作的实现。包括顺序查找、二分查找、插值查找和分块查找。,最后还介绍了,STL,中的查找函数：,find,和,binary_search,。,find,实现了顺序查找，,binary_search,实现了二分查找。,26总结本章介绍了集合关系的基本概念，以及集合类型的数据结构,