第九章 查找表 9.1静态查找表 9.2动态查找表 9.3哈希表及其查找.

Presentation on theme: "第九章 查找表 9.1静态查找表 9.2动态查找表 9.3哈希表及其查找."— Presentation transcript:

1 第九章 查找表 9.1静态查找表 9.2动态查找表 9.3哈希表及其查找

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

3 9.1静态查找表 9.1.1顺序查找 查找成功和失败 平均查找长度 查找过程中先后和给定值进行比较的关键字的个数的期望值
typdef struct{ ElemType *elem; //元素存储空间，0单元保留 int length; //表长度 }SSTable; 查找成功和失败 平均查找长度 查找过程中先后和给定值进行比较的关键字的个数的期望值 ASL＝∑PiCi ∑Pi＝1 i＝1，2，… …n Ci＝n－i＋1 Pi＝1/n ASLss＝1/n∑（n－i＋1）=(n+1)/2

4 折半查找（binary Search）：二分查找。 例8.2 利用二分查找在顺序有序表中查找。
9.1.2折半查找 折半查找（binary Search）：二分查找。 例8.2 利用二分查找在顺序有序表中查找。 算法8.2 Int Search_Bin(SStable ST,KeyType kval) ASLbs＝（n＋1）/nlog(n+1)-1

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

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

7

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

9 9.2.1二叉查找树 查找树、二叉查找树 例:二叉查找树的查询过程。 例:二叉查找树的插入算法
通过和根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。二叉查找树又称二叉排序树。 例:二叉查找树的查询过程。 Status Search_BST(BiTree T,KeyType kval,BiTree f, BiTree &p) 例:二叉查找树的插入算法 Status Insert_BST(BiTree &T, ElemType e)

10 删除结点的处理方法 二叉查找树的平均查找长度 二叉平衡（查找）树 1)若是叶子结点，直接删除 2)只有一个孩子，则将其孩子直接挂到其双亲上。
3)有两个孩子，找左孩子中最大的一个元素，代替被删除结点，最大元素肯定只有一个孩子，按2）处理删除最大元素 Status Delete_BST(BiTree &T, KeyType kval) 二叉查找树的平均查找长度 p（n）＝2（n＋1）/n *logn+C 二叉平衡（查找）树 树中每个结点的左、右子树深度之差的绝对值不大于1，这种平衡状态的二叉查找树。实现方法：平衡旋转技术

11 m阶B树除根和叶子外，每个结点子树在[m/2,m] B+树:每个结点n个关键字，n个指针 9.2.3 键树
9.2.2 B树和B+树 B树：每个结点n个关键字，n+1个指针 m阶B树除根和叶子外，每个结点子树在[m/2,m] B+树:每个结点n个关键字，n个指针 m阶B+ 树除根和叶子外，每个结点子树在[m/2,m] 9.2.3 键树 键树、数字查找树（Digital search trees） 结点不是关键字，而是关键字中的一个字符,从根到叶子结点的路径（根、叶子本身除外）才是关键字 键树的存储（双链树） 采用孩子－兄弟的存储方法。

12 四阶B树

13 四阶B+树

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

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

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

17 9.3.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为递增序列,有三种取法：p(i,k)探测函数 a) di＝1,2,...,m-1 b) di=12，-12，22，－22...，k2，－k2 （k<=m/2） c) di＝伪随机序列 例 设一组关键字(07,15,20,31,48,53,64,76, 82,99)试构建哈希表 取m＝11，p=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

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

19 9.3.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)

20 链地址法存储结构： typedef struct { ElemType data; LHNode *next; //记录数
}LHNode,*LHNodeptr; LHNodeptr *elem; int count; //记录数 int sizeindex; //哈希表容量 } LHashTable; Status SearchHash(LHashTable H,KeyType kval, LHNodeptr &p,int &c) Status InsertHash(HashTable &H,ElemType e)

21 平均查找长度对比 线形探测散列、二次探测散列、链地址法构建哈希函数比较 （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

22 平均查找长度与α的关系 查找成功时平均查找长度： 查找不成功时平均查找长度 ASLsl（α）≈(1+1/(1-α))/2 线性探测
ASLsr（α）≈-1/αln(1-α) 二次探测 ASLsc（α）≈1+α/ 链地址 查找不成功时平均查找长度 ASLul（α）≈(1+1/(1-α)2)/2 ASLsr（α）≈1/ (1-α) ASLsc（α）≈α+e-α

