数据结构OJ实验12-静态查找
A. DS静态查找之顺序查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用带哨兵的顺序查找算法
输入
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
样例查看模式
正常显示查看格式
输入样例1
8\n
33 66 22 88 11 27 44 55\n
3\n
22\n
11\n
99\n
输出样例1
3\n
5\n
error\n
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>v(n+1);
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
int m;
cin>>m;
while(m--)
{
int x;
cin>>x;
int k=n;
while(k)
{
if(v[k]==x)
{
break;
}
k--;
}
if(k)
{
cout<<k<<endl;
}
else
{
cout<<"error"<<endl;
}
}
return 0;
}B. DS静态查找之折半查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用折半查找算法
输入
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
样例查看模式
正常显示查看格式
输入样例1
8\n
11 22 33 44 55 66 77 88\n
3\n
22\n
88\n
99\n
输出样例1
2\n
8\n
error\n
AC代码
#include<iostream>
using namespace std;
const int N = 1e5;
int a[N];
int n;
bool flag = 0;
void find(int l, int r,int k)
{
if (l > r)return;
int mid = (l + r) / 2;
if (a[mid] == k)
{
flag = 1;
cout << mid << endl;
return;
}
else if (a[mid] < k)
{
find(mid + 1, r, k);
}
else
{
find(l, mid - 1, k);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int k;
cin >> k;
while (k--)
{
flag = 0;
int x;
cin >> x;
find(1,n,x);
if (!flag)cout << "error" << endl;
}
return 0;
}C. DS静态查找之顺序索引查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
输入
第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error
样例查看模式
正常显示查看格式
输入样例1
18\n
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53\n
3\n
22 48 86\n
6\n
13\n
5\n
48\n
40\n
53\n
90\n
输出样例1
3-4\n
error\n
12-8\n
error\n
18-9\n
error\n
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
int k;
cin >> k;
vector<int>index(k);
for (int i = 0; i < k; i++)
{
cin >> index[i];//每一块中的最大值
}
int t;
cin >> t;
while (t--)
{
int x;
cin >> x;
int idx = -1;
int cnt = 0;
for (int i = 0; i < k; i++)
{
cnt++;//查找次数加加
if (x <= index[i])//一定在index[i]这个块里！
{
idx = i;
break;
}
}
if (idx == -1)
{
cout << "error" << endl;
continue;
}
bool ok = 0;
//两块之间的间隔是n/k!!
//范围是一块的头到另一块的头！
for (int i = idx * (n/k); i < (idx+1)*(n/k); i++)
{
cnt++;
if (x == v[i])
{
ok = 1;
cout << i + 1 << "-" << cnt << endl;
break;
}
}
if (!ok)
{
cout << "error" << endl;
}
}
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，以此类推
| X的范围 | X的取值 | x2 | x2-y | |
|---|---|---|---|---|
| 0 | 5 | 2.5 | 6.25 | 1.25 |
| 0 | 2.5 | 1.25 | 1.5625 | -3.4375 |
| 1.25 | 2.5 | 1.875 | 3.515625 | -1.484375 |
| 1.875 | 2.5 | 2.1875 | 4.78515625 | -0.21484375 |
| 2.1875 | 2.5 | 2.34375 | 5.4931640625 | 0.4931640625 |
| 2.1875 | 2.34375 | 2.265625 | 5.133056640625 | 0.133056640625 |
| 2.1875 | 2.265625 | 2.2265625 | … | … |
最后求得5的平方根为2.236
温馨提示： 计算过程中为确保精确性，计算变量的类型都用double
保留小数位数的输出，C语言参考格式printf("%.3lf\n",x) ；C++参考cout<<fixed<<setprecision(3)<<x<<endl;（要包含头文件Iomanip）
程序框架参考平时练习中折半查找的方法
输入
第1行输入一个整数n(<100)，表示有n个数
从第2行起到第n+1行输入n个整数
输出
输出n个数的平方根，精确到小数点后三位。
样例查看模式
正常显示查看格式
输入样例1
2\n
13\n
5\n
输出样例1
3.606\n
2.236
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
double x;
cin>>x;
double l=1,r=x;
bool ok=0;
while(r-l>=0.00000001)
{
double mid=(l+r)/2;
if(abs(mid*mid-x)<=0.0000001)
{
printf("%.3lf\n",mid);
break;
}
else if(mid*mid-x>0.00000001)
{
r=mid;
}
else
{
l=mid;
}
}
}
return 0;
}E. 两个有序序列的中位数
题目描述
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
只需考虑中位数唯一的情况
输入
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出
在一行中输出两个输入序列的并集序列的中位数。
样例查看模式
正常显示查看格式
输入样例1
5\n
1 3 5 7 9\n
2 3 4 5 6
输出样例1
4
AC代码
#include<bits/stdc++.h>
using namespace std;
// 1 3 5 7 9
// 2 3 4 5 6
// 1 2 3 3 4 5 5 6 7 9
int main()
{
int n;
cin>>n;
vector<int>v(2*n);
for(int i=0;i<2*n;i++)
{
cin>>v[i];
}
sort(v.begin(),v.end());
cout<<v[n-1]<<endl;
return 0;
}F. 链表的有序构建和查找
题目描述
单链表结点的存储结构包含两部分：数据、下一结点指针（默认为空）。
单链表包含头结点，存储实际数据的结点位置从1开始。
现输入一批无序的整数队列，编写程序完成以下要求
1）构建单链表并且把数据按递增顺序插入到链表中，并且统计非空指针发生变化的次数。
例如在初始只包含头结点的单链表中，依次插入3和2
当把3插入时，是头结点的next指针发生变化，初始头结点的next指针是空的，现在指向3的结点，所以不计入指针变化次数。
当把2插入时，它是插入到头结点和3结点之间，这时候头结点的next指针从指向3变成指向2，因此这次计入指针变化次数。
总之，如果是把一个空的next指针指向新的结点，则不计入变化次数；如果是把一个非空next指针修改指向新结点则计入变化次数。
2）实现对单链表的元素查找。输入一个链表位置，返回该位置对应的数据。如果位置非法则输出提示信息，看样例。
要求：必须使用单链表结构实现上述要求，并且不能用第三方算法库或容器类对象
输入
第一行：第一个数字n表示样本数目，其后跟n个样本。
第二行：查找测试次数m 后跟m个待查找的位置。
输出
第一行输出构建链表过程中，非空指针变化的总次数，格式看样本
第二行输出单链表创建后，从头到尾依次输出链表中元素数据
第三行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error
样例查看模式
正常显示查看格式
输入样例1
6 1 8 5 2 4 3\n
4 0 2 10 6\n
输出样例1
非空指针变化4次\n
1 2 3 4 5 8\n
error\n
2\n
error\n
8\n
AC代码
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
node()
{
next = NULL;
}
};
class linkk
{
node* head;
int n;
int cnt;
public:
linkk()
{
n = 0;
cnt = 0;
head = new node;
}
void insert(int x)
{
node* temp = new node;
temp->data = x;
temp->next = NULL;
node* s = new node;
s = head;
while (1)
{
if (s->next == NULL)//直接插在后面
{
s->next = temp;
break;
}
if (s->next->data > x)
{
cnt++;//指针变化次数
temp->next = s->next;
s->next = temp;
break;
}
s = s->next;//注意！
}
n++;
}
void display()
{
cout << "非空指针变化" << cnt << "次" << endl;
node* k = new node;
k = head;
for (int i = 0; i < n - 1; i++)
{
k = k->next;
cout << k->data << " ";
}
k = k->next;
cout << k->data << endl;
}
int find(int x)
{
node* s = new node;
s = head;
if (x > n || x <= 0)
{
return -1;
}
for (int i = 0; i < x; i++)
{
s = s->next;
}
return s->data;
}
};
int main()
{
int nn;
cin >> nn;
linkk ll;
for (int i = 0; i < nn; i++)
{
int x;
cin >> x;
ll.insert(x);
}
ll.display();
int m;
cin >> m;
while (m--)
{
int x;
cin >> x;
if (ll.find(x) != -1)
{
cout << ll.find(x) << endl;
}
else
{
cout << "error" << endl;
}
}
return 0;
}