数据结构 C语言版第9章 查找课件.ppt

,DATA,10,65,865,数据结构,第9章 查找,学习提要,第9章 查找,本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找 动态查找表及查找算法：二叉排序树 哈希表及查找算法,学习提要（具体来讲）,.熟练掌握顺序表和有序表的查找方法。.熟练掌握二叉排序树的构造和查找方法。.掌握二叉平衡树的维护平衡方法。.理解树的特点以及它们的建树过程。.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。.掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。,基本概念,查找表 用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表 若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。,动态查找表：若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。关键字：是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。,查找：在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。,查找表的存储结构：查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。查找算法的时间效率：查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。,9.1.1.顺序查找（线性查找）静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。,9.1 静态查找表,顺序查找的基本思想：顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。,可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较效率较低。平均查找长度较大。在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。,查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。,（1）顺序查找(线性表在顺序存储结构下的顺序查找）数据结构：#define MAX_NUM 100/用于定义表的长度typedef struct int key;float info;SSTableMAX_NUM，SSItem;,每个结点包含两部分内容：Key 和info,其他信息,假设在查找表中，数据元素个数为n（nMAX_NUM），并分别存放在数组的下标变量ST1STn中。下面我们给出顺序查找的完整算法。,int seq_search(SSTable ST，int key)/在顺序表中查找关键字值等于key的记录，/若查找成功，返回该记录的位置下标序号，否则返回0 i=1;while(i=n,改进的顺序查找的算法：int Search_seq(SSTable ST,int n,int key)int i=n;ST0.key=key;while(STi.key!=key)i-;/*从表尾往前查*/return i;,监视哨,使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。,根据上述算法可知：查找成功时的平均查找次数为：ASL=(1+2+3+4+n)/n=(n+1)/2查找不成功时的比较次数为：n+1则顺序查找的平均查找长度为：ASL=(n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。缺点：平均查找长度较大。尤其当n较大时，不宜采用这种查找方法。,（2）线性表在链式存储结构下的顺序查找 链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示：typedef struct node keytype key;/结点的关键字类型 anytype otheritem;/结点的其他成分 struct node*next;/指向链表结点的指针 Link_Node,*Link;,将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。,Link_Node*link_search(Link h,keytype k)/link为带头结点链表的头指针，查找关键字值等于k的记录，/查找成功，返回指向找到的结点的指针，查找失败返回空指针 p=h-next;while(p!=NULL),9.1.2 折半查找（二分法查找）折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或隆序）排列，也就是说折半查找只适用于对有序顺序表进行查找。,1.折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。,分三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,查找23和79的过程如下图：,mid=(low+high)/2不进位取整,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),2.折半查找算法 假设查找表存放在数组ST的ST1 STn中，且升序，查找关键字值为key。折半查找的主要步骤为：（1）置初始查找范围：low=1，high=n;（2）求查找范围中间项：mid=(low+high)/2（3）将指定的关键字值key与中间项STmid.key比较 若相等，查找成功，找到的数据元素为此时mid 指向的位置；若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1;,若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;（4）重复步骤（2）、（3）直到查找成功或查找范围空（lowhigh），即查找失败为止。（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。,折半查找的c语言算法程序：int Search_Bin(SSTable ST,int n,int key)int low,high,mid;low=1;high=n;while(low=high)mid=(low+high)/2;if(STmid.key=key)return(mid);/*查找成功*/else if(key STmid.key)high=mid-1;/*在前半区间继续查找*/else low=mid+1;/*在后半区间继续查找*/return(0);/*查找不成功*/,是顺序查找的一种改进方法，就是把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。,9.1.3 分块查找（索引顺序查找）,索引表,块中的最大关键字,块内第一个记录位置的指针,分块查找步骤：,查索引表，确定要找的记录在哪一块。在相应的块中查找。,例如，要找关键字为22的记录。由索引的第一项可知，要找的记录要么在第二块中，要么不存在。并获取第二块中第一个记录的位置。,9.2.1 二叉排序树和平衡二叉树9.2.1.1 二叉排序树 1.二叉排序树（二叉查找树）的概念,9.2 动态查找表,二叉排序树是一种常用的动态查找表，下面首先给出它的非递归形式。二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：（1）任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。（2）任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。,二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质：（1）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。（2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。（3）它的左右子树都是二叉排序树。例如，由关键字值序列 10、18、3、8、12、2、7、3 构成的一棵二叉排序树如下图所示。,如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列 2，3，3，7，8，10，12，18，这是二叉排序树的一个重要特征，也正是由此将其称为“二叉排序树”。,2.二叉排序树的查找 二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，所以在二叉排序树中查找一个关键字值为k 的结点的基本思想是：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。,二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败，（2）将给定值k 与根结点的关键字值比较，若相等，则查找成功，（3）若根结点的关键字值小于给定值k，则在左子树中继续搜索，（4）否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下：,typedef struct node keytype key;anytype otheritem;struct node*lchild；struct node*rchild;Bin_Sort_Tree_Node,*Bin_Sort_Tree；二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：,Bin_Sort_Tree_Node*bt_search(Bin_Sort_Tree bt,keytype k)/在根指针为bt的二叉排序树上查找一个关键字值为k的结点，/若查找成功返回指向该结点的指针，否则返回空指针 if(bt=NULL)|(bt-key=k)return bt;else if(k key)return bt_search(bt-lchild,k);/在左子树中搜索 else return bt_search(bt-rchild,k);/在右子树中搜索,这个过程也可以用非递归算法实现，算法描述如下：Bin_Sort_Tree_Node*bt_search1(Bin_Sort_Tree bt,keytype k)p=bt;/指针p指向根结点，搜索从根结点开始 while(p!=NULL,3.二叉排序树的插入和删除 3-1.二叉排序树的插入 在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。,10、18、3、8、12、2、7、3,10,10,18,3,8,12,2,7,3,下面是二叉排序树插入操作的递归算法。void bt_insert1(Bin_Sort_Tree*bt,Bin_Sort_Tree_Node*pn)/在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点 if(*bt=NULL)*bt=pn;else if(*bt-key pn-key)bt_insert 1(,这个算法也可以用非递归的形式实现，如下所示：void bt_insert 2(Bin_Sort_Tree*bt,Bin_Sort_Tree_Node*pn)p=bt;while(p!=NULL,利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。,例如，由结点关键字序列 10、18、3、8、12、2、7、3 构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过8次的查找和插入操作，建成由这8个结点组成的二叉排序树。创建二叉排序树的算法如下：,Bin_Sort_Tree_Node*bt_bulid(Bin_Sort_Tree a,int n)/在数组a的a1an单元中存放着将要构成二叉排序树的n个结点内容bt=NULL;for(i=1;i key=ai.key;p-otheritem=ai.otheritem;p-lchile=NULL;p-rchile=NULL;bt_insert1(,3-2.二叉排序树的删除 下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：（1）若要删除的结点为叶子结点，可以直接进行删除。（2）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。,（3）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤类似。（4）若要删除结点的左右子树均非空，则首先找到要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。,9.2.1.2平衡二叉树,何谓“二叉平衡树”？,如何构造“平衡二叉树”,平衡二叉树是二叉查找树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差（平衡因子）的绝对值不大于1。,例如:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,一般地，假设由于在二叉树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况：,（1）单向右旋平衡处理：由于在*a的左子树的左子树上插入结点，使*a的平衡因子由1增至2而失去平衡，需进行一次顺时针旋转操作；(L-L型）,（2）单向左旋平衡处理：由于在*a的右子树的右子树上插入结点，使*a的平衡因子由-1减至-2而失去平衡，需进行一次逆时针旋转操作；(R-R型）,7,9,8,7,9,8,（3）双向旋转（先左后右）平衡处理：由于在*a的左子树的右子树上插入结点，使*a的平衡因子由1增至2而失去平衡，需进行两次旋转操作（先逆时针，后顺时针）；(L-R型）,（4）双向旋转（先右后左）平衡处理:由于在*a的右子树的左子树上插入结点，使*a的平衡因子由-1减至-2而失去平衡，需进行两次旋转操作（先顺时针，后逆时针）；(R-L型）,构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。,例如1:依次插入的关键字为5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向左旋转,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字 9,例2：试求按关键字序列（36，23，18，42，29，25，13，21，15，19）插入生成的平衡二叉树。,36,23,36,23,18,36,23,18,36,23,18,42,36,23,18,42,29,36,23,18,42,29,25,36,23,18,42,29,25,36,23,18,42,29,25,13,36,23,18,42,29,25,13,21,36,23,18,42,29,25,13,21,36,23,18,42,29,25,13,21,15,15,36,23,18,42,29,25,13,21,15,19,36,23,18,42,29,25,13,15,21,19,9.2.2.1 B-树,1定义,2查找过程,3插入操作,4删除操作,1B-树的定义,B-树是一种 平衡 的 多路 查找 树,主要用作文件的索引,在 m 阶的B-树上，每个非终端结点可能含有：n 个关键字 Ki（1 in）nm n+1 个指向子树的指针 Ai（0in）;,B-树的特性,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn;且 Ai-1 所指子树上所有关键字均小于Ki;Ai 所指子树上所有关键字均大于Ki;,树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少含有两棵子树;其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;,从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。,2.查找过程：,若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；,若查找不成功，则返回插入位置。,在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：,3插入,1）插入后，该结点的关键字个数nm，不修改指针;,2）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，令 s=m/2，在原结点中保留（A0，K1，。，Ks-1，As-1）；建新结点（As，Ks+1，。，Kn，An）；将Ks插入双亲结点；,3）若双亲为空，则建新的根结点。,例如:下列为 3 阶B-树,50,20 40,80,插入关键字=60,60 80,90,608090,90,50 80,60,30,40,20,30 50 80,80,30,50,和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。,4删除,是B-树的一种变型,9.2.2.2 B+树,1一棵m阶的B+树的结构特点：,有n棵子树的结点中含有n个关键字。所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；,每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；,所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。,50 96,15 50,62 78 96,71 78,84 89 96,56 62,20 26 43 50,3 8 15,sq,root,2查找过程,在查找时，不管成功与否，都必须查到叶子结点才能结束；即每次查找都是走了一条从根到叶子结点的路径,在结点内查找时，若给定值Ki，则 应继续在 Ai 所指子树中进行查找；,3插入和删除的操作,类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。,9.3.1 基本概念哈希函数，冲突,9.3 哈希（HSAE）表（散列查找）,哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。,前面介绍的静态查找表和动态查找表的特点是：为了从查找表中找到关键字值等于某个值的记录，都要经过一系列的关键字比较，以确定待查记录的存储位置或查找失败，查找所需时间总是与比较次数有关。如果将记录的存储位置与它的关键字之间建立一个确定的关系H，使每个关键字和一个唯一的存储位置对应，在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置，这就是本节将要介绍的哈希表查找方法的基本思想。,哈希函数：我们将记录的关键字值与记录的存储位置对应起来的关系H称为哈希函数，H(k)的结果称为哈希地址。哈希表：是根据哈希函数建立的表，其基本思想是：以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。当对记录进行查找时，再根据给定的关键字值，用同一个哈希函数计算出给定关键字值对应的存储地址，随后进行访问。所以哈希表即是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。,冲突：有时可能会出现不同的关键字值其哈希函数计算的哈希地址相同的情况，然而同一个存储位置不可能存储两个记录，我们将这种情况称为冲突，具有相同函数值的关键字值称为同义词。在实际应用中冲突是不可能完全避免的，人们通过实践总结出了多种减少冲突及解决冲突的方法。下面我们将简要地介绍一下。,根据关键字直接计算出元素所在位置的函数。例如：设哈希函数为：int(K/3)+1则构造 01、02、05、09、11、13、16、19、21、26、27、31、的散列表(哈希表）为：,哈希函数：,冲突：两个不同的关键字具有相同的存储位置。,为了有效地使用散列技术，需要解决两方面的问题：（1）构造好的哈希函数，使冲突的现象尽可能的少；（2）设计有效的解决冲突的方法。,二、构造哈希函数的方法,好的哈希函数应能使任意一个关键字得到一个随机的地址，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。对数字的关键字可有下列构造方法:,若是非数字关键字，则需先对其进行数字化处理。,1.直接定址法,3.平方取中法,5.除留余数法,4.折叠法,6.随机数法,2.数字分析法,哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b,例见P253。此法中：地址集合的大小=关键字集合的大小不会产生冲突。但实际使用很少。,1.直接定址法,此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。,2.数字分析法,假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,例见P254。关键字为8位十进制数,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。,3.平方取中法,此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。,例见P255图9.23,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,4.折叠法,此方法适合于:关键字的数字位数特别多。,国际标准图书编号：0-442-20586-4以其为关键字建立哈希表。,5864,4220,04,+,10088,H(key)=0088,5864,0224,04,+,6092,H(key)=6092,间界叠加,移位叠加,5.除留余数法,设定哈希函数为:H(key)=key MOD p 其中，pm(表长)并且 p 应为不大于 m 的素数以减少冲突的发生。,给定一组关键字为:12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3,例如：,为什么要对 p 加限制？,可见，因 p 可被 3整除,所以所有含3的倍数的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。,6.随机数法,设定哈希函数为:H(key)=Random(key)其中，Random 为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,三、处理冲突的方法,“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址,2.再哈希法,3.链地址法,1.开放定址法,4.建立一个公共溢出区,为产生冲突的地址 H(key)求得一个地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s,1.开放定址法,对增量 di 有三种取法：,1)线性探测再散列 di=c i 最简单的情况 c=12)平方探测再散列 di=12,-12,22,-22,3)随机探测再散列 di 是一组伪随机数列,即：产生的 Hi 均不相同，且所产生的 Hi 值能覆盖哈希表中所有 地址。,注意：增量 di 应具有“完备性”,1.开放定址法,设散列函数 H（k）=k MOD m（m为表长,设m=11)若发生冲突，设发生冲突的地址为 p,则沿着一个探查序列逐个探查，那么，探查的地址序列为P+1,P+2,P+3,m-1,0,1,P-1.,1.开放定址法,设散列函数 H（K）=K MOD m（m为表长）若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi=(H(K)+di)MOD m(di=1,2,m-1，i=1,2,F(F=m-1),0 1 2 3 4 5 6 7 8 9 10,设散列函数 H(k)=k MOD 11求：60、17、29、38在散列表中的位置。,H(60)=60 mod 11=5 H(17)=17 mod 11=6H(29)=29 mod 11=7H(38)=38 mod 11=5（冲突）H(38+1)=（5+1）mod 11=6（冲突）H(38+2)=（5+2）mod 11=7（冲突）H(38+3)=（5+3）mod 11=8,按开放地址法所建的散列表的散列查找算法：#difine M 100int h(int k)return(k%97);int SearchHase(int t,int k)int i,j=0;i=h(K);/*求得哈希地址*/while(jM/*查找成功*/else return(-1)/*查找不成功*/,例如:关键字集合 19,01,23,14,55,68,11,82,36,设定哈希函数 H(key)=key MOD 11(哈希表长=11),19,01,23,14,55,68,19,01,23,14,68,若采用线性探测再散列处理冲突,若采用二次探测再散列处理冲突,11,82,36,55,11,82,1 1 2 1 3 6 2 5 1,36,Hi=RHi(key)I=1,2,k,在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。,2.再哈希法,RHi(key)均是不同的哈希函数,3.链地址法链地址法解决冲突的方法：把具有相同散列地址的键值存放在同一个链表中，称为同义词链表。优点：插入、删除方便，缺点：占用存储空间多。,例 一组关键字为（21，14，19，58，65，32，72）H(K)=K MOD 11,ASL=(1*4+2*2+3*1)/7=11/7,4.建立一个公共溢出区,将发生冲突的关键字填入溢出区,查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:,四、哈希表的查找,对于给定值 K,计算哈希地址 i=H(K),若 ri=NULL 则查找不成功,若 ri.key=K 则查找成功,否则“求下一地址 Hi”，直至 rHi=NULL(查找不成功)或 rHi.key=K(查找成功)为止。,决定哈希表查找的ASL的因素：,哈希表查找的分析:,从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。,1)选用的哈希函数;2)选用的处理冲突的方法;3)哈希表饱和的程度，装填因子=n/m 值的大小（n记录数，m表的长度）,哈希表的ASL是处理冲突方法和装载因子的函数。,装填因子越小，表中填入的记录就越少，发生冲突的可能性就会小，反之，表中已填入的记录越多，再填充记录时，发生冲突的可能性就越大，则查找时进行关键字的比较次数就越多。,1.顺序表和有序表的查找方法及其平均查找长度的计算方法。,2.熟练掌握二叉排序树的构造和查找方法。,4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。,3.理解B-树，B+树和键树的特点以及它们的建树和查找的过程。,小结：,