2020-08-28 08:57发布
哨兵模式实现原理?
所谓“哨兵”就是用一个特殊值来作为数组的边界,使用“哨兵”可以少用一条判断语句,所以可以提高程序的效率。
比如从整数数组arr中,查找有没有整数num。
应用:假设一个乱序数组,需要查找一个元素是否在该数组中,这时需要用到顺序查找,也就是遍历数组。
一般情况下我们会写下如下代码:
int Sequential_Search(int *a,int n,int key)
{
//数组从1开始
int i;
for(int i=1;i<=n;i++)
if(a[i]==key)
return i;
}
return 0;//查找失败
有的数据结构书上,会运用哨兵元素,改成这样的代码:
int Sequential_Search2(int *a int n,int key)
int i=0;
a[0]=key;//哨兵
i=n;
while(a[i]!=key)
i--;
return i;//返回0就是查找失败
最多设置5个标签!
所谓“哨兵”就是用一个特殊值来作为数组的边界,使用“哨兵”可以少用一条判断语句,所以可以提高程序的效率。
比如从整数数组arr中,查找有没有整数num。
应用:假设一个乱序数组,需要查找一个元素是否在该数组中,这时需要用到顺序查找,也就是遍历数组。
一般情况下我们会写下如下代码:
int Sequential_Search(int *a,int n,int key)
{
//数组从1开始
int i;
for(int i=1;i<=n;i++)
{
if(a[i]==key)
return i;
}
return 0;//查找失败
}
有的数据结构书上,会运用哨兵元素,改成这样的代码:
int Sequential_Search2(int *a int n,int key)
{
int i=0;
a[0]=key;//哨兵
i=n;
while(a[i]!=key)
{
i--;
}
return i;//返回0就是查找失败
}
一周热门 更多>