数据结构 静态查找

简介: 数据结构 静态查找

1. DS静态查找之顺序查找


题目描述


给出一个队列和要查找的数值,找出数值在队列中的位置,队列位置从1开始


要求使用带哨兵的顺序查找算法


输入


第一行输入n,表示队列有n个数据

第二行输入n个数据,都是正整数,用空格隔开

第三行输入t,表示有t个要查找的数值

第四行起,输入t个数值,输入t行


输出


每行输出一个要查找的数值在队列的位置,如果查找不成功,输出字符串error


输入样例


8

33 66 22 88 11 27 44 55

3

22

11

99


输出样例


3

5

error


参考代码

#include<iostream>
using namespace std;
void search(int e, int array[], int t)
{
  for (int i = t - 1;i >= 0;i--)
  {
    if (array[i] == e)
    {
      if (i == 0)cout << "error\n";
      else
      {
        cout << i << endl;
        break;
      }
    }
  }
}
int main()
{
  int* array;
  int t, n;
  cin >> t;
  array = new int[t+1];
  for (int i = 1;i <= t;i++)
    cin >> array[i];
  cin >> n;
  int e;
  while (n--)
  {
    cin >> e;
    array[0] = e;
    search(e, array,t);
  }
  return 0;
}


2. DS静态查找之折半查找


题目描述


给出一个队列和要查找的数值,找出数值在队列中的位置,队列位置从1开始


要求使用折半查找算法


输入


第一行输入n,表示队列有n个数据

第二行输入n个数据,都是正整数,用空格隔开

第三行输入t,表示有t个要查找的数值

第四行起,输入t个数值,输入t行


输出


每行输出一个要查找的数值在队列的位置,如果查找不成功,输出字符串error


输入样例


8

11 22 33 44 55 66 77 88

3

22

88

99


输出样例


2

8

error


参考代码

#include<iostream>
using namespace std;
void search(int e, int array[], int t)
{
  int low = 1, height = t;
  int mid;
  mid = (low + height) / 2;
  for (;low <= height;)
  {
    if (array[mid] == e)
    {
      cout << mid << endl;
      break;
    }
    else if (e > array[mid]) { low = mid + 1;mid = (low + height) / 2; }
    else if (e < array[mid]) { height = mid - 1;mid = (low + height) / 2; }
  }
  if (low > height)cout << "error\n";
}
int main()
{
  int t, n;
  int* array;
  cin >> t;
  array = new int[t+1];
  for (int i = 1;i <= t;i++)
    cin >> array[i];
  cin >> n;
  int e;
  while (n--)
  {
    cin >> e;
    search(e, array, t);
  }
  return 0;
}


3. DS静态查找之顺序索引查找


题目描述


给出一个队列和要查找的数值,找出数值在队列中的位置,队列位置从1开始


要求使用顺序索引查找算法,其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。


输入


第一行输入n,表示主表有n个数据

第二行输入n个数据,都是正整数,用空格隔开

第三行输入k,表示主表划分为k个块,k也是索引表的长度

第四行输入k个数据,表示索引表中每个块的最大值

第五行输入t,表示有t个要查找的数值

第六行起,输入t个数值,输入t行


输出


每行输出一个要查找的数值在队列的位置和查找次数,数据之间用短划线隔开,如果查找不成功,输出字符串error


输入样例


18

22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53

3

22 48 86

6

13

5

48

40

53

90


输出样例


3-4

error

12-8

error

18-9

error


参考代码

#include<iostream>
using namespace std;
int main()
{
  int t;
  int* array;
  cin >> t;
  array = new int[t + 1];
  for (int i = 1;i <= t;i++)
    cin >> array[i];
  int k;
  cin >> k;
  int* maxnum = new int[k];
  for (int i = 0;i < k;i++)
    cin >> maxnum[i];
  int *index=new int[k - 1];
  index[0] = 1;
  for (int i = 1, j = 0;i <= t;i++)
  {
    if (array[i] > maxnum[j])
    {
      index[j+1] = i;
      j++;
    }
  }
  int n,e;
  cin >> n;
  int count;
  while (n--)
  {
    count = 0;
    cin >> e;
    if (e <= maxnum[k - 1])
    {
      int i, j;
      for (j = 0;j < k;j++)
      {
        count++;
        if (e <= maxnum[j])
        {
          i = index[j];
          break;
        }
      }
      int temp;
      if (j == k - 1)temp = t;
      else temp = index[j + 1];
      for (;i <= temp;i++)
      {
        count++;
        if (e == array[i])
        {
          cout << i << "-" << count << endl;
          break;
        }
      }
      if (i > temp)cout << "error\n";
    }
    else cout << "error\n";
  }
  return 0;
}


4. DS查找——折半查找求平方根


题目描述


