第7章 查找 北京师范大学 教育技术学院 杨开城.

Presentation on theme: "第7章 查找 北京师范大学 教育技术学院 杨开城."— Presentation transcript:

1 第7章 查找 北京师范大学 教育技术学院 杨开城

2 一、基本概念和术语 查找表：由同一类数据元素构成的集合。 静态查找表： 如果查找表只用于查找操作
动态查找表： 如果查找表不仅仅用于查找操作，还允许在查找过程中，对查找表进行插入和删除数据元素的操作 关键字：可以标识数据元素的某个数据项 主关键字：可以唯一标识数据元素的关键字 次关键字：能够同时标识多个数据元素的关键字 查找：对于给定的某个值Key，在查找表中寻找关键字值为Key的数据元素的过程 平均查找长度：查找的平均比较次数

3 二、静态查找表——无序表的查找 int Search1(elemtype r[],int n, elemtype key) // O(n)
{/*在顺序表r中查找key，找到则返回它的下标，否则返回-1，n是r中数据元素的个数*/ int i; for(i=0;i<n;i++) if(r[i]==key) return i;/*查找成功*/ return -1;/*查找失败*/ }

4 二、静态查找表——有序表的查找(1) ⑴简单线性查找
int Search2(elemtype r[],int n, elemtype key) //O(n) {/*在升序排序的顺序表r中查找key，找到则返回它的下标，否则返回-1， n是r中数据元素的个数*/ int i; for(i=0;i<n;i++) { if(r[i]==key)return i;/*查找成功*/ else if(r[i]>key)return -1;/*后面的数据元素不可能出现key,查找失败*/ } return -1;

5 二、静态查找表——有序表的查找(2) ⑵折半查找
int BiSearch(elemtype r[],int n,elemtype key) //O(log2n) {/*在升序排序顺序表r中折半查找key，找到则返回它的下标，否则返回-1， n是r中数据元素的个数*/ int high,low,mid; low=0; high=n-1;/*查找区间初始化完毕*/ while(high>=low) /*查找区间合法，继续查找循环*/ { mid=(high+low)/2; if(r[mid]==key)/*查找成功*/ return mid; else if(r[mid]>key) high=mid-1;/*选择左边的查找区间，继续查找*/ else low=mid+1;/*选择右边的查找区间，继续查找*/ } return -1;/*查找失败*/

