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++ 监视哨顺序查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2020-03-25

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++ vector(向量)使用方法详解(顺序访问vector的多种方式)

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

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

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

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

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

C++实现翻转单词顺序

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

如何在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

如何在 Java 中实现一个 redis 缓存服务

缓存服务的意义 为什么要使用缓存?说到底是为了提高系统的运行速度.将用户频繁访问的内容存放在离用户最近,访问速度最快的地方,提高用户的响应速度.一个 web 应用的简单结构如下图. web 应用典型架构 在这个结构中,用户的请求通过用户层来到业务层,业务层在从数据层获取数据,返回给用户层.在用户量小,数据量不太大的情况下,这个系统运行得很顺畅.但是随着用户量越来越大,数据库中的数据越来越多,系统的用户响应速度就越来越慢.系统的瓶颈一般都在数据库访问上.这个时候可能会将上面的架构改成下面的来缓解数

如何在 Linux 中查找一个命令或进程的执行时间

在类 Unix 系统中,你可能知道一个命令或进程开始执行的时间,以及一个进程运行了多久. 但是,你如何知道这个命令或进程何时结束或者它完成运行所花费的总时长呢? 在类 Unix 系统中,这是非常容易的! 有一个专门为此设计的程序名叫 GNU time. 使用 time 程序,我们可以轻松地测量 Linux 操作系统中命令或程序的总执行时间. time 命令在大多数 Linux 发行版中都有预装,所以你不必去安装它. 在 Linux 中查找一个命令或进程的执行时间 要测量一个命令或程序的执行时间,

如何在Android中实现一个简易的Http服务器

最近遇到一个需求需要在App中创建一个Http服务器供供浏览器调用,用了下开源的微型Htpp服务器框架:NanoHttpd,项目地址:https://github.com/NanoHttpd/nanohttpd 直接上代码 public class HttpServer extends NanoHTTPD { public HttpServer(int port) { super(port); } @Override public Response serve(IHTTPSession sess

用json方式实现在 js 中建立一个map

建立map的方式(其实用的是json实现方式) 复制代码 代码如下: var a = {}; a["key1"] = "value1"; a["key2"] = "value2"; 既然是个map就有检索某个键是否存在的方法,这样写 复制代码 代码如下: if ("key1" in a) { // something } else { // something else } 简单的一句话声明map里面的ke

Vue中建立全局引用或者全局命令的方法

如何在Vue中建立全局引用或者全局命令,具体内容如下 1 一般在vue中,有很多vue组件,这些组件每个都是一个文件.都可能需要引用到相同模块(或者插件).我们不想每个文件都import 一次模块. 如果是基于vue.js编写的插件我们可以用 Vue.use(...) main.js 2 但是如果想添加一个全局命令,同时又让每个vue的文件都能用到怎么办? 第一步:最好建立一个全局的命令文件例如:directive/directive.js 第二步:利用Vue.directive()建立一个全局

Django中实现一个高性能计数器(Counter)实例

计数器(Counter)是一个非常常用的功能组件,这篇blog以未读消息数为例,介绍了在 Django中实现一个高性能计数器的基本要点. 故事的开始:.count() 假设你有一个Notification Model类,保存的主要是所有的站内通知: 复制代码 代码如下: class Notification(models.Model):     """一个简化过的Notification类,拥有三个字段: - `user_id`: 消息所有人的用户ID     - `has_

C语言实现静态顺序表的实例详解

C语言实现静态顺序表的实例详解 线性表 定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识.只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作. 接下来看看静态的顺序表,直接上代码: SeqList.h #define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h&g

如何在AngularJs中调用第三方插件库

在AngularJs中我们会不可避免的使用第三方库,例如jquery插件库.我们不能散乱的在AngularJS中引入这些库,例如在controller中.那么应该怎么在Angular中使用第三方库呢? 如何使用? 很简单,给插件写一个directive. 在这里,我会使用一个简单的jquery插件Toolbar.js 的DEMO. 这是我们如何在jquery中创建一个tooltip的: <!-- Click this to see a toolbar --> <div id="

我想建立一个ftp用户,直接指向整个freehost目录

?怎么做 1.在计算机管理中,建立一个用户,在IIS的FTP中建立一个虚拟目录,目录名与用户名一样. 2.这个用户必须是超级管理员组才有权限.