假定输入y是整数,我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根,如果我们查找的数x比y的平方根小,则x2<y,如果我们查找的数x比y的平方根大,则x2>y,我们可以据此缩小查找范围,当我们查找的数足够准确时(比如满足|x2-y|<0.00001),就可以认为找到了y的平方根。


比如求5的平方根x,则x一定满足0<=x<=5,取x为(5+0)/2=2.5,因为2.5的平方为6.25>5,所以x一定小于2.5,也即x满足0<=x<=2.5,取x为1.25,以此类推


image.png


最后求得5的平方根为2.236


温馨提示: 计算过程中为确保精确性,计算变量的类型都用double


保留小数位数请采用printf("%.3lf\n",x) 的格式输出


程序框架参考平时练习中折半查找的方法


输入


第1行输入一个整数n(<100),表示有n个数


从第2行起到第n+1行输入n个整数


输出


输出n个数的平方根,精确到小数点后三位。


输入样例


2

13

5


输出样例


3.606

2.236


参考代码

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
void getsqrt(double number)
{
  double n2=number;
  double n1 = 0;
  double n;
  while (1)
  {
    n = (n1 + n2) / 2;
    if (abs(n * n - number) < 0.00001)
    {
      cout << fixed << setprecision(3) << n << endl;
      break;
    }
    if (n * n > number)n2 = n;
    else n1 = n;
  }
}
int main()
{
  int n;
  cin >> n;
  double number;
  while (n--)
  {
    cin >> number;
    getsqrt(number);
  }
  return 0;
}


相关文章
|
6月前
|
物联网 虚拟化 Windows
Windows 10 version 22H2 中文版、英文版下载 (2025 年 3 月更新)
Windows 10 version 22H2 中文版、英文版下载 (2025 年 3 月更新)
311 4
|
8月前
|
传感器 监控 物联网
智慧家居环境监测与控制系统研发与应用的目标分析
- **背景**:随着物联网技术的发展和智能家居市场的快速增长,人们对居住环境的舒适性、安全性及能源使用效率的要求日益提高。 - **目的**:通过研发和应用智慧家居环境监测与控制系统,实现住宅环境中温度、湿度、空气质量等关键参数的有效管理和自动化调节。
491 21
|
10月前
|
监控 自动驾驶 机器人
5G技术在智能制造中的融合应用
5G技术在智能制造中的融合应用
268 0
|
存储 SQL 多模数据库
多模数据库Lindorm再升级:对接Dataphin,打通数据治理“最后一公里”
Lindorm通过与Dataphin的深度整合,进一步解决了数据集成和数据治理的问题,为企业提供更加高效和更具性价比的方案。
多模数据库Lindorm再升级:对接Dataphin,打通数据治理“最后一公里”
|
机器学习/深度学习 人工智能 自然语言处理
新一代AI搜索引擎神器推荐及效果测试:秘塔AI、天工AI、Perplexity等
新一代AI搜索引擎神器推荐及效果测试:秘塔AI、天工AI、Perplexity等
新一代AI搜索引擎神器推荐及效果测试:秘塔AI、天工AI、Perplexity等
二叉树的中后序遍历构建及求叶子
二叉树的中后序遍历构建及求叶子
236 0
银行排队问题之单队列多窗口服务
银行排队问题之单队列多窗口服务
455 0
银行排队问题之单队列多窗口服务
|
安全 Python
一文彻底搞懂Python异常处理:try-except-else-finally
一文彻底搞懂Python异常处理:try-except-else-finally
|
JSON 前端开发 Java
如何在线生成二维码?
说到二维码,我相信大家每天都会用到,尤其是在手机支付的场景,使用频率极广。 实际上二维码在1994年的时候就已经诞生了,由 Denso 公司研制而成,只是那个时候使用范围还不是很大。 早期的二维码由于很容易通过技术方式进行伪造,因此很少有企业愿意去使用他,随着技术的不断迭代和更新,二维码的安全性更进一步得到了提升,从而使得更多的企业愿意使用这项新技术,例如当下的移动支付,还有微信互推,扫码出行等等,极大的方便了网民们的购物、社交和出行! 在实际的业务开发过程中,二维码的使用场景开发也会经常出现在我们开发人员的面前,我们应该如何去处理呢,今天小编就带着大家一起深入的了解一下它的技术实现过程
如何在线生成二维码?
|
机器学习/深度学习 存储 负载均衡
阿里云技术认证ACP是什么?阿里云ACP认证需要具备哪些知识?
相信很多人都不清楚阿里云技术认证ACP是什么,它其实是阿里云公司推出的针对专业工程师的技术认证,具有很高的含金量。那么,阿里云技术认证ACP到底是什么?获得阿里云ACP认证需要具备哪些知识?
1001 0
阿里云技术认证ACP是什么?阿里云ACP认证需要具备哪些知识?