C++ 实现带监视哨的顺序查找算法

监视哨往往是程序里面的一个变量，如果是对数字排序的话，那么该变量一般是数值型变量。变量的赋值就相当于哨兵，当排序数列中出现与哨兵相等的值或有某种既定关系出现时，就做一种操作，比如说停止排序，或进行下一趟排序。

举例：

顺序检索的算法描述如下

int Search_Sequen(SSTable ST,KeyType key){
//在线性表ST中顺序检索其关键字等于Key的数据元素，
//若找到，函数值为该元素在表中的位置，否则为-1.
ST.element[ST.length].key=key; //设置监视哨
i=0;
while(ST.element[i].key!=key) i++;
if(i<ST.length)
return i;
else
return -1;
}

正文

之前在牛客网上做习题发现的这个独特的顺序查询，第一次听到“监视哨”这个说法，就查了一下

具体实现就是将数组的第0位置空，在查找时将要查找的key插入作为监视哨

这样的好处是不用每次循环都检查查找是否结束，减少了元素比较次数，

最后的返回值要么是元素下标要么是数组第0位(这种情况就是到了监视哨)

以下是我的代码

#include <iostream>
using namespace std;

template<class T>
int linear_search(T& arr,int key)
{
 int length = sizeof(arr) / sizeof(arr[0]);
 int i = length;
 arr[0] = key;
 while (arr[i] != key)
 {
 i--;
 }
 return i;
}

int main()
{
 int array[] = { 0, 7,9,10,11,15 };
 int len = sizeof(array) / sizeof(array[0]);
 cout << linear_search(array, 10);
 return 0;
}

这里顺带提一下，vs2019会出现一个

error C2760: 语法错误: 意外的令牌“标识符”，预期的令牌为“;”

的错误，具体原理我不是很懂，单给出一个解决办法：

项目->属性->C/C++->语言->符合模式->否

最后给自己提一下醒，数组作为函数参数是传入数组首位的指针，指针是不带有数组其他属性的，

所以要在函数内获得数组的长度，只能用引用和模板的形式传入数组本身，这样就能用sizeof()获取数组长度了

总结

