矿大数据结构作业三

DFS,二分

你携秋水揽星河ᅟᅠ ‌

665人浏览 · 2024-06-24 09:56:41

你携秋水揽星河ᅟᅠ ‌ · 2024-06-24 09:56:41 发布

A.无向图的深度优先搜索

板子题，写一个dfs即可。存储时别忘了是无向图，两边都要存储

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool a [110][110];
bool is[110];
void dfs(int now){	
	cout<<now<<' ';
	is[now]=1;	
	for(int i=1;i<=m;i++){
		if(a[now][i]==1&&is[i]==0){
			dfs(i);
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y;cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
	}
	dfs(0);
}

B.最小堆的形成

#include <bits/stdc++.h>
using namespace std;
 
// 调整节点使其满足最小堆性质
void minHeapify(vector<int>& arr, int n, int i) {
    int smallest = i;  // 初始化最小值为当前节点
    int left = 2 * i + 1;  // 左子节点的索引
    int right = 2 * i + 2;  // 右子节点的索引
 
    // 如果左子节点小于根节点，则更新最小值
    if (left < n && arr[left] < arr[smallest])
        smallest = left;
 
    // 如果右子节点小于最小值，则更新最小值
    if (right < n && arr[right] < arr[smallest])
        smallest = right;
 
    // 如果最小值不等于当前节点，则交换节点位置，并继续向下调整
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        minHeapify(arr, n, smallest);
    }
}
 
// 将数组调整为最小堆
void buildMinHeap(vector<int>& arr, int n) {
    // 从最后一个非叶子节点开始向上调整到根节点
    for (int i = (n / 2) - 1; i >= 0; i--)
        minHeapify(arr, n, i);
}
 
// 输出最小堆的存储序列
void printMinHeap(vector<int>& arr, int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    buildMinHeap(arr, n);  // 将数组调整为最小堆
 
    printMinHeap(arr, n);  // 输出最小堆的存储序列
 
    return 0;
}

C.折半查找的次数

折半查找，其实就是二分法。开一个变量 cnt 记录循环的次数即可

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x;cin>>x;
	int l=1,r=n,mid=0;
	int cnt = 0;
	while(r>l){
		cnt++;
		mid = (l+r)/2;
		if(a[mid]>x) r=mid;
		else if(a[mid]<x) l=mid+1;
		else {
			break;
		}
	}
	if(a[l]==x||a[mid]==x) cout<<cnt;
	else cout<<"NO";
}

D.N个数的排序

看到数据量≤100，果断 sort 。如果数据量较大则可以考虑二分法

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<' ';
	}
}

E.班级同学信息查询

规范方法：写一个结构体或者开很多数组，分别记录学生的每个信息

但是，我们注意到，题目要求的是直接输出姓名和座位号，不会单独查询某个数据，那么我们就可以把姓名和座位号作为一个整体进行输入输出。用字符串数组存储即可。

#include<bits/stdc++.h>
using namespace std;
int n;
string s[1010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int temp;
		cin>>temp;
		getchar(); //处理学号和后面字符串间的空格
		getline(cin,s[temp]);
	}
	int tar;
	cin>>tar;
	cout<<s[tar];
}