数据结构 - 第三部分

《数据结构 - 第三部分》由会员分享，可在线阅读，更多相关《数据结构 - 第三部分（440页珍藏版）》请在金锄头文库上搜索。

1、1,第三部分 集合,集合中的元素互相之间没有关系 集合的存储：借用其他容器 集合的操作：查找和排序 这一部分将介绍 查找表 排序算法 散列表 不相交集,2,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,3,集合的基本概念,集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。 在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值 集合的主要运算： 查找某一元素是否存在 将集合中的元素按照它的唯一标识排序,4,集合的存储,任何容器都能存储集合 常用的表示形式是借鉴于线性表或树 唯一一个仅适合于存储和处理集合的数据

2、结构是散列表,5,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,6,查找的基本概念,用于查找的集合称之为查找表 查找表的分类： 静态查找表 动态查找表。 内部查找 外部查找,7,静态查找表的存储,静态查找表可以用顺序表存储。 如C+的标准模板库中的类模板vector，或第二章中定义的seqList，或直接存储在C+的原始数组中。 查找函数应该是一个函数模板。模板参数是数据元素的类型。,8,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,9,无序表的查找,无序表：数组中的元素是无序的

3、 无序表的查找：毫无选择只能做线性的顺序查找,template int seqSearch(vector ,10,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,11,有序表的查找,顺序查找 二分查找 插值查找 分块查找,12,顺序查找,与无序表的顺序查找类似，只是当被查元素在表中不存在时，不需要查到表尾,template int seqSearch(vector ,13,有序表的查找,顺序查找 二分查找 插值查找 分块查找,14,二分查找,每次检查待查数据中排在最中间的那个元素 如中间元素等于要查找的元素，则查找完成 否则，确定要找的数

4、据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。,15,查找 x=8,16,template int binarySearch(const vector ,17,有序表的查找,顺序查找 二分查找 插值查找 分块查找,18,插值查找,适用于数据的分布比较均匀的情况 查找位置的估计缺点：计算量大,19,插值查找适用情况,访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。 这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的,20,有序表

5、的查找,顺序查找 二分查找 插值查找 分块查找,21,分块查找,分块查找也称为索引顺序块的查找。 是处理大量数据查找的一种方法。 它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。,22,查找由两个阶段组成：查找索引和查找块,23,第7章 集合与静态查找表,集合的基本概念 查找的基本概念 无序表的查找 有序表的查找 STL中的静态表,24,STL中的静态表,对应于顺序查找和二分查找，C+的标准模板库中提供两个模板函数：find和binary_search。这两个函数模板都位于标准库algorithm中 find函数顺序查找一个序列 find有两个模板

6、参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。 函数有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。 find函数的返回值是一个迭代器对象，指出了被查找的元素在容器中的位置。,25,binary_search,binary_search函数用二分查找的方式查找一个有序序列。 它也有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。 函数也有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。 函数的返回值是bool

7、类型的，指出了被查找的元素在容器中是否存在。如果存在，返回true，否则，返回false。,26,应用实例,#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 = fi

8、nd(v.begin(), v.end(),13);cout *itr endl;return 0; ,27,总结,本章介绍了集合关系的基本概念，以及集合类型的数据结构中的基本操作。 针对静态的集合，介绍了查找操作的实现。包括顺序查找、二分查找、插值查找和分块查找。 最后还介绍了STL中的查找函数：find和binary_search。find实现了顺序查找，binary_search实现了二分查找。,28,第8章 动态查找表,二叉查找树 AVL树 红黑树 AA树 伸展树 B树和B+树 STL中的动态查找表,既要支持快速查找，又要支持插入删除，通常选用树作为存储的载体,29,二叉查找树,二叉查

9、找树的定义 二叉查找树的操作 二叉查找树的性能 二叉查找树类的实现,30,二叉查找树,如果p的左子树若非空，则左子树上的所有结点的关键字值均小于p结点的关键字值。 如果p的右子树若非空，则右子树上的所有结点的关键字值均大于p结点的关键字值。 结点p的左右子树同样是二叉查找树。,二叉查找树是二叉树在查找方面的重要应用。二叉查找树或者为空，或者具有如下性质：对任意一个结点p而言,31,e、g：二叉查找树,32,二叉查找树,二叉查找树的定义 二叉查找树的操作 二叉查找树的性能 二叉查找树类的实现,33,二叉查找树的操作,特定节点在树上是否存在 插入一个节点 删除一个节点,由于树是递归定义的，因此这些

10、操作往往也用递归实现。因为二叉树的平均高度为logN，这些操作的时间复杂度也是O(logN),34,查找过程,若根结点的关键字值等于查找的关键字，成功。 否则，若关键字值小于根结点，查其左子树。若关键字值大于根结点，查其右子树。在左右子树上的操作类似。,35,如：查找122，查找110，查找230，查找225,36,查找过程的递归描述,如果树为空，返回false 如果根节点等于被查结点，返回true 如果被查节点小于根节点，递归查找左子树，否则递归查找右子树,37,插入操作,若二叉树为空。则新插入的结点成为根结点。 如二叉树非空 首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结

11、点的左、右儿子。将被插结点作为叶子结点插入。,注意：新插入的结点总是叶子结点,38,将数的序列：122、99、250、110、300、280 作为二叉查找树的结点的关键字值，生成二叉查找树。,122,250,300,110,280,99,39,插入操作的递归实现,如果当前树为空，插入值作为树的根节点，返回 如果插入值小于根节点，插入到左子树，否则插入到右子树。,40,执行实例：插入值为 280 的结点,41,删除操作,删除叶结点 删除有一个儿子的结点 删除有两个儿子的结点,42,删除叶结点,直接删除，更改它的父亲结点的相应指针字段为空。这不会改变二叉查找树的特性。如：删除数据字段为 15、70

12、 的结点。,43,删除操作,删除叶结点 删除有一个儿子的结点 删除有两个儿子的结点,44,只有一个儿子,122,250,300,200,230,216,400,450,500,45,122,250,110,200,99,105,400,450,500,46,若被删结点只有一个唯一的儿子，将此儿子取代被删结点的位置。即，如被删结点是其父结点的左孩子，那么将他的儿子作为父结点的左孩子；如被删结点是其父结点的有孩子，那么将他的孩子作为父结点的右孩子。 能保持二查查找树的有序性,47,删除操作,删除叶结点 删除有一个儿子的结点 删除有两个儿子的结点,48,被删结点有两个儿子,通常的做法：选取“ 替身”

13、取代被删结点。有资格充当该替身的是谁哪？ 替身的要求：维持二叉查找树的特性不变。因此，只有在中序周游中紧靠着被删结点的结点才有资格作为“替身”，即， 左子树中最大的结点 或 右子树中最小的结点。,删除这个结点会使其他结点从树上脱离。,49,250,300,200,99,105,330,316,400,450,500,被删结点,替身,做法：将替身110的数据字段复制到被删结点的数据字段。 将结点 110 的左儿子作为 99 的右儿子。,用左子树中的最大值做替身,122,110,50,250,300,110,99,105,330,316,400,450,500,被删结点,替身,做法：将替身的数据字

14、段复制到被删结点的数据字段。将结点 200 的右儿子作为200 的父结点的左儿子。,用右子树的最小值做替身,122,200,51,结论： 先将替身的数据字段复制到被删结点 将原替身的另一儿子作为它的父亲结点的儿子，究竟是作为左儿子还是右儿子依原替身结点和其父亲结点的关系而定 释放原替身结点的空间。,52,删除总结,PL、PR皆 空， 直接删除 。,PL或PR为空,PL为空，删除后的情况。,53,用左子树的最大值代替,54,删除的递归实现,如果是空树，返回 如果被删节点小于根节点，递归在左子树上删除 如果被删节点大于根节点，递归在右子树删除 如果被删节点等于根节点 如果根节点有两个儿子，将右子树

15、的最小值放入根节点，在右子树上删除最小节点 如果只有左子树，左子树取代根节点，删除原来的根节点 如果只有右子树，右子树取代根节点，删除原来的根节点,55,二叉查找树,二叉查找树的定义 二叉查找树的操作 二叉查找树的性能 二叉查找树类的实现,56,二叉查找树性能,二叉查找树的操作（包括insert、find和delete等）的代价正比于操作过程中要访问的结点数。如果所操作的二叉查找树是完全平衡的，那么访问的代价将是对数级别的 在最坏的请况下，二叉查找树会退化为一个单链表。时间复杂度是O(N)。,57,平均性能,n 个结点二叉查找树的可能有n种形态，如果这些形态出现的概率是相等的。设P（n）为查找

16、n个结点的二叉查找树的平均查找时间，则,58,二叉查找树,二叉查找树的定义 二叉查找树的操作 二叉查找树的性能 二叉查找树类的实现,59,二叉排序树类的设计,采用标准的二叉链表存储一棵二叉查找树需要一个指向根节点的数据成员 公有的成员函数：find、insert和remove 以及构造、析构函数 二叉查找树的插入、删除和查找都是通过递归实现的，而这三个公有函数的参数表中并不需要包含递归参数。为此，对于每个公有的成员函数都定义了一个对应的带有递归参数的私有的成员函数,60,二叉排序树类的定义,template class BinarySearchTree private:struct BinaryNode Type data;BinaryNode *left;BinaryNode *right;BinaryNode( const Type ,