数据结构 C语言版(严蔚敏版)第9章 查找

1、1065865ABCDEFG学习提要学习提要第第9章章 查找查找 本章中介绍下列主要内容：本章中介绍下列主要内容： 静态查找表及查找算法：静态查找表及查找算法：顺序查找顺序查找、折半查找折半查找 动态查找表及查找算法：动态查找表及查找算法：二叉排序树二叉排序树 哈希表哈希表及查找算法及查找算法学习提要（具体来讲）学习提要（具体来讲）.熟练掌握顺序表和有序表的查找方法。熟练掌握顺序表和有序表的查找方法。.熟练掌握二叉排序树的构造和查找方法。熟练掌握二叉排序树的构造和查找方法。.掌握二叉平衡树的维护平衡方法。掌握二叉平衡树的维护平衡方法。.理解树的特点以及它们的建树过程。理解树的特点以及它们的建树

2、过程。.熟练掌握哈希表的构造方法，深刻理解哈熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。希表与其它结构的表的实质性的差别。.掌握描述查找过程的判定树的构造方法，掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。查找成功时的平均查找长度。基本概念基本概念 查找表查找表 用于查找的数据元素集合称为查找用于查找的数据元素集合称为查找表。表。查找表由同一类型的数据元素（或记录）查找表由同一类型的数据元素（或记录）构成。构成。 静态查找表静态查找表 若只对查找表进行如下两种操若只对查找表

3、进行如下两种操作：（作：（1）在查找表中查看某个特定的数据元素）在查找表中查看某个特定的数据元素是否在是否在查找表中，（查找表中，（2）检索某个特定元素的各）检索某个特定元素的各种种属性属性，则称这类查找表为静态查找表。静态，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为对静态查找表进行的查找操作称为静态查找静态查找。 动态查找表：动态查找表：若在查找过程中可以将查找若在查找过程中可以将查找表中不存在的表中不存在的数据元素插入数据元素插入，或者从查找表中，或者从查找表中删除某个数据元素删除某个数据元

4、素，则称这类查找表为，则称这类查找表为动态查动态查找表找表。动态查找表在查找过程中查找表可能会。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为发生变化。对动态查找表进行的查找操作称为动态查找动态查找。 关键字：关键字：是数据元素中的某个数据项。唯是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键个元素的关键字值互不相同，我们称这种关键字为字为主关键字主关键字；若查找表中某些元素的关键字；若查找表中某些元素的关键字值相同，称这种关键字为值相同，称这种关键字为次关键字次关键

5、字。例如，银。例如，银行帐户中的帐号是主关键字，而姓名是次关键行帐户中的帐号是主关键字，而姓名是次关键字。字。 查找查找：在数据元素集合中查找满足某种条：在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常件的数据元素的过程称为查找。最简单且最常用的查找条件是用的查找条件是“关键字值等于某个给定值关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称（或记录）。若表中存在这样的记录，则称查查找成功找成功，此时的查找结果应给出找到记录的全，此时的查找结果应给出找到记录的全部信息或指示找到记录

6、的存储位置；若表中不部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称存在关键字等于给定值的记录，则称查找不成查找不成功功，此时查找的结果可以给出一个空记录或空，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。即结果可能不唯一。 查找表的存储结构查找表的存储结构：查找表是一种非常灵活的：查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度

7、，有时会采用一些特不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以殊的存储结构。本章将介绍以线性结构线性结构、树型树型结构结构及及哈希表结构哈希表结构为存储结构的各种查找算法为存储结构的各种查找算法。 查找算法的时间效率查找算法的时间效率：查找过程的主要操作：查找过程的主要操作是关键字的比较，所以通常以是关键字的比较，所以通常以“平均比较次数平均比较次数”来衡量查找算法的时间效率。来衡量查找算法的时间效率。9.1.1. 顺序查找（线性查找）顺序查找（线性查找） 静态查找是指在静态查找表上进行的查找静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的操作

8、，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。表示的静态查找表及相应的查找算法。9.1 静态查找表静态查找表顺序查找的基本思想顺序查找的基本思想： 顺序查找是一种最简单的查找方法。其基本顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等

9、，则查找若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。，则查找失败，返回查找失败标志。 可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较在平均情况下，大约要与表中一半以上元素进行比较效率较低。平均查找长度较大。效率较低。平均查找长度较大。 在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找： a. 线性表

