数据结构（C语言版）课件 第8章 查找.pptx

0-1开课;;8.1查找的基本概念;静态查找：不涉及插入和删除操作的查找;查找结构;线性表：适用于静态查找，顺序查找、折半查找等技术;平均查找长度;8.2线性表的查找;顺序查找（线性查找）;顺序查找算法实现;顺序查找的性能;改进顺序查找;折半查找（二分查找）;折半查找算法实现;运行实例;;;;;;;非递归算法;递归算法;判定树;例如，结点个数（查找集合的记录个数）为11的判定树;例如，结点个数（查找集合的记录个数）为11的判定树;折半查找性能分析;判定树深度为;3;折半查找性能分析;分块查找;基本思想：首先查找索引表ID[]，以确定待查结点在哪一分块(由于索引项按关键码字有序，可用顺序或折半查找)。然后，在已确定的那一块中进行顺序查找。;运行实例;算法实现;分块查找性能分析;分块查找性能分析;8.3树表的查找（动态查找）;树表的提出;二叉排序树的定义;二叉排序树的定义;二叉排序树的存储;二叉排序树的查找;63;二叉排序树的插入;voidInsertBST(BiNode*root,intx)

{

if(root==NULL){

BiNode*s=(BiNode*)malloc(sizeof(BiNode));

s-data=x;

s-lchild=s-rchild=NULL;

root=s;

}

elseif(root-datax)InsertBST(root-lchild,x);

elseInsertBST(root-rchild,x);

};二叉排序树的构造;二叉排序树的删除;63;63;情况3——被删除的结点既有左子树也有右子树;情况3——被删除的结点既有左子树也有右子树;63;63;voidDeleteBST(BiNode*p,BiNode*f)

{

;BiNode*par=p,*s=p-lchild;/*p的左右子树均不空*/

while(s-rchild!=NULL)/*查找左子树的最右下结点*/

{

par=s;

s=s-rchild;

}

p-data=s-data;

if(par==p)par-rchild=s-lchild;/*特殊情况，p的左孩子无右子树*/

elsepar-lchild=s-lchild;

free(s);;举例：;二叉排序树的性能分析;例如，给定查找集合{40,35,30,25,20,15}，构造的二叉排序树深度为n;

;平衡二叉树的提出;二叉排序树的深度取决于给定查找集合的排列，即结点的插入顺序;平衡二叉树的定义;最小不平衡子树;平衡调整???法;LL型的平衡调整;LL型的平衡调整;RR型的平衡调整;RR型的平衡调整;平衡调整算法;LR型的平衡调整;LR型的平衡调整;LR型的平衡调整;LR型的平衡调整;RL型的平衡调整;RL型的平衡调整;RL型的平衡调整;构造平衡二叉排序树;举例：;例：设序列{16,3,7,11,9,26,18,14,15}，构造平衡二叉树;AVL树的性能分析;AVL树的性能分析;B树的定义;B_树：一棵m阶的B_树是一棵平衡的m叉搜索树，它或者为空树，或者为满足下列特性的m叉树：

（4）所有结点都包含以下数据：（n，A0，K1，A1，K2，…，Kn，An），

其中，n（?m/2??1≤n≤m?1）为关键码的个数，Ki（1≤i≤n）为关键码，且

Ki＜Ki+1（1≤i≤n-1），Ai（0≤i≤n）为指向子树根结点的指针，且指针Ai所指子树中所有结点的关键码均小于Ki+1大于Ki。;B_树：一棵m阶的B_树或者为空树，或者为满足下列特性的m叉树：

（5）叶子结点都在同一层；;5阶B_树示意图;B树的查找;118;B树的深度;因此，含有n个关键码的m阶B树的最大深度是;B树的插入;假定在m阶B树中插入关键码key，插入过程如下：;假定在m阶B树中插入关键码key，插入过程如下：;假定在m阶B树中插入关键码key，插入过程如下：;假定在m阶B树中插入关键码key，插入过程如下：;假定在m阶B树中插入关键码key，插入过程如下：;假定在m阶B树中插入关键码key，