专升本之查找

1、数据结构之查找1)了解查找表和平均查找长度的定义查找表：由一类同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查询表是一种非常灵便的数据结构。平均查找长度：注明：n是查找表的元素个数，Pi是查找第i个元素的概率，通常假设每个查找元素概率相同即 nCi=1i1(Pi=1/n),Ci是查找第i个元素需要比较的次数(轮到与这个元素比较时已经比较了几次)如：等概率的顺序查找的ASL第一个元素须比较1次，第二个元素须比较2次第n个元素须比较n次，所以Ci=1+2+3+.n=(1+n)*n)/2。(书上的Ci一般是n-i+1,从后往前查找：第0个元素需要比较n

2、+1次，第1个元素需要比较n次.第n-1个元素须比较2次，第n个元素须比较1次，则第i个元素时需比较n-i+1)=1/n*i(1+n)*n)/2=(n+1)/2。2)掌握顺序查找、折半查找和分块查找算法设计和算法分析顺序查找：/*顺序查找，a为数组，n为要查找的数组长度，key为要查找的关键字*/intSequential_Search(int*a,intn,intkey)inti;for(i=1;in;i+)if(ai=key)returni;return0;公式：ASL成功=nPiCiASL=nPiCi=1/n*nCi因为每次循环都需要对是否越界，即是否小于n做判断。事实上，还可以有更好一

3、点的办法，设置一个哨兵，可以解决不需要每次让i与n作比较。intSequential_Search2(int*a,intn,intkey)inti;a0=key;设置a0为关键字值，称为哨兵i=n;循环从数组尾部开始while(ai!=key)i-；)returni;/返回0,说明查找失败算法分析：对于这种算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为O(1),最坏情况是在最后一个位置才找到，需要进行n次比较，时间复杂度为O(n),当查找不成功需要在n+1次比较，时间复杂度为O(n)。平均查找次数ASL=(n+1)/2,最终时间复杂度为O(n)。缺点：当平均查找长度较大

4、时即n很大时，查找效率较低，优点：算法简单且适应面广，对表的结构无任何要求，对线性链表也同样适用折半查找：/*折半查找*/intBinary_Search(int*a,intn,intkey)intlow,hight,mid;low=1;/定义最低下标为记录首位high=n;/定义最高下标为记录末位while(low=hight)mid=(low+high)/2;/折半if(keyamid)/若查找值比中值大low=mid+1;最低下标调整到中位下标大一位elsereturnmid;若相等说明mid即为查找到的位置算法分析：时间复杂度：？log2n?+1。ASL=log2(n+11,折半查找的

5、查找效率比顺序查找高,但折半查找只适用于有序表，且限于顺序存储结构(对线性链表无法有效的进行折半查找)分块查找(索引顺序查找)：块与块之间有序，块内无序(但第第1个块中的元素，依次类推)2个块中的所有元素均大于场景：若以索引顺序表表示静态查找表，除表本身外，尚需建立一个索引表，索引表包括两项：关键字项（其值为该字表（块）内最大关键字）和指针项（指示孩子表的第一个记录在表中的位置）例：假定需在一个表中查找key,子表有三个步骤：1、现将key依次和索引表中各最大关键字比较（），确定在哪一个具体的块中2、然后在这个确定的块中的第一个关键字开始顺序查找算法：要建一个索引表1.structindex/

6、定义块的结构2.(3.intkey;/块的关键字4.intstart;/块的起始值5.intend;/块的结束值6.index_table4;/定义结构体数组1.intblock_search(intkey,inta)/自定义实现分块查找2.(3.inti,j;4.i=1;5.while(iindex_tablei.key)/确定在哪个块中6.i+;7.if(i3)/大于分得的块数，则返回08.return0;9.j=indextablei.start;/j等于块范围的起始值10.while(jindextablei.end)/如果大于块范围的结束值，则说明没有要查找的数，j置013.j=0;

7、14.returnj;15.ASL=L(查找索引表确定所在块的查找，可顺序查找也可折半查找)为顺序查找)第一种：用顺序查找确定所在块ASL=1/2(n/s+s)+1第二种：用折半查找确定所在快ASL=log2(n/s+1)+s/2+L(块中的查找，只能算法分析：2)掌握二叉排序树的算法设计，了解平衡二叉树、B-和B+树的定义和查找过程二叉排序树(二叉查找树)：(1)若他的左子树不空，则左子树上所有节点的值均小于它的根节点的值；(2)若他的右子树不空，则右子树上的所有节点均大于他的根节点的值(3)他的左右数也分别为二叉排序树算法设计：/二叉树二叉链表结点的结构定义typedefstructBiT

8、Node(intdata;structBiTNode*lchild,*rchild;BiTnode,*BiTree;递归版本：Node*bstree_search(BSTreex,Typekey)(if(x=NULL|x-key=key)returnx;if(keykey)returnbstree_search(x-left,key);elsereturnbstree_search(x-right,key);非递归版本：Node*iterative_bstree_search(BSTreex,Typekey)(while(x!=NULL)&(x-key!=key)(if(keykey)

9、x=x-left;elsex=x-right;)returnx;)插入和删除：插入：StatusInsertBiTree(BiTree*T,intkey)BiTreep,s;if(!SearchBiTree(叮,key,NULL,&p)/查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=key;s-lchild=s-rchild=NULL;if(!p)*T=s;/插入s为新的根结点elseif(keydata)p-lchild=s;/插入s为左孩子elsep-rchild=s;/插入s为右孩子returnTRUE;)elsereturnFALSE

10、;)删除：/若二叉排序树T中存在关键字等于key的数据元素时，则删除该元素结点/并返回TRUE否则返回FALSEStatusDeleteBST(BiTree*T,intkey)if(!*T)/不存在关键字等于key的数据元素returnFALSE;elseif(key=(*T)-data)/找到关键字等于key的数据元素returnDelete(T);elseif(keydata)returnDeleteBST(&(*T)-lchild,key);elsereturnDeleteBST(&(*T)-rchild,key);)平衡二叉树（AVL树）：或是一棵空树或是具有以下性质的

11、二叉树：他的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。查找过程：性能分析：时间复杂度：O（logn）B刷：B-树是一棵多路查找树（并不一定是二叉的），一棵m阶的B-树，或为空树，或为满足以下特性：1）树中每个节点至多有m棵子树；2）若根节点不是叶子节点，则至少有两颗子树（2,m）;3）除根之外的所有非终端节点至少有m/2棵子树（m/2,m）;意图：在于保证B-树中节点空间的利用率不低于某个下限，改为2m/3则是不行的，应为当某节点应插入关键字而使其中关键字数目为m时，无法分裂成两个子树个数均大于2m/3的节点；改为m/3是可行的，但他的节点空间利用率较低，不过分

12、裂不如b-树那样频繁。4）所有非终端节点中包含下列信息数据（n,A0,K1,A1,K2,A2,K3.Kn.An）淇中Ki为关键字，且Ki35,则若存在必在指针A1所指的子树内，顺指针找到*c节点；2）该节点有两个关键字，而4347rchild=NULL)右子树为空，重接左子树q=*p;*p=(*p)-lchild;free(q);else(*p)-lchild=NULL)/左子树为空，重接右子树q=*p;*p=(*p)-rchild;free(q);elseq=*p;s=(*p)-lchild;while(s-rchild)转左，然后向右到尽头，找到待删结点前驱q=s;/q删除结点的前驱s=s

