数据结构(C描述)电子教案第8章.ppt

第8章 查找,数据结构（C+描述）,目录,84 散列查找,83 树表查找,8.1 查找的基本概念,82 线性表的查找,退出,8.1 查找的基本概念,查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。,有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。,因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。,要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中i为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中i为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。,82 线性表的查找,8.2.1 顺序查找1顺序查找的基本思想,顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。,下面以顺序表的形式来描述算法。,2顺序查找算法实现,const int n=maxn/n为表的最大长度struct nodeelemtype key;/key为关键字，类型设定为elemtype;int seqsearch(node Rn+1,elemtype k)/在表中查找关键字值为的元素R0.key=k;int i=n;/从表尾开始向前扫描while(Ri.key!=k)i-;return i;,在函数seqsearch中，若返回的值为表示查找不成功，否则查找成功。函数中查找的范围从n到，为监视哨，起两个作用，其一，是为了省去判定 while循环中下标越界的条件i1，从而节省比较时间，其二，保存要找值的副本，若查找时，遇到它，表示查找不成功。若算法中不设立监视哨R0，程序花费的时间将会增加，这时的算法可写为下面形式。,int seqsearch(node Rn+1，elemtype k)int i=n;while(Ri.key!=k),当然上面算法也可以改成从表头向后扫描，将监视哨设在右边，这种方法请读者自己完成。,3.顺序查找性能分析,假设在每个位置查找的概率相等，即有pi=1/n，由于查找是从后往前扫描，则有每个位置的查找比较次数Cn=1，Cn-1=2，C1=n，于是，查找成功的平均查找ASL=,即它 的时间复杂度为O(n)。这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须进行n+1次比较之后才能确定查找失败。另处，从ASL可知，当n较大时，ASL值较大，查找的效率较低。,顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。,8.2.2二分查找1.二分查找的基本思想,二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。我们不妨假设表中元素为升序排列。二分查找的基本思想是：首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.keyk，则在R1到Rmid-1中继续查找，若有Rmid.keyk，则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。,从上述查找思想可知，每进行一次关键字比较，区间数目增加一倍，故称为二分（区间一分为二），而区间长度缩小一半，故也称为折半（查找的范围缩小一半）。,2二分查找算法实现,int binsearch(node Rn+1,elemtype k)int low=1,high=n;while(lowk)high=mid-1;/在左子区间中查找else low=mid+1;/在右子区间中查找return 0;/查找失败,例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找K=17和K=120的情况描述为图8-1及图8-2形式。,3.二分查找的性能分析,为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，图8-1给定的关键字序列8,17,25,44,68,77,98,100,115,125，的判定树见图8-3。,从图8-3 可知，查找根结点68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到结论：二叉树第K层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。假设该二叉树的深度为h，则二分查找的成功的平均查找长度为（假设每个结点的查找概率相等）：,ASL=1/n 1/n（1+22+322+h2h-1），因此，在最坏情形下，上面的不等号将会成立，并根据二叉树的性质，最大的结点数n=2h-1，h=log2(n+1)，于是可以得到平均查找长度ASL=(n+1)/n log2(n+1)-1。该公式可以按如下方法推出：,设s=20+2.21+3.22+(h-1).2h-2+h.2h-1则2s=21+2.22+(h-2).2h-2+h-1).2h-1+h.2hs=2s-s=h.2h-(20+21+22+2h-2+2h-1)=h.2h-(2h-1)=log2(n+1).(n+1)-n,所以，ASL=s/n=(n+1)/n log2(n+1)-1。,当n很大时，ASL log2(n+1)-1 可以作为二分查找成功时的平均查找长度，它的时间复杂度为O(log2n)。,8.2.3 索引查找1.索引查找的思想,索引查找，又称分级查找，它既是一种查找方法，又是一种存贮方法，称为索引存贮。它在我们的日常生活中有着广泛的应用。例如，在汉语字典中查找某个汉字时，若知道某个汉字读者，则可以先在音节表中查找到对应正文中的页码，然后再在正文中所对应的页中查出待查的汉字；若知道该汉字的字形，但不知道读者，则可以先在部首表中根据字的部首查找到对应检字表中的页码，再在检字表中根据字的笔画找到该汉字所在的页码。在这里，整个字典就是索引查找的对象，字典的正文是字典的主要部分，被称之为主表，而检字表，部首表和音节表都有是为了方便查找主表而建立的索引，所以被称之为索引表。,在索引查找中，主表只有一个，其中包含的是待查找的内容，而索引表可以有多个，包含一级索引，二级索引，所需的级数可根据具体问题而定。如刚才的利用读音查找汉字为一级索引，而 利用字形查找汉字为二级索引（部首表检字表汉字）。在此，我们仅讨论一级索引。,索引查找是在线性表（主表）的索引存贮结构上进行的，而索引存贮的基本思想是：首先将一个线性表（主表）按照一定的规则分成若干个逻辑上的子表，并为每个子表分别建立一个索引项，由所有这些索引项得到主表的一个索引表，然后，可采用顺序或链接的方法来存储索引表和各个子表。索引表中的每个索引项通常包含三个域：一是索引值域，用来存储标识对应子表的索引值，它相当于记录的关键字，在索引表中由此索引值来唯一标识一个索引项（子表）；二是子表的开始位置，用来存储对应子表的第一个元素的存储位置；三是子表的长度，用来存储对应子表的元素个数。,例如，设有一个学校部分教师档案表如表8-1所示，设编号为主关键字，则该表可以用一个线性表L=（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10）来表示，其中ai(1in)表示第i位教师的信息（包含有编号，姓名，部门，职称），而它的索引表可以按部门进行，也可以按职称进行，按部门的索引表中有4个子表，分别为：计算机系J=（a1,a2,a3,a4）电工系 D=(a5,a6,a7)管理系G=(a8,a9)成教部C=(a10),该4个子表示成一个索引表如表8-2所示。,表8-1 教师档案表,表8-2 按部门的索引表,index start length,若按职称进行索引，则得到的索引表中也有4个子表，分别为：Jiaosou=(a1,a8)FuJiaosou=(a3,a7,a10)Jiangshi=(a2,a5,a9)Zhujiao=(a4,a6),这时的主表用顺序存贮不太方便，因相同职称的教师没有连在一起，故用链式存储得到主表较方便。具体的存贮如图8-4所示。在图8-4中，箭头上面的数字表示该元素在主表中的下标位置（指针），每个子表中最后个元素的指针为-1，表示为空指针。,于是，可以得到如表8-3所示的职称索引表。,表8-3 按职称的索引表 index start length,从刚才的两种索引表中，可以给出索引查找的基本思想如下：第一步，在索引表中按index域查找所给值K1，这时可得到子表起始位置start 和长度length，若找不到K1，结束查找，表示查找不成功。第二步，在主表的start位置开始，长度为length的范围内查找所给值K2，若找到，查找不成功，否则，查找不成功。,例如，对于按部门的索引查找，主表可以用顺序存贮，假设K1=“D”，“D”代电工系，K2=“孙六”，则先在表8-2的索引表中找到的index域为“D”的项，得到start=4，length=3，然后从主表的第4个位置开始（即a5）找姓名为“孙六”的人，则在主表的第5个位置可以找到，故查找成功。若假设K1=“D”，K2=“杨九”，则索引表的查找与上面相同，然后在主表的第4个位置开始查找，没找到，进入第5个位置查找，还没找到进入第6位置查找，仍然没找到，但查找的length=3，既只允许3次查找，故查找不成功。若假设K1=“F”，K2=“张三”，则首先在索引表中就找不到“F”，故无需进入主表进行查找，查找不成功。,3.索引查找的性能分析,由于索引查找中涉及到两方面查找，第一个是索引表的查找，第二个是主表的查找，假设两种查找都按顺序查找方式进行，则索引表的平均查找长度为(m+1)/2，主表中的平均查找长度为（s+1）/2，(m为索引表的长度，S为主表中相应子表的长度)，则索引查找的平均查找长度为：ASL=(m+1)/2+(s+1）/2。若假定每个子表具有相同的长度，而主表的长度为n，则有n=m.s，这时当s=时，索引查找具有最小的平均查找长度，即ASL=1+。从该公式可以看出，索引查找的 性能优先顺序查找，但比二分查找要差，时间复杂度介于O(log2 n)O(n)之间。,8.2.4分块查找 1.分块查找 的思想,分块查找实际上就是一种索引查找，但查找的性能更优先于索引查找。原因是分块查找的索引表是一个有序表，故可以用二分查找 来代替 顺序查找 实现索引 表的快速查找。具体实现如下：将一个含有n个元素的主表分成m个子表，但要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，然后建立索引表，索引表中索引域的值用每个子表最大关键字代替，则可以按索引查找思想找到表中元素。,例如，给定关键字序列如下：18,7,26,34,15,42,36,70,60,55,83,90,78,72,74，假设m=3，s=5，即将该序序分成3个子表，每个子表有5 个元素，则得到的主表和索引表如图8-5所 示。,3.分块查找的性能分析,分块查找实际上就是索引查找,但分块查找中索引的域的类型与主表的关键字域的类型相同，且索引表按索引域递增（或递减）有序，故它的平均查找长度与索引查找接近，且优于索引查找。,83 树表查找,8.3.1二叉排序树查找1什么是二叉排序树,二叉排序树（Binary Sorting Tree），它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：(1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字；(3)左、右子树本身又都是一棵二叉排序树。,2二叉排序树的数据类型描述,和第六章类似，可以用一个二叉链表来描述一棵二叉排序树，具体为：struct Btreenode elemtype data;/代表关键字 Btreenode*left,*right;/代表左、右孩子;,3二叉排序树的基本运算,（1）二叉排序树的插入 若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为左子树插入，否则作为右子树插入，算法描述为：,void Insert(Btreenode*BST,elemtype X)if(BST=NULL)Btreenode*p=new Btreenode;p-data=X;p-left=p-right=NULL;BST=p;else if(BST-data=X)Insert(BST-left,X);/在左子树中扦入else Insert(BST-right,X);/在右子树中扦入,（2）二叉排序树的建立只要反复调用二叉排序树的扦入算法即可，算法描述为：,Btreenode*Creat(int n)/建立含有n个结点的二叉排序树 Btreenode*BST=NULL;for(int i=1;ix;/输入关键字序列Insert(BST,x);return BST;,例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图8-6所示。（注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样）,4二叉排序 树上的查找,（1）二叉排序 树的查找思想若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。,（2）二叉排序树查找的算法实现,Btreenode*find(Btreenode*BST,elentype x)/在以BST为根指针的二叉排队 树中查找值为x的结点 if(BST=NULL)return NULL;/查找失败 else if(BST-data=x)/查找成功 return BST;else if(BST-datax)/进入左子树查找 return find(BST-left,x);else/进入右子树查找 return find(BST-right,x);,5二叉排序树查找的性能分析,在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。,8.3.2平衡二叉树查找1平衡二叉树的概念,平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。,若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。如图8-8所示二叉排序树，是一棵平衡二叉树，而如图8-9所示二叉 排序树，就不是一棵平衡二叉树。,2.非平衡二叉树的平衡处理,若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与扦入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。,（1）LL型 的处理(左左型)如图8-10所示，在C的左孩子B上扦入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待扦入结点A作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子),（2）LR型的处理(左右型)如图8-11所示，在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。,（3）RR型的处理(右右型)如图8-12所示，在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待扦入结点C成为B的右子树。,（4）RL型的处理(右左型)如 图8-13所示，在A的右孩子C上扦入一个左孩子B，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将B变到A与C之间，使之成为RR型，然后按第(3)种情形RR型处理。,例8-2，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图8-14。,3平衡二叉树的查找及性能分析,平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。,例8-3，对例8-2给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-14，得到的二叉排序树见图8-15。,从图8-15的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-14的平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。,从结果可知，平衡二叉树的查找性能优于二叉排序树。,84 散列查找,8.4.1 基本概念散列查找，也称为哈希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表。散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造散列函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。例如，要找关键字为k的元素，则只需求出函数值H（k），H（k）为给定的散列函数，代表关键字k在存贮区中的地址，而存贮区为一块连续的内存单元，可用一个一维数组(或链表)来表示。,例8-4，假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为：H（18）=18%13=5 H（75）=75%13=10 H（60）=60%13=8 H（43）=43%13=4 H（54）=54%13=2 H（90）=90%13=12 H（46）=46%13=7于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT（散列表）中，具体表示为：,其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H（75）=75%13=10，则可以在HT10中找到75。,上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。,在散列存贮中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使散列查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。第一是与装填因子有关，所谓装填因子是指散列表中己存入的元素个数n与散列表的大小m的比值，即=n/m。当越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将变得太小，这样将会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。第二是与所构造的散列函数有关(前面己介绍)。第三是与解决冲突的方法有关，这些内容后面将再作进一步介绍。,8.4.2 散列函数的构造散列函数的构造目标是使散列地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单。具体常用的构造方法有如下几种：,1直接定址法 可表示为H（k）=a.k+b，其中a、b均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。,2数字分析法对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。,例如，对如下的关键字序列：430104681015355 430101701128352 430103720818350 430102690605351 430105801226356,通过对上述关键字序列分析，发现前5位相同，第6、8、10位上的数字变化多些，若规定地址取3位，则散列函数可取它的第6、8、10位。于是有：H（430104681015355）480H（430101701128352）101H（430103620805351）328H（430102690605351）296H（430105801226356）502,3平方取中法取关键字平方后的中间几位为散列函数地址。这是一种比较常用的散列函数构造方法，但在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。,如图8-16中，随机给出一些关键字，并取平方后的第2到4位为函数地址。,4折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列函数地址，称为折叠法。,例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有53558101104643014932，舍去高位，则有H（430104681015355）4932为该身份证关键字的散列函数地址。,5除留余数法该方法是用关键字序列中的关键字k除以散列表长度m所得余数作为散列函数的地址，即有H（k）km。,除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的m值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。一般情形下，m取为一个素数较理想，并且要求装填因子最好是在0.60.9之间，所以m最好取1.1n1.7n之间的一个素数较好，其中n为散列表中待装元素个数。,8.4.3 解决冲突的方法由于散列存贮中选取的散列函数不是线性函数，故不可避免地会产生冲突，下面给出常见的解决冲突方法。,1开放定址法开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中找出一个空闲的存储单元，把发生冲突的待扦入关键字存储到该单元中，从而解决冲突的发生。,在开放定址法中，散列表中的空闲单元（假设地址为K）不仅向散列地址为K的同义词关键字开放，即允许它们使用，而且还向发生冲突的其它关键字开放（它们的散列地址不为K），这些关键字称为非同义词关键字。例如，设有关键字序列14，27，40，15，16，散列函数为H（k）=k%13，则14，27，40的散列地址都为1，因此发生冲突，即14，27，40互为同义词，这时，假设处理冲突的方法是从冲突处顺序往后找空闲位置，找到后放入冲突数据即可。则14放入第1个位置，27只能放入第2个位置，40就只能放入第3个位置，接着往后有关键字15，16要放入散列表中，而15，16的散列地址分别为2和3，即15应放入第2个位置，16应放入第3个位置，而第2个位置己放入了27，第3个位置己放入了40，故也发生冲突，但这时是非同义词冲突，即15和27、16和40相互之间是非同义词。这时，解决冲突后，15应放入第4个位置，16应放入第5个位置。因此，在使用开放定址法处理冲突的散列表中，地址为K的单元到底存储的是同义词中的一个关键字，还是非同义词关键字，这就要看谁先占用它。,在开放定址法中，解决冲突时具体使用下面一些方法。（1）线性探查法,假设散列表的地址为0m-1，则散列表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾m-1时，又从0，1，2，.开始探查)等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。假设发生冲突时的地址为d0=H(k)，则探查下一位置的公式为di=(di-1+1)%m(1im-1)，最后将冲突位置的关键字存入di地址中。,例8-5 给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数H（k）=k%13，散列表空间地址为012，试用线性探查法建立散列存贮(散列表)结构。得到的散列表如图8-17所示,(2)平方探查法该方法规定，若在d地址发生冲突，下一次探查位置为d+12，d+22，直到找到一个空闲位置为止。,(3)双散列函数探查法该方法使用两个散列函数H和T，用H作散列函数建立散列存储（散列表），用T来解决冲突。具体实施时，若H(k)在d0位置发生冲突时，即d0=H(k)，则下一个探查位置序列应该是di=(di-1+T(k)%m(1im-1)。,2.拉链法拉链法也称链地址法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表,例8-6 对例8-5给定的关键字序列19,14,23,1,68,20,84,27,55,11,10,79，给定散列函数为H(k)=k%13，试用拉链法解决冲突建立散列表。,图8-18为用尾插法建立的关于例8-6的拉链法解决冲突的散列表。,8.4.5 散列查找的性能分析散列查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。,1.线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的散列函数H及装填因子的值和该处理方法有关，这时的成功的平均查找长度为ASL=1/2(1+1/(1-)。.,2.拉链法查找的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。它的平均查找长度ASL=1+/2。,例8-7 给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、散列查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。散列函数H(k)=k%11。,顺序查找的顺序表（一维数组）如图8-19所示，,从图8-19可以得到顺序查找的成功平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=4.5；,二分查找的判定树（中序序列为从小到大排列的有序序列）如图8-20所示，,从图8-20可以得到二分查找的成功平均查找长度为：ASL=(1+2*2+3*4+4)/8=2.625；,二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图 8-21(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图8-21(b)所示，,从图8-21(a)可以得到二叉排序树查找的成功平均查找长度为：ASL=(1+2*2+3*2+4+5*2)=3.125；从图8-21(b)可以得到平衡二叉树的成功平均查找长度为：ASL=(1+2*2+3*3+4*2)/8=2.75；,线性探查法解决冲突的散列表如图8-22所示，,从图8-22可以得到线性探查法的成功平均查找长度为：ASL=（1+1+2+1+3+2+1+8）/8=2.375；,拉链法解决冲突的散列表如图8-23所示。,从图8-23可以得到拉链法的成功平均查找长度为：ASL=(1*6+2*2)/8=1.25。,