《练习---第7章---查找》由会员分享，可在线阅读，更多相关《练习---第7章---查找（142页珍藏版）》请在金锄头文库上搜索。
1、1,下午3时0分,考研要求,（一） 查找的基本概念 （二） 顺序查找法 （三） 折半查找法 （四） B树及其基本操作、B+树的基本概念 （五） 散列（Hash）表 （六） 查找算法的分析及应用,2,下午3时0分,查找,查找的基本概念 线性表的查找顺序查找折半查找分块查找 树表的查找二叉查找树AVL树（平衡二叉树）B树 B+树红黑树,哈希表查找哈希表的基本概念哈希函数的构造方法哈希冲突解决方法哈希表上的运算,注意斜体部分要讲,3,下午3时0分,讲课思路,静态查找表顺序表的查找（使用监视哨）有序表的查找动态查找结构二叉查找树平衡二叉树B树和B+树,散列表或哈希表哈希表的概念哈希表的构造方法处理冲突
2、的方法,顺序查找 折半查找,4,下午3时0分,填 空,所谓（ ），就是在数据集合中寻找满足某种条件的数据对象。（ ）的结果通常有两种可能：成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中的位置, 还可给出该对象中的具体信息。不成功，或查找失败。作为结果，应报告一些信息,如失败标志、位置等。 通常称用于查找的数据集合为查找结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为( )。 实施查找时有两种不同的环境。 （ ）环境，查找结构在插入和删除等操作的前后不发生改变。该种查找表称为（ ）。 （ ）环境，为保持较高
3、的查找效率, 查找结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。该种查找表称为（ ）。,查找,查找,关键码,静态,动态,静态查找表,动态查找表,5,下午3时0分,使用（ ）的顺序查找是将最后一个数据单元的下一个单元设置为（ ），从前向后顺序查找。,监视哨,监视哨,填 空,6,下午3时0分,顺序查找主要用于在线性表中查找。设若表中有 CurrentSize 个元素，则顺序查找从表的前端开始，顺序用各元素的关键码与给定值 x 进行比较若找到与其值相等的元素，则查找成功，给出该元素在表中的位置。若整个表都已检测完仍未找到关键码与 x 相等的元素，则查找失败。给出失败信息。 一般的
4、顺序查找算法在第二章已经讨论过。殷人昆介绍一种使用“监视哨”的顺序查找方法。最后一个数据单元的下一个单元作为“监视哨”使用。而动画里的“监视哨”是放在0号单元。,顺序查找（Sequential Search）,7,下午3时0分,使用监视哨的顺序搜索算法,int dataList:SeqSearch (const K x) const ElementCurrentSize.key = x; /将最后一个数据单元的下一个单元设置为监视哨int i = 0; while (Elementi.key != x) i+; /从前向后顺序搜索return i+1; const int Size = 10;
5、 main () dataList L1 (Size); /定义int型搜索表L1int Target; int Loc;cin L1; cout Target; /输入要搜索的数据 if ( (Location = L1.SeqSearch(Target) != L1.Length() ) /监视哨cout “找到待查元素位置在：“ Loc+1 endl; /搜索成功else cout “ 没有找到待查元素n“; /搜索不成功 ,8,下午3时0分,填 空,在查找成功的平均查找长度公式中，设数据表中有 n 个元素， 表示（ ），表示（ ）。在顺序查找未设置“监视哨”情形：ci = i +1,
6、i = 0, 1, , n-1，等概率情形，查找成功的平均查找长度为：等概率情形，查找不成功情形，查找不成功的平均查找长度为：,pi,ci,查找第i 个元素的概率,查找到第i个元素所需比较次数,ASLunsucc = n+1(设置监视哨),9,下午3时0分,总 结,顺序表搜索等概率情况下，搜索成功的平均比较次数(n+1)/2搜索不成功的比较次数 n 插入的平均移动元素个数n/2 删除的平均移动元素个数(n-1)/2,ASLunsucc = n+1(设置监视哨),10,下午3时0分,无序表和有序表的顺序查找,一般的查找表,表中的数据元素是无序的，该算法查找成功的平均查找长度是(n+1)/2,平均
7、需要查找一半的表元素；查找失败需要查找n或n+1个元素。 而基于有序表的顺序查找，速度可以加快，要查找的元素为X，只要满足Ri-1.key x Ri.key就可以停止搜索。,11,下午3时0分,有序顺序表的顺序查找算法,Template int SortedList: SequentSearch(const K x)constfor(int i=1;ix)break; ,12,下午3时0分,判断树：有序顺序查找表的描述,我们用判断树来描述有序顺序查找表的查找过程，树中圆形结点表示在有序顺序表中已有的元素，叫做( );判定树中方形结点表示表中两个相邻元素之间的不在表中的数据值的集合，叫做( )。
8、 查找成功时，指针停在某个( )；查找失败时，指针停在某个( )；,内部结点或(查找)成功结点,外部结点或(查找)失败结点,内部结点,外部结点,13,下午3时0分,给出查找序列(10,20,30,40,50,60)顺序查找的判定树,见教材P303图7.1,描述在上述顺序查找判定树上查找25和查找40的查找过程,见教材P303图7.1,有序表的顺序查找判定树,14,下午3时0分,有序顺序表的折半查找算法(非递归),Template int SortedList: BinarySearch (const K x)constint high=CurrentSize-1,low=0,mid;while
9、(lowElementmid.key)low=mid+1;else if(xElementmid.key)high=mid-1;else return mid+1;return 0; ,15,下午3时0分,时间复杂度,顺序查找的时间复杂度是O(n) 而折半查找的时间复杂度是O(log2n)。,16,下午3时0分,给出查找序列(10,20,30,40,50,60)折半查找的判定树,见教材P306图7.3,描述在上述折半查找判定树上查找25和查找40的查找过程,见教材P306图7.3,有序表的折半查找判定树,17,下午3时0分,练 习,设有序顺序表中的元素依次为017, 094, 154, 170
10、, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均查找长度和查找不成功的平均查找长度。（教材P342 习题7.3）,low=0;high=13; int mid=(low+high)/2,0,1,3,4,2,5,6,7,8,9,10,11,12,13,18,下午3时0分,19,下午3时0分,二叉查找树,20,下午3时0分,填 空,二叉查找树或者是一棵空树，或者是具有下列性质的二叉树： 每个结点都有一个作为查找依据的 (key)，所有结点的 互不相同。 左子树（如果非空）上所有结点的关
11、键码都 根结点的关键码。 右子树（如果非空）上所有结点的关键码都 根结点的关键码。 左子树和右子树也是 。,关键码,关键码,小于,大于,二叉查找树,如果对一棵二叉查找树进行 ，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉查找树为。,中序遍历,二叉排序树,21,下午3时0分,若给定值小于根结点的关键码，则继续递归查找根结点的左子树； 否则。递归查找根结点的右子树。,查找45 查找成功,查找28 查找失败,给出下列二叉查找树查找28和45的方法,22,下午3时0分,插入新结点28,二叉查找树的插入,每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。,23,下午
12、3时0分,给出新结点28插入二叉查找树的过程,如果查找成功，说明树中已经有这个元素，不再插入； 如果查找不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到查找操作停止的地方。,24,下午3时0分,输入数据 53, 78, 65, 17, 87, 09, 81, 15 建立一棵二叉查找树，给出建立的过程。,25,下午3时0分,根据动画“7.2-1-2-二叉查找树的构造.swf”，输入数据 50, 30, 40, 80, 20, 36, 90, 40 , 38，建立一棵二叉查找树，给出建立的过程。,26,下午3时0分,画出动画“7.2-1-1-二叉查找树的构造”由关键字序列1，2，3，4
13、，5构造而得的二叉查找树，给出查找成功的平均查找长度,succ,27,下午3时0分,画出动画“7.2-1-1-二叉查找树的构造”由关键字序列3，1，2，4，5构造而得的二叉查找树，给出查找成功的平均查找长度,succ,28,下午3时0分,课 堂 练 习,设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据而生成的二叉查找树。,29,下午3时0分, 46, 25, 78, 62, 12, 37, 70, 29 ,30,下午3时0分,二叉查找树的删除算法,在二叉查找树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起
14、来，同时确保二叉查找树的性质不会失去。 为保证在删除后树的查找性能不至于降低，还需要防止重新链接后树的高度增加。 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。 被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的其它删除问题。,动画里在它的左子树中寻找中序下的最后一个结点(关键码最大),用它的值填补到被删结点中，再来处理这个结点的其它删除问题。,31,下午3时0分,53,7
15、8,65,17,87,09,23,45,删除45,右子树空, 用左子女顶替,53,78,65,17,87,09,23,，可以拿它的左子女结点顶替它的位置，再释放它。,被删结点右子树为空,给出下列二叉排序树 删除45的方法,32,下午3时0分,53,78,88,17,94,09,23,删除78,左子树空, 用右子女顶替,53,94,88,17,09,23,给出下列二叉排序树 删除78的方法,33,下午3时0分,88,53,78,81,17,94,09,45,删除78,左右子树都不空，在右子树上找中序下第一个结点填补(关键码最小),23,65,53,81,88,17,94,09,45,23,65,给出下列二叉排序树 删除78的方法,