13、-rchild;/删除结点(*p)-data=s-data;/s指向被删除结点的前驱if(q!=*p)q-rchild=s-lchild;/重接q右子树elseq-lchild=s-rchild;/重接q左子树free(s);)returnTRUE;)B+树:一棵m阶的B+树和m阶B-W的差异在于：(1)有n棵子树的节点中含有n个关键字(一个节点中有几颗子树就有几个关键字，B-树是n-1个兀素)。(2)所有的叶子节点中包含了全部关键字的信息及指向含这些关键字记录的指针这两部分内容，且叶子节点本身依关键字的大小自小而大顺序链接。(3)所有的非终端节点可以看成是索引部分，节点中仅含有其子树(根节点

14、)中的最大(或最小)关键字。通常在B+树有两个头指针，一个指向根节点，另一个指向关键字最小的叶子结点。因此，可以对b+树进行两种查找运算：（1）从最小关键字其顺序查找。（2）从根节点开始，进行随机查找。优点：1、IO次数更少；2、查询范围简单；3、查询性能稳定3）掌握哈希表的基本概念、哈希函数构造方法、哈希冲突解决方法和哈希查找过程哈希表的基本概念：哈希表也称散列表，根据设定的哈希函数H（key）和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。

15、（是一种根据关键字值（key-value）而进行访问的数据结构）。他是通过把关键字映射到数组的下标来加快查找速度。哈希函数构造方法：好的哈希函数：使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。常用的构造哈希函数：1、直接定址法：取关键字或者关键字的某个线性函数值为哈希地址。H（key）=key或H（key）a*key+b2、数字分析法：假设关键字是以R为基的数，并且哈希表中可能出现的关键字都是事先知道的。则可取关键字的若干数位组成哈希地址。3、平方取中法：取关键字平方后的中间几位为哈希地址。适用场景：通常在选定哈希函数时不一定能知

16、道关键字的全部情况，选其中几位也不合适，而一个数的平方后的中间几位数和数的每一位都相关，由此使随机分布得到的哈希地址也是随机的，取的位数有表长决定。例：A关键字：0100（关键字）A2:0010000哈希地址：010（取中间三位）4、折叠法：将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加作为哈希地址。适用场景：关键字位数很多，而且关键字中每一位上数字分布均匀时。5、除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。这是最简单也是最常用的构造函数的方法，不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。6、随机数法：选择一个随

17、机函数，取关键字的随机函数值为他的哈希地址，即H(key)=random(key)使用场景：当关键字长度不等时叫恰当。处理哈希冲突：冲突：对不同的关键字可能得到同一哈希地址。一般情况下，冲突只可能的减少，而不能完全避免。因为哈希函数是从关键字集合到地址集合的映像。同义词：具有相同函数值的关键字对该哈希函数来说称作同义词解决处理冲突的方法1、开放定址法：Hi=(H(key)+di)MODmi=1,2,3,4,5.k(k=m-1)H(key)为哈希函数；m为哈希表长；di为增量序列。Di通常有三种取法：(1)di=1,2,3,4.m-1,称为线性探测再散列；(2)Di=1A2,-1A2,2A2,-2A2.+-kA2(k=m/2)称为二次探测再散列；(3)口1=伪随机数序列，称为随机探测再散列。列如：2、再哈希法：Hi=RHi(key)i=1,2,3,4,5.kRHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“凝聚”，但增加了计算的时间。3、链地址法：将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生哈