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

1065865ABCDEFGDATA1065865ABCDEFG数据结构第9章查找1学习提要学习提要第第9章章 查找查找 本章中介绍下列主要内容：本章中介绍下列主要内容：静态查找表及查找算法：静态查找表及查找算法：顺序查找顺序查找、折半查找折半查找 动态查找表及查找算法：动态查找表及查找算法：二叉排序树二叉排序树 哈希表哈希表及查找算法及查找算法学习提要第9章查找本章中介绍下列主要内容：2学习提要（具体来讲）学习提要（具体来讲）.熟练掌握顺序表和有序表的查找方法。熟练掌握顺序表和有序表的查找方法。.熟练掌握二叉排序树的构造和查找方法。熟练掌握二叉排序树的构造和查找方法。.掌握二叉平衡树的维护平衡方法。掌握二叉平衡树的维护平衡方法。.理解树的特点以及它们的建树过程。理解树的特点以及它们的建树过程。.熟熟练练掌掌握握哈哈希希表表的的构构造造方方法法，深深刻刻理理解解哈哈希表与其它结构的表的实质性的差别。希表与其它结构的表的实质性的差别。.掌掌握握描描述述查查找找过过程程的的判判定定树树的的构构造造方方法法，以以及及按按定定义义计计算算各各种种查查找找方方法法在在等等概概率率情情况况下下查找成功时的平均查找长度。查找成功时的平均查找长度。学习提要（具体来讲）.熟练掌握顺序表和有序表的查找方法。3基本概念基本概念 查查找找表表 用用于于查查找找的的数数据据元元素素集集合合称称为为查查找找表表。查查找找表表由由同同一一类类型型的的数数据据元元素素（或或记记录录）构成。构成。静静态态查查找找表表 若若只只对对查查找找表表进进行行如如下下两两种种操操作作：（1）在在查查找找表表中中查查看看某某个个特特定定的的数数据据元元素素是是否否在在查查找找表表中中，（2）检检索索某某个个特特定定元元素素的的各各种种属属性性，则则称称这这类类查查找找表表为为静静态态查查找找表表。静静态态查查找找表表在在查查找找过过程程中中查查找找表表本本身身不不发发生生变变化化。对静态查找表进行的查找操作称为对静态查找表进行的查找操作称为静态查找静态查找。基本概念查找表用于查找的数据元素集合称为4 动动态态查查找找表表：若若在在查查找找过过程程中中可可以以将将查查找找表表中中不不存存在在的的数数据据元元素素插插入入，或或者者从从查查找找表表中中删删除除某某个个数数据据元元素素，则则称称这这类类查查找找表表为为动动态态查查找找表表。动动态态查查找找表表在在查查找找过过程程中中查查找找表表可可能能会会发发生生变变化化。对对动动态态查查找找表表进进行行的的查查找找操操作作称称为为动态查找动态查找。关关键键字字：是是数数据据元元素素中中的的某某个个数数据据项项。唯唯一一能能标标识识数数据据元元素素（或或记记录录）的的关关键键字字，即即每每个个元元素素的的关关键键字字值值互互不不相相同同，我我们们称称这这种种关关键键字字为为主主关关键键字字；若若查查找找表表中中某某些些元元素素的的关关键键字字值值相相同同，称称这这种种关关键键字字为为次次关关键键字字。例例如如，银银行行帐帐户户中中的的帐帐号号是是主主关关键键字字，而而姓姓名名是是次次关关键键字。字。动态查找表：若在查找过程中可以将查找表中不5 查查找找：在在数数据据元元素素集集合合中中查查找找满满足足某某种种条条件件的的数数据据元元素素的的过过程程称称为为查查找找。最最简简单单且且最最常常用用的的查查找找条条件件是是“关关键键字字值值等等于于某某个个给给定定值值”，在在查查找找表表搜搜索索关关键键字字等等于于给给定定值值的的数数据据元元素素（或或记记录录）。若若表表中中存存在在这这样样的的记记录录，则则称称查查找找成成功功，此此时时的的查查找找结结果果应应给给出出找找到到记记录录的的全全部部信信息息或或指指示示找找到到记记录录的的存存储储位位置置；若若表表中中不不存存在在关关键键字字等等于于给给定定值值的的记记录录，则则称称查查找找不不成成功功，此此时时查查找找的的结结果果可可以以给给出出一一个个空空记记录录或或空空指指针针。若若按按主主关关键键字字查查找找，查查找找结结果果是是唯唯一一的的；若若按按次次关关键键字字查查找找，结结果果可可能能是是多多个个记记录录，即即结果可能不唯一。结果可能不唯一。查找：在数据元素集合中查找满足某种条件的数6 查查找找表表的的存存储储结结构构：查查找找表表是是一一种种非非常常灵灵活活的的数数据据结结构构，对对于于不不同同的的存存储储结结构构，其其查查找找方方法法不不同同。为为了了提提高高查查找找速速度度，有有时时会会采采用用一一些些特特殊殊的的存存储储结结构构。本本章章将将介介绍绍以以线线性性结结构构、树树型型结构结构及及哈希表结构哈希表结构为存储结构的各种查找算法。为存储结构的各种查找算法。查查找找算算法法的的时时间间效效率率：查查找找过过程程的的主主要要操操作作是是关关键键字字的的比比较较，所所以以通通常常以以“平平均均比比较较次次数数”来衡量查找算法的时间效率。来衡量查找算法的时间效率。查找表的存储结构：查找表是一种非常灵活的数据结构，对于不同79.1.1.顺序查找（线性查找）顺序查找（线性查找）静静态态查查找找是是指指在在静静态态查查找找表表上上进进行行的的查查找找操操作作，在在查查找找表表中中查查找找满满足足条条件件的的数数据据元元素素的的存存储储位位置置或或各各种种属属性性。本本节节将将讨讨论论以以线线性性结结构构表示的静态查找表及相应的查找算法。表示的静态查找表及相应的查找算法。9.1 静态查找表静态查找表9.1.1.顺序查找（线性查找）9.1静态查找表8顺序查找的基本思想顺序查找的基本思想：顺顺序序查查找找是是一一种种最最简简单单的的查查找找方方法法。其其基基本本思思想想是是将将查查找找表表作作为为一一个个线线性性表表，可可以以是是顺顺序序表表，也也可可以以是是链链表表，依依次次用用查查找找条条件件中中给给定定的的值值与与查查找找表表中中数数据据元元素素的的关关键键字字值值进进行行比比较较，若若某某个个记记录录的的关关键键字字值值与与给给定定值值相相等等，则则查查找找成成功功，返返回回该该记记录录的的存存储储位位置置，反反之之，若若直直到到最最后后一一个个记记录录，其其关关键键字字值值与与给给定定值值均均不不相相等等，则查找失败，返回查找失败标志。则查找失败，返回查找失败标志。顺序查找的基本思想：9 可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在在平平均均情情况况下下，大大约约要要与与表表中中一一半半以以上上元元素素进进行行比比较效率较低。平均查找长度较大。较效率较低。平均查找长度较大。在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。查找过程：查找过程：对对给给定定的的一一关关键键字字K，从从线线性性表表的的一一端端开开始始，逐逐个个进进行行记记录录的的关关键键字字和和K的的比比较较，直直到到找找到到关关键键字字等等于于K的的记记录或到达表的另一端。录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。查找过程：10（1）顺序查找）顺序查找(线性表在顺序存储结构下的顺序查找）线性表在顺序存储结构下的顺序查找）数据结构：数据结构：#define MAX_NUM 100 /用于定义表的长度用于定义表的长度typedef struct int key;float info;SSTableMAX_NUM，SSItem;每个结点包含两部分每个结点包含两部分内容：内容：Key 和和info其他其他信息信息（1）顺序查找(线性表在顺序存储结构下的顺序查找）每个结11 假假 设设 在在 查查 找找 表表 中中，数数 据据 元元 素素 个个 数数 为为n（nMAX_NUM），并并分分别别存存放放在在数数组组的的下下标变量标变量ST1STn中。中。下面我们给出顺序查找的完整算法。下面我们给出顺序查找的完整算法。假设在查找表中，数据元素个数为n（nM12int seq_search(SSTable ST，int key)/在顺序表中查找关键字值等于在顺序表中查找关键字值等于key的记录，的记录，/若若查查找找成成功功，返返回回该该记记录录的的位位置置下下标标序序号号，否则返回否则返回0 i=1;while(i=n&STi.key!=key)i+;if(inext;while(p!=NULL)&(p-key!=k)p=p-next;return p;Link_Node*link_search(Link189.1.2 折半查找（二分法查找）折半查找（二分法查找）折折半半查查找找要要求求查查找找表表用用顺顺序序存存储储结结构构存存放放且且各各数数据据元元素素按按关关键键字字有有序序（升升序序或或隆隆序序）排排列列，也也就就是是说说折折半半查查找找只只适适用用于于对对有有序序顺顺序序表表进进行行查找。查找。9.1.2折半查找（二分法查找）19 1.折半查找的基本思想是折半查找的基本思想是：首首先先以以整整个个查查找找表表作作为为查查找找范范围围，用用查查找找条条件件中中给给定定值值k与与中中间间位位置置结结点点的的关关键键字字比比较较，若若相相等等，则则查查找找成成功功，否否则则，根根据据比比较较结结果果缩缩小小查查找找范范围围，如如果果k的的值值小小于于关关键键字字的的值值，根根据据查查找找表表的的有有序序性性可可知知查查找找的的数数据据元元素素只只有有可可能能在在表表的的前前半半部部分分，即即在在左左半半部部分分子子表表中中，所所以以继继续续对对左左子子表表进进行行折折半半查查找找；若若k的的值值大大于于中中间间结结点点的的关关键键字字值值，则则可可以以判判定定查查找找的的数数据据元元素素只只有有可可能能在在表表的的后后半半部部分分，即即在在右右半半部部分分子子表表中中，所所以以应应该该继继续续对对右右子子表表进进行行折折半半查查找找。每每进进行行一一次次折折半半查查找找，要要么么查查找找成成功功，结结束束查查找找，要要么么将将查查找找范范围围缩缩小小一一半半，如如此此重重复复，直直到到查查找找成成功功或或查查找找范范围围缩缩小小为为空空即查找失败为止。即查找失败为止。1.折半查找的基本思想是：20 思思想想：先先确确定定待待查查找找记记录录所所在在的的范范围围，然然后后逐逐步步缩缩小小范范围围，直直到到找找到到或或确确认认找找不不到到该该记记录录为止。为止。前前提提：必必须须在在具具有有顺顺序序存存储储结结构构的的有有序序表表中中进行进行。分三种情况：分三种情况：1 1）若中间项的值等于）若中间项的值等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；3 3）若）若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。特特点点：比比顺顺序序查查找找方方法法效效率率高高。最最坏坏的的情情况况下下，需需要要比比较较 loglog2 2n n次次。思想：先确定待查找记录所在的范围，然后逐步缩小范21查找查找23和和79的过程如下图：的过程如下图：mid=(low+high)/2不进位取整不进位取整(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid查找23和79的过程如下图：mid=(low+high)/2222.折半查找算法折半查找算法 假假设设查查找找表表存存放放在在数数组组ST的的ST1 STn中中，且升序，查找关键字值为且升序，查找关键字值为key。折半查找的主要步骤为：折半查找的主要步骤为：（1）置初始查找范围：）置初始查找范围：low=1，high=n;（2）求查找范围中间项：）求查找范围中间项：mid=(low+high)/2 （3）将将 指指 定定 的的 关关 键键 字字 值值 key与与 中中 间间 项项STmid.key比较比较 若若相相等等，查查找找成成功功，找找到到的的数数据据元元素素为为此此时时mid 指向的位置；指向的位置；若若小小于于，查查找找范范围围的的低低端端数数据据元元素素指指针针low不变，高端数据元素指针不变，高端数据元素指针high更新为更新为mid-1;2.折半查找算法23 若若大大于于，查查找找范范围围的的高高端端数数据据元元素素指指针针high不变，低端数据元素指针不变，低端数据元素指针low更新为更新为mid+1;（4）重重复复步步骤骤（2）、（3）直直到到查查找找成成功功或或查找范围空（查找范围空（lowhigh），即查找失败为止。），即查找失败为止。（5）如如果果查查找找成成功功，返返回回找找到到元元素素的的存存放放位位置置，即即当当前前的的中中间间项项位位置置指指针针mid；否否则则返返回回查找失败标志。查找失败标志。若大于，查找范围的高端数据元素指针high不变，低端24折半查找的折半查找的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 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_search(36这个过程也可以用非递归算法实现，算法描述如下：这个过程也可以用非递归算法实现，算法描述如下：Bin_Sort_Tree_Node*bt_search1(Bin_Sort_Tree bt,keytype k)p=bt;/指针指针p指向根结点，搜索从根结点开始指向根结点，搜索从根结点开始 while(p!=NULL&p-key!=k)if(k key)p=p-lchild;else p=p-rchild;return(p);这个过程也可以用非递归算法实现，算法描述如下：373.二叉排序树的插入和删除二叉排序树的插入和删除 3-1.二叉排序树的插入二叉排序树的插入 在在一一棵棵二二叉叉排排序序树树中中插插入入一一个个结结点点可可以以用用一一个个递递归归的的过过程程实实现现，即即：若若二二叉叉排排序序树树为为空空，则则新新结结点点作作为为二二叉叉排排序序树树的的根根结结点点；否否则则，若若给给定定结结点点的的关关键键字字值值小小于于根根结结点点关关键键字字值值，则则插插入入在在左左子子树树上上；若若给给定定结结点点的的关关键键字字值值大大于于根结点的值，则插入在右子树上。根结点的值，则插入在右子树上。3.二叉排序树的插入和删除38 10、18、3、8、12、2、7、3 101018101831018381018381210183812210183812273101838122710、18、3、8、12、2、7、31010181039下面是二叉排序树插入操作的递归算法。下面是二叉排序树插入操作的递归算法。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(&(*bt-lchild),pn);else if(*bt-key key)bt_insert1(&(*bt-rchild),pn);下面是二叉排序树插入操作的递归算法。40这个算法也可以用非递归的形式实现，如下所示：这个算法也可以用非递归的形式实现，如下所示：void bt_insert 2(Bin_Sort_Tree*bt,Bin_Sort_Tree_Node*pn)p=bt;while(p!=NULL&p-key!=pn-key)q=p;if(p-key pn-key)p=p-lchild;else p=p-rchild;if(p=NULL)if(q-key pn-key)q-lchild=pn;else q-rchild=pn-key;这个算法也可以用非递归的形式实现，如下所示：41 利用二叉排序树的插入算法，可以很容易利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插入由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。操作生成一棵二叉排序树。利用二叉排序树的插入算法，可以很容易地实现创42 例如，由结点关键字序列例如，由结点关键字序列 10、18、3、8、12、2、7、3 构造二叉排序树的过程为：从构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过点作为叶子结点插入，经过8次的查找和插入操次的查找和插入操作，建成由这作，建成由这8个结点组成的二叉排序树。个结点组成的二叉排序树。创建二叉排序树的算法如下：创建二叉排序树的算法如下：例如，由结点关键字序列10、18、3、43Bin_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(&bt,p);return(bt);Bin_Sort_Tree_Node*bt_bulid(44 3-2.二叉排序树的删除二叉排序树的删除 下面分四种情况讨论一下如何确保从二叉树下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性中删除一个结点后，不会影响二叉排序树的性质：质：（1）若要删除的结点为叶子结点，可以直接）若要删除的结点为叶子结点，可以直接进行删除。进行删除。（2）若要删除结点有右子树，但无左子树，）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。可用其右子树的根结点取代要删除结点的位置。3-2.二叉排序树的删除45 （3）若若要要删删除除结结点点有有左左子子树树，但但无无右右子子树树，可可用用其其左左子子树树的的根根结结点点取取代代要要删删除除结结点点的的位位置置，与步骤与步骤类似。类似。（4）若若要要删删除除结结点点的的左左右右子子树树均均非非空空，则则首首先先找找到到要要删删除除结结点点的的右右子子树树中中关关键键字字值值最最小小的的结结点点（即即子子树树中中最最左左结结点点），利利用用上上面面的的方方法法将将该该结结点点从从右右子子树树中中删删除除，并并用用它它取取代代要要删删除除结结点点的的位位置置，这这样样处处理理的的结结果果一一定定能能够够保保证证删删除除结结点点后后二叉树的性质不变。二叉树的性质不变。（3）若要删除结点有左子树，但无右子树，可用其左469.2.1.2平衡二叉树平衡二叉树何谓何谓“二叉平衡树二叉平衡树”？如何构造如何构造“平衡二叉树平衡二叉树”9.2.1.2平衡二叉树何谓“二叉平衡树”？如何构造“平衡47平衡二叉树平衡二叉树是二叉查找树的另一种形式，其特点为：树中每个结点的树中每个结点的左、右子树深度之左、右子树深度之差（平衡因子）的绝对值不大于差（平衡因子）的绝对值不大于1 1。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树平衡二叉树是二叉查找树的另一种形式，其特点为：树中每个结点48 一般地，假设由于在二叉树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为归纳为下列四种情况：下列四种情况：一般地，假设由于在二叉树上插入结点而失去平衡的最小49（1 1）单向右旋平衡处理：）单向右旋平衡处理：由于在由于在*a*a的的左子树的左子树上插入结点，使左子树的左子树上插入结点，使*a*a的的平衡因子由平衡因子由1 1增至增至2 2而失去平衡，需进而失去平衡，需进行一次顺时针旋转操作；行一次顺时针旋转操作；(L-L(L-L型）型）（1）单向右旋平衡处理：由于在*a的左子树的左子树上插入结点50（2 2）单向左旋平衡处理：）单向左旋平衡处理：由于在由于在*a*a的的右子树的右子树上插入结点，使右子树的右子树上插入结点，使*a*a的平的平衡因子由衡因子由-1-1减至减至-2-2而失去平衡，需进行而失去平衡，需进行一次逆时针旋转操作；一次逆时针旋转操作；(R-R(R-R型）型）798798（2）单向左旋平衡处理：由于在*a的右子树的右子树上插入结点51（3 3）双向旋转（先左后右）平衡处理：）双向旋转（先左后右）平衡处理：由于在由于在*a*a的左子树的右子树上插入结点，的左子树的右子树上插入结点，使使*a*a的平衡因子由的平衡因子由1 1增至增至2 2而失去平衡，需而失去平衡，需进行两次旋转操作进行两次旋转操作（先逆时针，后顺时针）（先逆时针，后顺时针）；(L-R(L-R型）型）（3）双向旋转（先左后右）平衡处理：由于在*a的左子树的右子52（4 4）双向旋转（先右后左）平衡处理）双向旋转（先右后左）平衡处理:由由于在于在*a*a的右子树的左子树上插入结点，使的右子树的左子树上插入结点，使*a*a的平衡因子由的平衡因子由-1-1减至减至-2-2而失去平衡，需而失去平衡，需进行两次旋转操作进行两次旋转操作（先顺时针，后逆时针）（先顺时针，后逆时针）；(R-L(R-L型）型）（4）双向旋转（先右后左）平衡处理:由于在*a的右子树的左子53 构造二叉平衡（查找）树的方法是：构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如1:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转构造二叉平衡（查找）树的方法是：例如1:依次插入的关54426589642895向左旋转一次继续插入关键字 9426589642895向左旋转一次继续插入关键字955 例例2：试求按关键字序列（：试求按关键字序列（36，23，18，42，29，25，13，21，15，19）插入生成的平衡二）插入生成的平衡二叉树。叉树。例2：试求按关键字序列（36，23，18，42，5636233623183623183623184236231842293623362318362318362318423623185736231842292536231842292536231842292513362318422925132136231842292536231842292536231858362318422925132136231842292513211515362318422925132136231842292513593623184229251321151936231842292513152119362318422925132115193623184229609.2.2.1 B-树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作9.2.2.1B-树1定义2查找过程3插入操611 1B-B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树,主要用作文件的索引1B-树的定义B-树是一种平衡的多路查找树,主要62 在 m 阶的B-树上，每个非终端结点可能含有：n 个关键字关键字 Ki（1 in）nm n+1 个指向子树的指针指向子树的指针 Ai（0in）;B-树的特性在m阶的B-树上，每个非终端结点可能含有：B-树的特63非叶结点中的多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 Kn;且 Ai-1 所指子树上所有关键字均小于小于Ki;Ai 所指子树上所有关键字均大于大于Ki;非叶结点中的多个关键字均自小至大有序排列，即：K1K264树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少含有两棵子树;其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;树中所有叶子结点均不带信息，且在树中的同一层次上;65 从根结点出发，沿指针搜索结点搜索结点和在在结点内进行结点内进行顺序（或折半）查找查找 两个过程交叉进行。2.查找过程：查找过程：若查找成功查找成功，则返回指向返回指向被查关键字所在结点的指针结点的指针和关键字在结点中的位置关键字在结点中的位置；若查找不成功查找不成功，则返回插入位置返回插入位置。从根结点出发，沿指针搜索结点和在2.查找过程66在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：3插入插入1）插入后，该结点的关键字个数nm，不修改指针;在查找不成功之后，需进行插入。3插入1）插入后，该结点的关672）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，令 s=m/2，在原结点中保留 （A0，K1，。，Ks-1，As-1）；建新结点 （As，Ks+1，。，Kn，An）；将Ks插入双亲结点；3）若双亲为空，则建新的根结点。2）插入后，该结点的关键字个数n=m，3）若双亲为空，则建68例如:下列为 3 阶B-树50 20 40 80 插入关键字=60,60 80 90,60 80 90 90 50 80 60 30,40 20 30 50 808030 50例如:下列为3阶B-树5020408069 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。4删除删除和插入的考虑相反，首先必须找到待删关键字所在结点，并70是是B-树的一种变型树的一种变型9.2.2.2 B+树树是B-树的一种变型9.2.2.2B+树711一棵一棵m阶的阶的B+树的结构特点：树的结构特点：有n棵子树的结点中含有n个关键字。所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针；并且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指向含最小关键字的结点；1一棵m阶的B+树的结构特点：有n棵子树的结点中含有n72 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。每个非叶结点中的关键字Ki即为其相应指针Ai所指73 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot509615506278742查找过程查找过程 在查找时，不管成功与否，都必须查到叶子结点才能结束；即每次查找都是走了一条从根到叶子结点的路径 在结点内查找时，若给定值Ki，则 应继续在 Ai 所指子树中进行查找；2查找过程在查找时，不管成功与否，都必须查到叶子结点753插入和删除的操作插入和删除的操作类似于类似于B-树进行，即必要时，树进行，即必要时，也需要进行结点的也需要进行结点的“分裂分裂”或或“归并归并”。3插入和删除的操作类似于B-树进行，即必要时，也需要进行结769.3.1 基本概念基本概念哈希函数，冲突哈希函数，冲突9.3 哈希（哈希（HSAE）表（散列查找）表（散列查找）哈希表技术的主要目标是提高查找效率，即哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。缩短查表和填表的时间。9.3.1基本概念哈希函数，冲突9.3哈希（HSA77 前前面面介介绍绍的的静静态态查查找找表表和和动动态态查查找找表表的的特特点点是是：为为了了从从查查找找表表中中找找到到关关键键字字值值等等于于某某个个值值的的记记录录，都都要要经经过过一一系系列列的的关关键键字字比比较较，以以确确定定待待查查记记录录的的存存储储位位置置或或查查找找失失败败，查查找找所所需时间总是与需时间总是与比较次数比较次数有关。有关。如如果果将将记记录录的的存存储储位位置置与与它它的的关关键键字字之之间间建建立立一一个个确确定定的的关关系系H，使使每每个个关关键键字字和和一一个个唯唯一一的的存存储储位位置置对对应应，在在查查找找时时，只只需需要要根根据据对对应应关关系系计计算算出出给给定定的的关关键键字字值值k对对应应的的值值H(k)，就就可可以以得得到到记记录录的的存存储储位位置置，这这就就是是本本节节将将要介绍的哈希表查找方法的基本思想。要介绍的哈希表查找方法的基本思想。前面介绍的静态查找表和动态查找表的特点是：为78 哈哈希希函函数数：我我们们将将记记录录的的关关键键字字值值与与记记录录的的存存储储位位置置对对应应起起来来的的关关系系H称称为为哈哈希希函函数数，H(k)的结果称为的结果称为哈希地址哈希地址。哈哈希希表表：是是根根据据哈哈希希函函数数建建立立的的表表，其其基基本本思思想想是是：以以记记录录的的关关键键字字值值为为自自变变量量，根根据据哈哈希希函函数数，计计算算出出对对应应的的哈哈希希地地址址，并并在在此此存存储储该该记记录录的的内内容容。当当对对记记录录进进行行查查找找时时，再再根根据据给给定定的的关关键键字字值值，用用同同一一个个哈哈希希函函数数计计算算出出给给定定关关键键字字值值对对应应的的存存储储地地址址，随随后后进进行行访访问问。所所以以哈哈希希表表即即是是一一种种存存储储形形式式，又又是是一一种种查查找找方法方法，通常将这种查找方法称为，通常将这种查找方法称为哈希查找哈希查找。哈希函数：我们将记录的关键字值与记录的存储位置对应起79 冲冲突突：有有时时可可能能会会出出现现不不同同的的关关键键字字值值其其哈哈希希函函数数计计算算的的哈哈希希地地址址相相同同的的情情况况，然然而而同同一一个个存存储储位位置置不不可可能能存存储储两两个个记记录录，我我们们将将这这种种情情况况称称为为冲冲突突，具具有有相相同同函函数数值值的的关关键键字字值值称称为为同同义义词词。在在实实际际应应用用中中冲冲突突是是不不可可能能完完全全避避免免的的，人人们们通通过过实实践践总总结结出出了了多多种种减减少少冲冲突突及及解解决决冲冲突突的的方方法法。下下面面我我们们将将简简要要地地介介绍绍一一下。下。冲突：有时可能会出现不同的关键字值其哈希函数80312726211916130911050102H(K)=int(K/3)+1121110987654321表项序号根据关键字直接计算出元素所在位置的函数。根据关键字直接计算出元素所在位置的函数。例如：设哈希函数为：例如：设哈希函数为：int(K/3)+1 int(K/3)+1则构造则构造 0101、0202、0505、0909、1111、1313、1616、1919、2121、2626、2727、3131、的散列表的散列表(哈希表）为：哈希表）为：哈希函数：哈希函数：冲突：冲突：两个不同的关键字具有相同的存储位置。两个不同的关键字具有相同的存储位置。31272621191613090501H(K)=int(K81 为为了了有有效效地地使使用用散散列列技技术术，需需要要解解决决两两方方面的问题：面的问题：（1）构构造造好好的的哈哈希希函函数数，使使冲冲突突的的现现象象尽可能的少；尽可能的少；（2）设计有效的）设计有效的解决冲突的方法解决冲突的方法。为了有效地使用散列技术，需要解决两方面的问题：82二、构造哈希函数的方法构造哈希函数的方法 好的哈希函数应能使任意一个关键字得到好的哈希函数应能使任意一个关键字得到一个随机的地址，以便使一组关键字的哈希一个随机的地址，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少地址均匀分布在整个地址区间中，从而减少冲突。冲突。对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法:若是非数字关键字非数字关键字，则需先需先对其进行进行数字化处理数字化处理。1.直接定址法直接定址法3.平方取中法平方取中法5.除留余数法除留余数法4.折叠法折叠法6.随机数法随机数法2.数字分析法数字分析法二、构造哈希函数的方法好的哈希函数应能使任意一个83哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b例见例见P253。此法中：此法中：地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小不会产生冲突。但实际使用很少。不会产生冲突。但实际使用很少。1.直接定址法直接定址法哈希函数为关键字的线性函数例见P253。此法中：1.84此方法仅适合于：此方法仅适合于：能预先估计出预先估计出全体关键字的每一位上每一位上各种数字出现的频度数字出现的频度。2.数字分析法数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。例见例见P254。关键字为。关键字为8位十位十进制数进制数此方法仅适合于：2.数字分析法假设关键字集合中的每85 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法平方取中法 此方法适合于此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。例见例见P255图图9.23以关键字的平方值的中间几位作为存储地址。求“关键字的86 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。4.折叠法折叠法 此方法适合于此方法适合于:关键字的数字位数特别多。将关键字分割成若干部分，然后取它们的叠加和为哈希地址87国际标准图书编号：国际标准图书编号：0-442-20586-4以其为关键字建立哈希表。以其为关键字建立哈希表。5864422004+10088H(key)=00885864022404+6092H(key)=6092间界叠加间界叠加移位叠加移位叠加国际标准图书编号：0-442-20586-458644220885.除留余数法除留余数法 设定哈希函数为设定哈希函数为:H(key)=key MOD p 其中其中，pm(表长表长)并且并且 p 应为不大于应为不大于 m 的素数的素数以减少冲突的发生。以减少冲突的发生。5.除留余数法设定哈希函数为:89 给定一组关键字为:12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3例如：例如：为什么要对 p 加限制？可见，因 p 可被 3整除,所以所有含所以所有含3的的倍数的关键字均映射到倍数的关键字均映射到“3 的倍数的倍数”的地的地址上址上，从而增加了“冲突”的可能。给定一组关键字为:12,39,18,24,3906.随机数法随机数法设定哈希函数为设定哈希函数为:H(key)=Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。6.随机数法设定哈希函数为:通常，此方法用于对长度不91 实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小尽可能地小。实际造表时，采用何种构造哈希函数的方法取决于建92三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突”的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址2.再哈希法再哈希法 3.链地址法链地址法1.开放定址法开放定址法 4.建立一个公共溢出区建立一个公共溢出区三、处理冲突的方法“处理冲突”的实际含义是：293 为产生冲突的地址 H(key)求得一个地址序列地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s1.开放定址法开放定址法为产生冲突的地址H(key)求得一个地址序列：1.94对增量 di 有三种取法：1)1)线性探测再散列线性探测再散列 di=c i 最简单的情况 c=12)2)平方探测再散列平方探测再散列 di=12,-12,22,-22,3)3)随机探测再散列随机探测再散列 di 是一组伪随机数列是一组伪随机数列对增量di有三种取法：1)线性探测再散列95即：产生的 Hi 均不相同，且所产生的 Hi 值能覆盖覆盖哈希表中所有 地址。注意：注意：增量增量 di 应具有应具有“完备性完备性”即：产生的Hi均不相同，且所产生的注意：增量di应具961.开放定址法开放定址法 设散列函数设散列函数 H（k）=k MOD m（m为表长为表长,设设m=11)若若发发生生冲冲突突，设设发发生生冲冲突突的的地地址址为为 p,则则沿沿着着一一个个探查序列逐个探查，那么，探查的地址序列为探查序列逐个探查，那么，探查的地址序列为P+1,P+2,P+3,m-1,0,1,P-1.29 17 600 1 2 3 4 5 6 7 8 9 101.开放定址法设散列函数H（k）=kMODm97 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 11H(k)=k MOD 11求：求：60 60、1717、2929、3838在散列表中的位置。在散列表中的位置。H(60)=60 mod 11=5 H(60)=60 mod 11=5 H(17)=17 mod 11=6H(17)=17 mod 11=6H(29)=29 mod 11=7H(29)=29 mod 11=7H(38)=38 mod 11=5H(38)=38 mod 11=5（冲突）（冲突）H(38+1)=H(38+1)=（5+15+1）mod 11=6 mod 11=6（冲突）（冲突）H(38+2)=（5+2）mod 11=7（冲突）（冲突）H(38+3)=（5+3）mod 11=81.开放定址法设散列函数H（K）=KMOD98按开放地址法所建的散列表的散列查找算法：按开放地址法所建的散列表的散列查找算法：#difine M 100int h(int k)return(k%97);int SearchHase(int t,int k)int i,j=0;i=h(K);/*求得哈希地址*/while(jM&(ti+j%M!=k)&(ti+j)%M!=0)j+;/*该地址有数据且与待查关键字不等时，求下一地址该地址有数据且与待查关键字不等时，求下一地址*/i=(i+j)%M;if(t(i)=k)return(i);/*查找成功查找成功*/else return(-1)/*查找不成功查找不成功*/按开放地址法所建的散列表的散列查找算法：99例如例如:关键字集合 19,01,23,14,55,68,11,82,36 设定设定哈希函数 H(key)=key MOD 11(哈希表长=11)190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 82365511 821 1 2 1 3 6 2 5 136例如:关键字集合设定哈希函数H(key)=key100Hi=RHi(key)I=1,2,k 在同义词产生地址冲突时计在同义词产生地址冲突时计算另一个哈希函数地址，直到冲算另一个哈希函数地址，直到冲突不再发生。突不再发生。2.再哈希法再哈希法RHi(key)均是不同的哈希函数均是不同的哈希函数Hi=RHi(key)I=1,2,k1013.链地址法链地址法链链地地址址法法解解决决冲冲突突的的方方法法：把把具具有有相相同同散散列列地地址址的的键键值值存存放放在同一个链表中，称为同义词链表。在同一个链表中，称为同义词链表。优点：插入、删除方便，缺点：占用存储空间多。优点：插入、删除方便，缺点：占用存储空间多。例例 一组关键字为一组关键字为（21，14，19，58，65，32，72）H(K)=K MOD 11 0 1 2 3 4 5 6 7 8 9 10ASL=(1*4+2*2+3*1)/7=11/73.链地址法例一组关键字为（21，14，1024.建立一个公共溢出区将发生冲突的关键字填入溢出区4.建立一个公共溢出区将发生冲突的关键字填入溢出区103 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为:四、哈希表的查找哈希表的查找 对于给定值 K,计算哈希地址 i=H(K)若若 ri=NULL 则查找不成功若若 ri.key=K 则查找成功否则否则“求下一地址 Hi”，直至 rHi=NULL (查找不成功)或 rHi.key=K (查找成功)为止。查找过程和造表过程一致。假设采用开放定址处理104决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。1)选用的哈希函数哈希函数;2)选用的处理冲突的方法处理冲突的方法;3)哈希表饱和的程度，装填因子装填因子 =n/m 值的大小大小（n记录数，记录数，m表的长度）表的长度）哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和装载因子装载因子的函数。的函数。决定哈希表查找的ASL的因素：哈希表查找的分析:从查105 装装填填因因子子越越小小，表表中中填填入入的的记记录录就就越越少少，发发生生冲冲突突的的可可能能性性就就会会小小，反反之之，表表中中已已填填入入的的记记录录越越多多，再再填填充充记记录录时时，发发生生冲冲突突的的可可能能性性就就越越大大，则则查查找找时时进进行行关关键键字字的的比比较较次次数数就就越多。越多。装填因子越小，表中填入的记录就越少，发生冲突106 1.顺序表顺序表和有序表有序表的查找方法及其平均查找长度的计算方法。2.熟练掌握二叉排序树二叉排序树的构造和查找方法。4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。3.理解B-树，B+树和键树的特点以及它们的建树和查找的过程。小结：1.顺序表和有序表的查找方法及其平均查找长度的计107