2

这是我在理论上一直在努力解决的问题，但在网上没有找到任何好的答案。我以前用二叉树编写过程序，这很简单：每个节点都有两个链接。但是现在我正在为一个项目计划一个基于树的文件系统，但我不确定如何进行。麻烦来了：

我想要一棵树，它具有指向叶子文件和内部节点子目录的指针（我认为这就是 Unix 的做法？）。但是如果用户想要创建一个新的文件或目录，则必须增加父节点中的链接数。

当我设计我的结构时，我该如何解释这一点？我不确定我的选择是什么，除了硬编码，比如 10 个链接和限制目录成员。任何指针？（哈，明白了吗？）

如果没有，是否有人知道我可以在其中了解更多信息的任何好资源？就像我说的，到目前为止，我的互联网搜索一直没有结果。

4

6 回答 6

7

您可以简单地使用孩子的链接列表。

请原谅我的 ASCII 图形：

+------+
|parent|
+------+
   |
   |
   \    +-----------+     +----------+       +----------+
    --->|first child|---->|next child|--...->|last child|-->NULL
        +-----------+     +----------+       +----------+

这使得步行孩子变得有点棘手，因为要获得第n个孩子，您需要访问前面的n -1 个孩子，但我认为这是一种可行的方法。

于 2012-04-12T13:59:59.353 回答
2

您可以使用孩子的链接列表。例如：

struct tree {
   /* data */
   struct children_list* children;
}

struct children_list {
   struct tree* child;
   struct children_list* next;
}
于 2012-04-12T14:02:18.377 回答
1

用数据成员创建一个节点=> 1.data 2.leftchild 3.rightsibling

假设父母有 k 个孩子。第一个孩子将被父节点中的leftchild指针指向..第二个孩子将被第一个孩子中的rightsibling指针指向..以类似的方式 ith child(1

这允许我们从父节点导航到子节点，反之亦然。注意：虚拟节点只是最后一个子节点的指示器...

于 2013-01-20T13:59:59.790 回答
1

这是 Linux 如何处理目录 http://en.wikipedia.org/wiki/Inode_pointer_structure

于 2012-04-12T14:01:31.620 回答
0

一个简单的解决方案是在每个树节点中都有一个列表。

于 2012-04-12T14:00:16.570 回答
0

您可以使用动态分配的数组，并存储数组指针及其大小。当你需要编辑它时，你只需重新分配它。

但是，在这种情况下，您应该在操作系统和文件系统书籍、文章、科学杂志/出版物等中寻找公认的解决方案。

于 2012-04-12T14:01:08.630 回答