数据结构：思想与方法-翁惠玉-27783第七章幻灯片.ppt

* 第7章 集合与静态查找表 集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表 * 集合的基本概念 集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。 在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值 集合的主要运算： 查找某一元素是否存在 将集合中的元素按照它的唯一标识排序 * 集合的存储 任何容器都能存储集合 常用的表示形式是借鉴于线性表或树 唯一一个仅适合于存储和处理集合的数据结构是散列表 * 第7章 集合与静态查找表 集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表 * 查找的基本概念 用于查找的集合称之为查找表 查找表的分类： 静态查找表 动态查找表。 内部查找 外部查找 * 静态查找表的存储 静态查找表可以用顺序表存储。 如C++的标准模板库中的类模板vector，或第二章中定义的seqList 查找函数应该是一个函数模板。模板参数是数据元素的类型。 * 第7章 集合与静态查找表 集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表 * 无序表的查找 无序表：数组中的元素是无序的 无序表的查找：毫无选择只能做线性的顺序查找 template class Type int seqSearch(vectorType data, const Type x) { data[0] = x; for (int i = data.size() + 1; x != data[i]; --i); return i; } * 第7章 集合与静态查找表 集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表 * 有序表的查找 顺序查找 二分查找 插值查找 分块查找 * 顺序查找 与无序表的顺序查找类似，只是当被查元素在表中不存在时，不需要查到表尾 template class Type int seqSearch(vectorType data, const Type x) { data[0] = x; for (int i = data.size() + 1; x data[i]; --i); if ( i == 0 || x != data[i]) return 0; else return i; } * 有序表的查找 顺序查找 二分查找 插值查找 分块查找 * 二分查找 每次检查待查数据中排在最中间的那个元素 如中间元素等于要查找的元素，则查找完成 否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。 * 查找 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 * template class Type int binarySearch(const vectorType data, const Type x) { int low = 1, high = data.size() + 1, mid; while (low = high ) //查找区间存在 { mid = (low + high) / 2; //计算中间位置 if ( x == data[mid] ) return mid; if ( x data[mid]) high = mid - 1; else low = mid + 1; } return 0; } * 有序表的查找 顺序查找 二分查找 插值查找 分块查找 * 插值查找 适用于知道数据的大致分布情况 查找位置的估计 缺点：计算量大 * 插值查找适用情况 访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。 这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的 * 有序表的查找 顺序查找 二分查找 插值查找 分块查找 * 分块查找 分块查找也称为索引顺序块的查找。 它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。 * 块内最大关键字 17 44 60 …… 块起