当前位置：文江博客话题详情

将 DFA 实现为链表的算法

发布于 2024-10-29 22:56:54 字数 39 浏览 3 评论 0原文

我想知道如何在 C/C++/Java 中将 DFA 实现为链表。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

南冥有猫 2024-11-05 22:56:54

由于每个状态都可以有多个分支，因此您可能需要多个链表。这意味着，每个状态都有一个由 n 个链表组成的数组。所以它更像是一个有循环的树结构，而不是一个简单的链表。

回复收藏 0 原文

已下线请稍等 2024-11-05 22:56:54

这绝对是可能的，但效率极低。您要做的就是简单地将所有状态存储在链接列表中，然后每个状态都需要保留一个转换表。转换表看起来像这样：

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

其中字母表是 {a,b}，2 和 5 是存储在链表中位置 2 和 5 的状态。正如我所说，这绝对不是您想要实施 DFA 的方式，但这是可能的。

This is definitely possible, but would be grossly inefficient. What you would do is to simply store all your states in a link list, and then each state would need to keep a transition table. The transition table would look something like:

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

where your alphabet is {a,b}, and 2 and 5 are the states stored at position 2 and 5 in the linked list. As I said, this is definitely NOT how you would want to implement a DFA, but it is possible.

回复收藏 0 原文

記憶穿過時間隧道 2024-11-05 22:56:54

我想到的第一件事是，

创建一个名为 state 的类/结构，其中包含两个数组组件。一种用于可以到达我们州的州，另一种用于从我们州可以到达的州。
然后创建一个链表，其元素是您的状态。

这是我对这个类的实现

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

        //methods of this state

}

The first thing that came up in my mind is that,

create a class/struct called state with two array components. one for the states that can reach our state and one for the ones that are reachable from our state.
Then create a linked list whose elements are your states.

here's my implementation of this class

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

        //methods of this state

}

回复收藏 0 原文

╄→承喏 2024-11-05 22:56:54

单链表无法有效地表示DFA。您可以将 DFA 视为有向加权图数据结构，因为状态是顶点，转移是边，转移符号是权重。实现图结构有两种主要方法。

i) 邻接表：它基本上有 V（顶点数）链表。每个链接列表包含与相应顶点有边的顶点。如果我们有顶点 (1,2,3) 和边 (1,2),(1,3),(2,1),(2,3),(3, 3) 对应的邻接列表为：

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

ii) 邻接矩阵：它是一个VxV矩阵，其中(i,j)处的每个条目表示从i到j的一条边。上面的相同示例表示如下（1 表示有边缘，0 表示没有边缘）：

但是您必须对这些进行少量更改，因为您的图是加权的。

对于列表实现，您可以将链接列表中的顶点更改为包含顶点和连接这些顶点的边的权重的结构。

对于矩阵实现，您可以将权重直接放入矩阵中而不是 0,1 值。

如果您不想处理图形类的实现，可以使用像 Boost Graph Library 这样的库，它包含两个实现以及所有重要的图形算法 DFS 到 Dijkstra 的最短路径算法。您可以从 http://www.boost 查找它.org/doc/libs/1_47_0/libs/graph/doc/index.html。

Single linked list couldn't represent the DFA efficiently. You can think DFA as a directed weighted graph data structure as states are vertices, transitions are edges, transition symbols are weights. There are two main method to implement graph structure.

i) Adjacency list: It basically has V(Number of vertices) linked lists. Each link list contains vertices which has edge to corresponding vertex. If we have vertices (1,2,3) and edges (1,2),(1,3),(2,1),(2,3),(3,3) corresponding adjanceny list is:

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

ii) Adjacency matrix: It is a VxV matrix with every entry at (i,j) symbolize an edge from i to j. The same example above represented like(1 means there is edge, 0 mean there is not):

But you must make little changes to these because your graph is weighted.

For list implementation you can change vertices in linklist to a struct which contains vertex and the weight of the edge connecting these vertices.

For matrix implementation you can place the weights directly into matrix instead of 0,1 values.

If you don't want to deal with the implementation of graph class there is libraries like Boost Graph Library which contains the two implementation and all the important graph algorithms DFS to Dijkstra's shortest path algorithm. You can look it up from http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/index.html.

回复收藏 0 原文

~没有更多了~