0

我正在寻找一种允许重复并维护插入顺序的数据结构，以便如果给定的文件输入为：a + a + b = c

因此，一旦正确拆分，我将得到：{a,+,a,+,b,=,c}

此数据结构还需要允许以正确的顺序删除和插入，例如，如果我将a替换为d，我应该得到{d,+,d,+,b,=,c}.

最后，该结构还必须能够识别哪些项目在某个项目之前或之后。例如，直接在=之前的项目是b并且直接在之后是c。

我知道列表允许重复，并且一些列表保持插入顺序，但我不确定哪个可以让我实现我的目标。

如果您知道可以实现上述所有功能的结构，请提供创建此类结构的语法。

问候

4

2 回答 2

3

似乎可以满足您的要求，对于示例用法，请参阅：ArrayListhttp ://www.java2s.com/Code/Java/Collections-Data-Structure/BidirectionalTraversalwithListIterator.htmListIterator

于 2013-01-23T11:03:36.523 回答
1

假设性能足以引起关注，不使用简单的 JavaList实现之一（因为您想避免在替换期间迭代整个列表以搜索项目），那么您将需要维护两个数据结构，一个用于跟踪令牌的顺序和一个作为用于替换的令牌位置的索引。

所以，类似（我没有通过编译器运行它，所以期待拼写错误）：

class TokenList
{
  List<String> tokens;
  Map<String,List<Integer>> tokenIndexes= new HashMap<String,List<Integer>>();

  TokenList(Iterable<String> tokens)
  {
    this.tokens = new ArrayList<String>(tokens);
    for (int i = 0; i < this.tokens.size(); i++)
    {
      String token = this.tokens.get(i);
      List<Integer> indexes = tokenIndexes.get(token);
      if (indexes == null)
      {
        index = new List<Integer>();
        tokenIndexes.put(token, indexes);
      }
      indexes.add(index);
    }
  }

  void replace(String oldToken, String newToken)
  {
    List<Integer> indexes = tokenIndexes.remove(oldToken);
    if (indexes == null)
      throw new IllegalArgumentException("token doesn't exist: " + oldToken);
    for (int index : indexes)
      tokens.set(i, newToken);
    tokenIndexes.put(newToken, indexes);
  }
}

这种结构假设令牌一旦创建就不会改变索引（tokenIndex地图需要重新创建，这是一个相对昂贵的操作）。

于 2013-01-23T11:40:21.923 回答