计算机考研:数据结构常用算法分析(八)？

搜索分为静态搜索和动态搜索。静态搜索只是找到并返回到搜索位置。另一方面，动态搜索则不同。如果搜索成功，将返回位置；如果搜索不成功，将返回新记录的插入位置。换句话说，静态查找不会改变查找表，而动态查找会有一个插入操作，它会改变查找表。

不同的搜索使用不同的存储结构。静态搜索使用顺序表，而动态搜索由于变化频繁，使用二叉排序树、二叉平衡树、B-和B+

静态搜索包括顺序搜索、半搜索和块搜索(索引顺序搜索)。

顺序搜索是最简单的搜索方法。

算法思维

设定给定值为k，并在表(r1r2...Rn)，从最后一个元素rn开始，查找key = k的记录，如果一条记录Ri(l≤i≤n)的key为k，则查找成功，返回记录序号I；否则，搜索失败并返回0。

算法描述

Intsqsearch (SQLIST R，key type K)//顺序查找表R//的算法

{ int I；

r.data[0]。key = k；//k存放在监控岗//

i = r.len//取表长//

while(r.data[i].钥匙！=k)

I-；//顺序搜索//

返回(一)；

}

算法使用了一点技巧:首先，K存储在岗哨中。如果有r.data[i]。key=k对于一个i(≠0)，搜索成功，返回I；如果我从n减少到1，没有K键的记录，如果我从1减少到0，一定有r.data[0]。key=k，表示搜索失败，返回i=0。

成功搜索的平均长度为ASL=，搜索失败时，搜索次数等于n+L。

半搜索算法及分析

当记录的键按≤或≥关系排序时，无论是递增还是递减，只要按顺序排序存储即可。

算法描述

Int Binsearch (SQLIST R，key type K)//半搜索有序表R的算法//

{ int低，高，中；

低= 1；high = r.len//上下限的初始值//

while(low & lt；=high) //当表空间存在时//

{ mid=(低+高)/2；//查找当前mid//

if (k==r.data[mid])。关键)

返回(mid)；//搜索成功，mid//

如果(k

高=中1；//调整上限，向左看//

其他

低= mid+1；//调整下限，向右看//

}

return(0)；//低& gt高，找不到//

}

决策树:用于描述二分搜索法过程的二叉树。具有n个节点的决策树的深度与具有n个节点的完全二叉树的深度相同。但是决策树不一定是完全的二叉树，其叶节点的层次之差不超过1。因此，当搜索成功时，与给定值相比较的关键字的数量最多为

ASL=

块搜索算法及分析

分块搜索，也叫索引顺序搜索，是顺序搜索方法的一种改进，目的是提高搜索效率。

1.

设记录表的长度为n，将表的n条记录分成b=个块，每个块有s条记录(最后一个块的记录数可以小于s)，即:

并且表是按顺序分块的，即i(1≤i≤b-1)块中所有记录的键都小于i+1块中记录的键，但是块中的记录可以乱序。

建立索引

每个块对应一个索引项:

KeymaxLink

其中Keymax是该块中记录的最大密钥；Link是块的第一条记录的序列号(或指针)。

3.该算法分为两步:

(1)通过索引表确定要查找的记录所在的块；(可以对半搜索，也可以按顺序搜索，因为索引表是按顺序的)

(2)在块中顺序搜索。(只能按顺序搜索，块是无序的。)

如果你对考研有疑问，不知道考研中心的内容怎么总结，不了解考研报名的地方政策，点击最下方咨询官网，免费获取复习资料:/xl/