1、Data Structure,第九章 查找,9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找 9.2 动态查找表9.2.1 二叉排序树和二叉平衡树9.2.2 B-树 9.3 哈希（Hashing）表（散列表）,Data Structure,一、教学目的与要求了解查找的基本概念和基本方法，掌握常用查找的算法 二、主要教学内容顺序查找和二分查找；索引查找和分块查找；散列查找；B树查找 三、教学重点、难点顺序查找和二分查找、索引查找和分块查找 四、授课方法及手段采用多媒体大屏幕投影授课 五、讲课具体内容（讲稿）,Data Structure,第九章 查找,查找表 (search t
2、able)：同一类型数据元素构成的集合。 查找操作： (1)查询某个“特定的”数据元素是否在查找表中; (2)检索某个“特定的”数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删除某个数据元素. 静态查找表：对查找表只作(1)、(2)操作； 动态查找表：可以对查找表作(1)-(4)操作。,Data Structure,有关查找的“词”的含义,关键字(KEY): 数据元素(或记录)的某个数据项的值，用以标识一个数据元素(或记录)。 可以唯一标识一个记录的关键字称为主关键字(Primary Key)；否则称为次关键字(Secondary Key)。 查找(Searchin
3、g) 根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素。 查找可能是成功的，也可能是不成功的。,Data Structure,9.1 静态查找表,可以用顺序表，也可以用线性链表来表示静态查找表顺序表的查找 /静态查找表的顺序存储结构 typedef struct ElemType *elem; /0号单元未用int length; SSTable;,Data Structure,监视哨,使用了监视哨，在查找过程中，不用每一步都去判断查找是否结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。,Data Structure,int Search_seq (SSTable
4、 ST, KeyType key) ST.elem0.key=key;for (I=st.length; !EQ(st.elemI.key,key); -I); /从表尾往前查return i; /Search_Seq,顺序查找算法：,Data Structure,根据上述算法可知：查找成功时的平均查找次数为：ASL=(1+2+3+4+n)/n=(n+1)/2查找不成功时的比较次数为： n+1则顺序查找的平均查找长度为：ASL = (n+1)/2+n+1)/2=(n+1)3/4,顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。 顺序查找的缺点：平均查找长度较大。,Data Stru
5、cture,9.1.2 有序表的查找（折半查找、二分法查找）,分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。,Data Structure,查找21的过程如下图（mid=(low+high)/2不进位取整）,(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92
6、),1 2 3 4 5 6 7 8 9 10 11,(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),Data Structure,查找85的过程如下图（mid=(low+high)/2不进位取整）,1 2 3 4 5 6 7 8 9 10 11,(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),(05, 13, 19, 21, 37, 56,
7、64, 75, 80, 88 92),(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),(05, 13, 19, 21, 37, 56, 64, 75, 80, 88 92),Data Structure,折半查找算法： int Search_Bin( SSTable ST, KeyType key) low=1; high=ST.length;while (low=high) mid=(low+high)/2;if EQ(key,ST.elemmid.key) return mid; /查找成功else if LT(key,ST.elemmid.key)
8、 high=mid-1; /在前半区间继续查找else low=mid+1; /在后半区间继续查找 /End whilereturn (0); /查找不成功 /End,Data Structure,折半查找的性能分析,判定树上每个结点需要的查找次数刚好为该结点所在的层数；,查找成功时查找次数不会超过判定树的深度；,n个结点的判定树的深度为 log2n+1；,折半查找的算法复杂度为log2n+1。,判定树：用树来表示查找过程，树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置。 查找上例中所有元素的二叉判定树为：,Data Structure,是顺序查找的一种改进方法，就是把被查找的表
9、分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。,9.1.4 索引顺序表查找（分块查找）,Data Structure,索引表,块中的最大关键字,块内第一个记录位置的指针,Data Structure,分块查找步骤：,查索引表，确定要找的记录在哪一块。（方法1：顺序查找；方法2：折半查找） 2.
10、 在相应的块中查找（顺序查找）。,例如，要找关键字为22的记录。由索引的第一项可知，要找的记录要么在第二块中，要么不存在。并获取第二块中第一个记录的位置。,Data Structure,思考：,上例中，15个数据分成3块查找，与15个数据分成5块查找，效率哪个高？ 如有900个数据，如何分块才能实现查找效率和空间效率的最优？答：分成30块，每块30个数据,Data Structure,9.2 动态查找表,什么是二叉排序树(Binary Sort Tree) ?二叉排序树是空树,或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树非空,则右
11、子树上所有结点的值均大于它的根结点的值;(3)它的左、右子树也分别为二叉排序树。,9.2.1 二叉排序树,Data Structure,二叉排序树举例,查找过程：从根结点出发，结点的值与key进行比较： （1）相等时查找成功； （2）key较大时，沿右子树继续查找（无右子树则查找失败）； （3）key较小时，沿左子树继续查找（无左子树则查找失败）。,其中序遍历序列为： 3,12,24,37,45,53,61,78,90,100,Data Structure,算法9.5(a)：二叉排序树递归查找算法1,BiTree SearchBST(BiTree T, keyType key) /在根指针T所
12、指二叉排序树中递归查找Key，若查找成功，返回指向该结点的指针，否则返回空指针。if (!T) | EQ(key,T-data.key) return(T); /查找结束else if LT(key,T-data.key) return(SearchBST(T-lchild,key); /在左子树中继续查找else return(SearchBST(T-rchild,key);/在右子树中继续查找 /SearchBST,Data Structure,二叉排序树的生成（插入结点）, 10、18、3、8、12、2、7、5 ,10,10,18,3,8,12,2,7,5,Data Structure,
13、算法9.5(b)：二叉排序树递归查找算法2,BiTree SearchBST(BiTree T, keyType key,BiTree f,Bitree /在右子树中继续查找 /SearchBST,Data Structure,算法9.5(c)：二叉排序树非递归查找算法,BiTree SearchBST(BiTree T, keyType key, Bitree /查找不成功 /SearchBST,Data Structure,算法9.6：二叉排序树结点插入算法,BiTree Insert BST(BiTree /树中已有此关键字，不再插入 /Insert BST,Data Structure
14、,二叉排序树结点的删除 （保持二叉排序树的特性及次序）,设被删除的结点为*p,其父结点为*f, 假设*p为*f的左孩子,则：(1)若*p为叶结点,即PL和PR均为空.直接删除不会影响树结构;,If (f-Lchild = = p)f-Lchild = NULL; Elsef-Rchild = NULL; free(p);,Data Structure,(2)若*p只有PL或只有PR,只要令PL或PR直接成为其双亲结点*f的左孩子即可,这样也不会影响树结构;,If (p-Lchild != NULL)f-Rchild = p-Lchild; Elsef-Rchild = p-Rchild; fr
15、ee(p);,Data Structure,(3)若*p有PL也有PR,为保持中序遍历二叉树的序列不变,可以有两种处理方法： 其一是令PL为*f的左子树,PR为*s的右子树(*s为中序遍历PL的最后一个结点); 其二是令*p的直接前驱(或直接后继)*s替代*p,然后删除直接前驱(或直接后继)*s.若*s有左孩子则左孩子取代*s的位置.这样虽然影响了树结构,但不会影响中序遍历二叉树时的结点次序。,Data Structure,在二叉排序树中删除结点*p,方法1,方法2,Data Structure,算法9.7：二叉排序树结点删除算法,BiTree DeleteBST(BiTree /end el
16、se /DeleteBST,Data Structure,算法9.8（注意：教材程序有错）,Void Delete(BiTree /重接*q的左子树/end else /Delete,f-lchild=q;,f-lchild=q;,free(s);,Data Structure,二叉排序树的查找分析,n个结点的二叉排序树的平均查找长度和树的形态有关。例：45,24,53,45,12,37,93 最坏情况是二叉排序树蜕变单支树:12,24,37, 45,53,93,ASL = O(log2n),ASL = O(n/2),Data Structure,二叉排序树举例,已知如下所示长度为12的字符串
17、表(Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度ASL;(2)若对表中元素先进行排序构成有序表,求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度;,Data Structure,二叉排序树举例1,(Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec),在等概率(1/12)的情况下查找成功的平均查找长度:,ASL=(1+2*2+3*3+4*3+5
18、*2+6*1)/12= 42/12 = 3.5,二叉排序树,Data Structure,July,Dec,Apr,May,June,Oct,Feb,Nov,Dec,判定树,Jan,Aug,Aug,二叉排序树举例2,(Apr,Aug,Dec,Fab,Jan,July,June,Mar,May,Nov,Oct,Sep),其在等概率(1/12)的情况下查找成功的平均查找长度:,ASL=(1+2*2+3*4+4*5)/12 = 37/12 = 3.1,Data Structure,平衡二叉树,什么是平衡二叉树(Balanced Binary Tree) ?平衡二叉树是空树，或者是具有以下性质的二叉树
19、： 它的左子树和右子树也都是平衡二叉树 且左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF(Balance Factor)是 左子树的深度减去右子树的深度,它只可能是-1、0、1 平衡二叉树(也称AVL树)的深度为O(log2N)(其中N为结点个数) 它的平均查找长度也是O(log2N),Data Structure,平衡二叉树及平衡因子举例,平衡的二叉树,Data Structure,不平衡的二叉树,不平衡二叉树及平衡因子举例,Data Structure,二叉排序树转成平衡树示例 设关键字序列为(13,24,37,90,53),Data Structure,二叉排序树转成平衡树
20、 失去平衡后进行调整的四种情况,(1)单向右旋平衡处理 当在左子树上插入左结点,使平衡因子由1增至2时 (2)单向左旋平衡处理(上例从图(d)到图(e) 当在右子树上插入右结点,使平衡因子由-1增至-2时 (3)双向旋转(先左后右)平衡处理 当在左子树上插入右结点,使平衡因子由1增至2时 (4)双向旋转(先右后左)平衡处理 当在右子树上插入左结点,使平衡因子由-1增至-2时 (例如上例从图(f)右旋到图(g)再左旋到图(h),Data Structure,2.非平衡二叉树的平衡处理,若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变
21、成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。,Data Structure,（1）LL型 的处理(左左型)将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。,Data Structure,LL型的复杂情况：,Data Structure,（2）LR型的处理(左右型)将C变到B与A之间，使之成为LL型，然后按第(1)种情形LL型处理。,Data Structure,LR型的复杂情况：,Data Structure,（3）RR型的处理(右右型)将A逆时针旋转，成为B的左子树，而原
22、来B的左子树则变成A的右子树，待插入结点C成为B的右子树。,Data Structure,RR型的复杂情况：,Data Structure,（4）RL型的处理(右左型)将C变到A与B之间，使之成为RR型，然后按第(3) 种情形RR型处理。,Data Structure,RL型的复杂情况：,Data Structure,给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉排序树。 分析：平衡二叉树实际上也是二叉排序树，故可以按建立二叉排序树的思想建立。 在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。,例题：,注意：插入结点后若出现多个结点不平衡，则调
23、整离插入点最近的不平衡点，并往插入点方向走2步，以确定其形状。,Data Structure,(a) 插入4,(b) 插入5,(c) 插入7,(d) 插入2,(e) 插入1,Data Structure,(f) 插入3,(g) 插入6,Data Structure,3平衡二叉树的查找及性能分析,平衡二叉树本身就是一棵二叉排序树，故它的查找方法与二叉排序树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。,Data Structure,9.2.2 B-树和B+树,前面所讨论的查找算法都是
24、在内存中进行的，它们适用于较小的文件，而对较大的、存放在外存储器上的文件就不合适了。1972年R.Bayer和E.M.McCreight提出了一种称为B-树的多路平衡查找树，它适合在磁盘等直接存取设备上组织动态的查找表。,Data Structure,一棵 m 阶的B-树，或是空树，或是满足以下条件的 m 叉树：（1）树中每个结点至多有 m 棵子树（2）若根结点不是叶子结点，则至少有二棵子树。（3）除根结点外的所有非终端结点至少有m/2棵子树（4）所有结点包含信息（n,A0,K1,A1,Kn,An)，其中Ki为关键字且有序。Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+
25、1,An所指子树中所有结点的关键字均大于Kn（5）所有叶子结点都出现在同一层次上，即所有空的指针出现在同一层上。,Data Structure,n+1个分支,Data Structure,B-树的操作,（1）查找要查找关键字k的记录，首先从根结点开始，若找到则找所对应的记录，否则沿p所指的子树继续查找，其中：A0 kKn若直到叶子结点还未找到，则查找失败。,Data Structure,（2）插入：设要插入关键值为k的记录，指向k所在记录的指针为p。首先找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-
26、1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是：申请一个新结点，由指针p指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。,Data Structure,插入30 ：,例：在下图的B-树中插入结点30和85,30 37,Data Structure,61 70 85,Data Structure,Data Structure,（3）关键字的删除（略）在B-树中删除一个关键字，首先应找到该关键字所在结点，并从中删除之。若该结点
27、为最下层的非终端结点，且其中的关键字数目不少于m/2，则删除完成，否则要进行“合并”结点的操作。假若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y替代Ki，然后在相应的结点中删去Y。因此，我们可以只讨论删除最下层非终端结点中的关键字的情形。有三种可能：（1）、（2）、（3）P244,Data Structure,9.3 哈希表（散列表）,在已经介绍过的线性表、树等数据结构中，记录存储在结构中的相对位置是随机的，因而相应的检索是通过若干次的比较以寻找指定的记录。,新的存储结构：散列存储 ，它既是一种存储方式，又是一种常见的检索方法。,Data Structure,散列存储
28、的基本思想：以关键码的值为自变量，通过一定的函数关系（称为散列函数，或称Hash函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。,9.3.1 什么是哈希表（散列表）,Data Structure,例：假设关键字序列为18,75,60,43,54,91,46，哈希函数为H(k)=k%10，存贮区的内存地址从0到12，则哈希表为：,H(18)=18%10 = 8,H(75)=75%10 = 5,H(60)=60%10 = 0,H(43)=43%10 = 3,H(54)=54%10 = 4,H(91)=91%10 = 1,H(46)=46%10 = 6,0
29、 1 2 3 4 5 6 7 8 9 10 11 12,60,91,43,54,46,18,75,哈希表 HT,Data Structure,从哈希表中查找一个元素相当方便，例如，查找75，只需计算出H(75)=75%10=5，即可在HT5中找到75。在存储时，以每个记录的关键字为自变量，通过哈希函数计算出存储地址，将该记录存放在存储地址对应的存储单元中。在查找时，以查找值为自变量，通过哈希函数计算出地址，从该地址所对应的存储单元中取出记录数据。,Data Structure,上面讨论的哈希表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形：两个不同的关键字有可能对
30、应同一个内存地址，即两个记录的关键值不等，但它们的哈希函数的值相同，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突(collision)。哈希函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。使用哈希方法，首先要选择一个好的哈希函数，使一组关键值所得到的哈希地址能均匀分布在整个地址空间中，并且冲突次数尽可能地少。,Data Structure,虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关：,第一是与装填因子有关。所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即=n/m。当越小时，发生冲突的可能性越小，越大（最大为1）时
31、，发生冲突的可能性就越大。第二是与所构造的哈希函数有关。第三是与解决冲突的方法有关，这些内容后面将再作进一步介绍。,Data Structure,9.3.2 哈希函数的构造哈希函数的构造目标是使哈希地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单，冲突次数少。常用的构造方法有如下几种：,对于Hash方法，需要研究下面两个主要问题：（1）选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数；（2）确定解决冲突的方法。,Data Structure,Data Structure,中间的四位的数字变化多些，可看成是随机的，若规定地址取3位，则哈希函数可取它的第4、5、6位。于是有：,通过
32、对上述关键字序列分析，发现前3位相同，第8位只有2、3、7三种值，因此，这四位不可取。,例如，对如下的关键字序列：9 9 3 4 6 5 3 29 9 3 7 2 2 4 29 9 3 8 7 4 3 39 9 3 0 1 3 6 7 9 9 3 2 2 8 1 79 9 3 3 8 9 6 79 9 3 5 4 1 5 79 9 3 6 8 5 3 79 9 3 6 8 5 3 2 ,H（99346532）465 H（99372242）722 H（99387433）874 H（99301367）016 H（99322817 ）228 ,Data Structure,取关键字平方后的中间几位为
33、哈希函数地址。这是一种比较常用的哈希函数构造方法。通常在选定哈希函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希函数地址也是随机的。,3平方取中法,Data Structure,如下图，随机给出一些关键字，取平方后的第2位到第4位为函数地址。,Data Structure,将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希函数地址，称为折叠法。,Data Structure,除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想
34、的p值，尽可能减少发生冲突的可能性。一般情形下，p取为一个素数较理想，并且要求装填因子最好是在0.60.9之间。所以p最好取1.1n1.7n之间的一个素数，其中n为哈希表中待装元素个数。,5除留余数法该方法是用关键字序列中的关键字k除以一个整数p所得余数作为哈希函数的地址，即：H(k)kp （p=m，m为哈希表长度）,Data Structure,9.3.3 解决冲突的方法由于哈希存贮中选取的哈希函数不是线性函数，将大的关键值的取值空间映射到小的地址空间中，故不可避免地会产生冲突。 哈希冲突的可能性有多大呢？,Data Structure,例：生日的惊奇,在一个房间里需要有多少个随机挑选的人，
35、才可能有两个人具有同样的生日（月和日）？一年有365个可能的生日（除了闰年以外），那么答案是不是“几百人”呢？,Data Structure,解题思路：在一个房间里有m个随机挑选的人，没有两个人具有相同生日的概率是多大？从任意一个人开始，第二个人与第一个人有不同生日的概率是364/365，第三人与前两人有不同生日的概率是363/365，第m人与前面的人有不同生日的概率为(365-m+1)/365。那么，m个人具有不同生日的概率是：,只要m=23，表达式的值就小于0.5 所以答案是：23,Data Structure,开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从哈希表中找出一个空闲
36、的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突的发生。开放定址法利用下列公式求“下一个”空地址：Hi=(H(key)+di) MOD m i=1,2,K(K=m-1) 其中：H(key)为哈希函数，m为哈希表长度，di为增量序列,1开放定址法,Data Structure,根据di的取法，解决冲突时具体使用下面一些方法： （1）线性探查法,假设哈希表的地址为0m-1，则哈希表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾m-1时，又从0，1，2，.开始探查)等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。,
37、Data Structure,例8-5：给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，哈希函数H（k）=k%13，哈希表空间地址为012，试用线性探查法建立哈希存贮（哈希表）结构。得到的哈希表如下图所示：,开放地址法充分利用了哈希表的空间，但在解决一个冲突时，可能造成下一个冲突。另外，用开放地址法解决冲突不能随便对结点进行删除。,Data Structure,链地址法也称拉链法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表。,例：对给定的关键字序列19,14,23,1,68,20,84, 27,55,11, 10,79，
38、给定哈希函数为H(k)=k%13，试用拉链法解决冲突建立哈希表。,2. 链地址法,Data Structure,数据：19,14,23,1, 68,20,84,27,55,11, 10,79,哈希函数：H(k)=k%13,Data Structure,哈希查找按理论分析，它的时间复杂度应为O(1)它的平均查找长度应为ASL = 1但实际上由于冲突的存在它的平均查找长度将会比1大,9.3.4 哈希查找的性能分析,Data Structure,由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子的值和该处理方法有关，这时的成功的平均查找长度为 ASL=1/2 (1+1/(1- ),1.线性探查法的性能分析,Data Structure,由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。 它的平均查找长度为： ASL=1+/2,2.拉链法查找的性能分析,
