主页 / coding / 问题 / 79301584
Accepted
GPWR
Asked: 2024-12-23 03:24:39 +0800 CST

C 文件管理器的高效链表设计

  • 772

语境。

我正在用 C 语言制作一个文件管理器。为了在 ncurses 中显示 CWD 中的文件列表，我选择将文件列表实现为以下结构的单链表：

typedef struct FileNode {
    char name[256]
    struct FileNode* next;
} FileNode;

我确信文件名永远不会超过 255 个字符加上空终止符。这是 ext2、ext3、ext4、BTRFS、XFS、ZFS 和 exFAT 的标准。（我不熟悉 DOS 文件系统，但我只针对 UNIX。）

我需要考虑将给定文件重命名为更长名称的情况，在这种情况下，我只会更改该文件节点的名称，而不会重建整个链接列表。但是，如果名称发生更改，则结构也可能会改变列表中的位置，因为列表是按名称的字母顺序排列的FileNode。

注意。我稍后可能会向FileNode结构中添加成员，例如，确定用户在 ncurses 界面中选择了列表中的哪些文件。

问题。

由于该FileNode结构为文件名保留了 256 个字节，因此对于包含大量名称相对较短的文件的目录，将浪费大量内存。我的文件管理器是通用的，所以我可以想象这种情况会发生。

在这种情况下，高级程序员会怎么做？创建大型文件列表或同时重命名许多文件时，文件名的动态分配会导致更多的开销。（这将是我的文件管理器的一个功能。）

我研究过的事情。

在考虑了一段时间的 FAM 之后（见下面的代码片段），我注意到文件重命名变得很复杂，除非我选择在重命名文件时释放节点并创建一个新节点。这是一个好的选择吗？代价高昂的部分是首先检查所有文件名的长度，以便生成一个适合这些长度的操作系统结构列表。重复我之前的问题，高级程序员会怎么做？

typedef FileNode {
    struct FileNode* next;
    char name[]; // this member should be the last
} FileNode;
c

1 个回答

  1. Best Answer

    从算法角度来看的一些想法：

    对于始终排序的列表，您可以利用数据结构，例如AVL or Red-Black Trees根据您的选择在创建、删除或重命名文件时维护 FileList 的排序顺序。

    要提高大型目录的性能：

    使用哈希表进行文件名查找，灵感来自 Linux 内核的dcache

    将文件名（或文件 ID）映射到FileNode红黑树中的指针，以进行 O(1) 查找。

    为了处理重命名的情况，我会：

    1. 使用哈希表检索 FileNode 指针。
    2. 释放FileNode->name所占用的内存。从红黑树中删除该节点并重新平衡。
    3. 重新分配所需的必要内存。
    4. 将 newName 复制到 FileNode->name。将节点插入红黑树并再次重新平衡。

    进一步改进的范围：

    • 1

相关问题