0901绪论

• 动态查找表：在查找的同时对表做修改运算（如插入和删除），否则称为静态查找表
• 内查找：整个查找过程都在内存中进行，若查找过程中需要访问外存，则称为外查找。

0902顺序表的查找

9.2.1、绪论

9.2.2、顺序查找

9.2.3、折半查找

9.2.4、分块查找

9.2.5、顺序表查找的习题

• 1、设计一个顺序查找的递归算法
• 2、对含有n个互不相同元素的线性表，设计一个算法同时找最大元素和最小元素，并问至少需要进行多少次比较？【至少n-1次，最差2n-2次】
• 3、【例10-1-30】
• 4、设计一个折半查找的递归算法
• 5、利用折半查找在一个有序表中插入一个关键字为x的元素并保持表的有序性
• 6、有一个关键字为整数且均不相同的序列R[0..n-1]，假设按关键字递增有序排列，设计一个高效算法判断是否存在某一整数i，恰好存放在R[i]中
• 7、【例10-1-34】

0903树表的查找

9.3.1、树表定义和分类

9.3.2、二叉排序树（BST）

• BST满足以下性质：
  • 若它的左子树非空，则左子树上所有记录的值均小于根记录的值
  • 叵它的右子树非空，则右子树上所有记录的值均大于根记录的值
  • 左、右子树本身又各是一棵二叉排序树
• BST的2个结论：
  • 一棵二叉排序树中的最大节点是根节点的最右下节点，最小节点是根节点的最左下节点
  • 只需给出一棵二叉排序的先序序列、后序序列或层次序列之一，便可以唯一确定这棵二叉树排序树，因为这些序列中所有元素的递增序列便是该二叉排序树的中序序列。
• BST的结构体定义
• BST的插入与生成
• BST的查找
• BST的删除

9.3.3、平衡二叉树（AVL）

• AVL满足以下的性质：
  • 其左子树和右子树都是AVL，且左、右子树深度之差的绝对值不超过1
• 失去平衡的4种调整方法：
  • LL型
  • LR型
  • RL型
  • RR型

9.3.4、B-树（多路平衡查找树）

• 定义
  • B-树中所有节点的孩子节点最大值称为B-树的阶，通常用m表示，从查找效率考虑 要求m>=3
• 一棵m阶B-树，满足下列要求的m次树：
  • 所有的叶子节点在同一层，并且不带信息
  • 树中每个节点至多有m棵子树（即至多含有m-1个关键字）
  • 若根节点不是终端节点，则根节点至少有两棵子树
  • 除根节点外，其他非叶子节点至少有m/2根子树（即至少含有m/2-1个关键字）
  • 每个非叶子节点的结构为n,p0,k1,p1,k2,p2...,kn,pn n为该节点中的关键字个数，n满足m/2-1<=n<=m-1，ki<ki+1，ki<=pi<ki+1
• B-树的结构体定义

#define m 10 //m为B-树的阶，结点中关键字最多可有m-1个
typedef struct node{
    int keynum;  //结点中关键字个数，即结点的大小
    KeyType key[m];//关键字向量，key[0]不可用
    struct node *parent; //双亲结点指针
    struct node* ptr[m];  //子树指针向量
}BTNode;
typedef BTNode *BTree;

• B-树的查找
• B-树的插入
• B-树的删除

9.3.5、B+树

• 一棵m阶的B+树满足下列条件
  • 每个分支节点至多有m棵子树
  • 根节点或者没有子树，或者至少有两根子树
  • 除根节点外，其他每个分支节点至少有m/2棵子树
  • 有n棵子树的节点有n个关键字
  • 所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子节点按关键字大小顺序链接（可以把每个叶子节点看成是一个基本索引块，它的指针不再指向另一级索引块，而是直接指向数据文件中的记录）
  • 所有分支节点（可看成是索引的索引）中仅包含它的各个子节点（既下级索引的索引块）中最大关键字及指向子节点的指针

9.3.6、树表查找的习题

0904哈希表的查找