第八章 查找表 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静态查找表 8.2.1顺序查找 算法8.1 例8.1 在顺序查找表中查找成功和失败 平均查找长度
int SeqSearch(SSTable ST, KeyType kval) 设监视哨 例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

4 折半查找（binary Search）：二分查找。 例8.2 利用二分查找在顺序有序表中查找。
8.2.2折半查找 折半查找（binary Search）：二分查找。 例8.2 利用二分查找在顺序有序表中查找。 算法8.2 Int Search_Bin(SStable ST,KeyType kval) ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(20+21*2+…+2h-1*h)Pi=1/n∑1h2i-1*i 令i=t+1 ;S=∑1h2i-1*i=2∑1h2i-2*i=2∑0h-12t-1*(t+1) =2∑0h-12t-1 *t+ 2∑0h-12t-1 =2(∑1h2t-1 *t-2h-1 *h+20-1 *0)+ ∑0h-12t =2(S-2h-1 *h)+2h-1 S=2h *h-2h+1=(n+1)log2(n+1)-(n+1)+1==(n+1)log2(n+1)-n ASLbs=1/n*S=(n+1)/nlog2(n+1)-1

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

6 8.3动态查找表 对动态查找表进行的操作有 InitDSTable（&DT） DestroyDSTable（&DT）
SearchDSTable（DT，kval） InsertDSTable（&DT,e） * DeleteDSTable（&DT,kval） * TraverseDSTable（DT）

7 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)

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

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

10 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;

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

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

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

14 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＝伪随机序列 例 设一组关键字(07,15,20,31,48,53,64,76, 82,99)试构建哈希表 取m＝11，p=11, Hash（key）＝key mod 11

15 链地址法/拉链法（开散列方法） 将所有关键字为同义词（即具有相同的哈希函数值）的记录存贮在同一线性链表中，而哈希表中下标为i的分量存储哈希函数值为i的链表的头指针

16 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)

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

18 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;} }

19 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); //重建哈希表 }

20 线形探测散列、二次探测散列、链地址法构建哈希函数比较
（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线性

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

22 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