java - 代表包安装和系统依赖的最佳数据结构

Question

我正在尝试基于面试过程创建一个程序（我选择 Java，但可以是 C/C++ 或 GoLang）来表示/模拟 Linux/Unix 环境中存在的包安装和系统依赖关系。基本上，我会做以下要求：

1) 维护已安装包及其依赖项的记录。
2) 支持显式安装包以响应命令（除非已经安装）。
3) 如果需要安装另一个包，支持隐式安装一个包。
4）支持显式删除一个包以响应命令（如果不需要支持其他包）。
5) 如果不再需要支持另一个组件，则支持隐式删除一个包。

在安装包之前，自动安装它需要的所有包。在删除一个包之前，请确认没有其他包需要它。必须先手动删除依赖包，然后才能删除包。

我想要可以用来执行此操作的最佳数据结构（以及我可以检查的链接）的提示。我尝试使用队列列表作为存储依赖项的一种方式，并使用队列来存储已安装的包，但我不确定这是否是最好的方法，例如：

...
ArrayList<Queue<String>> dependencies = new ArrayList<>(capacity);
Queue<String> pkgInstalled = new LinkedList<String>();
...

该过程将捕获用户的条目数据，直到发出 END 命令。命令语法为：

DEPEND item1 item2 item(n)：包 item1 依赖于包 item2（和 item3 或任何；

安装 item1：安装 item1 和 item1 所需的任何其他包。

REMOVE item1：删除 item1，如果可能，删除 item1 所需的包。

LIST：列出所有当前安装的包的名称。

END：当单独在一行中使用时，标记输入的结束。

1) 在每个回应的 INSTALL 或 REMOVE 行之后执行响应所采取的操作，确保以正确的顺序给出这些操作。
2) 对于 LIST 命令，显示当前安装的组件的名称。
3) 对于 DEPEND 和 END 命令，除了回显之外，不产生任何输出。
4) 对于 DEPEND 命令，每一项只会有一个依赖列表。

标签： javac++cgodata-structures

Answer 1

我不知道Queue本练习中 a （或 a LinkedList）的值，因为您希望能够随机访问包的依赖项。

我会建议

Map<String, Set<String>> dependsOn = new HashMap<>();
Map<String, Set<String>> requiredBy = new HashMap<>();

这样，当您删除一个包时，您可以找到它已拉入 ( dependsOn.get(packageToDelete)) 中的所有包，并packageToDelete从它们的每个条目中删除requiredBy；如果这使requiredBy集合为空，则也可以删除该包。

我还建议Set在添加新根包时使用 a 来添加依赖包。处理它们的顺序并不重要，快速并避免重复更有用。

最初我认为使用唯一的完全限定包名称作为键会更简单——更容易编码和调试。这需要一种基于名称查找包的方法，但这应该已经存在。但是，如果您愿意，您可以为您的类实现equals()and并将它们直接用作键。hashcode()PackageMap

为了阐明这可能如何工作，这里有一个例子：

public Set<String> addDependencies(Item pkg, Item... dependencies) {
    Set<String> pkgDependsOn = dependsOn.get(pkg.getFullyQualifiedName());
    if (pkgDependsOn == null) {
        pkgDependsOn = new HashSet<>();
        dependsOn.put(pkg.getFullyQualifiedName(), pkgDependsOn);
    }
    pkgDependsOn.addAll(Stream.of(dependencies).map(dep -> dep.getFullyQualifiedName()).collect(Collectors.toSet()));
    return pkgDependsOn;
}

（我可能会使用Map.merge()它，但写出来后我认为它足够复杂以至于令人困惑。）

返回Set依赖项的结果可能是矫枉过正，但我​​可以想象在某些情况下它可能有用。

如果您确实选择使用包本身作为键，它看起来像这样：

public Set<Item> addDependencies(Item pkg, Item... dependencies) {
    Set<Item> pkgDependsOn = dependsOn.get(pkg);
    if (pkgDependsOn == null) {
        pkgDependsOn = new HashSet<>();
        dependsOn.put(pkg, pkgDependsOn);
    }
    pkgDependsOn.addAll(Arrays.asList(dependencies));
    return pkgDependsOn;
}

我也没有进行错误检查（例如，如果您使包依赖于自身）、空检查等。