1

C/C++/Java で DFA をリンク リストとして実装する方法を知りたいです。

4

4 に答える 4

3

どの州にも複数の分岐がある可能性があるため、おそらく複数のリンク リストが必要です。つまり、すべての州には n 個のリンクされたリストの配列があります。そのため、単純なリンク リストというよりも、サイクルのあるツリー構造に似ています。

于 2011-04-05T08:18:11.403 に答える
0

これは間違いなく可能ですが、非常に非効率的です。あなたがすることは、すべての状態をリンク リストに格納するだけで、各状態は遷移テーブルを保持する必要があります。遷移表は次のようになります。

'a' -> 2
'b' -> 5

ここで、アルファベットは{a,b}で、2 と 5 は連結リストの 2 と 5 の位置に格納されている状態です。私が言ったように、これはDFAを実装したい方法ではありませんが、可能です。

于 2011-06-16T09:10:29.453 に答える
0

最初に頭に浮かんだのは、

2 つの配列コンポーネントを持つstateという名前のクラス/構造体を作成します。1 つは私たちの状態に到達できる状態用で、もう 1 つは私たちの状態から到達可能な状態用です。次に、要素が状態であるリンク リストを作成します。

これがこのクラスの私の実装です

class state
{
    private:
        string stateName;
        vector<state> states_before_me;
        vector<state> states_after_me;
        state* next;

        //methods of this state

}
于 2011-07-22T10:51:40.953 に答える
0

単一の連結リストでは、DFA を効率的に表すことができませんでした。状態は頂点、遷移はエッジ、遷移シンボルは重みであるため、DFA は有向加重グラフ データ構造と考えることができます。グラフ構造を実装するには、主に 2 つの方法があります。

i) 隣接リスト: 基本的に V(頂点の数) のリンクされたリストを持ちます。各リンク リストには、対応する頂点へのエッジを持つ頂点が含まれます。対応する頂点(1,2,3)とエッジがある場合、(1,2),(1,3),(2,1),(2,3),(3,3)隣接リストは次のようになります。

1->2->3
2->1->3
3->3

ii) 隣接行列: (i,j) のすべてのエントリが i から j へのエッジを表す VxV 行列です。上記の同じ例は次のように表されます (1 はエッジがあることを意味し、0 はエッジがないことを意味します)。

  1 2 3
1 0 1 1
2 1 0 1
3 0 0 1

ただし、グラフは重み付けされているため、これらを少し変更する必要があります。

リストの実装では、linklist の頂点を、頂点とこれらの頂点を接続するエッジの重みを含む構造体に変更できます。

行列の実装では、重みを 0,1 値の代わりに行列に直接配置できます。

グラフ クラスの実装を扱いたくない場合は、Boost Graph Library のようなライブラリがあり、2 つの実装とすべての重要なグラフ アルゴリズム DFS から Dijkstra の最短パス アルゴリズムが含まれています。http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/index.htmlから調べることができます。

于 2011-07-25T06:23:05.973 に答える