From: Xavier <xavier_qy@163.com>
To: tj@kernel.org, sfr@canb.auug.org.au
Cc: linux-kernel@vger.kernel.org, linux-next@vger.kernel.org,
xavier_qy@163.com
Subject: [PATCH v2] Documentation: Fix the compilation errors in union_find.rst
Date: Fri, 2 Aug 2024 11:33:46 +0800 [thread overview]
Message-ID: <20240802033346.468893-1-xavier_qy@163.com> (raw)
In-Reply-To: <ZqvAeam7_iN44C88@slm.duckdns.org>
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>
---
Documentation/core-api/index.rst | 1 +
Documentation/core-api/union_find.rst | 6 +++++-
.../translations/zh_CN/core-api/index.rst | 1 +
.../zh_CN/core-api/union_find.rst | 21 ++++++++++++-------
4 files changed, 20 insertions(+), 9 deletions(-)
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index f147854700e..e18a2ffe078 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -49,6 +49,7 @@ Library functionality that is used throughout the kernel.
wrappers/atomic_t
wrappers/atomic_bitops
floating-point
+ union_find
Low level entry and exit
========================
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
index 2bf0290c918..6df8b94fdb5 100644
--- a/Documentation/core-api/union_find.rst
+++ b/Documentation/core-api/union_find.rst
@@ -16,9 +16,11 @@ of disjoint sets. The primary operations supported by union-find are:
Initialization: Resetting each element as an individual set, with
each set's initial parent node pointing to itself.
+
Find: Determine which set a particular element belongs to, usually by
returning a “representative element” of that set. This operation
is used to check if two elements are in the same set.
+
Union: Merge two sets into one.
As a data structure used to maintain sets (groups), union-find is commonly
@@ -63,7 +65,7 @@ operation, the tree with the smaller rank is attached under the tree with the
larger rank to maintain balance.
Initializing union-find
---------------------
+-----------------------
You can complete the initialization using either static or initialization
interface. Initialize the parent pointer to point to itself and set the rank
@@ -71,7 +73,9 @@ to 0.
Example::
struct uf_node my_node = UF_INIT_NODE(my_node);
+
or
+
uf_node_init(&my_node);
Find the Root Node of union-find
diff --git a/Documentation/translations/zh_CN/core-api/index.rst b/Documentation/translations/zh_CN/core-api/index.rst
index 922cabf7b5d..453a02cd1f4 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 a56de57147e..bb93fa8c653 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;
合并两个并查集
--------------
+--------------
对于两个相交的并查集进行合并,会首先查找它们各自的根节点,然后根据根节点秩大小,将小的
节点连接到大的节点下面。
--
2.45.2
next prev parent reply other threads:[~2024-08-02 3:34 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-08-01 5:48 linux-next: build warnings after merge of the cgroup tree Stephen Rothwell
2024-08-01 7:15 ` [PATCH v1] Documentation: Fix the compilation errors in union_find.rst Xavier
2024-08-01 17:06 ` Tejun Heo
2024-08-02 3:33 ` Xavier [this message]
2024-08-02 18:58 ` [PATCH v2] " Tejun Heo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240802033346.468893-1-xavier_qy@163.com \
--to=xavier_qy@163.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-next@vger.kernel.org \
--cc=sfr@canb.auug.org.au \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®