面试数据结构查找.pdfVIP

1．查找：也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数

据元素。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则，查找失败，

返回失败信息。

2．关键字：是数据元素中某个数据项的值，它可以标识一个数据元素。

3．动态查找表：若在查找的同时对表做修改操作（如和删除）则称该表为动态查找表。

4．静态查找表：在查找的过程中不对表做修改操作，则称该表为静态查找表。

平均查找长度ASL(AverageSearchLength)：由于查找运算的主要操作是特定值与关键

字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次数，作为衡量一个查找

算法效率优劣的标准，也称其为平均查找长度。计算为：

n

对含有n个记录的表，ASLpc=ii

i=1

n

其中：p为查找表中第i个元素的概率，ipi=1

i=1

c为找到表中第i个元素所需比较次数

i

一、顺序查找的基本思想：

从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并

给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失

败，给出失败信息。

说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺

点就是查找效率低。

【适用性】：适用于线性表的顺序结构和链式结构。

平均查找长度=（n+1）/2.

【顺序查找优缺点】：

缺点:是当n很大时，平均查找长度较大，效率低；

优点:是对表中数据元素的没有要求。另外，对于线性链表，只能进行顺序查找。

intQsearch(intA[],intn,intk)//顺序查找

{

intt=0;

while(A[t]!=ktn)

t++;

if(t=n)

t=-1;

return(t);

}

二、有序表的折半查找基本思想：

在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成

功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中

间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成

功，或所查找的区域无数据元素，查找失败。

【步骤】

算法实现

设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定

值

初始时，令low=1,high=n,mid(low+high)/2

让k与mid指向的记录比较

若kr[mid].key，查找成功

若kr[mid].key，则high=mid-1

若kr[mid].key，则low=mid+1

重复上述操作，直至lowhigh时，查找失败

有序表按关键码排列如下：

7，14，18，21，23，29，31，35，38，42，46，49，52

在表中查找关键码为14的数据元素:

•intBinary_Search(ElemTypea[],ElemTypekx,intlength)

•{

•intmid,low,high,flag=0;

•low=0;high=length;/*①设置初始区间*/

•while(low=high)/*②表空测试*/

•{/*