【数据结构实验】查找(二分查找&顺序查找)

山风不打咩 2022-05-14 14:28:07 阅读数:346

数据结构数据实验结构查找

一、实验目的:

熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。

二、实验要求:

1、掌握查找的基本方法。

2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。

三、实验内容与过程

实验内容:

编程分别对有序顺序表的顺序查找,二分查找算法进行实现。

代码如下:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
const int N = 1000010;
int st[N];
int main()
{
printf("线性表的长度和询问次数");
scanf("%d%d", &n, &m);
printf("输入这个线性表");
for (int i = 0; i < n; i++) scanf("%d", &st[i]);
for (int i = 0; i < m; i++)
{
int l = 0; int r = n - 1;
int x; scanf("%d", &x);
printf("二分查找:");
//起始位置的确定
while (l < r)
{
int mid = l + r >> 1;
if (st[mid] >= x) r = mid;
else l = mid + 1;
}
if (st[l] == x)
{
cout<<"这个元素的起始位置是"<< l+1 << " ";
//最终位置确定
r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (st[mid] <= x)l = mid;
else r = mid - 1;
}
cout <<"这个元素的最终位置在"<< r+1 << endl;
}
else cout << "不存在该元素" << endl;
printf("顺序查找:");
bool flag=true;
for(int j=0;j<n;j++)
{
if(st[j]==x)
{
flag=false;
cout<<"元素在第"<<j+1<<"位 ";
}
}
if(flag) cout<<"此元素不存在!"<<endl;
}
return 0;
}

运行结果:

 

版权声明:本文为[山风不打咩]所创,转载请带上原文链接,感谢。 https://blog.csdn.net/m0_64659074/article/details/124760094