《数据结构查找》PPT课件.ppt

数据结构课程的内容,9.1 基本概念9.2 静态查找表9.3 动态查找表9.4 哈希表,第9章 查找,教材第8、11和12章省略，因操作系统课程会涉及。,9.1 基本概念,若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）,查找表查 找查找成功查找不成功静态查找动态查找关键字主关键字次关键字,由同一类型的数据元素（或记录）构成的集合。,查询(Searching)特定元素是否在表中。,只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录(预先确定的记录的某种标志)可以唯一标识一个记录的关键字,例如“学号”,例如“女”,是一种数据结构,识别若干记录的关键字,（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。,（3)有哪些查找方法？查找方法取决于表中数据的排列方式;,讨论：,（1）查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。,例如查字典,针对静态查找表和动态查找表的查找方法也有所不同。,“特定的”=关键字,（4）如何评估查找方法的优劣？,明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。,其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。,统计意义上的数学期望值,物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。,显然，ASL值越小，时间效率越高。,针对静态查找表的查找算法主要有：,9.2 静态查找表,静态查找表的抽象数据类型参见教材P216。,一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）,一、顺序查找（Linear search，又称线性查找）,（1）顺序表的机内存储结构：,typedef struct ElemType*elem;/表基址，0号单元留空。表容量为全部元素 int length;/表长，即表中数据元素个数SSTable;,顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？见下页之例或教材P216；对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！,（2）算法的实现：,技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。,例：,若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！,int Search_Seq(SSTable ST,KeyType key)/在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem0.key=key;/设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。for(i=ST.length;ST.elem i.key!=key;-i);/不要用for(i=n;i0;-i)或 for(i=1;i=n;i+)return i;/若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。/Search_Seq,返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem0.key使之结束并返回 i=0。讨论 查找效率怎样计算？用平均查找长度ASL衡量。,讨论 查不到怎么办？,讨论 如何计算ASL？,分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；查找第n个元素所需的比较次数为n；,总计全部比较次数为：12n=(1+n)n/2,未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1,这是查找成功的情况,若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL（1n）/2，时间效率为 O(n),二、折半查找（又称二分查找或对分查找）,优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL 太长，时间效率太低。,这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。,对顺序表结构如何编程实现折半查找算法？见下页之例，或见教材（P219）对单链表结构如何折半查找？无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？可借助二叉排序树来查找（属动态查找表形式）。,如何改进？,讨论 顺序查找的特点：,运算步骤：(1)low=1,high=11,mid=6，待查范围是 1,11；(2)若 ST.elemmid.key key，说明keylow,mid-1，则令：high=mid1;重算 mid；(4)若 ST.elem mid.key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elemmid.key=key（2）查找不成功：highlow（意即区间长度小于0）,解：先设定3个辅助标志:low,high,mid，,折半查找举例：,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid指向待查元素所在区间的中间位置,已知如下11个元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为21 和85的数据元素。,显然有：mid=(low+high)/2,讨论 若关键字不在表中，怎样得知和停止？,典型标志是：当查找范围的上界下界时停止查找。,讨论 二分查找的效率（ASL）,1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处 4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处 则第m次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素 2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。,全部比较总次数为120221322423m2m1,推导过程,三、分块查找（索引顺序查找）,这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例：,特点：块间有序，块内无序,查找步骤分两步进行：,对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw,对索引表查找的ASL,对块内查找的ASL,S为每块内部的记录个数，n/s即块的数目,例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5,特点：,一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树,9.3 动态查找表,表结构在查找过程中动态生成。,要求：,对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key 的记录。,典型的动态表二叉排序树,一、二叉排序树的定义,练：下列2种图形中，哪个不是二叉排序树？,-或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。,讨论：对(a)中序遍历后的结果是什么？,二、二叉排序树的查找、插入与删除,将数据元素构造成二叉排序树的优点：查找过程与顺序结构有序表中的折半查找相似，查找效率高；中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。,注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！,这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。,45,如果待查找的关键字序列输入顺序为：（24，53，45，45，12，24，90），,24,讨论1：二叉排序树的插入和查找操作,则生成二叉排序树的过程为：,例：输入待查找的关键字序列=（45，24，53，45，12，24，90）,则生成的二叉排序树形态不同：,二叉排序树的查找&插入算法如何实现？,查找算法参见教材P228算法9.5（a）;插入算法参见教材P228算法9.5（b)_9.6;,一种“二合一”的算法如下：,BiTree SearchBST（BiTree T,KeyType key）/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if(!T)|EQ(key,Tdata.key)return(T)；/查找结束 else if LT(key,Tdata.key)/在左子树中继续查找 return(SearchBST(Tlchild,key)；else return(SearchBST(Trchild,key)；/在右子树中继续查找/SearchBST,Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree/在右子树中继续查找/SearchBST,Status InsertBST(BiTree&T,ElemType e)if(!SearchBST(T,e.key,NULL,p)/查找不成功 s=(BiTree)malloc(sizeof(BiTNode)；sdata=e；slchild=srchild=NULL；/建立新结点 if(!p)T=s；/T为空树 else if LT(e.key,pdata.key)plchild=s；/被插结点*s为左孩子 else prchild=s；/被插结点*s为右孩子 return TRUE；else return FALSE；/树中已有关键字相同的结点，不再插入/Insert BST,对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。（对链表进行删除操作是很方便的）,讨论2：二叉排序树的删除操作,如何删除一个结点？假设：*p表示被删结点的指针；PL和PR 分别表示*P的左、右孩子指针；*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：PR 为*S 的右子树；SL 为 Q（*S的双亲结点）右孩子,*p为叶子：删除此结点时，直接修改*f指针域即可；*p只有一棵子树（或左或右）：令PL或PR为*f的左孩子即可；*p有两棵子树：情况最复杂,*p有两棵子树时，如何进行删除操作？,分析：设删除前的中序遍历序列为：.s p PR./显然p的直接前驱是s希望删除p后，其它元素的相对位置不变。有两种解决方法：法1：令*p的左子树为*f的左子树，*p的右子树为*s的右子树；/即FL=PL;FR=PR;法2：令*s代替*p/*s为*p左子树最右下的叶子 见课本P230 图9.9,法2:,法1:,例：请从下面的二叉排序树中删除结点P。,S,四、平衡二叉树,平衡二叉树又称AVL树，它是具有如下性质的二叉树：,为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样，可以得到AVL树的其它性质：,即|左子树深度-右子树深度|1,左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值 1,(a)平衡树(b)不平衡树,例：判断下列二叉树是否AVL树？,任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；,对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。,1,1,-1,-1,2,1,-1,如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。,现分别介绍这四种平衡旋转。,平衡旋转可以归纳为四类：LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转,若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）,1）LL平衡旋转：,若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）,2）RR平衡旋转：,若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）,3）LR平衡旋转：,若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）,4）RL平衡旋转：,例：请将下面序列构成一棵平衡二叉排序树：（13，24，37，90，53）,013,-113,-124,-213,需要RR平衡旋转(绕B逆转,B为根）,-124,-137,190,-237,需要RL平衡旋转(绕C先顺后逆）,9.4 哈希查找表,一、哈希表的概念二、哈希函数的构造方法三、冲突处理方法四、哈希表的查找及分析,一、哈希表的概念,哈希表：即散列存储结构。散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！,例1：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V01单元；将2001011810202的所有信息存入V02单元；将2001011810231的所有信息存入V31单元。,欲查找学号为2001011810216的信息，便可直接访问V16！,例2：,有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）k，请画出存储结构图。（注：H（k）k称为散列函数）,解：根据散列函数H（k）k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，对应散列存储表（哈希表）如下：,讨论：如何进行散列查找？根据存储时用到的散列函数H(k)表达式，迅即可查到结果！例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。,14,11,9,23,25,39,缺点：空间效率低！,选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。,通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。,若干术语,哈希方法(杂凑法)哈希函数(杂凑函数)哈 希 表(杂凑表)冲 突,哈希方法中使用的转换函数称为哈希函数(杂凑函数),按上述思想构造的表称为哈希表(杂凑表),有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=k mod 7,通过哈希函数对6个元素建立哈希表：,25,39,23,9,14,冲突现象举例：,6个元素用7个地址应该足够!,H(14)=14%7=0,11,H(25)=25%7=4H(11)=11%7=4,有冲突！,所以，哈希方法必须解决以下两个问题：,1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。,2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。,在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。,二、哈希函数的构造方法,常用的哈希函数构造方法有：,直接定址法 除留余数法 数字分析法 平方取中法 折叠法 随机数法,要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。,Hash(key)=akey+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。,例：关键码集合为100，300，500，700，800，900，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：,1、直接定址法,Hash(key)=key mod p(p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取pm且为质数（也可以是不包含小于20质因子的合数）。自练：自测卷简答题第4小题,2、除留余数法,特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。,3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9,例：有一组（例如80个）关键码，其样式如下：,3、数字分析法,讨论：第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。,位号：,若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。,特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。,5、折叠法,特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。适用于：每一位上各符号出现概率大致相同的情况。法1：移位法 将各部分的最后一位对齐相加。法2：间界叠加法从一端向另一端沿分割界来回折叠后,最后一位对齐相加。例：元素42751896,用法1：42751896=1041 用法2：427 518 96 724+518+69=1311,4、平方取中法,6、随机数法,Hash(key)=random(key)(random为随机函数)适用于：关键字长度不等的情况。造表和查找都很方便。,执行速度（即计算哈希函数所需时间）；关键字的长度；哈希表的大小；关键字的分布情况；查找频率。,小结：构造哈希函数的原则：,三、冲突处理方法,常见的冲突处理方法有：,开放定址法（开地址法）链地址法（拉链法）再哈希法（双哈希函数法）建立一个公共溢出区,1、开放定址法（开地址法）,设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。,具体实现：,Hi=(Hash(key)+di)mod m(1i m)其中：Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，m-1，且di=i,(1)线性探测法,含义：一旦冲突，就找附近（下一个）空地址存入。,关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；拟用线性探测法处理冲突。建哈希表如下：,解释：47、7（以及11、16、92）均是由哈希函数得到的没有冲突的哈希地址；,0 1 2 3 4 5 6 7 8 9 10,例：,29,22,8,3,Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1)mod 11=8，哈希地址8为空，因此将29存入。,另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。,其中3 还连续移动了两次（二次聚集）,线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。,讨论：,仍举上例，改用二次探测法处理冲突，建表如下：,0 1 2 3 4 5 6 7 8 9 10,注：只有3这个关键码的冲突处理与上例不同，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+12)mod 11=4，仍然冲突；H2=(Hash(3)-12)mod 11=2，找到空的哈希地址，存入。,(2)二次探测法,Hi=(Hash(key)di)mod m其中：Hash(key)为哈希函数 m为哈希表长度，m要求是某个4k+3的质数；di为增量序列 12，-12，22，-22，q2,(3)若di伪随机序列，就称为伪随机探测法,2、链地址法(拉链法）,基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。,设 47,7,29,11,16,92,22,8,3,50,37,89 的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，则建表如右图所示。,例：,注：有冲突的元素可以插在表尾,也可以插在表头,3、再哈希法（双哈希函数法）,Hi=RHi(key)i=1,2,，kRHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。优点：不易产生聚集；缺点：增加了计算时间。,4.建立一个公共溢出区,思路：除设立哈希基本表外，另设立一个溢出向量表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。,讨论：,“冲突”是不是特别讨厌？答：不一定！正因为有冲突，使得文件加密后无法破译（不可逆，是单向散列函数，可用于数字签名）。利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。,本章小结,重点：顺序查找、二分查找、分块查找、二叉排序树上查找、B树以及散列表上查找的基本思想和算法实现。,难点：二叉排序树的删除算法,