0

重複を許可し、挿入順序を維持するデータ構造を探しているので、次のファイル入力が与えられた場合:a + a + b = c

したがって、正しく分割されると、次のようになります。{a,+,a,+,b,=,c}

このデータ構造は、正しい順序での削除と挿入も可能にする必要があります。たとえば、aをdに置き換えた場合、 を取得する必要があります{d,+,d,+,b,=,c}。

最後に、構造は、特定のアイテムの前後にあるアイテムを認識できる必要があります。たとえば、 =の直前の項目はbで、直後の項目はcです。

リストには重複が許可されており、一部のリストでは挿入順序が維持されていることは承知していますが、どのリストが私の目標を達成できるかはわかりません。

上記のすべてを達成する構造を認識している場合は、そのような構造を作成するための構文を提供してください。

よろしく

4

2 に答える 2

3

サンプルの使用法については、次を参照してくださいArrayList。http://www.java2s.com/Code/Java/Collections-Data-Structure/BidirectionalTraversalwithListIterator.htmListIterator

于 2013-01-23T11:03:36.523 に答える
1

List単純な Java実装の 1 つを使用しないために (置換中に項目を検索するためにリスト全体を反復処理することを避けたいため)、パフォーマンスが十分に重要であると仮定すると、 2 つのデータ構造を維持する必要があります。トークンの順序の 1 つと、交換のためのトークン位置のインデックスとしての 1 つ。

したがって、次のようなものです（コンパイラを介してこれを実行していないため、タイプミスが予想されます）：

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 に答える