【数据结构】静态查找

Alex_Shen
2020-12-16 / 0 评论 / 0 点赞 / 133 阅读 / 5,337 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: 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 find(int* array, int num, int n) {
	array[0] = num;
	int i;
	for (i = n + 1; array[i] != num; i--);
	if (i == 0)
		cout << "error" << endl;
	else
		cout << i << endl;
}

int main() {
	int n;
	cin >> n;
	int* array = new int[n + 1];
	for (int i = 1; i <= n; i++)
		cin >> array[i];
	int t;
	cin >> t;
	while (t--) {
		int num;
		cin >> num;
		find(array, num, n);
	}
	return 0;
}

问题 B: 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 find(int* array, int num, int n) {
	int low = 1, high = n, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (array[mid] == num) {
			cout << mid << endl;
			return;
		}			
		else if (array[mid] < num)
			low = mid + 1;
		else
			high = mid - 1;
	}
	cout << "error" << endl;
	return;
}

int main() {
	int n;
	cin >> n;
	int* array = new int[n + 1];
	for (int i = 1; i <= n; i++)
		cin >> array[i];
	int t;
	cin >> t;
	while (t--) {
		int num;
		cin >> num;
		find(array, num, n);
	}
	return 0;
}

问题 C: 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;

//顺序索引查找
void find(int* array, int* index, int* indexi, int num, int n1, int n2) {
	int count = 0;
	int starti = 0;
	int i;
	for (i = 1; i <= n2; i++) {
		count++;
		if (num <= index[i] || i == n2) {
			starti = indexi[i];
			break;
		}			
	}
	for (int j = starti; j <= n1; j++) {
		count++;
		if (array[j] == num) {
			cout << j << "-" << count << endl;
			return;
		}
	}
	cout << "error" << endl;
	return;
}

int main() {
	int n1;
	cin >> n1;
	int* array = new int[n1 + 1];
	for (int i = 1; i <= n1; i++)
		cin >> array[i];
	int n2;
	cin >> n2;
	int* index = new int[n2 + 1];
	for (int i = 1; i <= n2; i++)
		cin >> index[i];
	index[0] = 0;
	int* indexi = new int[n2 + 1];
	indexi[1] = 1;
	for (int i = 2; i <= n2; i++)
		indexi[i] = indexi[i - 1] + n1 / n2;
	int t;
	cin >> t;
	while (t--) {
		int num;
		cin >> num;
		find(array, index, indexi, num, n1, n2);
	}
	return 0;
}

问题 D: 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,以此类推
最后求得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 printsqrt(double num) {
	double low = 0, high = num, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (abs(mid * mid - num) < 0.00001) {
			cout << fixed << setprecision(3) << mid << endl;
			return;
		}
		else if (mid * mid < num)
			low = mid;
		else
			high = mid;
	}
	return;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		double num;
		cin >> num;
		printsqrt(num);
	}
	return 0;
}

问题 E: 无线网络 (Ver. I)

题目描述

在东南亚发生了地震。 ACM(Asia Cooperated Medical team)已经用笔记本建立了无线网络,但是由于一次余震,网络中的所有计算机都损坏了。 计算机一个接一个地修复,网络逐渐开始工作。 由于硬件限制,每台计算机只能直接与距离它不远的计算机进行通信。 但是,每台计算机都可以被视为两台计算机之间通信的中介,也就是说,如果计算机A和计算机B可以直接通信,计算机C可以与计算机A进行通信,则计算机C和计算机B可以进行通信。
在修复网络的过程中,工作人员先后进行两种操作,先修复计算机,再测试两台计算机是否可以通信。 你的任务是回答所有的测试操作。

输入

输入数据只有一组
第一行包含两个整数N和d(1 <= N <= 100,0 <= d <= 20000)。 这里N是计算机的数量,编号从1到N,D是两台计算机可以直接通信的最大距离。 在接下来的N行中,每行包含两个整数xi,yi(0 <= xi,yi <= 10000),这是N台计算机的坐标。 从第(N + 1)行到输入结束,有一些操作,这些操作是一个接一个地执行的。 每行包含以下两种格式之一的操作:
1.“O p”(1 <= p <= N),修复计算机p
2.“S p q”(1 <= p,q <= N),测试计算机p和q是否可以通信
其中所有的修复操作都在测试操作之前
输入不会超过3000行

输出

对于每个测试操作,如果两台计算机可以通信则输出“SUCCESS”,否则输出“FAIL”。

样例输入

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 2
S 1 4
S 1 3
S 2 3

样例输出

SUCCESS
FAIL
FAIL
FAIL

题解

#include<iostream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;

struct point{
	int x, y;
	bool able;
	point(int a, int b) {
		x = a;
		y = b;
		able = false;
	}
};

double dis(point x, point y) {
	return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}

bool find(int Matrix[1000][1000], int N, int i1, int i2) {
	int visit[1000];
	queue<int> q;
	for (int i = 0; i <= N; i++)
		visit[i] = 0;

	visit[i1] = 1;
	for (int i = 1; i <= N; i++)
		if (i != i1 && Matrix[i1][i]) {
			q.push(i);
			visit[i] = 1;
		}

	while (!q.empty()) {
		int w = q.front();
		q.pop();
		if (w == i2)
			return true;
		for (int j = 1; j <= N; j++)
			if (j != w && Matrix[w][j] && !visit[j]) {
				q.push(j);
				visit[j] = 1;
			}
	}
	return false;
}

int main() {
	int N, d;
	cin >> N >> d;
	vector<point> p;
	p.push_back(point(-1, -1));
	int Matrix[1000][1000];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
			Matrix[i][j] = 0;
	}
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		p.push_back(point(x, y));
	}
	char opt;
	while (cin >> opt) {
		if (opt == 'O') {
			int num;
			cin >> num;
			p[num].able = true;
			for (int i = 1; i <= N; i++) {
				if (p[i].able && dis(p[i], p[num]) <= d) {
					Matrix[num][i] = 1;
					Matrix[i][num] = 1;
				}
			}
		}
		else if (opt == 'S') {
			int i1, i2;
			cin >> i1 >> i2;
			if (find(Matrix, N, i1, i2)) {
				cout << "SUCCESS" << endl;
			}
			else {
				cout << "FAIL" << endl;
			}
		}
	}
	return 0;
}

0

评论区