1 文件系统模拟（树数据结构）
在当今数字化时代，计算机技术已经深刻地嵌入我们的日常生活和工作中。而文件系统作为操作系统的核心组成部分，扮演着管理和组织计算机上数据的不可或缺的角色。它是我们数字生活的基石，为用户提供了有序存储、检索和管理数据的手段。
文件系统的设计与演进反映了计算机科学与技术的不断发展。从早期的简单文件系统到现代复杂的分层结构，文件系统的演进一直致力于提高数据存储和访问的效率，同时满足用户对数据组织的多样化需求。
文件系统模拟的核心思想是通过构建虚拟的文件系统环境，模拟用户进行各种文件操作，如创建、删除、移动、搜索等。这种模拟不仅提供了实际文件系统的功能，还允许用户在控制环境中进行实验，观察文件系统在不同条件下的行为和性能。
在这个数字时代，文件系统模拟的重要性不仅在于教学和研究，也在于实际应用中。通过模拟，我们能够更好地预测文件系统在特定负载下的表现，优化存储和检索过程，提高系统的整体性能。
综上所述，文件系统不仅仅是计算机领域中的一个组成部分，更是数字化时代的基石。文件系统模拟作为一种研究和实践手段，为我们提供了深入理解和优化文件系统的途径，推动了文件系统技术的不断发展。在未来，随着数据规模和复杂性的不断增加，文件系统模拟将继续发挥关键作用，助力构建更加高效可靠的数字化基础设施。
2 数据结构及理论建模
1. 树状数据结构
主数据结构是一个节点，节点之间的关系定义了目录和文件的层次结构。
2.节点结构：该结构表示文件系统树中的一个节点。
3.文件系统类：该类包含用于操作文件系统的方法，例如创建文件和目录、删除节点、移动节点、列出文件、搜索文件和设置权限（尽管后者当前是占位符）。
4.操作：
createFile：创建一个新的文件节点，并将其添加到指定的父节点。
createDirectory：创建新的目录节点并将其添加到指定的父节点。
deleteNode：删除指定的节点并将其从父节点的子节点列表中删除。
moveNode：通过更新父指针和同级指针将节点移动到新的父节点。
listFiles：列出目录中文件的名称。
searchFile：在目录中搜索具有给定名称的文件。
setPermissions：用于在节点上设置权限的占位符。
5.等级制度：节点之间相互连接，形成层次结构。指针指向第一个子节点，指针链接同一级别的节点（同一父节点的子节点）。childsibling
6.内存管理：节点是使用动态分配的，并且在提供的代码中不会显式释放内存。
7.根节点：文件系统以表示顶级目录的根节点 （） 启动。root
理论建模：
在下面的模型中，我们在根目录设立了两个文件file1, file2和两个文件夹directory1, directory2，其中我们模拟的文件是对file1进行删除操作,将file2移到directory1文件夹中，我们下面的代码也是实现了这个功能。
3 核心代码分析
节点结构：
此结构表示文件系统中的一个节点。它包括名称、文件或目录、大小、创建时间、修改时间以及指向其父节点、子节点和同级节点的指针等信息。
FileSystem 类：
创建文件：
创建具有指定名称、大小和父节点的文件。
将新文件节点追加到父节点的子列表中。
createDirectory：
创建具有指定名称和父节点的目录。
将新目录节点追加到父目录的子列表中。
delete节点：
删除指定的节点。
将节点从其 par 中删除
释放节点占用的内存。
移动：
将节点移动到新的父节点。
从其当前父节点的子节点列表中删除该节点。
将节点追加到新父节点的子列表中。
listFiles：
列出指定目录中的文件和目录的名称。
搜索文件：
在指定目录中搜索具有给定名称的文件。
4 测试样例
在测试样例中，我们成功输出了此刻根目录下的文件和目录，我们将文件1移动到目录1之后查看此刻的文件显示的根目录中没有文件意1，说明我们移动成功，我们将文件2删除之后也是查看此刻的根目录下的文件和目录此刻根目录下只有文件夹1和文件夹2，说明我们的模拟实验成功。
5 算法优缺点
优势：
灵活性：
树结构允许灵活组织文件和目录，算法同时处理文件和目录节点。
顺序搜索：
列出文件时使用的顺序搜索适用于小规模文件系统，并确保子节点的遍历。
模块化设计：
该代码采用模块化设计，每个操作有方法，从而促进了代码的组织和可读性。
显式内存管理：
该代码显式处理内存管理，在删除节点时解除分配内存。
弊端：
节点移除效率低下：
从其父节点的子列表中删除节点的算法具有 O（n） 的时间复杂度，因为它按顺序搜索要删除的节点。对于大型文件系统来说，这可能效率低下。
有限的错误处理：
该代码缺乏广泛的错误处理。例如，它假定提供的指针有效，并且内存分配始终成功。
无权限处理：
该方法是一个占位符，没有实际实现。对于实际的文件系统，处理权限至关重要，这需要合并。
6 附件之源代码
#include <iostream>
#include <string>
struct Node {
std::string name;
bool isFile;
int size;
std::string createTime;
std::string modifyTime;
Node* parent;
Node* child;
Node* sibling;
};
class FileSystem {
public:
Node* createFile(std::string name, int size, Node* parent) {
Node* file = new Node{
name, true, size, "2023-12-25", "2023-12-25", parent, nullptr, nullptr};
if (parent->child == nullptr) {
parent->child = file;
} else {
Node* temp = parent->child;
while (temp->sibling != nullptr) {
temp = temp->sibling;
}
temp->sibling = file;
}
return file;
}
Node* createDirectory(std::string name, Node* parent) {
Node* directory = new Node{
name, false, 0, "2023-12-25", "2023-12-25", parent, nullptr, nullptr};
if (parent->child == nullptr) {
parent->child = directory;
} else {
Node* temp = parent->child;
while (temp->sibling != nullptr) {
temp = temp->sibling;
}
temp->sibling = directory;
}
return directory;
}
void deleteNode(Node* node) {
if (node == nullptr) {
return;
}
// 从父节点的子节点链表中移除该节点
if (node->parent != nullptr) {
Node* prev = nullptr;
Node* current = node->parent->child;
while (current != nullptr && current != node) {
prev = current;
current = current->sibling;
}
if (current == node) {
if (prev != nullptr) {
prev->sibling = current->sibling;
} else {
node->parent->child = current->sibling;
}
}
}
// 释放节点所占用的内存空间
delete node;
}
void moveNode(Node* node, Node* newParent) {
if (node == nullptr || newParent == nullptr) {
return;
}
// 从原父节点的子节点链表中移除该节点
if (node->parent != nullptr) {
Node* prev = nullptr;
Node* current = node->parent->child;
while (current != nullptr && current != node) {
prev = current;
current = current->sibling;
}
if (current == node) {
if (prev != nullptr) {
prev->sibling = current->sibling;
} else {
node->parent->child = current->sibling;
}
}
}
// 将节点添加到新父节点的子节点链表
node->parent = newParent;
node->sibling = nullptr;
if (newParent->child == nullptr) {
newParent->child = node;
} else {
Node* temp = newParent->child;
while (temp->sibling != nullptr) {
temp = temp->sibling;
}
temp->sibling = node;
}
}
void listFiles(Node* directory) {
Node* temp = directory->child;
while (temp != nullptr) {
std::cout << temp->name << std::endl;
temp = temp->sibling;
}
}
Node* searchFile(Node* directory, std::string fileName) {
if (directory == nullptr) {
return nullptr;
}
Node* temp = directory->child;
while (temp != nullptr) {
if (!temp->isFile) {
temp = temp->sibling;
continue;
}
if (temp->name == fileName) {
return temp;
}
temp = temp->sibling;
}
return nullptr;
}
void setPermissions(Node* node, int permissions) {
// 设置权限的逻辑
}
};
int main() {
// 创建根节点
Node* root = new Node{
"root", false, 0, "2023-12-25", "2023-12-25", nullptr, nullptr, nullptr};
// 创建文件系统对象
FileSystem fs;
// 创建文件和目录
Node* file1 = fs.createFile("file1", 100, root);
Node* file2 = fs.createFile("file2", 150, root);
Node* directory1 = fs.createDirectory("directory1", root);
Node* directory2 = fs.createDirectory("directory2", root);
// 列出根节点下的文件和目录
std::cout << "根目录下的文件和目录:" << std::endl;
fs.listFiles(root);
std::cout << "---------------------------------" << std::endl;
// 移动文件或目录到另一个目录
fs.moveNode(file1, directory1);
std::cout << "将文件1移动到目录1中。" << std::endl;
std::cout << "---------------------------------" << std::endl;
// 列出根节点下的文件和目录，验证操作后的状态
std::cout << "操作移动后的根目录下的文件和目录:" << std::endl;
fs.listFiles(root);
// 删除文件或目录
fs.deleteNode(file2);
std::cout << "删除文件2。" << std::endl;
std::cout << "---------------------------------" << std::endl;
// 列出根节点下的文件和目录，验证操作后的状态
std::cout << "操作删除后的根目录下的文件和目录:" << std::endl;
fs.listFiles(root);
return 0;
}
