中山大学数据结构与算法实验报告9 – Michael Yeungの学习笔记

第一题多叉树与二叉树

1.实验题目

2. 实验目的

本实验的目标是将一个有n个节点的多叉树转换为二叉树，并通过层次遍历输出二叉树的节点顺序。通过本实验，学生能够：

理解多叉树和二叉树之间的关系。

掌握如何将多叉树转换为左儿子右兄弟的二叉树形式。

学会使用层次遍历对二叉树进行访问。

3. 算法设计

为实现将多叉树转换为二叉树并输出层次遍历顺序，我们首先需要构建多叉树的结构，并利用递归方法将其转化为二叉树的左儿子右兄弟结构。具体的算法步骤如下：

多叉树转二叉树：
- 对于每个节点，首先将其第一个儿子作为左儿子。
- 然后将后续的兄弟节点依次链接为右兄弟。
- 利用递归函数构建整个二叉树。
层次遍历：
- 使用队列对转换后的二叉树进行层次遍历，按照自上而下，自左而右的顺序访问每个节点，并记录其值。
时间复杂度：
- 转换树的过程和层次遍历的时间复杂度均为 O(n)，其中 n 是树的节点数。
代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x): val(x), left(NULL), right(NULL) {}
};

Node* buildtree(const vector<vector<int>>& adj, int root) {
    Node* node = new Node(root);
    if (!adj[root].empty()) {
        node->left = buildtree(adj, adj[root][0]);
        Node* sibling = node->left;
        for (int i = 1; i < adj[root].size(); i++) {
            sibling->right = buildtree(adj, adj[root][i]);
            sibling = sibling->right;
        }
    }
    return node;
}

vector<int> levelorder(Node* root) {
    vector<int> res;
    if (root == nullptr) return res;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        adj[parent].push_back(i);
    }
    Node* root = buildtree(adj, 1);
    vector<int> res = levelorder(root);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了以下测试用例：

输入样例：
- n = 5
- 父节点序列：1 1 1 2
输出样例：
- 层次遍历顺序为：1 2 5 3 4

程序运行

程序能够正确读取输入并输出二叉树的层次遍历顺序。
使用队列进行层次遍历时，保证了数据的顺序性和完整性。

5. 实验总结与心得

通过本次实验，我深入理解了多叉树到二叉树转换的过程，特别是如何利用左儿子右兄弟的结构来简化树的操作。同时，层次遍历是树结构处理中非常常见的一种方式，通过队列来实现，可以保证节点按照正确的顺序访问。

这次实验让我认识到，树的不同表示方式（如多叉树和二叉树）对于问题求解的效率和简便性有很大的影响。转换树的结构不仅有助于简化代码逻辑，还能提高数据处理的效率。此外，本次实验也加深了我对层次遍历和递归实现树结构操作的理解。

总体来说，本次实验帮助我巩固了树形结构的基本知识，并在实践中提高了算法设计和实现的能力。

第二题家族查询

1.实验题目

2. 实验目的

本实验的主要目的是实现判断两个给定人物是否有亲戚关系。通过本实验，学生能够：

理解并实现并查集（Union-Find）数据结构，处理集合的合并与查找操作。

掌握如何在大规模数据中高效地解决“是否属于同一集合”的查询问题。

提高算法设计与优化能力，尤其是在处理大规模数据时的效率分析与实现。

3. 算法设计

本实验主要使用了并查集（Union-Find）数据结构来解决亲戚关系问题。通过并查集，我们可以高效地进行两个人是否属于同一个亲戚群体的查询，并通过合并操作来建立亲戚关系。具体的算法步骤如下：

并查集初始化：
- 每个人初始化为自己所在的集合，即每个人都是自己的父亲。
- 使用一个数组 parent 存储每个元素的父节点，rank 数组用于优化合并操作的效率。
合并操作：
- 对于每一对有亲戚关系的人，执行 unite 操作，将他们所在的集合合并到一起，表示他们是亲戚。
- 使用路径压缩和按秩合并来优化查询和合并操作。
查询操作：
- 对每一对询问的人，判断他们是否属于同一个集合。如果属于同一个集合，则输出 "Yes"，否则输出 "No"。
时间复杂度：
- 每次 find 操作的时间复杂度为 O(α(n))，其中 α(n) 是反阿克曼函数，近似为常数。
- 每次 unite 操作的时间复杂度为 O(α(n))。
- 因此，整体算法时间复杂度为 O((n + m + q) * α(n))，其中 n 为人数，m 为亲戚关系数，q 为询问次数。
代码实现：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;  // 每个人初始化为自己的父节点
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 按秩合并，优化合并操作
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                if (rank[rootX] == rank[rootY]) {
                    rank[rootX]++;
                }
            }
        }
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        UnionFind uf(n);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            uf.unite(u, v);  // 合并亲戚关系
        }
        int q;
        cin >> q;
        while (q--) {
            int u, v;
            cin >> u >> v;
            if (uf.find(u) == uf.find(v)) {
                cout << "Yes" << endl;  // 如果同属于一个集合，输出 Yes
            } else {
                cout << "No" << endl;   // 否则输出 No
            }
        }
        cout << endl;
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了以下测试用例：

