9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较

Presentation on theme: "9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较"— Presentation transcript:

1 9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较
第九章 查找 9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较

2 9.1 基本概念 查找表（Search Table）:由同一类型的数据元素（或记录）构成的集合 对查找表进行的操作有以下四种：
9.1 基本概念 查找表（Search Table）:由同一类型的数据元素（或记录）构成的集合 对查找表进行的操作有以下四种： 查询某个特定的数据元素是否在查找表中 检索某个特定的数据元素的各种属性 在查找表中插入一个数据元素 从查找表中删除某个数据元素 静态查找表（Static Search Table）:对查找表只作前两种操作 动态查找表（Dynamic Search Table）:在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素

3 关键字（Key）:标志数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素
查找（Searching）:根据给定的某个值，在查找表中确定是否存在一个数据元素其关键字等于给定值的记录或数据元素 平均查找长度ASL（Average Search Length)为：

4 9.2 线性表的查找 顺序查找 折半查找 分块查找

5 9.2.1 顺序查找 基本思想：从表的一端开始，顺序扫描线性表，依次用待查找的关键字值与线性表里各结点的关键字值逐个比较，若在表中找到了某个记录的关键字与待查找的关键字值相等，表明查找成功；如果找遍所有结点也没有找到与待查找的关键字值相等，则表明查找失败 算法: typedef struct { keytype key; /*关键项*/ elemtype other; /*其它域*/ int length /*表长度*/ ｝SSTable;

6 顺序查找的平均查找长度 int Search-Seq(SSTable *ST，Keytype key) {
ST[0].key=key; /*设置监视哨*/ for(i=ST.length; ST[i].key!=key;  i); /*若找到，返回元素的位置；若找不到，则返回0*/ if (i == 0 ) printf(“Searching Fail!\n”); else printf(“Searching Success!\n”); return i; } 顺序查找的平均查找长度 返回

7 9.2.2 折半查找 基本思想： 首先用要查找的关键字值与中间位置结点的关键字值相比较；比较结果如果相等，则查找完成；
若不相等，再根据要查找的关键字值与该中间结点关键码值的大小来确定下一步查找在哪个子表中进行： 如果待查关键字大于中间结点的关键字值，则应查找中间结点以后的子表，否则，查找中间结点以前的子表

8 事例：已知如下11个数据元素的有序表：（5，14，19，22，37，56，64，75，80，89，92），现要查找关键字为22的数据元素
给定值key=22的查找过程 ：

9 #include "str.h" typedef struct { keytype key; /*关键项*/ elemtype other; /*其它域*/ int length /*表长度*/ ｝SSTable; int Search_Bin(SSTable ST，int key) int low，high，mid; low=1; high=ST.length; /*置区间初值*/ while(low<=high) mid=(low+high)/2;

10 折半查找的平均查找长度 ： if(key==ST.elem[mid].key)
return mid; /*找到了待查的结点，返回其所在位置*/ else if(key<ST.elem[mid].key) high=mid-1; /*继续在前半区间进行查找*/ else low=mid+1; /*继续在后半区间进行查找*/ } return 0; /*查找不成功，返回0值 */ 折半查找的平均查找长度 ：

11 折半查找判定树 ：折半查找过程可用二叉树来形象的描述，把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树，由此得到的二叉树，称为描述折半查找的判定树
事例： 返回

12 9.2.3 分块查找 基本思想：把线性表分成若干块，在每一块中结点的存放是任意的，块与块之间必须排序；建立一个索引表，存放每块中最大的关键字值；查找时首先用要查找的关键字值在索引表中查找，确定应在哪一块中，然后再到相应的块中顺序查找 事例：

13 算法： typedef struct { keytype key; /*关键项*/ elemtype other; /*其它域*/
int length /*表长度*/ ｝SSTable; /*索引表的结点类型*/ typedef struct keytype key ; int addr ; }Idtable ID[b];/*索引表，b为块数*/

14 int BLKSearch(R，ID，K)
SSTable R[]; Idtable ID[]; Keytype K; { int i; int low1,low2,mid,high1,high2; /* low1\ high1为折半查找区间下\上界置初值*/ low1=0; high1= b -1; while (low1<=high1) mid=(low1+high1)/2; if (K<=ID[mid].key) high1=mid-1; else low1=mid+1; }/*查找完毕，low1为找到的块号*/

15 if (low1< b) /*若low1>= b ，则K大于R中所有的关键字*/
{ /*块起始地址*/ low2=ID[low1].addr; if (low1== b-1) high2= R.length -1;/*求块的末地址*/ else high2=ID[low1+1].addr-1; /*在块内顺序查找*/ for (i=low2;i<=high2;i++) if (R[i].key==K) return i; /*查找成功*/ } return (-1); /*查找失败*/ } /*BLKSearch*/

