0

我的意思是说：

假设您输入了成对的字符/字符串：

x y
a b
b x

每个左手对象映射到右手对象作为祖先。所以，假设我然后输入一组新的数据对。这一次，我想查找输入的第一个对象是否是输入的第二个对象的祖先（根据我使用第一组输入构建的地图）。

例如，假设我输入：

a y

程序应该告诉我 a 实际上是 y 的祖先。它不必显示路线，只需简单的“是”或“否”。a 是祖先，因为它映射到 b，b 映射到 x，x 映射到 y。

a - b - x - y

有人能解释一下这样的东西是如何存储和构造的吗？我玩过 BFS，但无法弄清楚如何正确映射第一个输入数据。特别是，我如何确保正确映射后代？就像，我应该以某种方式认识到键'b'也是'a'的后代。这是在读取输入时完成的吗？在 BFS 期间？请帮忙。我真的需要理解这一点，因为这是我一直在努力解决的问题。我会欣赏 Java 中数据结构的实际示例，而不仅仅是指向 BFS 算法的链接。相信我，我都读过了。也许我对 BFS 的想法甚至是错误的。

我正在使用 ArrayLists 的 HashMap 来存储第一个输入数据。因此，即使 LHS 相等，我也正确地将右侧字符串映射到左侧字符串。我只是不知道如何添加未明确添加但隐含的后代。

4

2 回答 2

0

我认为您最好的选择是链接列表。您可以在列表中搜索 a。然后从 a 到 b、b 到 x 和 x 到 y 遍历父链接。如果您用尽列表但没有找到 y ，那么您就知道没有祖先关系。

这里有很多链表示例（创建自己的以及使用 java.util.LinkedList

或者，也许只是让您的对象实现一个接口，该接口定义了一个类似 getParent() 的方法，该方法返回一个公共类型或接口，如果不存在父级，则返回 null。然后将对象放入列表中。搜索 a 然后跟随父对象引用，直到您命中 null。如果您在那之前没有找到有问题的祖先，那么答案是否定的。

于 2013-05-01T03:05:51.743 回答
0

我认为可以根据父母名单坚持使用您的孩子地图。您只需要一个递归函数来查找父母是否已经是祖先。看下面的代码。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AncestorTracker {

    private final Map<String, List<String>> childToParentMappings = new HashMap<String, List<String>>();

    public void addChildParentMapping(String child, String parent) {
        List<String> existingParents = childToParentMappings.get(child);
        if (existingParents == null) {
            existingParents = new ArrayList<String>();
            childToParentMappings.put(child, existingParents);
        }
        if (!existingParents.contains(parent)) {
            existingParents.add(parent);
        }
    }

    public boolean isAncestor(String child, String ancestor) {
        boolean result = false;

        if (childToParentMappings.containsKey(child)) {
            List<String> immedidateParents = childToParentMappings.get(child);
            if (immedidateParents.contains(ancestor)) {
                result = true;
            } else {
                for (String immediateParent : immedidateParents) {
                    if (isAncestor(child, immediateParent)) {
                        result = true;
                        break;
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        AncestorTracker ancestorTracker = new AncestorTracker();
        String[][] pairs = { {"x", "y"}, {"a", "b"}, {"b", "x"}, {"a", "y"} };

        for (String[] aPair : pairs) {
            String child = aPair[1];
            String parent = aPair[0];

            if (ancestorTracker.isAncestor(child, parent)) {
                System.out.println(child + " is already a decendent of " + parent); 
            } else {
                ancestorTracker.addChildParentMapping(child, parent);
            }
        }
    }
}
于 2013-05-01T06:43:43.780 回答