数据数据结结构构 Data StructureData Structure第七章第七章 集合与静态查找表集合与静态查找表第第7 7章章 集合与静态查找表集合与静态查找表n集合的基本概念 n查找的基本概念 n无序表的查找 n有序表的查找 nSTL中的静态表集合的基本概念集合的基本概念n集合中的数据元素没有任何逻辑关系。 n在集合中，每个数据元素有一个区别于其他元素的唯一标 识，通常称为键值或关键字值n集合的主要运算： n查找某一元素是否存在 n将集合中的元素按照它的唯一标识排序Ex. DNS lookup. Given URL, find corresponding IP address.集合的应用集合的应用集合的存储集合的存储n任何容器都能存储集合 n常用的表示形式是借鉴于线性表或树 n唯一一个仅适合于存储和处理集合的数据 结构是散列表第第7 7章章 集合与静态查找表集合与静态查找表n集合的基本概念 n查找的基本概念 n无序表的查找 n有序表的查找 nSTL中的静态表查找的基本概念查找的基本概念n用于查找的集合称之为查找表 n查找表的分类： n静态查找表 n动态查找表 n内部查找 n外部查找静态查找表的存储静态查找表的存储n静态查找表可以用顺序表存储。 如C+的 标准模板库中的类模板vector，或第二章中 定义的seqList，或直接存储在 C+的原始数 组中。 n查找函数应该是一个函数模板。模板参数 是数据元素的类型。第第7 7章章 集合与静态查找表集合与静态查找表n集合的基本概念 n查找的基本概念 n无序表的查找 n有序表的查找 nSTL中的静态表无序表的查找无序表的查找n无序表：数组中的元素是无序的 n无序表的查找：毫无选择只能做线性的顺序查找 template int seqSearch(vector for (int i = data.size() + 1; x != datai; -i); return i; 算法时间复杂度分析算法时间复杂度分析n不成功查找：O（N）n成功查找：n最好：O（1）n最坏：O（N）n平均： O（N）若每个元素被找到的可能性相等，平均查找时间：第第7 7章章 集合与静态查找表集合与静态查找表n集合的基本概念 n查找的基本概念 n无序表的查找 n有序表的查找 n顺序查找 n二分查找 n插值查找 n分块查找nSTL中的静态表顺序查找顺序查找n与无序表的顺序查找类似，只是当被查元素在表 中不存在时，不需要查到表尾 template int seqSearch(vector for (int i = data.size() + 1; x datai; -i); if ( i = 0 | x != datai) return 0; else return i; 二分查找二分查找n每次检查待查数据中排在最中间的那个元素 n如中间元素等于要查找的元素，则查找完成 n否则，确定要找的数据是在前一半还是在后 一半，然后缩小范围，在前一半或后一半内 继续查找。查找查找 x=8x=8012mid=4 但 key=8 int binarySearch(const vector while (low #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; 总结总结n本章介绍了集合关系的基本概念，以及集 合类型的数据结构中的基本操作。 n针对静态的集合，介绍了查找操作的实现 。包括顺序查找、二分查找、插值查找和 分块查找。 作业作业n程序设计题：3、6题例题：在一个二维数组中，每一行都按照从左到右递增的顺序 排序，每一列都按照从上到下递增的顺序排序。请完成一个 函数，输入这样的一个二维数组和一个整数，判断数组中是 否含有该整数。 例：判断下列数组中是否含有7？n实现代码1d Range Search1d Range Searchnfind all keys between k1 and k2. nApplication. Database queries.nImplementationsnUnordered list. Fast insert, slow range search.nOrdered array. Slow insert, binary search for k1 and k2 to do range search.Orthogonal line segment Orthogonal line segment intersectionintersectionnGiven N horizontal and vertical line segments, find all intersections.nApplication.nCADnVLSI2-d orthogonal range search2-d orthogonal range searchnSearch for a 2d key.nRange search: find all keys that lie in a 2d range.nRectangle intersection: Find all intersections among a set of N orthogonal rectangles.nApplications. Networking, circuit design, databases, CAD, GIS, virtual reality.Space-partitioning treesSpace-partitioning treesnUse a tree to represent a recursive subdivision of 2d space.nGrid. Divide space uniformly into squares.n2d tree. Recursively divide space into two halfplanes.nQuadtree. Recursively divide space into four quadrants.nBSP tree. Recursively divide space into two regions.Geometric applications of BSTsGeometric applications of BSTs