16 （3） 结点的存储结构：各块可放在不同的向量中，也可将每一块存放在一个单链表中
算法分析： （1）平均查找长度ASL： ①以二分查找来确定块，分块查找成功时的平均查找长度ASLblk=ASLbn+ASLsq≈lg(b+1)-1+(s+1)/2≈lg(n/s+1)+s/2 ②以顺序查找确定块，分块查找成功时的平均查找长度ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s) （2）块的大小:根据表的特征进行分块 （3） 结点的存储结构：各块可放在不同的向量中，也可将每一块存放在一个单链表中

17 9.3 树表的查找 二叉查找树 平衡二叉树 B-树

18 9.3.1 二叉查找树 概念：二叉树的每个结点对应于一个关键字，整个二叉树各结点对应的关键字组成一个关键字集合，并且此关键字集合中的各个关键字在二叉树中是按一定顺序排列的，称此二叉树为二叉查找树 性质： 二叉查找树或者是一棵空树，或者是具有如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左子树和右子树又均是一棵二叉查找树

19 二叉链表的定义算法描述 ： 事例： typedef struct Bitnode { int key;
struct Bitnode *lchild，*rchild; } *Bitree; /*二叉链表的定义*/ 事例：

20 二叉排序树的生成 BSTree CreateBST(void) { //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTree T=NULL； //初始时T为空树 KeyType key； scanf("％d"，&key)； //读人一个关键字 while(key){ //假设key=0是输人结束标志 InsertBST(&T，key)； //将key插入二叉排序树T scanf("％d"，&key)；//读人下一关键字 } return T； //返回建立的二叉排序树的根指针 } //BSTree

21 二叉查找树的查找： 查找过程： 当二叉查找树为空时，查找失败 如果二叉查找树根结点记录的关键字等于key，则查找成功

22 查找算法： int SearchB(Bitree T，int key，Bitree f，Bitree p) { if(!T) { p=f; return 0; /*查找不成功*/ } else if(key==T->key) { p=T; return 1; } /*查找成功*/ else if(key<T->key) return(SearchB(T->lchild，key，T，p)); /*在左子树中继续查找*/ return(SearchB(T->rchild，key，T，p)); /*在右子树中继续查找*/

23 二叉查找树的插入 过程描述： 若二叉查找树为空，则将待插入结点s 作为根结点插入到树中去
如果二叉查找树非空，将待查结点的关键字s->key 和树根的关键字p->key 进行比较，如果相等，则表明树中已有此结点，无需插入 如果s->key小于 p->key ，则将待插结点s 插入到根的左子树中 如果s->key大于 p->key ，则将待插结点s 插入到根的右子树中，而在子树中的插入过程又和在树中的插入过程相同，如此进行下去，直到把结点 s 作为一个新的叶子插入二叉查找树中，或者直到发现树中已有结点 s 为止

24 算法描述： int InsetB(Bitree T，int key) { Bitree s，p;
if(!SearchB(T，key，NULL，p)) /*查找不成功，即key不存在于二叉树T中*/ { s=(Bitree) malloc(sizeof(Bitnode)); s->key=key; s->lchild=s->rchild=NULL; if(!p) T=s; /*把被插结点s作为新的根结点*/ else if(key < p->key) p->lchild=s; /*把被插结点s作为左孩子*/ else p->rchild=s; /*把被插结点s作为右孩子*/ return 1; } else return 0; /*二叉树T中已有关键字相同的结点，不再插入*/

25 事例：查找的关键字序列为{54，42，68，16，87}

26 二叉查找树的删除： (1)若*p结点为叶子结点，只需修改其双亲结点的指针
(2)若*p结点只有左子树PL，令PL直接成为其双亲结点*f的左子树 (3) 若*p结点只有右子树PR，令PR直接成为其双亲结点*f的左子树 (4)若*p结点的左子树和右子树均不空 令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图9-5(c)所示； 令*p的直接前驱（或直接后继）替代*p，然后再从二叉查找树中删去它的直接前驱（或直接后继）

27 图示：

28 算法： void delete(Bitree p) { Bitree q，s;
if(!p->rchild) /*右子树为空，则只需重新连接它的左子树*/ q = p; p=p->lchild; free(q); } else if(!p->lchild) /*左子树为空，则只需重新连接它的右子树*/ q=p; p=p->rchild;

29 else /*左右子树均不为空*/ { q = p; s = p->lchild; while(s->rchild) q=s; s=s->rchild; } /*向左转，然后向右到尽头*/ p->key=s->key; /*s指向被删除结点的前趋*/ if(q!=p) q->rchild = s->lchild; /*重新连接q的右子树*/ else q->lchild=s->lchild; /*重新连接q的左子树*/ }

30 int DeleteB(Bitree T，int key)
{ if(!T) return 0; else if(key==T->key) delete(T); if(key<T->key) DeleteB(T->lchild，key); DeleteB(T->rchild，key); return 1; } 返回

31 概念： 或者是一棵空树，或者是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树； 左子树和右子树的深度之差的绝对值不超过1 事例：
9.3.2 平衡二叉树 概念： 或者是一棵空树，或者是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树； 左子树和右子树的深度之差的绝对值不超过1 事例： 不平衡的二叉树

32 事例：构造关键字的序列为（1，2，3，9，5）的平衡二叉树

33 平衡处理的方法 ： （1）LL型调整： (2)RR型调整：

34 （3）LR型调整： (4) RL型调整 ：

35 算法描述： #define LH 1 /*左高*/ #define EH 0 /*等高*/ #define RH –1 /*右高*/
typedef struct Bstnode { int key; int bf; /*结点的平衡因子*/ struct Bstnode *lchild; /*左孩子指针*/ struct Bstnode *rchild; /*右孩子指针*/ } *Bstree;

36 /*对以p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点-旋转之前的左子树
根结点*/ void R_rotate(Bstree p) /*右旋转操作*/ { Bstree lc; lc=p->lchild; /*lc指向p的左子树根结点*/ p->lchild=p->rchild; /*lc的右子树挂接为p的左子树*/ lc->rchild=p; p=lc; /* p指向新的根结点*/ }

37 /*对以p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点-旋转之前的右子树
根结点*/ void L_rotate(Bstree p) /*左旋转操作*/ { Bstree rc; rc=p->rchild; /*rc指向p的右子树根结点*/ p->rchild=rc->lchild; /*rc的左子树接为p的右子树*/ rc->lchild=p; p=rc; /*p指向新的根结点*/ }

38 /*对以指针T所指结点为根的二叉树作左平衡旋转处理，算法结束时，指针T指向新的根结点*/
void Lbalance(Bstree T) { Bstree lc，rd; lc=T->lchild; /*lc指向二叉树T的左子树根结点*/ switch(lc->bf) /*检查T的左子树的平衡度*/ case LH: /*作单右旋处理操作*/ T->bf=lc->bf=EH; R_rotate(T); break; case RH: /*作双旋处理操作*/ rd=lc->rchild; /*rd指向二叉树T的左孩子的右子树根*/

39 switch(rd->bf) /*修改二叉树T及其左孩子的平衡因子*/
{ case LH: T->bf=RH; lc->bf=EH; break; case EH: T->bf=lc->bf=EH; case RH: T->bf=EH; lc->bf=LH; } rd->bf=EH; L_rotate(T->lchild); /*对二叉树T的左子树作左旋平衡处理*/ R_rotate(T); /*对二叉树T作右旋平衡处理*/ } }

40 AVL树的插入算法 if(NewValue < Root->Left->Value)
InsertAVLNode(NewValue, Root) { if(!Root) Root = allocate memory for node; Root->Value = NewValue; Root->Height = 0; Root->Left = Root->Right = NULL; } else if(NewValue < Root->Value) Root->Left=InsertAVLNode(NewValue,Root->Left); if(Root->Left->Height-Root->Right->Height == 2) if(NewValue < Root->Left->Value)

41 Root = SingleRightRotation(Root);
else Root = DoubleLeftRightRotation(Root); } else if(NewValue > Root->Value){ Root->Right=InsertAVLNode(NewValue,Root->Right); if(Root->Right->Height-Root->Left->Height == 2) if(NewValue < Root->Right->Value) Root = SingleLeftRotation(Root); Root = DoubleRightLeftRotation(Root); if(Root->Left->Height >= Root->Right->Height) Root->Height = Root->Left->Height + 1; Root->Height = Root->Right->Height + 1; return Root; } 返回

