数据结构OJ实验12-静态查找

2024-01-02 05:55:29

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的取值x2x2-y
052.56.251.25
02.51.251.5625-3.4375
1.252.51.8753.515625-1.484375
1.8752.52.18754.78515625-0.21484375
2.18752.52.343755.49316406250.4931640625
2.18752.343752.2656255.1330566406250.133056640625
2.18752.2656252.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并集的中位数。有序序列A?0??,A?1??,?,A?N?1??的中位数指A?(N?1)/2??的值,即第?(N+1)/2?个数（A?0??为第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;
}

文章来源:https://blog.csdn.net/gyeolhada/article/details/135328641
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。