数据结构第四次实验（排序）

· 2022-02-28 · # 数据结构上机

第四次上机主要考察算法。

折半查找的次数

题目描述

给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。

输入

第一行是N，表示序列中数的个数，序列最长1000，第二行是一个有序序列，第三行是要找的数x。

输出

如果找到x，输出折半比较的次数，否则输出NO。

样例输入 [Copy](javascript:CopyToClipboard($('#sampleinput').text()))

11
5 13 19 21 37 56 64 75 80 88 92
19

样例输出 [Copy](javascript:CopyToClipboard($('#sampleoutput').text()))

# include <iostream>
using namespace std;
int a[1005];
int search(int a[],int x,int n)
{
	int l=0,r=n-1;
	int ans=0;
	while(l<r)
	{
		int m=(l+r)/2;
		if(a[m]==x)
		{
			ans++;
			r=m;
			break;
		}
		else if(a[m]>x)
		{
			r=m-1;
			ans++;
		}
		else
		{
			l=m+1;
			ans++;
		}
	}
	if(a[r]==x) cout<<ans<<endl;
	else cout<<"NO"<<endl;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int x;
	cin>>x;
	search(a,x,n);
}

二叉搜索树的查找

题目描述

给你一个数据序列，请构造一个二叉搜索树，然后计算出找到给定数据需比较的次数。

输入

第一行是N，表示序列中数的个数，序列最长1000，第二行是一个数据序列，第三行是要找的数x。

输出

如果找到x，输出比较的次数，没找到则输出NO。

样例输入 [Copy](javascript:CopyToClipboard($('#sampleinput').text()))

5
1 2 3 5 4
5

样例输出 [Copy](javascript:CopyToClipboard($('#sampleoutput').text()))

# include <bits/stdc++.h>
using namespace std;
int ans=0,flag=0;
struct node{
    int val;
    node* l;
    node* r;
};
void insert(node* &T,int x)
{
    if(T==NULL)
    {
        T=new node;
        T->l=NULL;
        T->r=NULL;
        T->val=x;
    }
    else if(x<T->val)
        insert(T->l,x);
    else
        insert(T->r,x);
}
void search(node* T ,int x)
{
    if(T)
    {
        ans++;
        if(x==T->val)
        {
            flag=1;
            cout<<ans;
        }
        else if(x<T->val)
            search(T->l,x);
        else
            search(T->r,x);
    }
}
int main()
{
    int n;
    cin>>n;
    node *T=NULL;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        insert(T,x);
    }
    int m;
    cin>>m;
    search(T,m);
    if(flag==0)
        cout<<"NO";
}

5个数从大到小排序

题目描述

数学课上，老师公布了一个小组的5名同学的成绩，你能编程把成绩从大到小排序吗，以便老师知道考试名次？

输入

5个整数，用空格间隔开。

输出

从大到小的5个数，中间用空格间隔。

样例输入 [Copy](javascript:CopyToClipboard($('#sampleinput').text()))

86 78 99 100 66

样例输出 [Copy](javascript:CopyToClipboard($('#sampleoutput').text()))

100 99 86 78 66

# include <bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> nums(5,0);
	for(int i=0;i<5;i++)
	{
		cin>>nums[i];
	}
	sort(nums.begin(),nums.end());
	for(int i=4;i>=0;i--)
		cout<<nums[i]<<" ";
}

病人排队

题目描述

**病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：

**1.老年人（年龄 >= 60岁）比非老年人优先看病。

**2.老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。

**3.非老年人按登记的先后顺序看病。

输入

第1行，输入一个小于100的正整数，表示病人的个数；

后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于10的字符串表示病人的ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。

输出

按排好的看病顺序输出病人的ID，每行一个。

样例输入 [Copy](javascript:CopyToClipboard($('#sampleinput').text()))

样例输出 [Copy](javascript:CopyToClipboard($('#sampleoutput').text()))

# include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	string id[100];
	int age[100];
	for(int i=0;i<n;i++)
	{
		cin>>id[i];
		cin>>age[i];
	}//输入完毕
	int sx[100];
	int p=0;
	for(int i=0;i<n;i++)
	{
		if(age[i]>=60)
		{
			sx[p]=i;
			p++;	
		}	
	} 
	for(int i=0;i<p;i++)
	{
		for(int j=0;j<p-i-1;j++)
		{
			if(age[sx[j]]<age[sx[j+1]])
			{
				int temp;
				temp=sx[j];
				sx[j]=sx[j+1];
				sx[j+1]=temp;
			}
		}
	}
	for (int i = 0; i < p; i++)
	{
		cout << id[sx[i]] << endl;
	}
	for (int i = 0; i < n; i++)
	{
		if (age[i] < 60)
		{
			cout << id[i] << endl;
		}
	}
}