《《数据结构及应用算法》第八章查找表》由会员分享，可在线阅读，更多相关《《数据结构及应用算法》第八章查找表（22页珍藏版）》请在金锄头文库上搜索。
1、第八章 查找表,8.1静态查找表 8.2动态查找表 8.3哈希表及其查找,查找表： 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 对查找表的操作有 查找某个“特定”的元素是否在表中。 查找某个“特点”的元素的各种属性。 在查找表中插入一个元素。 在查找表中删除一个元素 静态查找表、动态查找表 关键字 数据元素中的某个数据项值。可以表示一个数据元素，如可以唯一表示，则为主关键字（primary key）。 查找 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。若找到表示查找成功，返回该元素详细信息或在查找表中的位置；负责返回NULL,8.1静态查找表,8.1.1顺序
2、查找 算法8.1 int Search_Seq(SSTable ST, KeyType kval) 设监视哨 例8.1 在顺序查找表中查找成功和失败 平均查找长度 查找过程中先后和给定值进行比较的关键字的个数的期望值 ASLPiCi Pi1 i1，2，。n Cini1 Pi1/n ASLss1/n（ni1）=(n+1)/2,8.1.2折半查找折半查找（binary Search）：二分查找。 例8.2 利用二分查找在顺序有序表中查找。 算法8.2 Int Search_Bin(SStable ST,KeyType kval) ASLbs（n1）/nlog(n+1)-1 ASLbs=(20+21
3、*2+2h-1*h)Pi=1/n1h2i-1*i 令i=t+1 ;S=1h2i-1*i=21h2i-2*i=20h-12t-1*(t+1) =20h-12t-1 *t+ 20h-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,又称索引顺序查找 介于顺序查和折半查找之间。适合于关键字分块有序 typedef struct KeyType key;int
4、stadr; indexItem; typedef structindexItem *elem;int length; indexTable; 算法8.3 Search_Idx(SSTable ST,indexTable ID, KeyT kval) 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)log2(b+1)-1+(n/b+1)/2,8.1.3分块查找,8.2动态查找表,对动态查找表进行的操作有 InitDSTable（&DT） DestroyDSTable（&DT） SearchDSTable（DT，kval） InsertDSTable（&DT,e）
5、 * DeleteDSTable（&DT,kval） * TraverseDSTable（DT）,8.2.1二叉查找树 查找树、二叉查找树 通过合根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。二叉排序树又称二叉查找树。 例8.4二叉查找树的查询过程。 算法8.4 bool Search_BST(BiTree T,KeyType kval, BiTree &p,BiTree &f) 二叉查找树的插入算法 算法8.5 bool Insert_BST(BiTree &T, ElemType e),删除结点的处理方法 若是叶子结点，直接删除 只有一个孩子，则将其
6、孩子直接挂到其双亲上。 有两个孩子，找左孩子中最大的一个元素，代替被删除结点，最大元素肯定只有一个孩子，按2）处理删除最大元素 算法8.6 bool Delete_BST(BiTree &T, KeyType kval) 二叉查找树的平均查找长度 p（n）2（n1）/n *logn+C 二叉平衡（查找）树 树中每个结点的左、右子树深度之差的绝对值不大于1，这种平衡状态的二叉查找树。实现方法：平衡旋转技术,8.2.2键树 键树、数字查找树（Digital search trees） 结点不是关键字，而是关键字中的一个字符,从根到叶子结点的路径（根、叶子本身除外）才是关键字 例8.5 统计正文中某
7、些单词出现的次数 算法8.7 void setmatch(DLTree root,char line) 算法8.8 bool Search_DLTree(DLTree rt, int j, int &k) 算法8.9 双链树的创建 bool Insert_DLTree(DLTree &root,KeysType K,int &n) 键树的存储（双链树） 采用孩子兄弟的存储方法。,Const MAXKEYLEN16； Const LINESIZE80； typedef struct char chMAXKEYLEN;int num; KeysType; typedef enumLEAF, BRA
8、NCHNodeKind; typedef structchar symbol;struct DLTNode *next;NodeKind kind;Unionstruct DLTNode *first;int idx; DLTNode,*DLTree;,8.3哈希表及其查找,8.3.1哈希表的定义和特点 哈希表 在记录的关键字和其存储位置（数组下标）之间设定一个确定的对应关系f，关键字为kval的记录存储在f（kval）位置处 哈希表的装填系数 n/m 其中m为哈希表分配空间 n为填入的记录数。 实际应用：0.650.85,哈希函数 可以对关键字做简单的算术或逻辑运算。 例8.6：i=f1(k
9、ey)=key 例8.7：i=f2(key)=(关键字的第一个字母ASCII码)(A的 ASCII码) 例8.8：i=f3(key)=(f2(关键字的第一个字母)+ f2(关键字的最后一个字母)/2 冲突 若出现f（key1）f（key2）的现象称冲突。没有冲突的哈希函数很少存在，只能尽量均匀。称“再散列”。在建哈希表时，不仅要设定哈希函数，还要设定处理冲突的方法 哈希表的严格定义： 根据设定的哈希函数和处理冲突的方法为一组记录建立的一种存储结构，哈希函数又称散列函数。构建哈希表又称散列技术,8.3.2构造哈希函数的方法 除留余数法 Hash（key）key mod p （p=m） 其中p为不
10、大于m且最接近m 的最大素数。如m=1000 p=997 平方取中法 对一个关键字平方，取中间几位，中间几位和每位数字都有关系，不易冲突 折叠法 将关键字分割成位数相同的几部分（最后一部分可以不同），然后几部分相加舍进位作为哈希地址。 有移位叠加、间界叠加,8.3.3处理冲突的方法 开放定址法 从哈希地址Hash(key)求得一个地址序列H1、H2 Hk,0=k=m-1, 即H1Hk-1都不空，直到Hk为空为止。若哈希表未满，必能找到km，使Hk空。Hi=(Hash(key)+di)mod m i=1,2,.,k k=m-1di为递增序列,有三种取法a) di1,2,.,m-1b) di=12
11、，-12，22，22.，k2，k2 （k=m/2）c) di伪随机序列 例8.9 设一组关键字(07,15,20,31,48,53,64,76, 82,99)试构建哈希表取m11，p=11, Hash（key）key mod 11,链地址法 将所有关键字为同义词（即具有相同的哈希函数值）的记录存贮在同一线性链表中，而哈希表中下标为i的分量存储哈希函数值为i的链表的头指针,开放定址法的存储结构 int hashsize=997,. typedef struct ElemType *elem; /记录存储基址int count; /记录数int sizeindex; /哈希表容量 HashTabl
12、e; const SUCCESS1； const UNSUCCESS0； const DUPLICATE-1； 算法8.10 Status SearchHash(HashTable H,KeyType kval,int &p,int &c) 算法8.11 Status InsertHash(HashTable &H,ElemType e),8.3.4哈希函数的查找及其性能分析,链地址法存储结构： typedef struct ElemType data; LHNode *next; /记录数 LHNode,*LHNodeptr; typedef struct LHNodeptr *elem;
13、int count; /记录数int sizeindex; /哈希表容量 LHashTable;,Status SearchHash(LHashTable H,KeyType kval, LHNodeptr ,Status InsertHash(HashTable /重建哈希表 ,线形探测散列、二次探测散列、链地址法构建哈希函数比较 （07，15，20，31，48，53，64，76，82，99） m=11 n=10 p=11 0.91,* 表示m=13 p=130.77,查找成功时平均查找长度： ASLsl（）(1+1/(1-)/2 ASLsr（）-1/ln(1-) ASLsc（）1+/2 查找不成功时平均查找长度 ASLul（）(1+1/(1-)2)/2 ASLsr（）1/ (1-) ASLsc（）+e-,C语言中编译程序使用的符号表，操作有 对给定的名字查是否已在表中。 填入新的名字。 对给定的名字访问其有关信息。 对给定名字更新和填写其信息。 删除一些无用的名字 例8.10 C语言32关键字的查找表希望ASL40 考虑m4j3 取m43 ，p41 hash（key）（key的第一个字符序号）100（key的最后一个字符序号） mod 41 实际ASL=2.5,8.3.5哈希表的应用举例,
