diff options
| author | Xavier <xavier_qy@163.com> | 2024-08-02 05:33:46 +0200 |
|---|---|---|
| committer | Tejun Heo <tj@kernel.org> | 2024-08-02 20:58:16 +0200 |
| commit | 563ea1f5f85171b68f9075f5c3c22c4b521f1b5e (patch) | |
| tree | 9807a18bfb5605d8be35d03459f64e725f758868 /Documentation/translations | |
| parent | cgroup: Show # of subsystem CSSes in cgroup.stat (diff) | |
| download | linux-563ea1f5f85171b68f9075f5c3c22c4b521f1b5e.tar.xz linux-563ea1f5f85171b68f9075f5c3c22c4b521f1b5e.zip | |
Documentation: Fix the compilation errors in union_find.rst
Fix the compilation errors and warnings caused by merging
Documentation/core-api/union_find.rst and
Documentation/translations/zh_CN/core-api/union_find.rst.
Signed-off-by: Xavier <xavier_qy@163.com>
Signed-off-by: Tejun Heo <tj@kernel.org>
Diffstat (limited to 'Documentation/translations')
| -rw-r--r-- | Documentation/translations/zh_CN/core-api/index.rst | 1 | ||||
| -rw-r--r-- | Documentation/translations/zh_CN/core-api/union_find.rst | 21 |
2 files changed, 14 insertions, 8 deletions
diff --git a/Documentation/translations/zh_CN/core-api/index.rst b/Documentation/translations/zh_CN/core-api/index.rst index 922cabf7b5dd..453a02cd1f44 100644 --- a/Documentation/translations/zh_CN/core-api/index.rst +++ b/Documentation/translations/zh_CN/core-api/index.rst @@ -49,6 +49,7 @@ generic-radix-tree packing this_cpu_ops + union_find ======= diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst index a56de57147e9..bb93fa8c6533 100644 --- a/Documentation/translations/zh_CN/core-api/union_find.rst +++ b/Documentation/translations/zh_CN/core-api/union_find.rst @@ -3,21 +3,23 @@ :Original: Documentation/core-api/union_find.rst -=========================== +============================= Linux中的并查集（Union-Find） -=========================== +============================= :日期: 2024年6月21日 :作者: Xavier <xavier_qy@163.com> 何为并查集，它有什么用？ ---------------------- +------------------------ 并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作： - 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身 + 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身。 + 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为 了判断两个元素是否在同一个集合之中。 + 合并：将两个集合合并为一个。 并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和 @@ -37,7 +39,7 @@ Linux中的并查集（Union-Find） https://en.wikipedia.org/wiki/Disjoint-set_data_structure 并查集的Linux实现 ----------------- +------------------ Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要 “#include <linux/union_find.h>”。 @@ -48,22 +50,25 @@ Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需 struct uf_node *parent; unsigned int rank; }; + 其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大 的节点下面以增加平衡性。 初始化并查集 ---------- +------------- 可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置 为 0。 示例:: struct uf_node my_node = UF_INIT_NODE(my_node); + 或 + uf_node_init(&my_node); 查找并查集的根节点 ----------------- +------------------ 主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中 会对路径进行压缩，提高后续查找效率。 @@ -78,7 +83,7 @@ Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需 connected = 0; 合并两个并查集 -------------- +-------------- 对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的 节点连接到大的节点下面。 |