23 9.3.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

24 谢 谢

25 顺序表查找 int Search_Seq(SSTable ST, KeyType key) {//设监视哨
// 若找到，则函数值为该元素在表中的位置，否则为0。 int i=0; ST.elem[0].key=key; // "哨兵" for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq

26 折半查找 int Search_Bin ( SSTable ST, KeyType key ) {
// 若找到，则函数值为该元素在表中的位置，否则为0。 low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if (EQ(key , ST.elem[mid].key)) return mid;// 找到待查元素 else if (LT(key, ST.elem[mid].key)) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin

27 索引查找 int Search_Idx ( SSTable ST, indexTable ID, KeyType kval ) {
low = 1; high = ID.length; found = FALSE; if (kval>ID.elem[high].key) return 0; // 给定值kval大于查找表中所有关键字 while ( low <=high && !found ) { // 折半查找索引表，确定记录查找区间 mid = (low+high)/2; if ( kval < ID.elem[mid].key ) high = mid - 1; else if ( kval > ID.elem[mid].key ) low = mid +1; else { found = TRUE; low = mid; } }//while s = ID.elem[low].stadr; // 经索引表查找后，下一步的查找范围定位在第low块 if ( low < ID.length ) t = ID.elem[low +1].stadr-1; else t = ST.length; // s和t为在ST表进行查找的下界和上界，若不是最后一块，则上界为“下一块的起始位置之前” if ( ST.elem[t].key== kval ) return t; else { // 在ST.elem[s] 至ST.elem[t-1]的区间内进行顺序查找 ST.elem[0] = ST.elem[t]; ST.elem[t].key = kval; // 设置监视哨 for ( k=s; ST.elem[k].key !=kval; k++ ) ; ST.elem[t] = ST.elem[0]; // 恢复暂存值 if ( k != t ) return k; else return 0; } // else } // Search_Idx

28 二叉排序树查找 BiTree SearchBST (BiTree T, KeyType key) { // 算法9.5a if (!T || EQ(key, T->data.key)) return T; // 查找结束 if (LT(key, T->data.key)) return SearchBST(T->lchild, key else return SearchBST(T->rchild, key); // 在右子树查找 } // SearchBST Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) { if (!T) { p = f; return FALSE; } // 查找不成功 if (EQ(key, T->data.key)) { p = T; return TRUE; } // 查找成功 if (LT(key, T->data.key)) return SearchBST(T->lchild, key, T, p); // 在左子树查找 else return SearchBST(T->rchild, key, T, p); // 在右子树查找 查到空树或对应值结束

29 二叉排序树插入 Status InsertBST(BiTree &T, ElemType e) { // 算法9.6
// 当二叉排序树T中不存在关键字等于e.key的数据元素时， // 插入e并返回TRUE，否则返回FALSE BiTree p,s; if (SearchBST(T, e.key, NULL, p)) return FALSE; s = (BiTree)malloc(sizeof(BiTNode)); s->data = e; s->lchild = s->rchild = NULL; if (!p) T = s; // 插入 s 为新的根结点 else if (LT(e.key, p->data.key)) p->lchild=s; // 插入s为左孩子 else p->rchild = s; // 插入 s 为右孩子 return TRUE; } // Insert BST

30 删除结点 Status DeleteBST(BiTree &T, KeyType key) { // 算法9.7 if (!T) return FALSE; // 不存在等于key的数据元素 if (EQ(key, T->data.key)) return Delete(T); if (LT(key, T->data.key)) return DeleteBST(T->lchild, key); else return DeleteBST(T->rchild, key); } // DeleteBST Status Delete(BiTree &p) { // 算法9.8 if (!p->rchild) { q = p; p = p->lchild; free(q); else if (!p->lchild) { q = p; p = p->rchild; free(q);} else { // 左右子树均不空 q = p; s = p->lchild; while (s->rchild) { q = s; s = s->rchild; } p->data = s->data; if (q != p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); }//else return TRUE; } // Delete 什么情况下会出现 q==p?

31 开放定址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

32 开放定址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

33 链地址Hash查找 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;} }

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