搜索多树数据结构的最有效方法

Question

我想知道是否有一种更有效的方式来搜索多树而不是我一直在做的事情.我最近为项目构建了一个多树数据结构,如下所示.

洞穴将各方列入阵列列表.不同的政党会拥有不同的生物.不同的生物会持有不同的物品.

我需要一种方法来搜索整个树,以便将对象与其拥有的属性(如索引)相匹配.这是我的程序片段,它搜索每个ArrayList以查看派对,生物,宝藏或工件是否与int I调用索引匹配.

编辑(解释我的代码)类Party,Creature,Treasure和Artifact都具有索引,名称,类型等属性.多树将Cave设置为根音符.Cave有一个ArrayList,可以包含许多Party对象.每个Party都有一个ArrayList,可以包含许多Creature对象.每个生物都有两个数组列表,一个用于保存Artifact对象,另一个用于Treasure对象.

下面我正在搜索哪个派对,生物,工件或宝藏包含我正在搜索的特定索引.我通过迭代派对来实现这一点,我在每个派对中查看这些生物,并且每个生物都会查看文物和宝物.这就是为什么我在for循环中有这么多for循环:(.

case 0 :
            int index =                 Integer.parseInt( stat );
            for ( Party p : SorcerersCave.theCave.parties ) {
                if ( index == p.getIndex()) {
                    generateInterface.theGame.printOutput( "\t" + p );
                    break;
                } else {
                    for ( Creature c : p.members ){
                        if ( index == c.getIndex() ){
                            generateInterface.theGame.printOutput( "\t" + c );
                            break;
                        } else {
                            for ( Treasure t : c.inventory ){
                                if ( index == t.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + t );
                                    break;
                                }
                            }
                            for ( Artifact a : c.artifacts ){
                                if ( index == a.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + a );
                                    break;
                                }
                            }
                        }
                    }
                }
            }

我觉得这段代码太复杂了,很难理解.代码可以工作,但它在我看起来非常好看的代码上是一个丑陋的污点.我一直在寻找更好的方法来做到这一点,甚至是改善它的方法.

注意*项目要求禁止我们将每个对象放在同一个ArrayList中.

Answer 1

您的类可以实现一个公共接口SearchableByIndex，如下所示，并且该接口将由树中的每个类实现：

public interface SearchableByIndex {
    public SearchableByIndex searchByIndex(int index);
    public int getIndex();
}

然后Cave，Party并Creature需要以下代码：

public SearchableByIndex searchByIndex(int index) {
    if (getIndex() == index) {
        return this;
    } else {
        for (Party party : parties) {    // or Creature creature : members etc.
            SearchableByIndex found = party.searchByIndex(index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

宝藏和神器的版本：

public SearchableByIndex searchByIndex(int index) {
    return (getIndex() == index) ? this : null;
}

而不是你在那里的嵌套循环，你会

case 0:
    int index = Integer.parseInt(stat);
    SearchableByIndex foundItem = SorcerersCave.theCave.searchByIndex(index);
    if (foundItem != null) {
        generateInterface.theGame.printOutput("\t" + foundItem);
    } else {
        // print out that the item was not found
    }
    break;

虽然searchByIndex()每个类上的方法可能看起来重复，但这是 OOP 方法。这样，每个班级都会负责搜索其所有内容。在您的情况下，所有类的代码都非常相似（唯一的变化是 for 循环的行），但您可以认为这是一个意外 - 任何类都可以包含它想要的任何数据，并且其他类不应该关心关于它如何存储数据。

将来，如果您的某个类将包含更多可搜索数据（Treasure、Artifact和Hostage？），或者您想更改其数据的结构（HashMap如果可以的话，考虑一下！），您只需searchByIndex()更改特定的班级。

此外，只有包含数据的类才应该知道它是如何包含数据的。按照您现在的方式，调用搜索的其他一些类确切地知道数据如何存储在每个类中 - 这不应该是这样。如果一个类发生变化，就会破坏其他类的内部代码。例如，该类Cave应该在其文档中声明它拥有不同的Party实例，并且如果您通过 搜索它，它可以给出其中的一些实例searchForIndex()。