第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找.

Presentation on theme: "第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找."— Presentation transcript:

1 第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找

2 8.1概述 查找表： 对查找表的操作有 静态查找表、动态查找表 关键字 查找 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。
查找某个“特定”的元素是否在表中。 查找某个“特点”的元素的各种属性。 在查找表中插入一个元素。 在查找表中删除一个元素 静态查找表、动态查找表 关键字 数据元素中的某个数据项值。可以标识一个数据元素，如可以唯一标识，则为主关键字（primary key）。 查找 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。若找到表示查找成功，返回该元素详细信息或在查找表中的位置；负责返回NULL

3 8.2静态查找表 typedef struct{ Datatype data; //元素数据 KeyType key; //元素关键字
}Elemtype; //数据元素类型 Elemtype *elem; //约定从下标1开始 int len; }StaticSrhTable; //顺序静态查找表类型

4 8.2.1顺序查找 算法8.1 int SeqSearch(StaticSrhTable SST, KeyType kval) {
/* 在顺序表SST中顺序查找关键字为kval的记录。 若找到，则返回记录在表中的位序；否则，返回0 */ SST.elem[0].key = kval; // 放置监视哨 for (i = SST.len; SST.elem[i].key != kval; i--); // 查找 return i; // 查找结果 }

5 例8.1 在顺序查找表中查找成功和失败 平均查找长度 查找过程中先后和给定值进行比较的关键字的个数的期望值
ASL＝∑PiCi ∑Pi＝1 i＝1，2，。。。。。n Ci＝n－i＋1 Pi＝1/n ASLss＝1/n∑（n－i＋1）=(n+1)/2

6 8.2.2折半查找(顺序有序表) 折半查找（binary Search）：二分查找。
int BinSearch(StaticSrhTable SST, KeyType kval){ bot=1, top=SST.len; // 置查找范围初值 while(bot<=top) { mid = (bot+top)/2; if (SST.elem[mid].key==kval) return mid; //查找成功 else { if (SST.elem[mid].key>kval) top=mid-1;//前半区 else bot =mid+1; // 后半区 } return 0; // 未查找到

7 ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(20+21*2+…+2h-1*h)Pi=
二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(20+21*2+…+2h-1*h)Pi=

8 8.2.3分块查找（索引顺序） 又称索引顺序查找 介于顺序查和折半查找之间。适合于关键字分块有序 设索引长度b，顺序表长度为n，则：
typedef struct { KeyType key; int stadr; }indexItem; typedef struct{ indexItem *elem; int length; }indexTable; 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)≈log2(b+1)-1+(n/b+1)/2

9 state BlkInxSearch(StaticSrhTable SST, InxTab Inx, KeyType kval){
bot = 1, top = Inx.len, blFound = FALSE; // 置查找范围初值 if (kval > Inx.elem[top].key) return 0; // 越界 while (bot <= top && !blFound) { mid = (bot + top) / 2; if (Inx.elem[mid].key == kval) { // 查找成功 blFound = TRUE; bot = mid; } else { if (Inx.elem[mid].key > kval) top = mid - 1; // 前半区 else bot = mid + 1; // 后半区 } //退出循环时，bot所指的为所找的块 bn = Inx.elem[bot].StartAdd; //第bot块的数据记录起始地址 if (bot < Inx.len) en = Inx.elem[bot + 1].StartAdd – 1; else en = SST.len; //第bot块的数据记录尾地址 for (i = bn; (i <= en) && (SST.elem[i].key != kval); i++); if (i <= en) return i; return 0; //未查找到 为什么选择bot 而不是top?

10 索引顺序查找

11 8.3动态查找表 ADT DynamicSearchTable{ 数据对象：D是具有相同特性的元素集合。 数据关系：同属集合关系。
基本操作： InitDSTable（&DT） DestroyDSTable（&DT） SearchDSTable（DT，kval） InsertDSTable（&DT,e） * DeleteDSTable（&DT,kval） * TraverseDSTable（DT,Visit()） }ADT DynamicSearchTable;

12 8.3.1二叉查找树（检索树） 查找树、二叉查找树 例二叉查找树的查询过程。 二叉查找树的插入算法
通过合根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。二叉排序树又称二叉查找树。 例二叉查找树的查询过程。 算法8.4 bool Search_BST(BiTree T,KeyType kval, BiTree &p,BiTree &f) 二叉查找树的插入算法 算法8.5 bool Insert_BST(BiTree &T, KeyType kval)

13 二叉查找树查找算法 Bool BinSrTree(BiTree BT, KeyType kval, BiTree &p, BiTree &f) {/* 查找关键字为kval的记录。 若找到，则指针p指向该记录并返回TRUE；否则，返回FALSE。指针f指向p所指记录的双亲记录;若查找失败则p为空指针，f则为这个空指针的双亲。*/ p = BT; while (p) { if (p->data.key == kval) return TRUE; // 查找成功 else { f = p; if (p->data.key > kval) p = p->lChild;// 查找左子树 else p = p->rChild; // 查找右子树 } return FALSE; // 未查找到 }// BinSrTree

14 二叉查找树的插入算法 Bool BinSrTree_Ins(BiTree &BT, KeyType kval)
{/* 当二叉查找树BT中不存在关键字为kval的记录时，插入之并返回TRUE； 否则，不进行插入操作并返回FALSE。*/ f = NULL; if (BinSrTree(BT, kval, p, f)) return FALSE; // 不插入 t = new BiTNode; t->data.key = kval; t->lChild = t->rChild = NULL; if (!f) BT = t; // 空树时为根结点 else if (kval < f->data.key) f->lChild = t; // 为左孩子 else f->rChild = t; // 为右孩子 return TURE; }//BinSrTree_Ins

15 删除结点的处理方法 二叉查找树的平均查找长度 1)若是叶子结点，直接删除 2)只有一个孩子，则将其孩子直接挂到其双亲上。
3)有两个孩子，找左孩子中最大的一个元素，代替被删除结点，最大元素肯定只有一个孩子，按2）处理删除最大元素 算法8.6 bool Delete_BST(BiTree &T, KeyType kval) 二叉查找树的平均查找长度 p（n）＝2（n＋1）/n *logn+C

16 Bool BinSrTree_Del(BiTree &BT, KeyType kval) {
f = NULL; if (！BinSrTree(BT, kval, p, f)) return FALSE; // 不删除 if (p->lChild && p->rChild) { //度为2，左右子树都非空 q = p; t = p->lChild; while (t->rChild) { q = t; t = t->rChild;} p->data = t->data; // t指向左子树中关键字最大的结点 if (q != p) q->rChild = t->lChild; else q->lChild = t->lChild; // t结点为p结点的左子树根 free(t); } else { //度<=1 q = p; if (!p->rChild) p = p->lChild; // 右子树为空，挂其左子树 else p = p->rChild; // 左子树为空，挂其右子树 if(!f)BT=p; //删除的是根结点 else{if(q==f->lchild)f->lchild=p;else f->rchild=p; } delete q; }// BinSrTree_Del

17 平衡二叉树（AVL树） 什么是平衡二叉树 平衡因子 最小子树根 实现方法：平衡旋转技术
树中每个结点的左、右子树深度之差的绝对值不大于1，这种平衡状态的二叉查找树。 平衡因子 结点的左子树深度和右子树深度之差。 AVL树的平衡因子只能取-1,0,1 最小子树根 离插入结点最近且平衡因子不满足绝对值小于等于1的祖先结点。 实现方法：平衡旋转技术 四种平衡旋转方式

18 BL和BR深度相等吗？ A 2 B 1 BL BR AR h-1 h-2 插入节点 LL型旋转

19 RR型旋转 BL和BR深度相等吗？ AL BL BR AL BL BR 插入节点 A -2 B B -1 A h-2 h-2 h-2 h-2
B -1 A AL h-2 BL BR AL BL BR h-2 h-2 h-2 h-1 h-1 插入节点 RR型旋转

20 LR型旋转 AR BL CL CR AR BL CL CR 插入节点 插在CL和CR一样吗？ CL和CR深度相等吗？ A 2 C B -1
B -1 B A -1 AR C 1 h-2 BL CL CR AR BL h-3 CL CR h-2 h-2 h-2 h-2 h-3 h-2 插入节点 插在CL和CR一样吗？ CL和CR深度相等吗？ LR型旋转

21 RL型旋转 AL BR AL CL CR BR CL CR 插入节点 插在CL和CR一样吗？ CL和CR深度相等吗？ A -2 C B 1
B 1 A B -1 AL C 1 BR h-2 AL CL CR BR h-2 h-2 h-3 CL CR h-2 h-2 h-3 h-2 插入节点 插在CL和CR一样吗？ CL和CR深度相等吗？ RL型旋转

22 Bool L_Rotate(AVLTree &T) rchd=T->rchild;
{//对T为根的二叉树作左旋转，处理后T仍指向树根 rchd=T->rchild; T->rchild=rchd->lchild; rchd->lchild=T; T=rchd; }// L_Rotate Bool R_Rotate(AVLTree &T) {//对T为根的二叉树作右旋转，处理后T仍指向树根 lchd=T->lchild; T->lchild=lchd->rchild; lchd->rchild=T; T=lchd; }// R_Rotate

23 void Balance(AVLTree &T,LRtype LR)
{//对T为最小子树根结点的二叉树做平衡旋转，处理后T仍指新树根 TB=(LR==LEFT)?T->lchild:T->rchild; if(LR==LEFT){ //情况(a)(c)，插入在T左子树 if(TB.bf==1) {T->bf=TB->bf=0;R_Rotate(T);} //LL型 else{ //LR型 if(TB->rchild->bf==1) {T->bf=-1;TB->bf=0;} //插在CL上 置A的bf=-1;B的bf=0 else {T->bf=0;TB->bf=1;} //插在CR上 置A的bf=0;B的bf=1 TB->rchild->bf=0; ////置C的bf=0 L_Rotate(TB);R_Rotate(T); //先左后右两次旋转 } else{ //情况(b)(d)，插入在T右子树 if(TB.bf==-1) {T->bf=TB->bf=0;L_Rotate(T);} //RR型 else{ //RL型 if(TB->lchild->bf==1) {T->bf=0;TB->bf=-1;} //插在CL上置A的bf=0;B的bf=-1 else {T->bf=1;TB->bf=0;} //插在CR上 置A的bf=1;B的bf=0 TB->rchild->bf=0; //置C的bf=0 R_Rotate(TB);L_Rotate(T); //先左后右两次旋转 }//Balance

24 T=new AVLNode;T->data=e; T->lchild=T->rchild=NULL;
Status InsertAVL(AVLTree &T,ElemType e,Boolean &taller) {//在二叉树T中查找e，若存在则返回0，否则插入e为新结点，并通过平衡旋转保持 //二叉树是平衡的。参数taller表示插入e后二叉树T是否深度增加 if(!T){ // 插入新结点作为树根 T=new AVLNode;T->data=e; T->lchild=T->rchild=NULL; T->bf=0;taller=TRUE; //单个结点是平衡的，树高度增加了 return 1; } if(e.key==T->data.key) //已存在的关键字，不插入 {taller=FALSE;return 0;} if(e.key<T->data.key){ //在左子树继续查找 if(!InserverAVL(T->lchild,e,taller))return 0; //未插入 if(!taller)return 1; //未长高，返回 switch(T->bf){ //左子树长高了 case -1: //原左子树比右子树矮 T->bf=0;taller=FALSE;break; case 0： //原左子树和右子树一样高 T->bf=1;taller=TRUE;break; case 1: //原左子树比右子树高，插入后失衡 Balance(T,LEFT);taller=FALSE;break； }//switch

25 else{ //e.key > T->data.key 在右子树继续查找
if(!InserverAVL(T->rchild,e,taller))return 0; //未插入 if(!taller)return 1; //未长高，返回 switch(T->bf){ //左子树长高了 case -1: //原左子树比右子树矮，插入后失衡 Balance(T,RIGHT);taller=FALSE;break; case 0： //原左子树和右子树一样高 T->bf=-1;taller=TRUE;break; case 1: //原左子树比右子树高 T->bf=0;taller=FALSE;break; }//switch } return 1; }//Balance

26 键树、数字查找树（Digital search trees）
8.3.2键树 键树、数字查找树（Digital search trees） 结点不是关键字，而是关键字中的一个字符,从根到叶子结点的路径（根、叶子本身除外）才是关键字 例 统计正文中某些单词出现的次数 键树的存储（双链树） 采用孩子－兄弟的存储方法。

27 Const MAXKEYLEN＝16； Const LINESIZE＝80； typedef struct { char ch[MAXKEYLEN]; int num; }KeysType; typedef enum{LEAF, BRANCH}NodeKind; typedef struct{ char symbol; struct DLTNode *next; NodeKind kind; Union{ struct DLTNode *first; int idx; } }DLTNode,*DLTree;

28 8.4哈希表及其查找 8.4.1哈希表的定义和特点 哈希表 哈希表的装填系数 α＝n/m
在记录的关键字和其存储位置（数组下标）之间设定一个确定的对应关系f，关键字为kval的记录存储在f（kval）位置处 哈希表的装填系数 α＝n/m 其中m为哈希表分配空间 n为填入的记录数。 实际应用：0.65～0.85

29 哈希函数 冲突 哈希表的严格定义： 可以对关键字做简单的算术或逻辑运算。 例：i=f1(key)=key
例：i=f2(key)=(关键字的第一个字母ASCII码)－(‘A’的 ASCII码) 例：i=f3(key)=(f2(关键字的第一个字母)+ f2(关键字的最后一个字母))/2 冲突 若出现f（key1）＝f（key2）的现象称冲突。没有冲突的哈希函数很少存在，只能尽量均匀。称“再散列”。在建哈希表时，不仅要设定哈希函数，还要设定处理冲突的方法 哈希表的严格定义： 根据设定的哈希函数和处理冲突的方法为一组记录建立的一种存储结构，哈希函数又称散列函数。构建哈希表又称散列技术

30 8.4.2构造哈希函数的方法 除留余数法 平方取中法 折叠法 Hash（key）＝key mod p （p<=m）
其中p为不大于m且最接近m 的最大素数。如m=1000 p=997 平方取中法 对一个关键字平方，取中间几位，中间几位和每位数字都有关系，不易冲突 折叠法 将关键字分割成位数相同的几部分（最后一部分可以不同），然后几部分相加舍进位作为哈希地址。 有移位叠加、间界叠加

31 8.4.3处理冲突的方法 开放定址法 (闭散列方法) 从哈希地址Hash(key)求得一个地址序列H1、H2… Hk,0<=k<=m-1, 即H1－Hk-1都不空，直到Hk为空为止。若哈希表未满，必能找到k<m，使Hk空。 Hi=(Hash(key)+di)mod m i=1,2,...,k k<=m-1 di为递增序列,有三种取法 a) di＝1,2,...,m-1 b) di=12，-12，22，－22...，k2，－k2 （k<=m/2） c) di＝伪随机序列 di 也可以是P(k, i) 与k相关，避免二次聚集

32 例 设一组关键字(07,15,20,31,48,53,64,76, 82,99)试构建哈希表, 取m＝11， Hash（key）＝key mod 11
1 2 3 4 5 6 7 8 9 10 53 64 76 99 15 48 82 07 20 31

33 链地址法/拉链法（开散列方法） 将所有关键字为同义词（即具有相同的哈希函数值）的记录存贮在同一线性链表中，而哈希表中下标为i的分量存储哈希函数值为i的链表的头指针 1 2 3 4 5 6 7 8 9 10 ↓ ^ 99 15 82 07 20 76 48 31 53 64

34 8.4.4哈希函数的查找及其性能分析 开放定址法的存储结构
int hashsize[]={997,...} typedef struct { ElemType *elem; //记录存储基址 int count; //记录数 int sizeindex; //哈希表容量 }HashTable; const SUCCESS＝1； const UNSUCCESS＝0； const DUPLICATE＝-1； 算法 Status SearchHash(HashTable H,KeyType kval,int &p,int &c) 算法 Status InsertHash(HashTable &H,ElemType e)

35 开放定址Hash查找 Status SearchHash(HashTable H, HKeyType K, int &p, int &c) { // 在开放定址哈希表H中查找关键码为K的元素， // 若查找成功，以p指示位置，并返回SUCCESS； // 否则，以p指示插入位置，并返回UNSUCCESS, // c用以计冲突次数，其初值置零，供建表插入时参考 p = Hash(K); // 求得哈希地址 while ((H.elem[p].key != NULLKEY) && // 该位置中填有记录 !equal(K, (H.elem[p].key))) collision(p, ++c); // 求得下一探查地址p if (equal(K, (H.elem[p].key))) return SUCCESS; // 查找成功，p返回待查数据元素位置 else return UNSUCCESS; //查找不成功(H.elem[p].key == NULLKEY)， // p返回的是插入位置 } // SearchHash

36 开放定址Hash插入 Status InsertHash(HashTable &H, HElemType e) {
// 查找不成功时插入数据元素e到哈希表中，并返回OK； // 若冲突次数过大，则重建哈希表 int c = 0, p = 0; if (SearchHash(H, e.key, p, c) == SUCCESS ) return DUPLICATE; // 表中已有与e有相同关键字的元素 if (c < H.cursize) { // 冲突次数c未达到上限（阀值c可调） H.elem[p] = e; ++H.count; return SUCCESS; // 插入e } else { RecreateHashTable(H); // 重建哈希表 return UNSUCCESS; } // InsertHash

37 链地址法存储结构： typedef struct { ElemType data; LHNode *next; //记录数
}LHNode,*LHNodeptr; LHNodeptr *elem; int count; //记录数 int sizeindex; //哈希表容量 } LHashTable;

38 Status SearchHash(LHashTable H,KeyType kval, LHNodeptr &p,int &c)
{ //若查到，p指向该结点； //若查不到，p返回最后一个结点待插入 p=H.elem[Hash(kval)]; while(p && p->data.key!=kval){q=p;p=p->next;c++;} //q紧随p if(p)return SUCCESS; else {p=q;return UNSUCCESS;} }

39 链地址Hash插入 Status InsertHash(HashTable &H,ElemType e) { c=0;
if(SearchHash(H, e. key, p, c)== SUCCESS) return DUPLICATE; else if (c<hashsize[H.sizeindex]/2){ s＝new LHNode; s->data=e;p->next=s; H.count++; return OK; }//if else recreateHashTable(H); //重建哈希表 }

40 线形探测散列、二次探测散列、链地址法构建哈希函数比较
（07，15，20，31，48，53，64，76，82，99） m=11 n=10 p=11 α＝0.91 关键字 07 15 20 31 48 53 64 76 82 99 ASL 线性 1 2 3 4 2.4 二次 2.0 链地址法 1.7 * 1.3 * 表示m=13 p=13α＝0.77线性

41 查找成功时平均查找长度： 查找不成功时平均查找长度 ASLsl（α）≈(1+1/(1-α))/2 ASLsr（α）≈-1/αln(1-α)
ASLsc（α）≈1+α/2 查找不成功时平均查找长度 ASLul（α）≈(1+1/(1-α)2)/2 ASLsr（α）≈1/ (1-α) ASLsc（α）≈α+e-α

42 8.4.5哈希表的应用举例 C语言中编译程序使用的符号表，操作有 例 C语言32关键字的查找表希望ASL<=2
对给定的名字查是否已在表中。 填入新的名字。 对给定的名字访问其有关信息。 对给定名字更新和填写其信息。 删除一些无用的名字 例 C语言32关键字的查找表希望ASL<=2 以二次探测散列处理冲突,得α<=0.795 因n=32 故m>40 考虑m＝4j＋3 取m＝43 ，p＝41 hash（key）＝[（key的第一个字符序号）×100＋（key的最后一个字符序号）] mod 41 实际ASL=2.5