1、数据结构数据结构项目七共分为四个任务项目七共分为四个任务项目七项目七 查找查找任务一任务一 查找的相关术语查找的相关术语 任务二任务二 静态查找表静态查找表 任务三任务三 动态查找表动态查找表 任务四任务四 哈希查找哈希查找 任务一任务一 查找的相关术语查找的相关术语 1查找表查找表 2关键字关键字 3查找查找 4平均查找长度平均查找长度 1查找表查找表 查找表查找表（Search Table）是按某种数据结构形式存储的同一类型数）是按某种数据结构形式存储的同一类型数据元素（或记录）的集合。据元素（或记录）的集合。静态查找表：静态查找表：只能进行查找操作，而不能改变查找表中的原始数据。只能进行
2、查找操作，而不能改变查找表中的原始数据。动态查找表：动态查找表：除能查找数据元素之外，还能向表中插入新的数据元素除能查找数据元素之外，还能向表中插入新的数据元素或从表中删除已有的数据元素。或从表中删除已有的数据元素。2关键字关键字 关键字关键字（Key）是数据元素（或记录）中某个数据项的值，用它可）是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。以标识一个数据元素（或记录）。能惟一地确定一个记录的关键字称为能惟一地确定一个记录的关键字称为主关键字主关键字（Primary Key）。）。不能惟一地确定一个记录的关键字称为不能惟一地确定一个记录的关键字称为次关键字次关键字
3、（Secondary Key）。）。3查找查找 查找查找（Searching）是指根据给定的值，在查找表中确定一个其关键）是指根据给定的值，在查找表中确定一个其关键字与之相等的数据元素（或记录）。字与之相等的数据元素（或记录）。若找到相应的数据元素，则称若找到相应的数据元素，则称查找成功查找成功；否则称；否则称查找失败查找失败。4平均查找长度平均查找长度 平均查找长度平均查找长度（Average Search Length，简称，简称ASL）是指为确定）是指为确定某一数据元素在查找表中的位置，需与给定值进行比较的关键字个数某一数据元素在查找表中的位置，需与给定值进行比较的关键字个数的期望值。的
4、期望值。对于含有对于含有n个数据元素的查找表，查找成功时的平均查找长度为个数据元素的查找表，查找成功时的平均查找长度为 Pi为表中第为表中第i个数据元素的查找概率；个数据元素的查找概率；Ci为找到第为找到第i个数据元素时，所需进行的关键字比较的次数。个数据元素时，所需进行的关键字比较的次数。任务二任务二 静态查找表静态查找表 一、顺序查找一、顺序查找 二、折半查找二、折半查找 三、索引顺序查找三、索引顺序查找 静态查找表的顺序存储结构：静态查找表的顺序存储结构：#define MAXSIZE 100/顺序表的最大长度顺序表的最大长度typedef struct KeyType key;/关键字
5、项关键字项OtherType otheritem;/另外的数据项另外的数据项RecordType;typedef structRecordType elemMAXSIZE+1;/定义数据元素数组，定义数据元素数组，elem0为哨兵单元为哨兵单元int length;/顺序表长度顺序表长度SeqList;一、顺序查找一、顺序查找 1算法描述算法描述 2性能分析性能分析 1算法描述算法描述 基本思想：基本思想：从表中最后一个数据元素开始，自后向前将关键字逐个与从表中最后一个数据元素开始，自后向前将关键字逐个与给定值进行比较。若相等，则查找成功，给出所查数据元素在查找表给定值进行比较。若相等，则查找
6、成功，给出所查数据元素在查找表中的位置；否则，查找失败。中的位置；否则，查找失败。int SeqSearch(SeqList L,KeyType key)/在顺序表在顺序表L中顺序查找关键字等于中顺序查找关键字等于key的数据元素，若找到，返回的数据元素，若找到，返回值为该元素在表中的位置，否则为值为该元素在表中的位置，否则为0int i;L.elem0.key=key;/0号单元存放监测值，用于监测是否查询完整个表号单元存放监测值，用于监测是否查询完整个表for(i=L.length;L.ri.key!=key);i-);/自后向前进行关键字的比较自后向前进行关键字的比较return i;算
7、法描述算法描述如下：如下：2性能分析性能分析 对于具有对于具有n个数据元素的查找表，在查找第个数据元素的查找表，在查找第i个数据元素个数据元素elemi时，需进时，需进行行ni1次比较，即次比较，即Cini1，则顺序查找的平均查找长度为，则顺序查找的平均查找长度为 ASLPn2Pn-1(n1)P2nP1假设每个记录的查找概率相等，即假设每个记录的查找概率相等，即 则在等概率情况下，查找成功时的平均查找长度为则在等概率情况下，查找成功时的平均查找长度为 顺序查找适用面广，但平均查找长度较大时，查找效率相对较低。顺序查找适用面广，但平均查找长度较大时，查找效率相对较低。二、折半查找二、折半查找 1
8、算法描述算法描述 2性能分析性能分析 1算法描述算法描述 基本思想：基本思想：在关键字升序排列的顺序表中，将处于查找表中间位置的数在关键字升序排列的顺序表中，将处于查找表中间位置的数据元素的关键字与给定值进行比较，若二者相等，则查找成功；若中间据元素的关键字与给定值进行比较，若二者相等，则查找成功；若中间元素的关键字大于给定值，说明要查找的元素在表的前半部分，则在表元素的关键字大于给定值，说明要查找的元素在表的前半部分，则在表的前半部分继续查找；若中间元素的关键字小于给定值，说明要查找的的前半部分继续查找；若中间元素的关键字小于给定值，说明要查找的元素在表的后半部分，则在表的后半部分继续查找。
9、反复进行比较，直元素在表的后半部分，则在表的后半部分继续查找。反复进行比较，直至找到与给定值相等的数据元素（即查找成功）或者当前查找范围内无至找到与给定值相等的数据元素（即查找成功）或者当前查找范围内无数据元素（即查找不成功）。数据元素（即查找不成功）。基本步骤如下：基本步骤如下：确定查找区间的中点位置确定查找区间的中点位置 若若keyelemmid.key，则查找成功；，则查找成功；若若keyelemmid.key，则，则highmid1;若若keyelemmid.key，则，则lowmid1。将位于将位于mid位置处的数据元素的关键字与给定值位置处的数据元素的关键字与给定值key进行比较：
10、进行比较：重复以上步骤，直至查找成功或重复以上步骤，直至查找成功或lowhigh（查找失败）。（查找失败）。折半查找的算法：折半查找的算法：int BinSearch(SeqList L,KeyType key)/在顺序表在顺序表L中折半查找关键字等于中折半查找关键字等于key的数据元素，若找到，返回值为该的数据元素，若找到，返回值为该元素在表中的位置，否则为元素在表中的位置，否则为0int low,high,mid;low=1;high=L.length;/设置初始查找区间设置初始查找区间while(low key)high=mid-1;/查找区间为表的前半部分查找区间为表的前半部分else
11、 low=mid+1;/查找区间为表的后半部分查找区间为表的后半部分return 0;/查找不成功，返回查找不成功，返回02性能分析性能分析 有序表有序表L 3，7，12，30，34，45，49，52，63，71，77，86，94折半查找的过程可以用一个二叉树来描述，树中的一个结点表示查找表折半查找的过程可以用一个二叉树来描述，树中的一个结点表示查找表中的一个数据元素，结点中的值为数据元素在表中的位置。中的一个数据元素，结点中的值为数据元素在表中的位置。根结点对应当前查找根结点对应当前查找区间的中间元素，左区间的中间元素，左子树对应表的前半部子树对应表的前半部分，右子树对应表的分，右子树对应表
12、的后半部分。后半部分。查找某一数据元素的过程，可以看成是查找某一数据元素的过程，可以看成是从判定树的根结点到该数据元素对从判定树的根结点到该数据元素对应结点的一条路径应结点的一条路径，该结点在树中的层次数即为关键字比较的次数。折半，该结点在树中的层次数即为关键字比较的次数。折半查找在查找成功时关键字比较的次数至多为查找在查找成功时关键字比较的次数至多为 。假设查找表的长度为假设查找表的长度为n2h1，那么，判定树必为高度是，那么，判定树必为高度是hlog2(n1)的满二叉树。假设表中每个数据元素的查找概率相等，即的满二叉树。假设表中每个数据元素的查找概率相等，即1/n，则查找，则查找成功时的平
13、均查找长度：成功时的平均查找长度：折半查找折半查找平均性能好平均性能好，适用于适用于不经常变动而查找频繁的不经常变动而查找频繁的有序表有序表。三、索引顺序查找三、索引顺序查找 1算法描述算法描述 2性能分析性能分析 1算法描述算法描述 基本思想：基本思想：首先将查找表划分成若干个等长的块（子表），其中最后一首先将查找表划分成若干个等长的块（子表），其中最后一块可以不满。划分时要保证数据元素的关键字在块可以不满。划分时要保证数据元素的关键字在块与块之间是有序的块与块之间是有序的，而块内元素可以任意排列。然后，为每个块建立一个索引项，它包括而块内元素可以任意排列。然后，为每个块建立一个索引项，它包
14、括关关键字项键字项和和指针项指针项两部分，分别记录每块中的最大关键字和每块的起始位两部分，分别记录每块中的最大关键字和每块的起始位置。将所有块的索引项按关键字有序排列，从而构造了一个索引表。置。将所有块的索引项按关键字有序排列，从而构造了一个索引表。第第i i（1 1inin）块中所有数据元素的关键字均）块中所有数据元素的关键字均大于第大于第i i1 1块中所有数据元素的关键字块中所有数据元素的关键字索引顺序索引顺序查找的过程查找的过程：首先，将要查找的数据元素与索引表中的关键：首先，将要查找的数据元素与索引表中的关键字项进行比较，以确定待查数据元素所在的块，然后在相应的块中进字项进行比较，以
15、确定待查数据元素所在的块，然后在相应的块中进行查找。行查找。由于索引表是按关键字有序排列的顺序表，故可以采用由于索引表是按关键字有序排列的顺序表，故可以采用顺序查找或折顺序查找或折半查找法确定半查找法确定数据元素所在的数据元素所在的块块；而块中元素不要求按关键字有序，；而块中元素不要求按关键字有序，故进行故进行块内块内查找时要根据实际情况确定查找方法，查找时要根据实际情况确定查找方法，一般采用顺序查找一般采用顺序查找法法。若用若用折半查找法确定折半查找法确定待查元素待查元素所在块所在块，则平均查找长度为，则平均查找长度为 2性能分析性能分析 索引顺序查找是由索引表查找和子表顺序查找两部分完成的
16、，即索引顺序查找是由索引表查找和子表顺序查找两部分完成的，即ASL(索引顺序查找索引顺序查找)ASL(索引表查找索引表查找)ASL(顺序查找顺序查找)。若将含有若将含有n个数据元素的查找表均匀地分成个数据元素的查找表均匀地分成m块，每块中均含有块，每块中均含有s个数个数据元素，则有据元素，则有sn/m。假设每个数据元素的查找概率是相同的，索引。假设每个数据元素的查找概率是相同的，索引表中块的查找概率为表中块的查找概率为1/m，块中元素的查找概率为，块中元素的查找概率为1/s。若用若用顺序查找法确定顺序查找法确定待查元素待查元素所在块所在块，则平均查找长度为，则平均查找长度为 任务三任务三 动态
17、查找表动态查找表 一、二叉排序树一、二叉排序树 二、平衡二叉树二、平衡二叉树 基于动态查找表的查找又称基于树的查基于动态查找表的查找又称基于树的查找，其特点是表的结构在查找过程中动找，其特点是表的结构在查找过程中动态生成，查找表被组织成特定的树形结态生成，查找表被组织成特定的树形结构，并在树结构上实现查找。构，并在树结构上实现查找。一、二叉排序树一、二叉排序树 1二叉排序树的定义二叉排序树的定义 2二叉排序树的插入二叉排序树的插入 3二叉排序树的生成二叉排序树的生成 4二叉排序树的删除二叉排序树的删除 5二叉排序树的查找二叉排序树的查找 1二叉排序树的定义二叉排序树的定义 二叉排序树（二叉排序
18、树（Binary Sort Tree）又称二叉查找树，它是一种特殊结构）又称二叉查找树，它是一种特殊结构的二叉树。一棵非空的二叉排序树应具有下列性质：的二叉树。一棵非空的二叉排序树应具有下列性质：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；它的左右子树也分别为二叉排序树。它的左右子树也分别为二叉排序树。中序遍历一棵二叉排序树可中序遍历一棵二叉排序树可以得到一个递增有序序列。以得到一个递增有序序列。2二叉排序树
19、的插入二叉排序树的插入 插入过程为：插入过程为：若二叉排序树是空树，则若二叉排序树是空树，则key成为二叉排序树的根。成为二叉排序树的根。若二叉排序树非空，则将若二叉排序树非空，则将key与二叉排序树的根进行比较：与二叉排序树的根进行比较：如果如果key的值等于根结点的值，则停止插入；的值等于根结点的值，则停止插入；如果如果key的值小于根结点的值，则将的值小于根结点的值，则将key插入其左子树；插入其左子树；如果如果key的值大于根结点的值，则将的值大于根结点的值，则将key插入其右子树。插入其右子树。重复以上过程，直到结点重复以上过程，直到结点s插入到二叉排序树中的相应位置。插入到二叉排序
20、树中的相应位置。3二叉排序树的生成二叉排序树的生成 将二叉排序树初始化为一棵空树，逐个读取查找表中的每个数据元素，将二叉排序树初始化为一棵空树，逐个读取查找表中的每个数据元素，每个数据元素生成一个新结点，并将其插入到当前已生成的二叉排序树每个数据元素生成一个新结点，并将其插入到当前已生成的二叉排序树中，直到所有结点都插入完成。中，直到所有结点都插入完成。按照关键字序列按照关键字序列43，80，71，13，60，99，26，11，48，32的输的输入顺序创建一棵二叉排序树的过程：入顺序创建一棵二叉排序树的过程：输入顺序不同，所创建的二输入顺序不同，所创建的二叉排序树的形态也不同。叉排序树的形态也
21、不同。4二叉排序树的删除二叉排序树的删除 首先查找要删除的结点是否在树中，首先查找要删除的结点是否在树中，若不在若不在，则不执行任何操作；，则不执行任何操作；若在若在，假设要删除的结点为假设要删除的结点为p，其双亲结点为，其双亲结点为f，若结点，若结点p是是f的左孩子（的左孩子（p是是f的的右孩子的情况与之类似，这里不再详述），则有以下右孩子的情况与之类似，这里不再详述），则有以下3种情况：种情况：当结点当结点p为叶子结点时，直接删除该结点即可，即将其双亲结点的为叶子结点时，直接删除该结点即可，即将其双亲结点的左指针置空，同时释放结点左指针置空，同时释放结点p，对应的语句为：，对应的语句为：f
22、-lchild=NULL;free(p)；当结点当结点p只有左子树或只有右子树时，可以将只有左子树或只有右子树时，可以将p的左子树或右子树直的左子树或右子树直接改为其双亲结点接改为其双亲结点f的左子树，对应的语句为：的左子树，对应的语句为：f-lchild=p-lchild;（或（或f-lchild=p-rchild;）free(p)；当结点当结点p既有左子树，又有右子树时，删除的方法就会较为复杂。中既有左子树，又有右子树时，删除的方法就会较为复杂。中序遍历整个二叉排序树，得到一个按关键字有序排列的序列。在删除结序遍历整个二叉排序树，得到一个按关键字有序排列的序列。在删除结点点p后，应保持其他
23、元素在该序列中的相对位置不变。后，应保持其他元素在该序列中的相对位置不变。方法一方法一：令：令p的左子树为的左子树为f的左子树，而的左子树，而p的右子树为的右子树为s的右子树。的右子树。方法二方法二：用结点：用结点s的值代替结点的值代替结点p的值，然后将的值，然后将s删除。删除。5二叉排序树的查找二叉排序树的查找 若二叉排序树为空树，则查找失败。若二叉排序树为空树，则查找失败。若二叉排序树非空，将给定值若二叉排序树非空，将给定值key与根结点的关键字进行比较：与根结点的关键字进行比较：当当key等于根结点关键字时，则查找成功；等于根结点关键字时，则查找成功；当当key小于根结点关键字时，在其左
24、子树上继续查找；小于根结点关键字时，在其左子树上继续查找；当当key大于根结点关键字时，在其右子树上继续查找。大于根结点关键字时，在其右子树上继续查找。重复以上过程，直到查找成功或者要查找的子树为空（查找失败）。重复以上过程，直到查找成功或者要查找的子树为空（查找失败）。二叉排序树的查找操作的算法描述如下：二叉排序树的查找操作的算法描述如下：BSTree BSTSearch(BSTree BT,KeyType key)/在根为在根为BT的二叉排序树中查找关键字等于的二叉排序树中查找关键字等于key的数据元素，若查的数据元素，若查找成功，返回指向该结点的指针，否则返回空找成功，返回指向该结点的指
25、针，否则返回空BSTree BT1;BT1=BT;while(BT1)if(BT1-key=key)/若若key等于等于BT1根结点的关键字根结点的关键字 return BT1;/查找成功查找成功if(key key)/若若key小于小于BT1根结点的关键字根结点的关键字 BT1=BT1-lchild;/在左子树中查找在左子树中查找else BT1=BT1-rchild;/若若key大于大于BT1根结点的关键字，则在右子树中查找根结点的关键字，则在右子树中查找return NULL;/查找失败查找失败当关键字按升序或降序输入时，生成的二叉排序树是一棵单支树，树当关键字按升序或降序输入时，生成的
26、二叉排序树是一棵单支树，树的深度等于结点个数，它的的深度等于结点个数，它的平均查找长度与顺序查找相同平均查找长度与顺序查找相同，这是，这是最坏最坏的情况的情况。在。在最好情况最好情况下，生成的二叉排序树与二分查找的判定树形态下，生成的二叉排序树与二分查找的判定树形态相似，此时它的相似，此时它的平均查找长度与折半查找相同平均查找长度与折半查找相同。二、平衡二叉树二、平衡二叉树 1平衡二叉树的定义平衡二叉树的定义 2平衡二叉树的调整方法平衡二叉树的调整方法 1平衡二叉树的定义平衡二叉树的定义 平衡二叉树又称为平衡二叉树又称为AVL树。一棵非空的平衡二叉树应具有下列性质：树。一棵非空的平衡二叉树应具
27、有下列性质：左子树与右子树的高度之差的绝对值小于等于左子树与右子树的高度之差的绝对值小于等于1；左子树和右子树都是平衡二叉树。左子树和右子树都是平衡二叉树。结点的左子树深度与右子树深度之差称为结点的结点的左子树深度与右子树深度之差称为结点的平衡因子平衡因子。typedef struct AVLNodeKeyType key;/关键字域关键字域int bf;/平衡因子平衡因子struct AVLNode*lchild,*rchild;/左、右孩子指针左、右孩子指针AVLNode,*AVLTree;平衡二叉树的结点类型定义：平衡二叉树的结点类型定义：2平衡二叉树的调整方法平衡二叉树的调整方法 在一
28、棵平衡二叉树中插入一个结点时，使该二叉树失去平衡，假设最在一棵平衡二叉树中插入一个结点时，使该二叉树失去平衡，假设最低层失衡结点为低层失衡结点为A，根据新插入结点的位置不同，相应的调整方法可分，根据新插入结点的位置不同，相应的调整方法可分为以下四种。为以下四种。（1）LL型型（2）RR型型（3）LR型型（4）RL型型（1）LL型型 当在结点当在结点A A的左孩子的左子树中插的左孩子的左子树中插入新结点入新结点S S时，结点时，结点A A的平衡因子的平衡因子由由1 1变为变为2 2，导致二叉树失衡。，导致二叉树失衡。将结点将结点A A作为作为B B的右孩子，将的右孩子，将B B原原来的右子树来的
29、右子树B BR R作为作为A A的左子树，的左子树，相当于以相当于以B B为轴对结点为轴对结点A A做了一做了一次向右的顺时针旋转。次向右的顺时针旋转。（2）RR型型 当在结点当在结点A A的右孩子的右子树的右孩子的右子树中插入新结点中插入新结点S S时，结点时，结点A A的的平衡因子由平衡因子由1 1变为变为2 2，导，导致二叉树失衡。致二叉树失衡。将结点将结点A A作为作为B B的左孩子，将的左孩子，将B B原原来的左子树来的左子树B BL L作为作为A A的右子树，的右子树，相当于以相当于以B B为轴对结点为轴对结点A A做了一做了一次向左的逆时针旋转次向左的逆时针旋转。（3）LR型型
30、有有3种情况（调整方法相似）：种情况（调整方法相似）：在在C的左子树的左子树CL下插入下插入S（以此为例）（以此为例）在在CR下插入新结点下插入新结点 B的右子树为空，的右子树为空，C本身就是插入的新结点本身就是插入的新结点 首先将首先将B B作为作为C C的左子树，将的左子树，将C C原来的左子原来的左子树树C CL L作为作为B B的右子树；然后将的右子树；然后将A A作为作为C C的右子的右子树，将树，将C C原来的右子树原来的右子树C CR R作为作为A A的左子树，的左子树，相当于对相当于对B B做了一次向左的逆时针旋转，做了一次向左的逆时针旋转，对对A A做了一次向右的顺时针旋转。
31、做了一次向右的顺时针旋转。（4）RL型型 有有3种情况（调整方法相似）：种情况（调整方法相似）：在在C的左子树的左子树CL下插入下插入S（以此为例）（以此为例）在在CR下插入新结点下插入新结点 B的左子树为空，的左子树为空，C本身就是插入的新结点本身就是插入的新结点 首先将首先将B B作为作为C C的右子树，将的右子树，将C C原来的右子原来的右子树树C CR R作为作为B B的左子树；然后将的左子树；然后将A A作为作为C C的左子的左子树，将树，将C C原来的左子树原来的左子树C CL L作为作为A A的右子树，的右子树，相当于对相当于对B B做了一次向右的顺时针旋转，做了一次向右的顺时针
32、旋转，对对A A做了一次向左的逆时针旋转做了一次向左的逆时针旋转。任务四任务四 哈希查找哈希查找 一、哈希表的基本概念一、哈希表的基本概念 二、构造哈希函数的方法二、构造哈希函数的方法 三、处理冲突的方法三、处理冲突的方法 四、哈希表的查找及分析四、哈希表的查找及分析 一、哈希表的基本概念一、哈希表的基本概念 哈希（哈希（Hash）函数：如果在关键字与数据元素的存储位置之间建立某种）函数：如果在关键字与数据元素的存储位置之间建立某种对应关系对应关系H，根据这种对应关系就能很快地计算出与该关键字，根据这种对应关系就能很快地计算出与该关键字key对应的对应的存储位置的值存储位置的值H(key)，我
33、们将关键字与存储位置之间的这种对应关系称，我们将关键字与存储位置之间的这种对应关系称为为哈希（哈希（Hash）函数）函数。把关键字为把关键字为key的元素直接存入地址为的元素直接存入地址为H(key)的存储单元，当查找关键的存储单元，当查找关键字为字为key的元素时，利用哈希函数计算出该元素的存储位置的元素时，利用哈希函数计算出该元素的存储位置H(key)，从，从而达到按关键字直接存取元素的目的。按照这个思想建立的查找表叫而达到按关键字直接存取元素的目的。按照这个思想建立的查找表叫做做哈希表哈希表，所得到的存储位置称为，所得到的存储位置称为哈希地址哈希地址，利用哈希表进行查找的，利用哈希表进行
34、查找的方法称为方法称为哈希查找哈希查找。二、构造哈希函数的方法二、构造哈希函数的方法 1直接定址法直接定址法 2数字分析法数字分析法 3平方取中法平方取中法 4折叠法折叠法 5除留余数法除留余数法 6随机数法随机数法 好的哈希函数可以使所有关键字的映好的哈希函数可以使所有关键字的映像均匀地分布在地址列表中。像均匀地分布在地址列表中。1直接定址法直接定址法 直接定址法是指直接定址法是指取关键字或关键字的某个线性函数值为哈希地址取关键字或关键字的某个线性函数值为哈希地址。即。即 H(key)key 或或 H(key)akeyb（其中，（其中，a a和和b b为常数。）为常数。）例如，有一张高考成绩
35、上线学生人数统计表，假设一次高考成绩例如，有一张高考成绩上线学生人数统计表，假设一次高考成绩的满分为的满分为750750分，上线成绩为分，上线成绩为699699分，则以成绩（四舍五入）作为分，则以成绩（四舍五入）作为关键字，哈希函数取关键字加一个常数，即关键字，哈希函数取关键字加一个常数，即H(keyH(key)keykey(698)698)，所得哈希表如下表所示。，所得哈希表如下表所示。2数字分析法数字分析法 数字分析法是指在所有关键字已知，并且每个关键字的位数较多的前数字分析法是指在所有关键字已知，并且每个关键字的位数较多的前提下，将提下，将关键字中取值较分散的数字位作为哈希地址关键字中取
36、值较分散的数字位作为哈希地址的方法。的方法。例如，有一组数据元素，如下图所示。例如，有一组数据元素，如下图所示。关键字的第关键字的第、和和位分别均为位分别均为6 6、5 5、2 2和和1 1，第，第位只出现位只出现1 1和和2 2两个数字，因此，第两个数字，因此，第、和和位不能取。而第位不能取。而第和和位位上的数字分布较均匀，因此，可以采用这两位上的数字分布较均匀，因此，可以采用这两位数字组成哈希地址。故哈希地址为：数字组成哈希地址。故哈希地址为：H(65843121)H(65843121)4343，H(65398121)H(65398121)9898，等等。，等等。3平方取中法平方取中法 平
37、方取中法是指平方取中法是指取关键字平方后的中间几位作为哈希地址取关键字平方后的中间几位作为哈希地址，具体取几，具体取几位视表长而定。位视表长而定。例如，要求用平方取中法为标识符建立一个哈希表，假设允许标例如，要求用平方取中法为标识符建立一个哈希表，假设允许标识符为一个字母，或一个字母与一个数字的组合，取标识符在计识符为一个字母，或一个字母与一个数字的组合，取标识符在计算机中的八进制数为它的关键字。若表长为算机中的八进制数为它的关键字。若表长为2 29 9512512，则可取关，则可取关键字平方后中间键字平方后中间9 9位二进制数为哈希地址，如下表所示。位二进制数为哈希地址，如下表所示。注：字母
38、和数字按两位八进制形式转换。注：字母和数字按两位八进制形式转换。4折叠法折叠法 折叠法是指首先将关键字分成位数相等的几部分，最后一部分位数不足折叠法是指首先将关键字分成位数相等的几部分，最后一部分位数不足时以时以0补足，然后将这几部分的叠加求和，舍弃最高位进位后的结果作为补足，然后将这几部分的叠加求和，舍弃最高位进位后的结果作为哈希地址。叠加的方式有哈希地址。叠加的方式有移位叠加移位叠加和和间界叠加间界叠加两种方法。两种方法。例如，每种图书都有一个国际标准图书编号（例如，每种图书都有一个国际标准图书编号（ISBNISBN），它是一个），它是一个1313位的位的十进制数字，若以它为关键字建立一个
39、哈希表十进制数字，若以它为关键字建立一个哈希表 ，图书编号，图书编号978-7-121-978-7-121-07916-007916-0的哈希地址如下图所示。的哈希地址如下图所示。5除留余数法除留余数法 除留余数法是指除留余数法是指取关键字被某个不大于哈希表表长取关键字被某个不大于哈希表表长m的数的数p除后所得余数除后所得余数作为哈希地址作为哈希地址，即，即 H(key)key%p (pm)例如，已知关键字序列为例如，已知关键字序列为2323，4949，7070，6868，5050，9090，对于表长为，对于表长为2020的哈希表，选取的哈希表，选取p p1919，计算所得的哈希地址如下表所示
40、。，计算所得的哈希地址如下表所示。6随机数法随机数法 选择一个随机函数为哈希函数，取关键字的随机函数值为它的哈希地选择一个随机函数为哈希函数，取关键字的随机函数值为它的哈希地址，即址，即H(key)random(key)其中，其中，random()为随机函数。为随机函数。随机数法适用于关键字长度不等的情况。随机数法适用于关键字长度不等的情况。三、三、处理冲突处理冲突的方法的方法 1开放定址法开放定址法 2再哈希法再哈希法 3链地址法链地址法 4建立一个公共溢出区建立一个公共溢出区 所谓处理冲突是指，当由关键字计算出所谓处理冲突是指，当由关键字计算出的哈希地址出现冲突时，为该关键字对的哈希地址出
41、现冲突时，为该关键字对应的数据元素找到另一个应的数据元素找到另一个“空空”的哈希的哈希地址。地址。1开放定址法开放定址法 开放定址法是指当由关键字开放定址法是指当由关键字key得到的哈希地址得到的哈希地址PH(key)出现冲突时，出现冲突时，以以P为基础，产生另一个哈希地址为基础，产生另一个哈希地址P1，如果，如果P1仍然冲突，再以仍然冲突，再以P1为基础，为基础，产生另一个哈希地址产生另一个哈希地址P2，直到找出一个不冲突的哈希地址，直到找出一个不冲突的哈希地址Pi，将相，将相应元素存入其中。应元素存入其中。该方法的函数形式如下：该方法的函数形式如下：Hi(key)(H(key)di)%m
42、(1im)其中，其中，H(key)为哈希函数，为哈希函数，m为哈希表的表长，为哈希表的表长，di为增量序列。为增量序列。根据增量序列的取值方式的不同，开放定址法又分为以下三种：根据增量序列的取值方式的不同，开放定址法又分为以下三种：线性探测再散列：线性探测再散列：di为为1，2，3，h1，即冲突发生时，顺序查，即冲突发生时，顺序查看哈希表中的下一个位置，直到找出一个空位置或查遍整个表为止。看哈希表中的下一个位置，直到找出一个空位置或查遍整个表为止。二次探测再散列：二次探测再散列：di为为12，12，2，22，3，32，k，k2(km/2)，即冲突发生时，在表的前后位置进行跳跃式探测。，即冲突发
43、生时，在表的前后位置进行跳跃式探测。伪随机探测再散列：伪随机探测再散列：di为一个伪随机数序列，即冲突发生时，下一为一个伪随机数序列，即冲突发生时，下一个探测位置由一个一个伪随机数序列确定。具体实现时，应建立一个个探测位置由一个一个伪随机数序列确定。具体实现时，应建立一个伪随机数发生器，（如伪随机数发生器，（如i(ip)%m），并给定一个随机数做起点。），并给定一个随机数做起点。例如，已知关键字序列为例如，已知关键字序列为59,31,3,14,27,41,10,95,6759,31,3,14,27,41,10,95,67，哈，哈希表长为希表长为1111，选取的哈希函数为，选取的哈希函数为H(k
44、eyH(key)key%11key%11，使用线性探测再散，使用线性探测再散列法建表及处理冲突的过程如下图所示。列法建表及处理冲突的过程如下图所示。2再哈希法再哈希法 再哈希法是指构造多个不同的哈希函数，在哈希地址发生冲突时，再哈希法是指构造多个不同的哈希函数，在哈希地址发生冲突时，使用另外一个哈希函数来计算哈希地址，直到冲突不再发生，即使用另外一个哈希函数来计算哈希地址，直到冲突不再发生，即HiHi(key)再哈希法不易产生再哈希法不易产生“聚集聚集”，但会增加计算时间，降低查找效率。，但会增加计算时间，降低查找效率。3链地址法链地址法 链地址法是指将所有哈希地址相同的数据元素存储在同一个单
45、链表中，链地址法是指将所有哈希地址相同的数据元素存储在同一个单链表中，并将单链表的表头指针存在哈希表中。并将单链表的表头指针存在哈希表中。例如，已知关键字序列为例如，已知关键字序列为59,31,3,14,27,41,10,95,6759,31,3,14,27,41,10,95,67，哈，哈希函数希函数H(keyH(key)key%11key%11，用链地址法处理冲突构造所得的哈希表如下，用链地址法处理冲突构造所得的哈希表如下图所示。图所示。4建立一个公共溢出区建立一个公共溢出区 建立一个公共溢出区是指将整个哈希表分成建立一个公共溢出区是指将整个哈希表分成基本表基本表和和溢出表溢出表两部分。两部
46、分。其中，所有发生冲突的数据元素均存放在溢出表中。其中，所有发生冲突的数据元素均存放在溢出表中。四、哈希表的查找及分析四、哈希表的查找及分析 1算法描述算法描述 2性能分析性能分析 1算法描述算法描述 基本思想：基本思想：根据选定的哈希函数计算出给定值的哈希地址，若该地址根据选定的哈希函数计算出给定值的哈希地址，若该地址上没有数据元素，则查找不成功；如果哈希表中该地址上的数据元素上没有数据元素，则查找不成功；如果哈希表中该地址上的数据元素的关键字与给定值相等，则查找成功；否则，按处理冲突的方法计算的关键字与给定值相等，则查找成功；否则，按处理冲突的方法计算下一个哈希地址，重复上述过程，直至所得
47、哈希地址单元为空或者找下一个哈希地址，重复上述过程，直至所得哈希地址单元为空或者找到关键字与给定值相等的数据元素为止。到关键字与给定值相等的数据元素为止。哈希表上进行查找的过程与哈希表的创建过程基本一致。哈希表上进行查找的过程与哈希表的创建过程基本一致。2性能分析性能分析 影响哈希表中关键字比较次数的因素有三个：影响哈希表中关键字比较次数的因素有三个：哈希函数哈希函数、处理冲突的处理冲突的方法方法以及以及哈希表的装填因子哈希表的装填因子。假设哈希函数都是均匀的，因此，只需考虑后两个因素的影响。假设哈希函数都是均匀的，因此，只需考虑后两个因素的影响。（1）不同的处理冲突的方法对查找效率的影响）不
48、同的处理冲突的方法对查找效率的影响（2）不同的装填因子对查找效率的影响）不同的装填因子对查找效率的影响（1）不同的处理冲突的方法对查找效率的影响）不同的处理冲突的方法对查找效率的影响 链地址法链地址法的冲突处理方法的查找效率要的冲突处理方法的查找效率要高于线性探测再散列法高于线性探测再散列法，这是，这是因为线性探测再散列法在处理冲突过程中易出现因为线性探测再散列法在处理冲突过程中易出现“二次聚集二次聚集”。例如，用线性探测再散列法和链地址法处理关键字集例如，用线性探测再散列法和链地址法处理关键字集59,31,3,59,31,3,14,27,41,10,95,6714,27,41,10,95,67的平均查找长度。的平均查找长度。线性探测再散列法的平均查找长度为：线性探测再散列法的平均查找长度为：链地址法的平均查找长度为：链地址法的平均查找长度为：（2）不同的装填因子对查找效率的影响）不同的装填因子对查找效率的影响 对采用同一处理冲突方法的同一哈希函数，其平均查找长度依赖于对采用同一处理冲突方法的同一哈希函数，其平均查找长度依赖于哈哈希表的装填因子希表的装填因子。定义定义几种不同处理冲突方法的平均查找长度如下表所示：几种不同处理冲突方法的平均查找长度如下表所示：
