查找算法汇总

第1章查找表1.0基础知识简介1.1静态查找表1.2动态查找表1.3哈希表1.基本概念——若表中存在特定元素，称查找成功，应输出该记录——否则，称查找不成功（也应输出失败标志或失败位置）1)查找表2)查找3)查找成功4)查找不成功5)静态查找6)动态查找7)关键字8)主关键字9)次关键字——由同一类型的数据元素（或记录）构成的集合——查询(Searching)特定元素是否在表中——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素——元素中某个数据项的值，可用来识别一个元素

(预先确定的数据元素的某种标志)

——可以唯一标识一个元素的关键字例如“学号”例如“姓名”是一种数据结构——识别若干元素的关键字1.0基础知识2.对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表3.查找表的分类1.1静态查找表1、顺序表的查找2、有序表的查找3、索引顺序表的查找1、顺序表的查找L复习顺序表的查找运算线性表有两种基本的查找运算。按序号查找GetData(L,i):要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。复习顺序表的按内容查找算法分析：查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在表中的序号；若e与表中的所有元素都不相等，则查找失败，返回“-1”。复习算法实现：int

Locate(SeqListL，ElemTypee){

i=0;

//i为计数器,从第一个元素开始比较

while((i<=L.length-1)&&(L.elem[i]!=e))

/*顺序扫描表,直到找到值为e的元素,或扫描到表尾而没找到*/i++;

if

(i<=L.length-1)

return(i+1);

/*若找到值为e的元素，则返回其序号*/

else

return(-1);

/*若没找到，则返回空序号*/}typedefstruct{

//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int

length;//表的长度}SSTable;ElemType

*elem;i例01234567891011513192137566475808892找6464监视哨iiii比较次数=5技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。ST.elemiST.elemi60ikey=64key=60i64示例：已知静态查找表ST如下：intSearch_Seq(SSTableST,KeyTypekey){

//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;--i);

//从后往前找

returni;

//找不到时，i为0}//Search_Seq2、有序表的查找lowhighmidlowmid54上述顺序查找算法实现简单，但不适用于表长较大的查找表。折半查找为此引入折半查找算法先给数据排序（例如按升序排好），形成有序表，然后再将key与中间元素相比，若key小，则缩小至前半部内查找；若key大，则缩小至后半部内查找；intSearch_Bin(SSTableST,KeyTypekey){

low=1;

high=ST.length;

//置区间初值

while(low<=high){

mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))//＝＝returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))

//<

high=mid-1;//继续在前半区间进行查找

else

low=mid+1;

//继续在后半区间进行查找

}return0;//顺序表中不存在待查元素}//Search_Bin算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid查找过程：将表分成几块，块内无序，块间有序；先确定待查元素所在块，再在块内查找适用条件：分块有序表算法实现用数组存放待查元素,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针3.索引查找12345678910111213141516171822121389203342443824486058745786532248861713索引表查38查找过程：（1）先确定待查元素所在的块（子表）（2）然后在块中顺序查找ASL最大最小两者之间表结构有序表无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找索引查找1.2动态查找表一、二叉排序树二、平衡二叉树（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；一、二叉排序树503080209010854035252388例如:是二叉排序树。66不思考：二叉排序树的中序遍历序列有什么特点？二叉排序树的中序遍历序列是一个有序序列（升序）2．二叉排序树的查找算法1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。否则，若二叉排序树为空，则查找不成功；50308020908540358832例如:二叉排序树查找关键字==50,505035,503040355090,50809095从上述查找过程可见：在查找过程中，生成了一条查找路径：

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功根据动态查找表的定义，“插入”操作在查找不成功时才进行；3．二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。30201040352523设key=222245241253903027{45,24,53,12,30,27,90}（1）被删除的结点是叶子；4．二叉排序树的删除算法可分三种情况讨论：和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。50308020908540358832（1）被删除的结点是叶子结点例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”50308020908540358832（2）被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=408050308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点（中序遍历）被删关键字=505030802090854035883240被删关键字=50908588二、平衡二叉树树中每个结点的左、右子树深度之差的绝对值不大于1。例如:548254821是平衡树不是平衡树平衡因子又称AVL树，是具有如下性质的二叉树：如何构建一棵平衡二叉排序树？构建过程类似于二叉排序树的建立过程，即在二叉排序树的建立过程每当插入一个结点后，立刻检查该树是否平衡，如果平衡：继续；否则：进行相应的调整！构造平衡二叉树的方法：

插入、判断、平衡旋转若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：构造平衡二叉树的方法：

插入、判断、平衡旋转若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：构造平衡二叉树的方法：

插入、判断、平衡旋转ABCABCCABBCAABCBCALL型RR型RL型LR型CBAACB013037024例1：请将下面序列构成一棵平衡二叉排序树：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053

例2:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转426589642895向左旋转一次继续插入关键字9依次插入的关键字为5,4,2,8,6,9

一、哈希表是什么？二、哈希函数的构造方法

三、处理冲突的方法

四、哈希表的查找1.3哈希表一、哈希表是什么？前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记录。哈希表它既是一种查找方法，又是一种存贮方法哈希表：即散列存储结构。

散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！1.哈希表的概念例如：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。（注：H（k）＝k称为散列函数）解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。2.若干术语哈希方法(杂凑法)哈希函数(杂凑函数)哈希表(杂凑表)冲突哈希方法中使用的转换函数称为哈希函数(杂凑函数)按上述思想构造的表称为哈希表(杂凑表)

有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！0123456二、构造哈希函数的方法对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理。1.

直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法哈希函数为关键字的线性函数H(key)=key或者

H(key)=akey+b1.

直接定址法此法仅适合于：地址集合的大小==关键字集合的大小此方法仅适合于：

能预先估计出全体关键字的每一位上各种数字出现的频度。2.

数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法

此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。4.折叠法此方法适合于:

关键字的数字位数特别多。5.除留余数法设定哈希函数为:

H(key)=keyMODp

其中，

p≤m(表长)

并且p应为不大于m的素数或是不含20以下的质因子6.随机数法设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数

通常，此方法用于对长度不等的关键字构造哈希函数。注意：实际造表时总的原则是使产生冲突的可能性降到尽可能地小。三、处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链地址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODmi=1,2,…,s1.开放定址法其中：对增量di

有三种取法1)线性探测再散列

di=ci最简单的情况c=12)二次探测再散列

di=12,-12,22,-22,…,3)随机探测再散列

di

是一组伪随机数列或者

di=i×H2(key)(又称双散列函数探测)例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)19012314556819012314682+4若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突1182365511(0-1)mod118236112136251Flash演示将所有哈希地址相同的记录都链接在同一链表中。

2.链地址法0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的关键字，哈希函数为H(key)=keyMOD7查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为：四、哈希表的查找

对于给定值K，计算哈希地址i=H(K)