10、为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。查找过程：查找过程： 对给定的一关键字对给定的一关键字K，从线性表的一端开始，逐个进，从线性表的一端开始，逐个进行记录的关键字和行记录的关键字和K的比较，直到找到关键字等于的比较，直到找到关键字等于K的记的记录或到达表的另一端。录或到达表的另一端。（1）顺序查找）顺序查找 (线性表在顺序存储结构下的顺序查找）线性表在顺序存储结构下的顺序查找） 数据结构：数据结构：#define MAX_NUM 100 /用于定义表的长度用于定义表的长度t

11、ypedef struct int key; float info;SSTableMAX_NUM，SSItem ;每个结点包含两部分每个结点包含两部分内容：内容：Key 和和info其他其他信息信息 假设在查找表中，数据元素个数为假设在查找表中，数据元素个数为n（nMAX_NUM），并分别存放在数组的下标变），并分别存放在数组的下标变量量ST1STn中。中。下面我们给出顺序查找的完整算法。下面我们给出顺序查找的完整算法。int seq_search (SSTable ST，int key)/在顺序表中查找关键字值等于在顺序表中查找关键字值等于key的记录，的记录， /若查找成功，返回该记录的位

12、置下标序号，若查找成功，返回该记录的位置下标序号，否则返回否则返回0 i=1; while (i=n & STi.key != key) i+; if (inext; while (p!=NULL) & (p-key!=k) p=p-next; return p; 9.1.2 折半查找（二分法查找）折半查找（二分法查找） 折半查找要求查找表用顺序存储结构存放且折半查找要求查找表用顺序存储结构存放且各数据元素各数据元素按关键字有序按关键字有序（升序或隆序）排列（升序或隆序）排列，也就是说折半查找只适用于对有序顺序表进，也就是说折半查找只适用于对有序顺序表进行查找。行查找。 1.

13、折半查找的基本思想是折半查找的基本思想是： 首先以整个查找表作为查找范围，用查找条件中首先以整个查找表作为查找范围，用查找条件中给定值给定值k与中间位置结点的关键字比较，若相等，则与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若分子表中，所以继续对左子表进行折半查找；若k的的值大于中间结点的关

14、键字值，则可以判定查找的数据值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。小为空即查找失败为止。 思想：先确定待查找记录所在的范围，然后思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该

15、记录逐步缩小范围，直到找到或确认找不到该记录为止。为止。 前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表中有序表中进行进行。分三种情况：分三种情况：1 1）若中间项的值等于）若中间项的值等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；3 3）若）若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比特点：比顺序查找方法效率高。最坏的情况下，需要比较较 loglog2 2n n次次。查找查找23和

16、和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, 3

17、7, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid2. 折半查找算法折半查找算法 假设查找表存放在数组假设查找表存放在数组ST的的ST1 STn中，中，且升序，查找关键字值为且升序，查找关键字值为key。 折半查找的主要步骤为：折半查找的主要步骤为： （1）置初始查找范围：）置初始查找范围：low=1，high=n; （2）求查找范围中间项：）求查找范围中间项：mid=(low+high)/2 （ 3 ） 将 指 定 的 关 键 字 值） 将 指 定 的 关 键 字 值 k e y

18、与 中 间 项与 中 间 项STmid.key比较比较 若相等，查找成功，找到的数据元素为此时若相等，查找成功，找到的数据元素为此时mid 指向的位置；指向的位置； 若小于，查找范围的低端数据元素指针若小于，查找范围的低端数据元素指针low不变，高端数据元素指针不变，高端数据元素指针high更新为更新为mid-1; 若大于，查找范围的高端数据元素指针若大于，查找范围的高端数据元素指针high不变，低端数据元素指针不变，低端数据元素指针low更新为更新为mid+1; （4）重复步骤（）重复步骤（2）、（）、（3）直到查找成功或）直到查找成功或查找范围空（查找范围空（lowhigh），即查找失败为

19、止。），即查找失败为止。 （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( ke

20、y 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指向根结点，搜索从根结点开始指向根结点，搜索从根结点开

21、始 while ( p != NULL & p -key != k ) if (k key ) p = p - lchild; else p = p - rchild; return ( p);3. 二叉排序树的插入和删除二叉排序树的插入和删除 3-1. 二叉排序树的插入二叉排序树的插入 在一棵二叉排序树中插入一个结点可以用一在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则给定结点的关键字值小于根结

22、点关键字值，则插入在左子树上；若给定结点的关键字值大于插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。根结点的值，则插入在右子树上。 10、18、3、8、12、2、7、3 1010181018310183810183812101838122101838122731018381227下面是二叉排序树插入操作的递归算法。下面是二叉排序树插入操作的递归算法。void bt_insert1(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) /在以在以bt为根的二叉排序树上插入一个由指针为根的二叉排序树上插入一个由指针pn指向的新的结点指向的新

23、的结点 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) ;这个算法也可以用非递归的形式实现，如下所示：这个算法也可以用非递归的形式实现，如下所示：void bt_insert 2(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) p = bt; while ( p != NULL &

24、amp; 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; 利用二叉排序树的插入算法，可以很容易利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。入操作

25、生成一棵二叉排序树。 例如，由结点关键字序列例如，由结点关键字序列 10、18、3、8、12、2、7、3 构造二叉排序树的过程为：从构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过点作为叶子结点插入，经过8次的查找和插入操次的查找和插入操作，建成由这作，建成由这8个结点组成的二叉排序树。个结点组成的二叉排序树。 创建二叉排序树的算法如下：创建二叉排序树的算

26、法如下：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( &bt , p); return ( bt) ; 3-2. 二叉排序树的删除二叉排序树的删除 下面分四种情况讨论一下如何确保

27、从二叉下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的树中删除一个结点后，不会影响二叉排序树的性质：性质： （1）若要删除的结点为叶子结点，可以直）若要删除的结点为叶子结点，可以直接进行删除。接进行删除。 （2）若要删除结点有右子树，但无左子树）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位，可用其右子树的根结点取代要删除结点的位置。置。 （3）若要删除结点有左子树，但无右子树，）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，可用其左子树的根结点取代要删除结点的位置，与步骤与步骤类似。类似。 （4）若要删除结点

28、的左右子树均非空，则首）若要删除结点的左右子树均非空，则首先找到要删除结点的右子树中关键字值最小的结先找到要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。二叉树的性质不变。9.2.1 .2平衡二叉树平衡二叉树 何谓何谓“二叉平衡树二叉平衡树”？ 如何构造如何构造“平衡二叉树平衡二叉树”平衡二叉树平衡二叉树是二叉查找树的另一种形式，其特点为：

29、 树中每个结点的树中每个结点的左、右子树深度之左、右子树深度之差（平衡因子）的绝对值不大于差（平衡因子）的绝对值不大于1 1 。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树1RLhh 一般地， 假设由于在二叉树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为归纳为下列四种情况：下列四种情况：（1 1）单向右旋平衡处理：）单向右旋平衡处理：由于在由于在* *a a的的左子树的左子树上插入结点，使左子树的左子树上插入结点，使* *a a的的平衡因子由平衡因子由1 1增至增至2 2而失去平

30、衡，需进而失去平衡，需进行一次顺时针旋转操作；行一次顺时针旋转操作；(L-L(L-L型）型）（2 2）单向左旋平衡处理：）单向左旋平衡处理：由于在由于在* *a a的的右子树的右子树上插入结点，使右子树的右子树上插入结点，使* *a a的的平衡因子由平衡因子由-1-1减至减至-2-2而失去平衡，需而失去平衡，需进行一次逆时针旋转操作；进行一次逆时针旋转操作； (R-R(R-R型）型）798798（3 3）双向旋转（先左后右）平衡处理：）双向旋转（先左后右）平衡处理：由于在由于在* *a a的左子树的右子树上插入结点，的左子树的右子树上插入结点，使使* *a a的平衡因子由的平衡因子由1 1增至

31、增至2 2而失去平衡，而失去平衡，需进行两次旋转操作需进行两次旋转操作（先逆时针，后顺（先逆时针，后顺时针）时针）； (L-R(L-R型）型）（4 4）双向旋转（先右后左）平衡处理）双向旋转（先右后左）平衡处理: :由由于在于在* *a a的右子树的左子树上插入结点，使的右子树的左子树上插入结点，使* *a a的平衡因子由的平衡因子由-1-1减至减至-2-2而失去平衡，需而失去平衡，需进行两次旋转操作进行两次旋转操作（先顺时针，后逆时（先顺时针，后逆时针）针）；(R-L(R-L型）型） 构造二叉平衡（查找）树的方法是：构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中

32、，采用平衡旋转技术。例如1:依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转426589642895向左旋转一次继续插入关键字 9 例例2：试求按关键字序列（：试求按关键字序列（36，23，18，42，29，25，13，21，15，19）插入生成的平衡二）插入生成的平衡二叉树。叉树。 3623362318362318362318423623184229362318422925362318422925362318422925133623184229251321362318422925132136231842292513211515362

33、31842292513211519362318422925131521199.2.2.1 B - 树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作1 1B-B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树,主要用作文件的索引 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字关键字 Ki（1 in） nm n+1 个指向子树的指针指向子树的指针 Ai（0in）;B-树的特性非叶结点中的多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 Kn;

34、且 Ai-1 所指子树上所有关键字均小于小于Ki; Ai 所指子树上所有关键字均大于大于Ki; 树中所有叶子结点均不带信息，且在树中的同一层次上; 根结点或为叶子结点，或至少含有两棵子树; 其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树; 从根结点出发，沿指针搜索结点搜索结点和在在结点内进行结点内进行顺序（或折半）查找查找 两个过程交叉进行。2.查找过程：查找过程： 若查找成功查找成功，则返回指向返回指向被查关键字所在结点的指针结点的指针和关键字在结点中的位置关键字在结点中的位置；若查找不成功查找不成功，则返回插入位置返回插入位置。在查找不成功之后，需进行插入。显然，关键字插入插

35、入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：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, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 50 和插入的考虑相反，首先必须找到待删

36、关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。4删除删除是是B-树的一种变型树的一种变型9.2.2.2 B+树树1一棵一棵m阶的阶的B+树的结构特点：树的结构特点： 有n棵子树的结点中含有n个关键字。 所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针；并且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指向含最小关键字的结点； 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； 所

37、有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。 50 96 15 5062 78 96 71 788 4 8 9 96 56 6220 26 43 50 3 8 15sqroot2查找过程查找过程 在查找时，不管成功与否，都必须查到叶子结点才能结束；即每次查找都是走了一条从根到叶子结点的路径 在结点内查找时，若给定值Ki， 则 应继续在 Ai 所指子树中进行查找；3插入和删除的操作插入和删除的操作类似于类似于B-树进行，即必要时，树进行，即必要时，也需要进行结点的也需要进行结点的“分裂分裂”或或“归并归并”。9.3.1 基本概念基本概念哈希函数，冲突哈希函数

38、，冲突9.3 哈希（哈希（HSAE）表（散列查找）表（散列查找） 哈希表技术的主要目标是提高查找效率，哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。即缩短查表和填表的时间。 前面介绍的静态查找表和动态查找表的特前面介绍的静态查找表和动态查找表的特点是：为了从查找表中找到关键字值等于某个点是：为了从查找表中找到关键字值等于某个值的记录，都要经过一系列的关键字值的记录，都要经过一系列的关键字比较比较，以，以确定待查记录的存储位置或查找失败，查找所确定待查记录的存储位置或查找失败，查找所需时间总是与需时间总是与比较次数比较次数有关。有关。 如果将记录的存储位置与它的关键字之间如果将记录

39、的存储位置与它的关键字之间建立一个确定的关系建立一个确定的关系H，使每个关键字和一个使每个关键字和一个唯一的存储位置对应，唯一的存储位置对应，在查找时，只需要根据在查找时，只需要根据对应关系计算出给定的关键字值对应关系计算出给定的关键字值k对应的值对应的值H(k)，就可以得到记录的存储位置，就可以得到记录的存储位置，这就是本这就是本节将要介绍的哈希表查找方法的基本思想。节将要介绍的哈希表查找方法的基本思想。 哈希函数：哈希函数：我们将记录的关键字值与记录我们将记录的关键字值与记录的存储位置对应起来的关系的存储位置对应起来的关系H称为哈希函数，称为哈希函数，H(k)的结果称为的结果称为哈希地址哈

40、希地址。 哈希表：哈希表：是根据哈希函数建立的表，其基是根据哈希函数建立的表，其基本思想是：以记录的关键字值为自变量，根据本思想是：以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。当对记录进行查找时，再根储该记录的内容。当对记录进行查找时，再根据给定的关键字值，用同一个哈希函数计算出据给定的关键字值，用同一个哈希函数计算出给定关键字值对应的存储地址，随后进行访问给定关键字值对应的存储地址，随后进行访问。所以哈希表即是一种。所以哈希表即是一种存储形式存储形式，又是一种，又是一种查查找方法找方法，通常将这种查找方法称为，

41、通常将这种查找方法称为哈希查找哈希查找。 冲突：冲突：有时可能会出现不同的关键字值其有时可能会出现不同的关键字值其哈希函数计算的哈希地址相同的情况，然而同哈希函数计算的哈希地址相同的情况，然而同一个存储位置不可能存储两个记录，我们将这一个存储位置不可能存储两个记录，我们将这种情况称为冲突，具有相同函数值的关键字值种情况称为冲突，具有相同函数值的关键字值称为称为同义词同义词。在实际应用中冲突是不可能完全。在实际应用中冲突是不可能完全避免的，人们通过实践总结出了多种减少冲突避免的，人们通过实践总结出了多种减少冲突及解决冲突的方法。下面我们将简要地介绍一及解决冲突的方法。下面我们将简要地介绍一下。下

42、。312726211916130911050102H(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、的散列表的散列表( (哈希表）为：哈希表）为：哈希函数：哈希函数：冲突：冲突：两个不同的关键字具有相同的存储位置。两个不同的关键字具有相同的存储位置。 为了有效地使用散列技术，需要解决

43、两方为了有效地使用散列技术，需要解决两方面的问题：面的问题： （1）构造）构造好的哈希函数好的哈希函数，使冲突的现象，使冲突的现象尽可能的少；尽可能的少； （2）设计有效的）设计有效的解决冲突的方法解决冲突的方法。二、构造哈希函数的方法构造哈希函数的方法 好的哈希函数应能使任意一个关键字得到好的哈希函数应能使任意一个关键字得到一个随机的地址，以便使一组关键字的哈希一个随机的地址，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少地址均匀分布在整个地址区间中，从而减少冲突。冲突。对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法: 若是非数字关键字非数字关键字，则需先需先对其

44、进行进行数字化处理数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数除留余数法法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b例见例见P253 。 此法中：此法中：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小不会产生冲突。但实际使用很少。不会产生冲突。但实际使用很少。1. 直接定址法直接定址法此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一位上每一位上各种数字出现的频度数字出现的频度。2. 数字分析法数

45、字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。例见例见P254。关键字为。关键字为8位十位十进制数进制数 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 平方取中法平方取中法 此方法适合于此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。例见例见P255图图9.23 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠

46、加间界叠加。4. 折叠法折叠法 此方法适合于此方法适合于: 关键字的数字位数特别多。国际标准图书编号：国际标准图书编号：0-442-20586-4以其为关键字建立哈希表。以其为关键字建立哈希表。5864422004+10088H(key)=00885864022404+6092H(key)=6092间界叠加间界叠加移位叠加移位叠加5. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数以减少冲突的发生。以减少冲突的发生。 给定一组关键字为: 12, 39, 18

47、, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3例如：例如：为什么要对 p 加限制？ 可见，因 p 可被 3整除, 所以所有含所以所有含3的的倍数的关键字均映射到倍数的关键字均映射到“3 的倍数的倍数”的地的地址上址上，从而增加了“冲突”的可能。6.随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。 实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)

48、，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小尽可能地小。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址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, , s1. 开放定址法开放定址法对增量 di 有三种取法： 1) 1)

49、线性探测再散列线性探测再散列 di = c i 最简单的情况 c=1 2) 2) 平方探测再散列平方探测再散列 di = 12, -12, 22, -22, , 3) 3) 随机探测再散列随机探测再散列 di 是一组伪随机数列是一组伪随机数列即：产生的 Hi 均不相同，且所产生的 Hi 值能覆盖覆盖哈希表中所有 地址。注意：注意：增量增量 di 应具有应具有“完备性完备性”1 . 开放定址法开放定址法 设散列函数设散列函数 H（k）=k MOD m （m为表长为表长, 设设m=11)若发生冲突，设发生冲突的地址为若发生冲突，设发生冲突的地址为 p , 则沿着一个则沿着一个探查序列逐个探查，那么

50、，探查的地址序列为探查序列逐个探查，那么，探查的地址序列为P+1, P+2, P+3 , m-1 , 0, 1, , P-1. 29 17 600 1 2 3 4 5 6 7 8 9 10 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求：求： 6060、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 1