《数据结构-第7章-查找.pptx》由会员分享，可在线阅读，更多相关《数据结构-第7章-查找.pptx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构 新世纪应用型高等教育新世纪应用型高等教育计算机类课程规划教材计算机类课程规划教材新世纪应用型高等教育教材编审委员会新世纪应用型高等教育教材编审委员会 组编组编 主编主编 曹春萍曹春萍7.1 查找的基本概念第第7 7章章查找查找查找又称为检索，其功能是从大量的数据元素中找出某个特定的满足给定条件的记录或数查找又称为检索，其功能是从大量的数据元素中找出某个特定的满足给定条件的记录或数据元素。若找到满足给定条件的记录或数据元素，则称查找是成功的，此时查找的结果为给出据元素。若找到满足给定条件的记录或数据元素，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中位置的
2、指针；相反，若未找到满足给定条件的记录整个记录的信息，或指示该记录在查找表中位置的指针；相反，若未找到满足给定条件的记录或数据元素，则称查找不成功，此时，查找的结果可给出一个或数据元素，则称查找不成功，此时，查找的结果可给出一个“空空”记录或记录或“空空”指针。指针。查找的目的一般有如下四查找的目的一般有如下四种：种：（1）查找某指定的数据元素在查找表中是否存在）查找某指定的数据元素在查找表中是否存在；（2）检索某个特定的数据元素的各种属性）检索某个特定的数据元素的各种属性；（3）在查找表的合理位置上插入一个数据元素）在查找表的合理位置上插入一个数据元素；（4）从查找表中删除某个数据元素。）从
3、查找表中删除某个数据元素。7.1 查找的基本概念第第7 7章章查找查找关键字关键字关键字关键字 标识数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记标识数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字可以唯一标识一个记录，则称此关键字为主关键字（不同的记录，其主关键录）。若此关键字可以唯一标识一个记录，则称此关键字为主关键字（不同的记录，其主关键字均不同）。反之，把用以识别若干个记录的关键字称为次关键字。当数据元素只有一个数据字均不同）。反之，把用以识别若干个记录的关键字称为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。项
4、时，其关键字即为该数据元素的值。利用关键字的概念，查找运算的功能可确切地表述如下：根据给定的某个关键字值利用关键字的概念，查找运算的功能可确切地表述如下：根据给定的某个关键字值key，在某种数据结构中寻找一个其键值等于在某种数据结构中寻找一个其键值等于key的数据元素。若找到一个这样的数据元素，则称查的数据元素。若找到一个这样的数据元素，则称查找成功；否则，称查找不成功。找成功；否则，称查找不成功。7.1 查找的基本概念第第7 7章章查找查找静态查找（静态查找（静态查找（静态查找（static searchstatic search）若对查找表只做前两种操作（即，肯定不会改变原查找表的若对查找
5、表只做前两种操作（即，肯定不会改变原查找表的内容），则称此查找为静态查找。内容），则称此查找为静态查找。动态查找（动态查找（动态查找（动态查找（dynamic searchdynamic search）若在查找过程中同时插入查找表中不存在的数据元素，或若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此查找为动态查找。者从查找表中删除已存在的某个数据元素，则称此查找为动态查找。平均查找长度（平均查找长度（平均查找长度（平均查找长度（average search length,ASLaverage search length,ASL）为确定所查找的数据元
6、素在查找表中的为确定所查找的数据元素在查找表中的位置而需和给定关键字进行比较的次数的平均值。位置而需和给定关键字进行比较的次数的平均值。ASL是衡量一个查找算法性能好坏的依据是衡量一个查找算法性能好坏的依据,因因为查找的过程实际上是为查找的过程实际上是“将查找表中各数据元素的关键字与给定的关键字进行比较的过程将查找表中各数据元素的关键字与给定的关键字进行比较的过程”，所以比较次数越少，则查找所需的时间就越短，效率就越高。所以比较次数越少，则查找所需的时间就越短，效率就越高。7.2 静态查找表第第7 7章章查找查找7.2.1 7.2.1 顺序查找顺序查找顺序查找是一种最简单也是效率比较低下的查顺
7、序查找是一种最简单也是效率比较低下的查找算法。查找的基本思想是将每个结点的关键字与给找算法。查找的基本思想是将每个结点的关键字与给定的待查的关键字值定的待查的关键字值key依次进行比较，若当前扫描依次进行比较，若当前扫描到的结点关键字值与到的结点关键字值与key相等，则查找成功，返回该相等，则查找成功，返回该数据元素的存储位置；反之，若扫描结束后，仍未找数据元素的存储位置；反之，若扫描结束后，仍未找到关键字等于到关键字等于key的结点，则查找失败，返回查找失的结点，则查找失败，返回查找失败标志。顺序查找法既可以采用顺序存储结构，也可败标志。顺序查找法既可以采用顺序存储结构，也可以采用链式存储结
8、构。以采用链式存储结构。/静态查找表的顺序存储表示#define maxsize 100 /*定义最大存储容量*/typedef struct datatype datamaxsize;int length;seqtable;/*静态查找表的链式存储表示*/typedef struct node datatype data;struct node *next;linktable;7.2 静态查找表第第7 7章章查找查找7.2.2 7.2.2 折半查找折半查找折半折半查找也称为查找也称为“二分查找二分查找”,其查找效率较高，但要求待查找的数据元素采用顺序存其查找效率较高，但要求待查找的数据元素采
9、用顺序存储结构，而且查找表按关键字有序储结构，而且查找表按关键字有序(已经按关键字排好序已经按关键字排好序)。采用折半查找算法在有序表（假设为升序）中查找结点时，首先找到表的中间结点，将采用折半查找算法在有序表（假设为升序）中查找结点时，首先找到表的中间结点，将其关键字值与给定的要找的值其关键字值与给定的要找的值key进行比较，若相等，则查找成功；若当前结点的关键字值进行比较，若相等，则查找成功；若当前结点的关键字值大于要找的值大于要找的值key，则继续在表的前半部分进行折半查找，否则继续在表的后半部分进行折，则继续在表的前半部分进行折半查找，否则继续在表的后半部分进行折半查找。半查找。7.2
10、 静态查找表第第7 7章章查找查找7.2.3 7.2.3 分块查找分块查找分块查找是一种性能介于顺序查找和二分查找之间的查找方法，但它要求先对查找表建分块查找是一种性能介于顺序查找和二分查找之间的查找方法，但它要求先对查找表建立一个索引表，再进行分块查找。立一个索引表，再进行分块查找。索引表建立方法是先对查找表进行分块，要求索引表建立方法是先对查找表进行分块，要求“分块有序分块有序”，所谓，所谓“分块有序分块有序”是指块是指块内关键字不一定有序，但块间有序，即后一块子表中所有数据元素的关键字值均大于前一块内关键字不一定有序，但块间有序，即后一块子表中所有数据元素的关键字值均大于前一块中最大的关
11、键字值。然后，抽取各块中的最大关键字及其起始位置构成一个索引表，如图中最大的关键字值。然后，抽取各块中的最大关键字及其起始位置构成一个索引表，如图7-3所示。所示。分块查找方法为分两步进行，先查找索引表，因其有序，故可采用二分查找，以确定待分块查找方法为分两步进行，先查找索引表，因其有序，故可采用二分查找，以确定待查记录在哪一块，然后，在已确定的块中再进行顺序查找。查记录在哪一块，然后，在已确定的块中再进行顺序查找。7.3 动态查找表第第7 7章章查找查找7.3.1 7.3.1 二叉排序树二叉排序树1 1二叉排序树定义二叉排序树定义二叉排序树定义二叉排序树定义二叉排序树（二叉排序树（Binar
12、y Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：）或者是一棵空树，或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。树上所有结点的值均大于根结点的值。(2)左右子树也都是二叉排序树。左右子树也都是二叉排序树。从二叉排序树的定义可得出二叉排序树的一个重要性质：按中序遍历该树所得到的中序从二叉排序树的定义可得出二叉排序树的一个重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列。序列是一个递增有序序列。7.3
13、 动态查找表第第7 7章章查找查找2 2二叉排序树的查找过程二叉排序树的查找过程二叉排序树的查找过程二叉排序树的查找过程在在二叉排序树中查找关键字值为二叉排序树中查找关键字值为key的数据元素的基本思想是用给定值的数据元素的基本思想是用给定值key与根结点的关与根结点的关键字值比较，如果键字值比较，如果key小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，直至查找成功或查找失败为树中查找，否则将继续在右子树中查找，依此方法，查找下去，直至查找成功或查找失败为止。二叉排
14、序树的查找过程描述如下：止。二叉排序树的查找过程描述如下：（1）若二叉排序树为空树，则查找失败；）若二叉排序树为空树，则查找失败；（2）若二叉排序树非空，将给定值）若二叉排序树非空，将给定值key与根结点关键字值比较，若相等，查找成功，结与根结点关键字值比较，若相等，查找成功，结束查找过程；束查找过程；（3）否则，当结定值）否则，当结定值key小于根结点关键字值时，则继续在根结点的左子树中查找；小于根结点关键字值时，则继续在根结点的左子树中查找；（4）否则，当给定值）否则，当给定值key大于根结点关键字值时，则继续在根结点的右子树中查找。大于根结点关键字值时，则继续在根结点的右子树中查找。7.
15、3 动态查找表第第7 7章章查找查找3 3二叉排序树的插入二叉排序树的插入二叉排序树的插入二叉排序树的插入二叉排序树是一种动态树表，树的结构通常不是一成不变的，在一棵二叉排序树中插入二叉排序树是一种动态树表，树的结构通常不是一成不变的，在一棵二叉排序树中插入一个结点时，首先要在二叉排序树中进行查找，若查找成功，则不用插入；查找不成功时，一个结点时，首先要在二叉排序树中进行查找，若查找成功，则不用插入；查找不成功时，则插入，新插入结点一定是二叉排序树的叶了结点。插入可以用一个递归过程实现，即：若则插入，新插入结点一定是二叉排序树的叶了结点。插入可以用一个递归过程实现，即：若二叉排序树为空，则新结
16、点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上树上。4.4.二叉排序树的建立二叉排序树的建立二叉排序树的建立二叉排序树的建立利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想是：利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想是：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树由
17、一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。7.3 动态查找表第第7 7章章查找查找5 5二叉排序二叉排序二叉排序二叉排序树删除操作树删除操作树删除操作树删除操作从二叉排序树中删除一个结之后，使得其仍能保持二叉排序树的特性不变，即删除一个从二叉排序树中删除一个结之后，使得其仍能保持二叉排序树的特性不变，即删除一个结点后还是一棵二叉排序树。结点后还是一棵二叉排序树。下面分下面分3种情况讨论一下，如何确保从二叉排序树中删除一个结点后，不会影响二叉排种情况讨论一下，如何确保从二叉排序树中删除一个结点后，不会影响二叉排序树的性质。设待删结点为序树的性质。设待删结点为*p(p为指向待删
18、结点的指针为指向待删结点的指针)，其双亲结点为，其双亲结点为*f，且不失一般性，且不失一般性，可设可设*p是是*f的左孩子结点（右孩子结点的情况类似）。的左孩子结点（右孩子结点的情况类似）。7.3 动态查找表第第7 7章章查找查找(1)若若*p结点为叶结点，由于删去叶子结点后不影响整棵树的特性，所以，只需将被删结结点为叶结点，由于删去叶子结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针。如图点的双亲结点相应指针域改为空指针。如图7-6所示。所示。7.3 动态查找表第第7 7章章查找查找(2)若若*p结点只有右子树结点只有右子树PR或只有左子树或只有左子树PL，此时，
19、只要令，此时，只要令PL或或PR直接成为其双亲结直接成为其双亲结点点*f的左子树即可，显然，作此修改也不破坏二叉排序树的特性。如图的左子树即可，显然，作此修改也不破坏二叉排序树的特性。如图7-7所示。所示。7.3 动态查找表第第7 7章章查找查找(3)*p结点既有左子树结点既有左子树PL，又有右子树，又有右子树PR，可按中序遍历保持有序进行调整。如图，可按中序遍历保持有序进行调整。如图7-8所所示，删除示，删除*p结点前，中序遍历序列为：结点前，中序遍历序列为：CL，C，QL，Q，SL,S,*P,PR,*f，；则删除结；则删除结点点*P后，为保持其它元素之间的相对位置不变，则中序序列为：后，为
20、保持其它元素之间的相对位置不变，则中序序列为：CL，C，QL，Q，SL,S,PR,*f，。以有两种实现方法：其一是令以有两种实现方法：其一是令*P的直接前驱（或直接后继）替代的直接前驱（或直接后继）替代*P，然后再从二叉排序，然后再从二叉排序树中删去它的直接前驱（或直接后继），如图树中删去它的直接前驱（或直接后继），如图7-8(a)所示。其二是令所示。其二是令*P的左子树为的左子树为*f的左子的左子树，而树，而*P的右子树为的右子树为S的右子树，如图的右子树，如图7-8(b)所示。所示。7.3 动态查找表第第7 7章章查找查找7.3 动态查找表第第7 7章章查找查找6 6二叉排序树查找性能分析
21、二叉排序树查找性能分析二叉排序树查找性能分析二叉排序树查找性能分析在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加点的路径的过程，和给定值比较的关键字个数等于路径长度加1(或结点所在层次数或结点所在层次数)，因此和，因此和折半查找类似，与给定值比较的关键字个数不折半查找类似，与给定值比较的关键字个数不超超过过树的深度。但含有树的深度。但含有n个结点的判定树是唯一的个结点的判定树是唯一的，而而含有含有n个结点的二叉排序树却不唯一。例如，个结
22、点的二叉排序树却不唯一。例如，图图7-9（a）和图）和图7-9（b）所示的是结点数为）所示的是结点数为6的两的两棵棵二二叉排序树，图叉排序树，图7-9（a）中树的深度为）中树的深度为3，而，而图图7-9（b）中树的深度为）中树的深度为6。7.3 动态查找表第第7 7章章查找查找7.3.2 7.3.2 平衡二叉树平衡二叉树1 1平衡二叉树定义平衡二叉树定义平衡二叉树定义平衡二叉树定义平衡二叉树又称平衡二叉树又称AVL树，它或者是树，它或者是棵空树，或者是具有下列性质的二叉排序树：它的棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度差的绝对值不超过左子
23、树和右子树都是平衡二叉树，且左子树和右子树高度差的绝对值不超过1。图图7-10给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的二叉树中左子给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的二叉树中左子树与右子树高度之差，称这个数字为结点的平衡因子。由平衡二叉树的定义可知，所有结点树与右子树高度之差，称这个数字为结点的平衡因子。由平衡二叉树的定义可知，所有结点的平衡因子只能取的平衡因子只能取-1，0，1三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于对值大于l，这棵树就不是平衡二叉树。如图，这棵树就不是平衡
24、二叉树。如图7-10（a）所示的二叉排序树不是平衡二叉树。）所示的二叉排序树不是平衡二叉树。7.3 动态查找表第第7 7章章查找查找1 1平衡二叉树定义平衡二叉树定义平衡二叉树定义平衡二叉树定义7.3 动态查找表第第7 7章章查找查找2 2二叉排序树的平衡化二叉排序树的平衡化二叉排序树的平衡化二叉排序树的平衡化在平衡二叉树上插入或删除结点后，可能使二叉树失去平衡，因此，需要对失去平衡的在平衡二叉树上插入或删除结点后，可能使二叉树失去平衡，因此，需要对失去平衡的二叉树进行平衡化调整。设二叉树进行平衡化调整。设A结点为失去平衡的最小子树根结点，对该子树进行平衡化调整结点为失去平衡的最小子树根结点，
25、对该子树进行平衡化调整归纳起来有以下四种情况。归纳起来有以下四种情况。（1 1）左单旋转（）左单旋转（）左单旋转（）左单旋转（RRRR型）型）型）型）这种失衡是因为在失衡结点的右孩子的右子树上插入结点造成的。如图这种失衡是因为在失衡结点的右孩子的右子树上插入结点造成的。如图7-11（a）为插入）为插入前的子树。其中前的子树。其中A的左子树为的左子树为AL，A的右孩子结点为的右孩子结点为B，BL、BR分别为结点分别为结点B的左右子树，的左右子树，AL、BL、BR三棵子树的高度均为三棵子树的高度均为h。则图。则图7-10（a）所示的二叉树是平衡二叉树。）所示的二叉树是平衡二叉树。7.3 动态查找表
26、第第7 7章章查找查找（1 1）左单旋转（）左单旋转（）左单旋转（）左单旋转（RRRR型型型型）7.3 动态查找表第第7 7章章查找查找（2 2）右单旋转）右单旋转）右单旋转）右单旋转(LL(LL型型型型)这种失衡是因为在失衡结点的左孩子的左子树上插入结点后，导致结点这种失衡是因为在失衡结点的左孩子的左子树上插入结点后，导致结点A的平衡因子由的平衡因子由1变为变为2，如图，如图7-12（a）、（）、（b）所示，此时应进行一次顺时针旋转操作，使结点）所示，此时应进行一次顺时针旋转操作，使结点A成为结点成为结点B的右孩子，如图的右孩子，如图7-12（c）所示）所示。7.3 动态查找表第第7 7章章
27、查找查找（3 3）先左后右双向旋转（）先左后右双向旋转（）先左后右双向旋转（）先左后右双向旋转（LRLR型）型）型）型）这种失衡是因为在失衡结点的左孩子的右子树上插这种失衡是因为在失衡结点的左孩子的右子树上插入结点造成的。如图入结点造成的。如图7-13所示，插入前，根结点所示，插入前，根结点A的平衡的平衡因子为因子为1，将结点，将结点x插入到插入到B的右子树上。并使结点的右子树上。并使结点B的右的右子树高度增子树高度增1，从而使结点，从而使结点A的平衡因子变为的平衡因子变为2，导致以，导致以结点结点A为根的子树平衡被破坏，如图为根的子树平衡被破坏，如图7-14（a）、图）、图7-15（a）所示
28、。）所示。7.3 动态查找表第第7 7章章查找查找（4 4）先右后左双向旋转（）先右后左双向旋转（）先右后左双向旋转（）先右后左双向旋转（RLRL型）型）型）型）这种失衡是因为在失衡结点的右孩子的左子树上插入结点造成的。导致结点这种失衡是因为在失衡结点的右孩子的左子树上插入结点造成的。导致结点A的平衡因子的平衡因子由由-1变为变为-2，则同样需两次旋转，即先右后左双向旋转，调整过程与，则同样需两次旋转，即先右后左双向旋转，调整过程与LR对称，下面只给出双向对称，下面只给出双向旋转旋转RL型型I，如图，如图7-16所示。双向旋转所示。双向旋转RL型型II，请读者自行完成。，请读者自行完成。7.3
29、 动态查找表第第7 7章章查找查找（4 4）先右后左双向旋转（）先右后左双向旋转（）先右后左双向旋转（）先右后左双向旋转（RLRL型型型型）7.3 动态查找表第第7 7章章查找查找3 3.平衡二叉树的插入平衡二叉树的插入平衡二叉树的插入平衡二叉树的插入在平衡二叉树在平衡二叉树T上插入一个关键字为上插入一个关键字为x的数据元素，递归算法的基本思想可描述如下：的数据元素，递归算法的基本思想可描述如下：(1)若若T为空树，则插入的数据元素为空树，则插入的数据元素x为为T的根结点，树的深度增的根结点，树的深度增1；(2)若若x和和T的根结点关键字相等，则不进行插入；的根结点关键字相等，则不进行插入；(
30、3)若若x小于小于T的根结点关键字值，而且在的根结点关键字值，而且在T的左子树中不存在与的左子树中不存在与x有相同关键字值的结点，有相同关键字值的结点，则将新元素插入在则将新元素插入在T的左子树上，并且插入之后的左子树深度增加的左子树上，并且插入之后的左子树深度增加1时，分别就下列情况进行处时，分别就下列情况进行处理。理。7.3 动态查找表第第7 7章章查找查找4 4.平衡二叉树查找性能分析平衡二叉树查找性能分析平衡二叉树查找性能分析平衡二叉树查找性能分析在平衡二叉树上进行查找的过程和二叉排序树类似，查找时和给定值进行比较的关键字数在平衡二叉树上进行查找的过程和二叉排序树类似，查找时和给定值进
31、行比较的关键字数不超过树的深度。下面我们讨论含有不超过树的深度。下面我们讨论含有n个关键字的平衡二叉树的最大深度。个关键字的平衡二叉树的最大深度。假设以假设以Nh表示深度为表示深度为h的平衡二叉树中含有的最少结点数。显然，的平衡二叉树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且，并且Nh=Nh-1+Nh-2+1。含有。含有n个结点的平衡二叉树的最大深度为个结点的平衡二叉树的最大深度为 。利用归纳法可以证明：。利用归纳法可以证明：当当h0，时间复杂度为，时间复杂度为O(log2n)。7.4 散列表第第7 7章章查找查找7.4.1 7.4.1 散列表的概念散列表的概念1 1散列表散
32、列表散列表散列表设所有可能出现的关键字集合记为设所有可能出现的关键字集合记为U(简称全集简称全集)。实际发生。实际发生(即实际存储即实际存储)的关键字集合记的关键字集合记为为K(|K|比比|U|小得多小得多)。散列方法是使用函数散列方法是使用函数h将将U映射映射到到表表T0.m-1的下标上的下标上(m=O(|U|)。这样这样以以U中关键字为自变量，以中关键字为自变量，以h为函为函数数的运算结果就是相应结点的存储的运算结果就是相应结点的存储地地址址。从而达到在。从而达到在O(1)时间内就可时间内就可完成完成查找查找。7.4 散列表第第7 7章章查找查找2 2散列表的冲突现象散列表的冲突现象散列表
33、的冲突现象散列表的冲突现象(1)冲突冲突对于不同的关键字可能得到同一哈希地址，即对于不同的关键字可能得到同一哈希地址，即key1key2，但，但h(key1)=h(key2)，该现象，该现象称为冲突称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。7.4 散列表第第7 7章章查找查找7.4.2 7.4.2 散散列函数的构造列函数的构造方法方法1 1散列函数的选择标准散列函数的选择标准散列函数的选择标准散列函数的选择标准散列函数的选择有两条标准：简单和均匀。简单是指散列函数的计算简单快速；均匀是散
34、列函数的选择有两条标准：简单和均匀。简单是指散列函数的计算简单快速；均匀是指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到散列表空间的任何一个指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到散列表空间的任何一个位置上。也就是说，散列函数能将子集位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集随机均匀地分布在表的地址集0，1，m-1上，上，以使冲突最小化。以使冲突最小化。7.4 散列表第第7 7章章查找查找2 2常用散列函数常用散列函数常用散列函数常用散列函数为简单起见，假定关键字是定义在自然数集合上，目前比较常用的散列函数有以下几种：为简单起见，假定关键字
35、是定义在自然数集合上，目前比较常用的散列函数有以下几种：(1)平方取中法平方取中法先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。为均匀。7.4 散列表第第7 7章章查找查找(2)除留余数法除留余数法该方法是最为简单常用的一种方法。它是以表长该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址。来除关键
36、字，取其余数作为散列地址。其散列函数的形式为：其散列函数的形式为：h(key)=key%m。其中，其中，key是关键字。是关键字。m的选取十分重要，如果的选取十分重要，如果m选择不当，在某些情况下会造成严重冲选择不当，在某些情况下会造成严重冲突。例如，若突。例如，若m=2k，则，则h(key)的值仅依赖于最后的值仅依赖于最后k个比特。如果个比特。如果key是十进制数，则是十进制数，则m应避免应避免取取10的幂次。多数情况下，选取一个不超过的幂次。多数情况下，选取一个不超过m的素数的素数p，令散列函数为，令散列函数为h(key)=key%p，会收，会收到较好的效果。到较好的效果。7.4 散列表第
37、第7 7章章查找查找(3)相乘取整法相乘取整法该方法包括两个步骤：首先用关键字该方法包括两个步骤：首先用关键字key乘上某个常数乘上某个常数A(0A1)，并抽取出，并抽取出keyA的小的小数部分，然后用数部分，然后用m乘以该小数后取整。即：乘以该小数后取整。即：该方法最大的优点是选取该方法最大的优点是选取m不再像除留余数法那样关键。虽然该方法对任何不再像除留余数法那样关键。虽然该方法对任何A的值都适的值都适用，但对某些值效果会更好。用，但对某些值效果会更好。Knuth建议：建议：7.4 散列表第第7 7章章查找查找7.4.3 7.4.3 处理冲突的处理冲突的方法方法散散列表中的冲突现象是难以避
38、免的，因此，寻求较好的解决冲突的方法是一个重要的问列表中的冲突现象是难以避免的，因此，寻求较好的解决冲突的方法是一个重要的问题。通常有两类处理冲突的方法：开放定址题。通常有两类处理冲突的方法：开放定址(Open Addressing)法和拉链法和拉链(Chaining)法。前法。前者是将所有结点均存放在散列表者是将所有结点均存放在散列表T0.m-1中；后者是将互为同义词的结点链成一个单链表，中；后者是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表而将此链表的头指针放在散列表T0.m-1中中。7.4 散列表第第7 7章章查找查找1 1.开放定址法开放定址法开放定址法开放定址法(1
39、)开放地址法解决冲突的方法开放地址法解决冲突的方法用开放定址法解决冲突的方法是：当冲突发生时，使用某种探查用开放定址法解决冲突的方法是：当冲突发生时，使用某种探查(亦称探测亦称探测)技术在散列技术在散列表中形成一个探查表中形成一个探查(测测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址一个开放的地址(即该地址单元为空即该地址单元为空)为止为止(若要插入，在探查到开放的地址时，则可将待插入若要插入，在探查到开放的地址时，则可将待插入的新结点存入到该地址单元的新结点存入到该地址单元)。查找时探查到开放的地址则
40、表明表中无待查的关键字，即查找。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。失败。7.4 散列表第第7 7章章查找查找(2)开放地址法的一般形式开放地址法的一般形式开放定址法的一般形式为：开放定址法的一般形式为：h i =(h(key)+d i)%m 1im-1其中：其中：h(key)为散列函数，为散列函数，di为增量序列，为增量序列，m为表长；为表长；h(key)是初始的探查位置，后续的探查位置依次是是初始的探查位置，后续的探查位置依次是hl，h2，hm-1，即，即h(key)，hl，h2，hm-1形成了一个探查序列；形成了一个探查序列；若令开放地址一般形式的若令开放地址一般
41、形式的i从从0开始，并令开始，并令d0=0，则，则h0=h(key)，hi=(h(key)+di)%m，1im-1；探查序列可简记为；探查序列可简记为hi(0im-1)。7.4 散列表第第7 7章章查找查找(3)开放地址法对装填因子的要求开放地址法对装填因子的要求开放定址法要求散列表的装填因子开放定址法要求散列表的装填因子1，实用中取，实用中取为为0.5到到0.9之间的某个值为宜。之间的某个值为宜。(4)形成探测序列的方法形成探测序列的方法按照形成探查序列方法的不同，可将开放定址法分为线性探查法、二次探查法、双重散按照形成探查序列方法的不同，可将开放定址法分为线性探查法、二次探查法、双重散列法
42、等。列法等。线性探查法线性探查法(Linear Probing)该方法的基本思想是：将散列表该方法的基本思想是：将散列表T0.m-1看成是一个循环向量，若初始探查的地址为看成是一个循环向量，若初始探查的地址为d(即即h(key)=d)，则最长的探查序列为：，则最长的探查序列为：d，d+l，d+2，m-1，0，1，d-1。即探查时。即探查时从地址从地址d开始，首先探查开始，首先探查Td，然后依次探查，然后依次探查Td+1，直到，直到Tm-1，此后又循环到，此后又循环到T0，T1，直到探查到，直到探查到Td-1为止。为止。7.4 散列表第第7 7章章查找查找2 2拉链法拉链法拉链法拉链法(1)拉链
43、法解决冲突的方法拉链法解决冲突的方法拉链法解决冲突的方法是：将所有关键字为同义词的结点链接在同一个单链表中。若选拉链法解决冲突的方法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为定的散列表长度为m，则可将散列表定义为一个由，则可将散列表定义为一个由m个头指针组成的指针数组个头指针组成的指针数组T0.m-1。凡。凡是散列地址为是散列地址为i的结点，均插入到以的结点，均插入到以Ti为头指针的单链表中。为头指针的单链表中。T中各分量的初值均应为空指针。中各分量的初值均应为空指针。在拉链法中，装填因子在拉链法中，装填因子可以大于可以大于1，但一般均取，但一般均取1。7.4 散
44、列表第第7 7章章查找查找(2)拉链法的特点拉链法的特点与开放定址法相比，拉链法有如下几个优点：与开放定址法相比，拉链法有如下几个优点：拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；度较短；由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；的情况；开放定址法为减少冲突，要求装填因子开放定址法为减少冲突，要求装填因子较小，故当结点规模较大时会浪费很多空间。较小，故当结点规模较大时会浪
45、费很多空间。而拉链法中可取而拉链法中可取1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。的结点即可。7.4 散列表第第7 7章章查找查找7.4.4 7.4.4 散列表的查找及散列表的查找及分析分析1 1散列表数据类型描述散列表数据类型描述散列表数据类型描述散列表数据类型描述#define NIL-1/*空结点标记依赖于关键字类型，本节假定关键字均为非负整数空结
46、点标记依赖于关键字类型，本节假定关键字均为非负整数*/#define M 13/*表长度依赖于应用，但一般应确定表长度依赖于应用，但一般应确定M为一素数为一素数*/typedef int keytype;typedef struct keytype key;/*关键字关键字*/InfoType otherinfo;/*此类依赖于应用此类依赖于应用*/NodeType;typedef NodeType HashTableM;/*散列表类型散列表类型*/7.4 散列表第第7 7章章查找查找2 2基于开放地址法的查找算法基于开放地址法的查找算法基于开放地址法的查找算法基于开放地址法的查找算法散列表的
47、查找过程和建表过程一致。其查找过程为：假设给定值为散列表的查找过程和建表过程一致。其查找过程为：假设给定值为key，根据建表时设，根据建表时设定的散列函数定的散列函数h，计算出散列地址，计算出散列地址h(key)，若表中该地址单元为空，则查找失败；否则将该地，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值址中的结点与给定值key比较，若相等则查找成功，否则按建表时设定的处理冲突的方法找比较，若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址，直到某个地址单元为空下一个地址，直到某个地址单元为空(查找失败查找失败)或者关键字相等或者关键字相等(查找成功查找成功)为止为
48、止。3 3基于开放地址法的插入及建表基于开放地址法的插入及建表基于开放地址法的插入及建表基于开放地址法的插入及建表建表时首先要将表中各结点的关键字清空，使其地址为开放的；然后调用插入算法将给建表时首先要将表中各结点的关键字清空，使其地址为开放的；然后调用插入算法将给定的关键字序列依次插入表中。插入算法首先调用查找算法，若在表中找到待插入的关键字定的关键字序列依次插入表中。插入算法首先调用查找算法，若在表中找到待插入的关键字或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功成功。7.
49、4 散列表第第7 7章章查找查找4 4删除删除删除删除基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为不能将被删结点的关键字置为NIL，而应该将其置为特定的删除标记，如，而应该将其置为特定的删除标记，如DELETED。因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插人操作，使其探查到人操作，使其探查到DELETED标记时，将相应的表单元视为一个空单元，将新结点插入
50、其标记时，将相应的表单元视为一个空单元，将新结点插入其中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。7.4 散列表第第7 7章章查找查找5 5性能分析性能分析性能分析性能分析插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就虽然散列表在关键