顺序查找的算法:查找前对结点之间并没有排序 要求.用C+语言描述的顺序查找算法如下 int seqserch(recordfile r, int k, int n) /k为给定值,m为表长; /返回0表明查找不成功否则返回关键字等于k的 记录在表r中的序号 i int i=n; r[O key=k; while(ri. keyl=k return
int seqserch(recordfile r,int k,int n) //k为给定值,n为表长; //返回0表明查找不成功,否则返回关键字等于k的 记录在表r中的序号. { int i=n; r[0].key=k; while(r[i].key!=k) i--; return i;} 顺序查找的算法:查找前对结点之间并没有排序 要求.用C++语言描述的顺序查找算法如下：
在此算法中,查找之前,先对r[0]的关键字赋值 为k,目的在于免去查找过程中每一步都要检测 整个表是否查找完毕。在此r[0]起了监视哨的作 用 这种改进能使顺序查找在n≥1000时进行一次查 找所需要的平均时间几乎减少一半,从而提高查 找效率。 顺序查找方法的ASL: 有n个记录的表,查找成功时的平均查找长度为 ASL=∑PC
在此算法中，查找之前，先对r[0]的关键字赋值 为k，目的在于免去查找过程中每一步都要检测 整个表是否查找完毕。在此r[0]起了监视哨的作 用 这种改进能使顺序查找在n≥1000时进行一次查 找所需要的平均时间几乎减少一半，从而提高查 找效率。 •顺序查找方法的ASL： ••有n个记录的表，查找成功时的平均查找长度为
在顺序查找时,c取决于所查记录在表中的位 置。如查找记录r[n时,仅需比较一次,而查 找记录r[订]时,则需比较n次。一般地,ci=n i+1。故顺序查找的平均查找长度为 ASL=np/ +(n-Dp2+.+2pn-/+pn 假设每个记录的平均查找概率相等即:P;=1m。 ASL3=∑Pc=∑m-+1)=2
••假设每个记录的平均查找概率相等即：Pi = 1/n 。 。 在顺序查找时，ci取决于所查记录在表中的位 置。如查找记录r[n]时，仅需比较一次，而查 找记录r[1]时，则需比较n次。一般地，ci=ni+1。故顺序查找的平均查找长度为： ASL = np1 +(n-1)p2 + … + 2pn-1 + pn
算法的评价 顺序查找法和后面将要讨论的其它查找法相比, 其缺点是平均查找长度较大,特别是当n很大时, 查找效率低。然而,它有很大的优点:算法简单 且适用面广。它对表的结构无任何要求,无论记 录是否按关键字有序均可应用,而且上述所有讨 论对线性链表也同样适用
顺序查找法和后面将要讨论的其它查找法相比， 其缺点是平均查找长度较大，特别是当 n 很大时， 查找效率低。然而，它有很大的优点：算法简单 且适用面广。它对表的结构无任何要求，无论记 录是否按关键字有序均可应用，而且上述所有讨 论对线性链表也同样适用。 算法的评价
922二分法查找 查找过程:每次将待查记录所在区间缩小一半, 适用条件:采用顺序存储结构的有序表 算法实现: 设表长为n,Jow、high和mid分别指向待查元素所在区间的上 界、下界和中点,k为给定值 初始时,令lw=1,up=n,md(ow+up)2」 让k与md指向的记录比较 若k=r| mid key,查找成功 若k<r| mid]. key,则up=mid-1 若k>r| mid key,则low=mid+1 重复上述操作,直至ow>up时,查找失败
9.2.2二分法查找 查找过程：每次将待查记录所在区间缩小一半， 适用条件：采用顺序存储结构的有序表 •算法实现: 设表长为n，low、high和mid分别指向待查元素所在区间的上 界、下界和中点,k为给定值 初始时，令low=1,up=n,mid=(low+up)/2 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若k<r[mid].key，则up=mid-1 若k>r[mid].key，则low=mid+1 重复上述操作，直至low>up时，查找失败