输入样例：

输出样例：
```
No
Yes

Yes
No
Yes
```

程序运行

程序能够正确读取输入并输出每对查询的亲戚关系。
在处理多个查询时，程序能够高效地进行并查集的查找与合并操作。
输入较大数据（如 n = 5000，m = 5000，q = 5000）时，程序依然能够在合理时间内完成计算。

5. 实验总结与心得

通过本次实验，我深入了解了并查集（Union-Find）数据结构的基本原理及其在处理动态集合合并和查询问题中的应用。实验中的主要挑战在于如何高效地处理大规模数据，特别是在进行多次查询时，确保每个操作的时间复杂度尽可能低。

通过路径压缩和按秩合并优化，程序能够在常数时间内完成集合查找和合并操作，使得整个算法非常高效。对于类似的动态连通性问题，并查集是一个非常合适的数据结构，可以显著提高查询效率。

此外，本次实验让我更加熟悉了处理大规模数据时，如何选择合适的算法和数据结构以达到性能要求。特别是在面对需要频繁查询和合并的场景时，能够用并查集这种高效的数据结构来解决问题，是非常实用的。

通过这次实验，我不仅加强了对并查集的理解，还提高了处理复杂问题时选择合适算法的能力。

第三题连通性问题

1. 实验题目

2. 实验目的

本实验的主要目的是通过实现一个高效的程序，来解决给定数对序列的连通性问题。通过本实验，学生能够：

理解并掌握并查集（Union-Find）数据结构，尤其是其在连通性问题中的应用。
学会如何优化算法，利用并查集的合并与查找操作有效处理大规模输入。
提高大数据量下的算法设计与分析能力。

3. 算法设计

本实验的目标是过滤给定数对序列，去除其中可以通过传递性推导得到的数对。为了解决这个问题，我们使用并查集（Union-Find）数据结构，具体的算法步骤如下：

初始化并查集：
- 创建一个并查集来管理各个数字的连接状态。并查集通过两个主要操作来维护集合的划分：find 查找某个元素的根节点，unite 合并两个元素所在的集合。
- 使用路径压缩与按秩合并策略优化并查集操作，以保证查找和合并操作的时间复杂度接近常数时间。
处理输入数据：
- 每次输入一个数对时，判断该数对是否已经属于同一集合。如果不属于同一集合，则输出该数对并将其合并到同一集合中。
- 如果该数对已经属于同一集合，则表明它可以通过前面的数对推导出，因此不需要输出。
优化策略：
- 通过并查集的路径压缩和按秩合并策略，确保每次合并和查找的时间复杂度都尽可能低，从而在面对大规模数据时保持高效性。
时间复杂度：
- find 和 unite 操作的时间复杂度是接近常数的，具体来说是 O(α(n))，其中 α(n) 是阿克曼函数的反函数，非常缓慢增长。
- 因此，对于 m 个数对的处理，总时间复杂度为 O(m * α(n))，其中 n 是数字的最大值。
代码实现：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    int a, b;
    UnionFind uf(1000001);  // 设定最大数字为1000000
    while (cin >> a >> b) {
        if (uf.find(a) != uf.find(b)) {
            cout << a << " " << b << endl;
            uf.unite(a, b);
        }
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同规模的输入：

输入样例：

输出样例：
```
3 4
4 9
8 0
2 3
5 6
5 9
7 3
4 8
6 1
```
解释：
- 第一行输入的数对 3 4 是新的，不在任何已有集合中，因此输出。
- 第二行输入的数对 4 9 也是新的，不在任何已有集合中，因此输出。
- 随着数对的合并，某些数对变得可以通过其他数对的传递性推导出来，因此不再输出。

程序运行

程序通过并查集高效地处理输入，能够在大量数对的情况下快速判断并合并连通集合。
程序的运行时间在最坏情况下依然保持较低，适用于处理最多百万级别的数对。

5. 实验总结与心得

通过本次实验，我学会了如何利用并查集（Union-Find）数据结构高效地解决连通性问题。实验中的核心是合并和查找操作的优化，通过路径压缩和按秩合并，确保了操作的高效性。

本实验加深了我对并查集算法的理解，尤其是在处理大规模数据时如何通过优化提高程序性能。并查集作为一个经典的算法工具，在很多实际问题中都有广泛的应用，掌握其优化技巧对解决复杂问题具有重要意义。

此外，本次实验让我理解了如何在大数据量的情况下高效判断集合之间的关系，以及如何设计并实现一个高效的算法。

近期文章

最新评论

第一题多叉树与二叉树

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第二题家族查询

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第三题连通性问题

1. 实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

发送评论编辑评论

近期文章

第一题 多叉树与二叉树

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第二题 家族查询

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第三题 连通性问题

1. 实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

发送评论 编辑评论

推荐文章

第一题多叉树与二叉树

第二题家族查询

第三题连通性问题

发送评论编辑评论