《第七章 集合与静态查找表》由会员分享，可在线阅读，更多相关《第七章 集合与静态查找表（36页珍藏版）》请在金锄头文库上搜索。
1、数据结构Data Structure,第七章 集合与静态查找表,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,集合的基本概念,集合中的数据元素没有任何逻辑关系。 在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值集合的主要运算： 查找某一元素是否存在 将集合中的元素按照它的唯一标识排序,Ex. DNS lookup. Given URL, find corresponding IP address.,集合的应用,集合的存储,任何容器都能存储集合 常用的表示形式是借鉴于线性表或树 唯一一个仅适合于存储和处理集合的
2、数据结构是散列表,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,查找的基本概念,用于查找的集合称之为查找表 查找表的分类： 静态查找表 动态查找表 内部查找 外部查找,静态查找表的存储,静态查找表可以用顺序表存储。 如C+的标准模板库中的类模板vector，或第二章中定义的seqList，或直接存储在 C+的原始数组中。 查找函数应该是一个函数模板。模板参数是数据元素的类型。,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,无序表的查找,无序表：数组中的元素是无序的 无序表的查找：
3、毫无选择只能做线性的顺序查找 template int seqSearch(vector &data, const Type &x) data0 = x; for (int i = data.size() + 1; x != datai; -i); return i; ,算法时间复杂度分析,不成功查找：O（N）成功查找：最好：O（1）最坏：O（N）平均： O（N） 若每个元素被找到的可能性相等，平均查找时间：,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 顺序查找 二分查找 插值查找 分块查找STL中的静态表,顺序查找,与无序表的顺序查找类似，只是当被查
4、元素在表中不存在时，不需要查到表尾 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; ,二分查找,每次检查待查数据中排在最中间的那个元素 如中间元素等于要查找的元素，则查找完成 否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。,查找 x=8,template int binarySearch(co
5、nst 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;,算法时间复杂度分析,不成功查找： O(logN)成功查找：最好：O(1)最坏：O(logN)平均：O(logN),插值查找,适用于数据的分布比较
6、均匀的情况 查找位置的估计 缺点：计算量大,插值查找适用情况,访问一个数据元素必须比一个典型的指令 费时得多。例如，数组可能在磁盘里而不 是在内存里，而且每次比较都需要访问一 次磁盘。 这些数据必须不仅有序，而且分布相当均 匀，这可以使每次估计都相当准确，可以 将大量的数据排除出查找范围。这样，花 费这些计算代价是值得的,分块查找,分块查找也称为索引顺序块的查找。 是处理大量数据查找的一种方法。 它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。,查找由两个阶段组成：查找索引和查找块,Index Table,Sequence Table are di
7、vided into several blocks,算法时间复杂度分析,表长为n，被分成了m块若索引和块内均采用顺序查找，平均查找时间为：,Complexity,Challenge. Efficient implementations of both search and insert.,Search. Scan through all keys until find a match.Insert. Scan through all keys until find a match; if no match add to front.,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无
8、序表的查找 有序表的查找 STL中的静态表,STL中的静态表,对应于顺序查找和二分查找，C+的标准模板库中提供两个模板函数：find和binary_search。这两个函数模板都位于标准库algorithm中find函数顺序查找一个序列 find有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。 函数有三个形式参数。第一、二个形式参数是两个迭代器对 象，指出查找的范围。第三个参数是需要查找的对象值。 find函数的返回值是一个迭代器对象，指出了被查找的元素在容器中的位置。,binary_search,binary_search函数用二分查找的方式
9、查找一个有序序列。 它也有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数 是集合元素的类型。 函数也有三个形式参数。第一、二个形式参数是 两个迭代器对象，指出查找的范围。第三个参数 是需要查找的对象值。 函数的返回值是bool类型的，指出了被查找的元 素在容器中是否存在。如果存在，返回true，否 则，返回false。,应用实例,#include #include #include using namespace std;int main() int a = 2,4,7,8,10,12,13,15,16,19,20; vector v; vector:itera
10、tor 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;,总结,本章介绍了集合关系的基本概念，以及集合类型的数据结构中的基本操作。 针对静态的集合，介绍了查找操作的实现。包括顺序查找、二分查找、插值查找和分块查找。,作业,程序设计题：3、6题,例题：在一个二维数组中，每一行都按照从左到右递增
11、的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例：判断下列数组中是否含有7？,实现代码,1d Range Search,find all keys between k1 and k2. Application. Database queries.ImplementationsUnordered list. Fast insert, slow range search.Ordered array. Slow insert, binary search for k1 and k2 to do range search.,
12、Orthogonal line segment intersection,Given N horizontal and vertical line segments, find all intersections.Application.CADVLSI,2-d orthogonal range search,Search for a 2d key.Range search: find all keys that lie in a 2d range.Rectangle intersection: Find all intersections among a set of N orthogonal
13、 rectangles.Applications. Networking, circuit design, databases, CAD, GIS, virtual reality.,Space-partitioning trees,Use a tree to represent a recursive subdivision of 2d space.Grid. Divide space uniformly into squares.2d tree. Recursively divide space into two halfplanes.Quadtree. Recursively divide space into four quadrants.BSP tree. Recursively divide space into two regions.,Geometric applications of BSTs,
