java - 使用队列创建一个文件系统，实现为 Java 中的单链表树

Question

我们得到了一些实现为单链表树的树。 insertPath 函数构造一个子树(或使用现有的子树)来存储一个新文件，由 filePathQueue 表示进入Tree<FileNode> t .队列有一个订单 IN -> [ “myFile” , “mySubDir” , “myDir” ] -> OUT ，这意味着我应该能够出列以按顺序获取父目录，然后检查树中的当前级别以查看该目录是否存在。每个 FileNode 都有一个值，即它的名称，以及一个 boolean 值 true。表明它是一个文件，false表示它是一个目录。我已经粘贴了我的 insertPath 代码以及 findChild 代码。其余的都给了我们，我认为教授提供的代码可以正常工作。我实现的唯一代码是 findChild 和 insertPath。

当代码使用我的工作文件夹中的“sample”目录创建一个新的文件系统时会抛出异常，该目录包含三个子目录，每个子目录都有一些文件和它们自己的子目录。澄清一下:构造函数将单独的队列传递给我，这些队列代表目录中的每个文件和文件夹，我将循环将其转换为树。因此 insertPath 被多次调用，每次都传递更新的树。

我不知道为什么添加到树中会引发异常:它告诉我我正在尝试使一个空队列出列，但根据我的代码，如果队列为空，我应该从它中返回吗？异常在底部。有问题的行是 insertPath 方法中的递归调用以及顶部的出队。任何帮助是极大的赞赏。谢谢。

public Tree<T> findChild(T otherLabel) {
    if(getFirstChild() == null)
        return null;
    if(getFirstChild().getLabel() == otherLabel)
        return getFirstChild();
    Tree<T> test = getNextSibling();
    while(test != null){
        if(test.getLabel() == otherLabel)
            return test;
        test = test.getNextSibling();
    }
    return null;
}

public void insertPath(Tree<FileNode> t, QueueList<String> filePathQueue) {
try{
    String check = filePathQueue.dequeue();
    if(filePathQueue.size() == 0){
        Tree<FileNode> file = new Tree<FileNode>(new FileNode(check,false));
        t.addChild(file);
        return;
    }
    Tree<FileNode> dir = new Tree<FileNode>(new FileNode(check,true));
    Tree<FileNode> subdir = t.findChild(dir.getLabel());
    if(subdir == null){
        t.addChild(dir);
        insertPath(t.getFirstChild(), filePathQueue);
    }
    insertPath(subdir, filePathQueue);

    } 
catch(Exception e){ e.printStackTrace(); return;}

InvalidOperationException: Queue empty: nothing to dequeue.
at QueueList.dequeue(QueueList.java:39)
at FileSystem.insertPath(FileSystem.java:38)
at FileSystem.insertPath(FileSystem.java:50)
at FileSystem.insertPath(FileSystem.java:48)

Answer 1

您在 insertPath() 方法末尾递归调用 insertPath() 两次:

public void insertPath(Tree<FileNode> t, QueueList<String> filePathQueue) {
    ...
    if(subdir == null){
        t.addChild(dir);
        insertPath(t.getFirstChild(), filePathQueue); // ONCE
    }
    insertPath(subdir, filePathQueue); // TWICE
}

因此，如果使用只有一个元素的 filePathQueue 进入上述代码块，则对 insertPath() 的每次调用都将尝试拉取一个，第二个将抛出您在问题中演示的 InvalidOperationException。

您似乎想要在 subdir 为 not null 时包含一个 else block ，或者改进您的 insertPath() 方法用于检查 filePathQueue 大小在您尝试从中取出项目。

但鉴于这是家庭作业 - 我会让你决定走哪条路。 :-)