5

我想知道是否有比我一直在做的更有效的方法来搜索多树。我最近为一个项目构建了一个多树数据结构，如下图所示。 使用 ArrayLists 的多树数据结构

洞穴会将各方放在一个数组列表中。不同的政党将拥有不同的生物。不同的生物会持有不同的物品。

我需要一种方法来搜索整个树以将对象与它具有的属性（例如索引）匹配。这是我的程序的一个片段，它搜索每个 ArrayList 以查看是否有一方、生物、宝藏或神器与我称为 index 的 int 匹配。

编辑（解释我的代码）Party、Creature、Treasure 和 Artifact 类都具有索引、名称、类型等属性。多树将 Cave 设置为根注释。Cave 有一个 ArrayList 可以包含许多 Party 对象。每个 Party 都有一个 ArrayList，可以包含多个 Creature 对象。每个生物都有两个数组列表，一个用于保存神器对象，一个用于保存宝藏对象。

下面我正在搜索以查看哪个派对、生物、神器或宝藏拥有我正在搜索的特定索引。我通过迭代派对来做到这一点，每个派对我都查看生物，每个生物我查看文物和宝藏。这就是为什么我在 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 中。

4

7 回答 7

2

您的类可以实现一个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和特定的类。ArtifactHostageHashMapsearchByIndex()

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

于 2013-06-25T06:07:56.203 回答
2

项目要求禁止我们将每个对象放在同一个 ArrayList 中。

（据推测， a HashMaporTreeMap也被禁止......）

如果没有某种辅助数据结构来将index值映射到它们所引用的对象，您别无选择，只能进行树遍历。因此，平均而言，您的“查找对象”代码将是O(N)如果有N对象......具有相当大的比例常数。

（大概，对问题施加限制的人并不关心性能。您应该采取相同的态度......尤其是考虑到您评论中列出的上下文。）

您可以通过几种方式改进代码，使其更具可读性和（很可能）更高效。

  1. 使用“break to label”，以便内部循环在受到打击时退出到外部循环的末尾。（假设这就是你想要的。）

  2. 每次在容器层次结构中查找元素时，使用临时变量来避免评估多个方法调用。 更新：看起来你刚刚重写了代码来做到这一点......

...项目要求规定每个对象都需要在多树数据结构中实例化，如我发布的图表所示。

但是他们是否明确禁止二级数据结构？还是您只是假设您不允许这样做？

于 2013-06-25T06:19:06.820 回答
1

我会改用 for-each 循环：

int index = Integer.parseInt(stat);
for(Party party : parties){
    if( index == party.members.get( c ).getIndex() ){
        generateInterface.theGame.printOutput( "\t" + party.summary );
        break;
    } else {
        for(Creature creature : party.Creatures){
            // etc etc.....
        }
    }
}

这将使代码更易于阅读。它确实有一个缺点，即循环中没有内置计数器。

编辑：本文可能会澄清： https ://blogs.oracle.com/CoreJavaTechTips/entry/using_enhanced_for_loops_with

于 2013-06-25T05:42:13.490 回答
1

这是一个非常奇怪的约束集，但是本着树遍历的精神，根本不需要修改原始数据结构，为什么不把朴素的递归遍历函数写成一组重载方法呢？它可能看起来像这样：

public Object search(int index, Cave c) {
  if (c.id == index) return c;

  for (Party p : c.parties) {
    Object result = search(index, p);
    if (result != null) 
      return result;
  }

  return null;
}

public Object search(int index, Party p) {
  ...
}

等等。

于 2013-06-25T06:17:03.467 回答
0

你能用更规则的结构吗？这些方面的东西（我正在使用伪代码）：

interface INode { ... stuff kept in nodes is described here ... }
interface ITree extends INode { bool HasId(int id); ITree[] Children; }

INode SearchTreeForId(ITree[] children, int id) {
  for each (child in children) {
    match = (child.HasId(id) ? child : SearchTreeForId(child.Children));
    if (match != null) return match;
  }
  return null;
}

// Then...
{
  node = SearchTreeForId(SorcerersCave.theCave.Parties, id);
  if (node != null) generateInterface(...);
}
于 2013-06-25T05:37:40.157 回答
0

使用辅助方法进行深度优先搜索。

private Interface IndexObject
{
    // Interface will be used in dfsList
    public int getIndex();
}

private Interface ListObject extends IndexObject
{
    // For classes with sublists
    public ArrayList<IndexObject> getList();
}

public void search(int index) {
    Object found = dfsList(parties, index);
}

// Helper method
public Object dfsList(ArrayList<IndexObject> aList, int index) {
    for (IndexObject obj : aList) {
        if (obj.getIndex() == index) {
            return obj;
        }
        else if (obj instanceof ListObject) {
            IndexObject found = dfsList(obj.getList(), index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}
于 2013-06-25T05:58:50.857 回答
0

由于您的入口点是 Cave 对象，因此可以考虑制作一个唯一的字符串，例如表示整个 Cave 对象（Cave、Part、Creatures、Treasures、Artifacts）的主键，例如连接您要搜索的那些字段，例如如果您想按索引 3 搜索工件，您可以创建一个字符串，例如

C-P-C-T/A

其中每个字母代表“this”类中的唯一索引，所以在这种情况下它可能像

3-4-32-A3

其中 3 代表第 3 个洞穴，4 代表第 4 方....直到 A3 代表第 3 个神器。

希望您找到比这更好的解决方案，如果请分享。

于 2018-05-06T19:52:06.127 回答