到此这篇关于C++ 实现带监视哨的顺序查找的文章就介绍到这了,更多相关c++ 监视哨顺序查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • c++ vector(向量)使用方法详解(顺序访问vector的多种方式）

    vector 是向量类型,它可以容纳许多类型的数据,如若干个整数,所以称其为容器.vector 是C++ STL的一个重要成员,使用它时需要包含头文件: 复制代码 代码如下: #include<vector>; 一.vector 的初始化:可以有五种方式,举例说明如下: (1) vector<int> a(10); //定义了10个整型元素的向量(尖括号中为元素类型名,它可以是任何合法的数据类型),但没有给出初值,其值是不确定的.(2)vector<int> a(10,

  • C++程序的执行顺序结构以及关系和逻辑运算符讲解

    C++程序的执行顺序结构以及关系和逻辑运算符讲解

    C++顺序结构程序 [例]求一元二次方程式ax2+bx+c=0的根.a,b,c的值在运行时由键盘输入,它们的值满足b2-4ac≥0.根据求x1,x2的算法.它可以编写出以下C++程序: #include <iostream> #include <cmath> //由于程序要用到数学函数sqrt,故应包含头文件cmath using namespace std; int main( ) { float a,b,c,x1,x2; cin>>a>>b>>

  • 如何在C++中建立一个顺序表

    如何在C++中建立一个顺序表

    准备数据 复制代码 代码如下: #define MAXLEN 100 //定义顺序表的最大长度struct DATA{ char key[10]; //结点的关键字  char name[20]; int age;};struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen;   //顺序表已存结点的数量 }; 定义了顺序表的最大长度MAXLEN.顺序表数据元素的类型DATA以及顺序表的数据结构SLTyp

  • C++实现翻转单词顺序

    题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变.句子中单词以空格符隔开.为简单起见,标点符号和普通字母一样处理.例如输入"I am a student.",则输出"student. a am I". 思路:首先将整个句子按字符翻转,然后再将其中每个单词的字符旋转. #include <string> #include "stdafx.h" void Reverse(char *pBegin, char *pEnd

  • C++实现顺序表的常用操作(插入删出查找输出)

    C++实现顺序表的常用操作(插入删出查找输出)

    实现顺序表的插入,删除,查找,输出操作在C语言中经常用到.下面小编给大家整理实现代码,一起看下吧 代码如下所示: #include<iostream> using namespace std; #define MAXSIZE 15 typedef int DataType; typedef struct { DataType data[MAXSIZE]; //通常用一位数组来描述顺序表的数据存储 int SeqLength; /*线性表长度*/ } SeqList; SeqList *Init

  • C++构造函数初始化顺序详解

    1.构造函数.析构函数与拷贝构造函数介绍 构造函数 1.构造函数不能有返回值 2.缺省构造函数时,系统将自动调用该缺省构造函数初始化对象,缺省构造函数会将所有数据成员都初始化为零或空 3.创建一个对象时,系统自动调用构造函数 析构函数 1.析构函数没有参数,也没有返回值.不能重载,也就是说,一个类中只可能定义一个析构函数 2.如果一个类中没有定义析构函数,系统也会自动生成一个默认的析构函数,为空函数,什么都不做 3.调用条件:1.在函数体内定义的对象,当函数执行结束时,该对象所在类的析构函数会被

  • C++ 实现带监视哨的顺序查找算法

    监视哨往往是程序里面的一个变量,如果是对数字排序的话,那么该变量一般是数值型变量.变量的赋值就相当于哨兵,当排序数列中出现与哨兵相等的值或有某种既定关系出现时,就做一种操作,比如说停止排序,或进行下一趟排序. 举例: 顺序检索的算法描述如下 int Search_Sequen(SSTable ST,KeyType key){ //在线性表ST中顺序检索其关键字等于Key的数据元素, //若找到,函数值为该元素在表中的位置,否则为-1. ST.element[ST.length].key=key;

  • 基于JavaScript实现的顺序查找算法示例

    基于JavaScript实现的顺序查找算法示例

    本文实例讲述了基于JavaScript实现的顺序查找算法.分享给大家供大家参考,具体如下: 对于查找数据来说,最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断,直到找到了想要的结果.这个方法叫做顺序查找,有时候也被叫做线性查找.它属于暴力查找技巧的一种. 顺序查找实现起来非常简单,代码如下: function generalSearch(arr,data){//普通的顺序查找,就是遍历一遍看是否找到 for(var i=0;i<arr.length;i++){ if(arr[i]==

  • Java顺序查找算法详解

    Java顺序查找算法详解

    目录 一.查找的基本概念 1.查找表 2.关键字 3.查找 4.动态查找表与静态查找表 5.平均查找长度 二.顺序查找法 1.概念 2.实践 一.查找的基本概念 在讲顺序查找法之前先来认识一些关于查找的基本概念. 1.查找表 由同一类型的数据元素(或记录)所构成的集合 数据元素之间存在完全松散的关系 非常灵活的数据结构 2.关键字 关键字是数据元素(或记录)中某个数据项的值,可以用它标识一个数据元素(或记录) 若关键字可以唯一地标识一个记录,则称之为主关键字 反之,若用以识别若干记录的关键字称之

  • C语言顺序查找算法介绍及示例

    C语言顺序查找算法介绍及示例

    目录 1. 顺序查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 顺序查找介绍 1.1 定义 查找是指在指定数据组合中找出满足条件的元素个体.顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法. 顺序查找是最基础也是最简单的查找算法,在需要进行查找时,这是我们的首选方法,只有数据较多,结构复杂,耗时较多需要优化时,我们才会考虑使用其他查找方法. 1.2 基本原理 对于任意一个序列以及一个

  • c++和python实现顺序查找实例

    c++和python实现顺序查找实例

    目录 (1)python实现顺序查找 (2)C++实现顺序查找 如何在一堆数据中找到某个数值的位置? 数值型数据作为信息的基本载体,广泛用于各种信息的记录,这些数据不仅需要被存储,更需要被使用.因此,从数据库中正确的找到目标数据,是至关重要的操作. 我们先不考虑计算机是如何完成数值查找的,你会如何从下面这张表(黑色是数值,蓝色是位置索引)中找到724这个数值? 显然,上面有序表所有的数值都按照次序进行排列,人眼可以根据数值大小关系确定区间从而很快的找到724在133位置上.但是,当我们面临的是几

  • Python实现七大查找算法的示例代码

    Python实现七大查找算法的示例代码

    查找算法 -- 简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素.     查找表(Search Table):由同一类型的数据元素构成的集合     关键字(Key):数据元素中某个数据项的值,又称为键值     主键(Primary Key):可唯一的标识某个数据元素或记录的关键字 查找表按照操作方式可分为:         1.静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是:         ①

  • Python查找算法之分块查找算法的实现

    Python查找算法之分块查找算法的实现

    一.分块查找算法 分块查找是二分法查找和顺序查找的改进方法,分块查找要求索引表是有序的,对块内结点没有排序要求,块内结点可以是有序的也可以是无序的. 分块查找就是把一个大的线性表分解成若干块,每块中的节点可以任意存放,但块与块之间必须排序.与此同时,还要建立一个索引表,把每块中的最大值作为索引表的索引值,此索引表需要按块的顺序存放到一个辅助数组中.查找时,首先在索引表中进行查找,确定要找的结点所在的块.由于索引表是排序的,因此,对索引表的查找可以采用顺序查找或二分查找:然后,在相应的块中采用顺序

  • Python 语言实现六大查找算法

    Python 语言实现六大查找算法

    目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

    数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return false;for($i=0; $i<$count; $i++){for($j=$count-1; $j>$i; $j–){if ($array[$j] < $array[$j-1]){$tmp =

随机推荐