数据结构作业3

此作业为某大学数据结构作业3，答案为我当时所写，仅供学习和参考

问题 A: 无向图的深度优先搜索

题目描述

已知一个无向图G的顶点和边，顶点从0依次编号，现在需要深度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的深度优先搜索序列。

输入

第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。

输出

该图从0号顶点开始的深度优先搜索序列。

样例输入

5 5
0 1
2 0
1 3
1 4
4 2

样例输出

0 1 3 4 2

参考答案

查看答案

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct node{
    int data;
    multiset<node*> next;
};

void addEdge(vector<node*> &v, int e1, int e2){
    v[e1]->next.insert(v[e2]);
    v[e2]->next.insert(v[e1]);
}

void dfs(vector<bool> &flag, node* root){
    if (root == nullptr) return;
    cout << root->data << " ";
    flag[root->data] = false;
    for (auto it : root->next) {
        if (flag[it->data]) dfs(flag, it);
    }
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<node*> v(m);
    for (int i = 0; i < m; ++i) v[i] = new node{i, {}};
    for (int i = 0; i < n; ++i) {
        int e1, e2;
        cin >> e1 >> e2;
        addEdge(v, e1, e2);
    }

    vector<bool> flag(m, true);
    dfs(flag, v[0]);
    return 0;
}

问题 B: 最小堆的形成

题目描述

现在给你n个结点的完全二叉树数组存储序列，请编程调整为最小堆，并输出相应最小堆的存储序列。

输入

第一行是n，第二行是n个结点的完全二叉树数组存储序列。

输出

输出相应最小堆的存储序列。

样例输入

8
53 17 78 23 45 65 87 9

样例输出

9 17 65 23 45 78 87 53

参考答案

查看答案

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void down_update(vector<int> &v, int i, int n){
    int index = i;
    while (i*2 <= n) {
        if (v[i*2] < v[i]) index = i*2;
        if (i*2+1 <=n && v[i*2+1] < v[index]) index = i*2+1;
        if (index == i) break;
        swap(v[i], v[index]);
        i = index;
    }
}

void build_heap(vector<int> &v, int n){
    for (int i = n/2; i >= 1; --i) {
        down_update(v, i, n);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n+1);
    v[0] = 0;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    build_heap(v, n);
    for_each(v.begin()+1, v.end(), [] (int i)-> void {cout << i << " ";});
    return 0;
}

问题 C: 折半查找的次数

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

2

参考答案

查看答案

#include <iostream>
#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 num;
    cin >> num;
    for (int l = 0, r = n-1, j = 1; l <= r; ++j) {
        if (r-l <= 1 && v[l] != num && v[r] != num) break;
        int mid = (l+r) / 2;
        if (v[mid] == num) {
            cout << j;
            return 0;
        }
        else if (num < v[mid]) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    cout << "NO";
    return 0;
}

问题 D: N个数的排序

题目描述

给你N个自然数，编程输出排序后的这N个数。

输入

第一行是整数的个数N（N<=100）。第二行是用空格隔开的N个数。

输出

排序输出N个数，每个数间用一个空格间隔。

样例输入

5
9 6 8 7 5

样例输出

5 6 7 8 9

参考答案

查看答案

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void ui_sort(vector<int> &arr, int n){
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[0]) swap(arr[0], arr[i]);
    }
    for (int i = 2; i < n; ++i) {
        int j = i;
        while (arr[j] < arr[j-1]) {
            swap(arr[j], arr[j - 1]);
            --j;
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    ui_sort(v, n);
    for (auto it : v) cout << it << " ";
    return 0;
}

问题 E: 班级同学信息查询

题目描述

班级里有N个同学，老师希望你编个程序，把每个同学的学号、姓名、座位号保存下来，然后每次要查同学信息时，直接输入相应同学的学号，即可输出该同学的姓名和座位号。

输入

第一行为整数N（N<100）,表示班里同学的人数。接下来N行，每行分别是每个同学的学号、姓名和座位号，最后一行是要查询的同学的学号。

输出

输出查询同学的姓名和座位号。

样例输入

3
1 zhang 11
2 wang 22
3 li 33
2

样例输出

wang 22

参考答案

查看答案

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct info{
    string name;
    int no;
};

int main() {
    unordered_map<string, info> ump;
    int n;
    cin >> n;
    string s_no;
    info stu;
    for (int i = 0; i < n; ++i) {
        cin >> s_no >> stu.name >> stu.no;
        ump.insert({s_no, stu});
    }
    cin >> s_no;
    stu = ump.find(s_no)->second;
    cout << stu.name << " " << stu.no;
    return 0;
}