42 9.3.3 B-树 概念： 一棵m(m≥3)阶的B-树是满足如下性质的m叉树： (1) 每个结点至少包含下列数据域：
(j，P0，Kl，P1，K2，…，Ki，Pi)其中： j为关键字总数 Ki(1≤i≤j)是关键字，关键字序列递增有序：K1 <K2<…<Ki Pi(0≤i≤j)是孩子指针，对于叶结点，每个Pi为空指针

43 (2) 所有叶子都在同一层上，叶子的层数为树的高度h
(3) 每个非根结点中所包含的关键字个数j满足： 每个非根结点至少应有 个关键字，至多 有m-1个关键字 (4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树；根至多有m-1个关键字，故至多有m棵子树

44 存储结构： #define Max l000 //结点中关键字的最大数目 #define Min 500 //非根结点中关键字的最小数目
typedef int KeyType； //KeyType应由用户定义 typedef struct node {　int keynum； 　 KeyType key[Max+1]； 　 struct node *parent； //指向双亲结点 struct node *son[Max+1]；//孩子指针向量为son[0..keynum] }BTreeNode； typedef BTreeNode *BTree；

45 9.4 哈希表的查找 哈希表 哈希（Hash）函数：记录的存储地址和它的关键字之间建立一个确定的对应关系H，使每个关键字和结构中唯一的一个存储位置相对应，则对应关系H为关键字集合到地址空间之间的哈函数 哈希表：此时地址空间表A 散列方法：使用函数h将U（关键字集合）映射到表T[0..m-1]的下标

46 哈希表类型说明： 事例： #define NIL -1 //空结点标记依赖于关键字类型 #define M 997 //表长度依赖于应用
typedef struct{ //哈希表结点类型 KeyType key； InfoType otherinfo； //此类依赖于应用 }NodeType； typedef NodeType HashTable[m]； //哈希表类型 事例：

47 冲突（collision） ：不同的关键字，根据某个哈希函数可能得到同一哈希地址 同义词（synonym）：具有相同函数值的关键字

48 9.4.2 构造哈希表的基本方法 平方取中法 ：H（key）=key2的中间几位 事例：
折叠 法：将关键字分割成位数相同的几部分取这几部分的叠加和作为哈希地址 关键字key=

49 除留余数法：关键字值进行取模运算H（key）=key MOD p （p≤m）
事例： 直接定址法：取关键字本身或者它的线性函数作为它的哈希地址，即H（K）=K或者H（K）=a×K+b 事例：一人口统计表，记录了从1岁到100岁的人口数目，其中，年龄作为关键字，哈希函数取关键字自身

50 9.4.3 解决冲突的方法 开放定址法：当冲突发生时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元地查找，直到找到给定的关键字或者碰到一个开放的地址为止 Hi＝（H（key）＋ di） MOD m i＝1，2，…，k（k≤m-1），其中：H（key）为哈希函数；m为哈希表表长；d为增量序列，可有下列三种取法： di=1，2，3，…，m-1称线性探测再散列 di=12，-12，22，-22，32，…，k2，-k2（k≤m/2）称二次探测再散列 di=随机数序列，称随机探测再散列

51 事例：在长度为11的哈希表中已填有关键字分别为17，60，29的记录（哈希函数（key）＝key MOD ll），现插入关键字为38的记录

52 事例：已知一组关键字为（27，6，84，21，36，38，10，16，55，14， 79）
链地址法：为每个哈希地址建立一个链表，当发生冲突时，就把发生冲突的记录链接到相应的哈希地址的链表上去；结果将所有关键字为同义词的记录存储在同一线性链表中 事例：已知一组关键字为（27，6，84，21，36，38，10，16，55，14， 79） 则按哈希函数H（key） =key MOD 13 和链地址法处理冲突

53 9.4.4 哈希表的查找方法 算法思想：给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较；若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址

54 算法描述（开放定址法 ）： int HashSearch(HashTable T，KeyType K，int *pos)
{ int i=0； //记录探查次数 do { *pos=Hash(K，i)； //求探查地址hi if(T[*pos].key==K) return l； //查找成功返回 if(T[*pos].key==NIL) return 0；//查找到空结点返回 }while(++i<m) //最多做m次探查 return -1； //表满且未找到时，查找失败 } //HashSearch

55 9.5 各种查找方法的比较 顺序查找的效率很低，对于待查的结构没有任何要求，算法非常简单，既适用于顺序存储结构，又适用于链接存储结构。
9.5 各种查找方法的比较 顺序查找的效率很低，对于待查的结构没有任何要求，算法非常简单，既适用于顺序存储结构，又适用于链接存储结构。 折半查找法的平均查找长度小，查找速度快，但要求表中的记录是有序的，且只能用于顺序存储结构 分块查找的平均查找长度介于顺序查找和折半查找之间。由于结构是分块的，所以，当表中记录有变化时，只要调整相应的块，可用于顺序存储结构，也可用于链接存储结构。 哈希法是直接计算地址的方法，在查找过程中不需要进行比较，其查找时间与表中记录的个数无关