6 二、静态查找表——有序表的查找(3) ⑶斐波那契查找 #define FIBONUM 20
int FiboSearch(elemtype r[],int n,elemtype key) {/*在升序排序顺序表r中进行斐波那契查找key，找到则返回它的下标，否则返回-1，n是r中数据元素的个数*/ int Fibo[FIBONUM]={1,2}; int i,high,low,index,num,mid; for(i=2;i<FIBONUM;i++)/*产生足够数量的斐波那契数*/ Fibo[i]=Fibo[i-1]+Fibo[i-2]; low=0; high=n-1;/*查找区间初始化完毕*/ num=n;/*num是查找区间中数据元素的个数*/ while(high>=low) /*查找区间合法，继续查找循环*/ { for(i=0;i<FIBONUM-1;i++)/*确定不大于num的最大的斐波那契数*/ if(Fibo[i]<=num&&Fibo[i+1]>num)break; index=Fibo[i];/*index是那个不大于num的最大的斐波那契数*/

7 二、静态查找表——有序表的查找(3) mid=low+index-1;/*确定需要比较的数据单元的下标mid*/
if(r[mid]==key)return mid;/*查找成功*/ else if(r[mid]>key)high=mid-1;/*选择左边的查找区间*/ else low=mid+1;/*选择右边的查找区间*/ num=high-low+1;/*计算查找区间中的数据元素的个数*/ } return -1;/*查找失败*/ ⑷插值查找

8 二、静态查找表——分块查找 分块查找表又称索引顺序表 首先根据索引表中的信息确定要查找的关键字所在的数据块 在数据块内部进行查找

9 三、动态查找表——二叉排序树(1) 二叉排序树：以升序为例，二叉排序树或者是空树，或者是一颗具有下列性质的二叉树：
①如果左子树不空，那么左子树所有结点的值都小于根结点的值；②如果右子树不空，那么右子树所有结点的值都大于根结点的值；③左右子树都是二叉排序树。

10 三、动态查找表——二叉排序树(2) 二叉排序树的查找算法
BTREENODEPTR Search(BTREE root,int key,BTREENODEPTR *f) {/*在二叉排序树root中查找关键字是key的结点,返回结点指针并将f指向该结点双亲*/ BTREENODEPTR p; *f=NULL;/*暂时设置双亲为NULL*/ p=root;/*p指向根结点*/ while(p!=NULL) /*只要p合法，继续查找循环*/ { if(p->data==key) break;/*查找成功*/ else { *f=p; /*双亲指针跟随p */ if(p->data>key) p=p->lchild; /*p指向左子树，继续在左子树中查找*/ else p=p->rchild;/*p指向右子树，继续在右子树中查找*/ } return p;/*无论查找成功或失败，都返回p，p可能是NULL，*f指向p的双亲*/

11 三、动态查找表——二叉排序树(3) 二叉排序树的插入 【基本思想】 如果二叉排序树是空树，那么就将key结点作为二叉排序树的根；
如果相等，直接返回； 如果根结点比key大，则将key插入到左子树中； 如果根结点比key小，则将key插入到右子树中。 最终要么插入失败，要么key将成为一个叶子结点。

12 三、动态查找表——二叉排序树(4) int Insert(BTREE *root,int key)
{/*向二叉排序树root中插入结点key，插入成功返回1，否则返回0*/ if(*root==NULL) {/*树为空，生成新的根结点*/ *root=(BTREE)malloc(sizeof(BTREENODE)); if(*root==NULL) return 0; (*root)->lchild=(*root)->rchild=NULL; (*root)->data=key; return 1; } if((*root)->data>key) return Insert(&(*root)->lchild,key); /*向左子树插入*/ else if((*root)->data<key) return Insert(&(*root)->rchild,key); /*向右子树插入*/ else return 1;/*直接返回*/

13 三、动态查找表——二叉排序树(5) 二叉排序树的删除 【基本思想】
假设p指向某二叉排序树中要删除的结点，而f指向该结点的双亲，要删除结点p，需要区分三种情况 ： ⑴结点p是单枝结点 ⑵结点p是叶子结点 ⑶结点p是双枝结点

14 三、动态查找表——二叉排序树(6) void Delete(BTREE *root,int key)
{/*在二叉排序树root中删除关键字是key的结点*/ BTREENODEPTR p,q,f,h; /*在二叉排序树中查找key，获得指向key结点的指针p和p结点的双亲f*/ p=Search(*root,key,&f); if(p==NULL)return;/*查找失败，直接返回*/ if(p->lchild==NULL&&p->rchild==NULL) h=NULL;/*叶子结点的情况*/ else if(p->lchild==NULL||p->rchild==NULL) {/*单枝结点的情况,h指向p的单枝子树*/ if(p->lchild!=NULL)h=p->lchild; else h=p->rchild; }

15 三、动态查找表——二叉排序树(6) else/*双枝结点*/ { f=p;/*开始寻找p的直接后继，并且f跟随q，保持是q的双亲状态*/
q=p->rchild;/*q指向p的右孩子*/ while(q->lchild!=NULL) /*只要q的左孩子不空，就还没有达到最左端*/ { f=q;/*f跟随q*/ q=q->lchild;/*q指向自己的左孩子*/ } p->data=q->data;/*将q结点的数据复制到p结点中*/ p=q;/*p指向q，问题转化为删除单枝结点p*/ h=p->rchild;/*h是p单枝子树*/ if(f==NULL) *root=h;/*删除的是根结点*/ else if(f->rchild==p)f->rchild=h;/*将f的左孩子或右孩子指向h，摘除p*/ else f->lchild=h; free(p);/*释放p*/

16 三、动态查找表——平衡二叉树(1) 平衡二叉树：又称AVL树。它或者是空树，或者是具有下列性质的二叉排序树：它的左右子树深度差的绝对值不超过1，并且它的左右子树也是平衡二叉树。

17 三、动态查找表——平衡二叉树(2) 平衡二叉树的插入 通常有两种调整操作：单旋调整和双旋调整。
平衡二叉树的插入，需要在二叉排序树插入算法基础上，做如下改动： ⑴递归函数返回值的含义是：子树是否长高。 ⑵递归调用返回时，检查结点的平衡状态。如果失去平衡，则进行平衡调整。 通常有两种调整操作：单旋调整和双旋调整。

18 三、动态查找表——平衡二叉树(3) 单旋 右单旋：A的平衡因子是-1并且B的平衡因子是-1 左单旋： A的平衡因子是1并且B的平衡因子是1

19 三、动态查找表——平衡二叉树(4) void LeftRotate(BTREENODEPTR *root)
{/*左单旋调整root,*root指向A，*root可能是某个结点的左孩子或右孩子指针*/ BTREENODEPTR p; p=(*root)->rchild;/*p指向B*/ (*root)->rchild=p->lchild; /*B的左孩子称为A的右孩子*/ p->lchild=(*root); /*将A作为B的左孩子*/ *root=p;/*将B作为子树的根*/ } void RightRotate(BTREENODEPTR *root) {/*右单旋调整root,*root指向A，*root可能是某个结点的左孩子或右孩子指针*/ BTREENODEPTR p; p=(*root)->lchild; /*p指向B*/ (*root)->lchild=p->rchild; /*B的右孩子称为A的左孩子*/ p->rchild=(*root); /*将A作为B的右孩子*/ *root=p; /*将B作为子树的根*/

20 三、动态查找表——平衡二叉树(5) 双旋 先左后右单旋：A的平衡因子是-1并且B的平衡因子是1 调整之后平衡因子变化：
如果C的平衡因子是-1,那么A的平衡因子是1，B的平衡因子是0 如果C的平衡因子是1，那么A的平衡因子是0，B的平衡因子是-1 如果C的平衡因子是0，那么A和B的平衡因子都是0 C的平衡因子是0 先右后左单旋：A的平衡因子是1并且B的平衡因子是-1 如果C的平衡因子是-1,那么A的平衡因子是0，B的平衡因子是1 如果C的平衡因子是1，那么A的平衡因子是-1，B的平衡因子是0

21 三、动态查找表——平衡二叉树(6) void LeftRightRotate(BTREENODEPTR *root)
{/*先左后右双旋调整root,*root指向A，*root可能是某个结点的左孩子或右孩子指针*/ LeftRotate(&(*root)->lchild);/*先左单旋调整B*/ RightRotate(root);/*再右单旋调整A*/ } void RightLeftRotate(BTREENODEPTR *root) {/*先右后左双旋调整root,*root指向A，*root可能是某个结点的左孩子或右孩子指针*/ RightRotate(&(*root)->rchild); /*先右单旋调整B*/ LeftRotate(root); /*再左单旋调整A*/

22 三、动态查找表——平衡二叉树(7) typedef struct btreenode { int data; /*结点的数据域*/
int balance; /*结点的平衡因子*/ struct btreenode *lchild,*rchild; /*左右孩子的指针*/ } BTREENODE, *BTREENODEPTR,*BTREE; int InsertBal(BTREE *root,int key) {/*向平衡二叉树root中插入结点key，如果二叉树长高，返回1，否则返回0*/ int taller;/*是否长高的标志*/ if(*root==NULL) {/*根是空，生成新叶子结点，它可能是某个结点的孩子，也可能是整个树的根*/ *root=(BTREE)malloc(sizeof(BTREENODE)); if(*root==NULL) return 0; (*root)->lchild=(*root)->rchild=NULL; (*root)->data=key; (*root)->balance=0; return 1; /*子树深度由0变成1，长高了*/ }

23 三、动态查找表——平衡二叉树(8) else if((*root)->data>key)
{ taller=InsertBal(&(*root)->lchild,key); /*将key插入左子树*/ if(taller==1) /*如果左子树长高，可能需要调整*/ switch((*root)->balance) { case 0:/*原平衡因子是0，平衡因子变成了-1，树长高*/ (*root)->balance=-1; break; case 1: /*原平衡因子是1，平衡因子变成了0，树深度不变*/ taller=0; (*root)->balance=0; break; case -1:/*原平衡因子是-1，左子树又长高，*root结点失去平衡*/ if((*root)->lchild->balance==-1) /*右单旋*/ { RightRotate(root); (*root)->balance=0; /*将A和B的平衡因子都归0*/ (*root)->rchild->balance=0; }

24 三、动态查找表——平衡二叉树(9) else if((*root)->lchild->balance==1)
{/*先左后右的双旋，先调整平衡因子后旋转调整*/ if((*root)->lchild->rchild->balance==-1) /*key插在CL上*/ { (*root)->balance=1; (*root)->lchild->balance=0; } else if((*root)->lchild->rchild->balance==1) /*key插在CR上*/ { (*root)->balance=0; (*root)->lchild->balance=-1; else /*C就是插入的key*/ { (*root)->balance=0; (*root)->lchild->balance=0; (*root)->lchild->rchild->balance=0;/*C的平衡因子是0*/ LeftRightRotate(root);/*先左后右双旋A*/ taller=0;/*旋转调整后，树不会长高*/ break; }//switch return taller; }

25 三、动态查找表——平衡二叉树(10) else if((*root)->data<key)
{ taller=InsertBal(&(*root)->rchild,key); /*将key插入右子树*/ if(taller==1) /*如果右子树长高，可能需要调整*/ switch((*root)->balance) { case 0:/*原平衡因子是0，平衡因子变1，树长高*/ (*root)->balance=1; break; case -1:/*原平衡因子是-1，平衡因子变0，树高度不变*/ taller=0; (*root)->balance=0; break; case 1:/*原平衡因子是1, *root结点失去平衡*/ if((*root)->rchild->balance==1) /*左单旋即可*/ { LeftRotate(root); (*root)->balance=0; (*root)->lchild->balance=0; }

26 三、动态查找表——平衡二叉树(11) else if((*root)->rchild->balance==-1)
{/*需要先右后左双旋，先调整平衡因子，再旋转*/ if((*root)->rchild->lchild->balance==1) /*key插在CR上了*/ { (*root)->balance=-1; (*root)->rchild->balance=0; } else if((*root)->rchild->lchild->balance==-1) /*key插在CL上了*/ { (*root)->balance=0; (*root)->rchild->balance=1; else /*C就是插入key的结果*/ { (*root)->balance=0; (*root)->rchild->balance=0; (*root)->rchild->lchild->balance=0; RightLeftRotate(root); taller=0;/*调整完毕后，整个子树不会长高*/ break; }//switch return taller;/*返回子树长高状态*/ } else return 0;/*树中存在结点key，不能再插入，返回0*/ }

27 三、动态查找表——平衡二叉树(12) 平衡二叉树的删除

28 三、动态查找表——B-树(1) B-树 一棵m阶的B-树，要么是一棵空树，要么是具有下列性质的m叉树： ⑴树中每个结点至多有m棵子树；
⑵除非树只有一个根结点，否则根至少有2棵子树； ⑶除了根之外的所有的非终端结点至少有 棵子树； ⑷所有非终端结点的数据域都具有下面的格式： （n,A0, K1, A1, K2, A2,…, Kn, An） ⑸所有终端结点都出现在同一个层次上，并且不带任何信息。其实这些结点只是逻辑上存在，实际上不存在。指向这些结点的指针都是NULL。

29 三、动态查找表——B-树(2) B-树的数据类型定义 #define M 5 /*B-树的阶数*/
typedef struct b_treenode { int n; /*关键字的个数*/ int keys[M+1]; /*存放关键字的数组*/ struct b_treenode *parent; /*指向双亲结点的指针*/ struct b_treenode *child[M+1]; /*子树指针的数组*/ }B_TREENODE,*B_TREE;

30 三、动态查找表——B-树(3) B-树的查找 typedef struct { B_TREENODE *p; /*关键字所在结点的指针*/
int i; /*关键字在keys数组中的下标*/ }BTSRESULT;/*描述B-树查找结果的数据结构*/ BTSRESULT BTSearch(B_TREE root,int key) {/*在B-树root中，查找关键字key，返回查找结果*/ int i; B_TREENODE *p; BTSRESULT result; /*存放查找结果*/ result.p=NULL;/*设置查找结果的初始值：查找失败的状态*/ result.i=-1;

31 三、动态查找表——B-树(4) p=root; /*p指向根结点，从根开始*/ while(1)
{ for(i=1;i<=p->n;i++) /*在p结点的关键字数组中进行线性查找*/ { if(p->keys[i]==key) /*查找成功*/ { result.p=p;/*设置查找结果*/ result.i=i; return result; } else if(p->keys[i]>key) break; /*p结点中没有key，并且遇到的第一个比key大的关键字是p->keys[i],p->keys[i]左边的子树指针是p->child[i-1]*/ if(p->child[i-1]!=NULL) p=p->child[i-1];/*跳到相应的子树上继续查找*/ else break;/*查找失败*/

32 三、动态查找表——B-树(5) B-树的插入 与二叉排序树的插入相似，最终插入到最底层的某个结点中。接下来区分两种情况处理：
⑴m阶B-树中的某叶子结点P插入关键字之后，关键字总量n小于m，则插入操作完毕。这棵树仍然是B-树。 ⑵m阶B-树中的某叶子结点P插入关键字之后，关键字总量n等于m。这时需要对结点进行“分裂”处理。

33 三、动态查找表——B-树(6)

34 三、动态查找表——B-树(6) B-树的删除 在m阶B-树中的删除某关键字key，要区分两种情况：
⑴key位于非最底层结点中。找到key的直接后继key1，删除key1的操作按照第⑵种情况处理。 ⑵key位于最底层结点中。这种情况下，直接在结点中删除key之后，要进一步检查结点的关键字个数n的值，如果n值合法，那么删除操作结束；否则需要进一步处理：“借”或者“合并”。

35 三、动态查找表——B-树(7) B-树删除中的“借”操作

36 三、动态查找表——B-树(8) B-树删除中的合并操作

37

38 三、动态查找表——B+树 B+树：是应对文件管理系统所需而设计的B-树的一个变种。 一棵m阶B+树和m阶B-树的差异在于：
⑴结点中关键字的个数与子树的个数相同，n个子树的结点包含n个关键字。 ⑵所有的最底层结点包含了全部的关键字信息，最底层结点之间被按照大小顺序链接起来。 ⑶所有的非最底层结点只是最底层结点的索引，第i个关键字是第i个子树中关键字的最大值。

39 三、动态查找表——键树 键树：又称数字查找树，它是一棵度大于等于2的树。它的独特性是，树中每个结点并不存放关键字，而是存放组成关键字的符号或数位。

40 四、哈希表 哈希表：只需根据关键字的值经过某种简单计算就可以确定数据元素位置的查找表
哈希函数：哈希表中，关键字的值K与关键字的存储位置A具有的某种确定的对应关系：A=f(K) 散列：通过哈希函数，给定关键字K，计算它的存储位置的过程 哈希地址或散列地址:散列计算所得的存储位置 冲突：如果K1≠K2，那么有f(k1)=f(k2)

41 四、哈希表——哈希函数的构造 ⑴直接定址法 ⑵数字分析法 ⑶平方取中法 ⑷折叠法 ⑸除留余数法 15928 15758 13576
15328 15616 13498

42 四、哈希表——冲突处理 ⑴开放定址法 ⑵再哈希法 ⑶链地址法 ⑷公共溢出区法

43 导航图(1)

44 导航图(2)

45 导航图(3)

46 导航图(4)

47 导航图(5)

48 导航图(6)

49 导航图(7)

50 导航图(8)

51 导航图(9)

52 导航图(10)