0

我从一个编程任务开始。我必须根据图表设计一个 DFA。这是我用于它的数据结构：

typedef struct n{
    struct n *next[255];           //pointer to the next state. Value is NULL if no transition for the input character( denoted by their ascii value)
    bool start_state;
    bool end_state;
}node;

现在我已经准备好了一个基于 DFA 图形的结构。我需要在几个地方使用这个 DFA；DFA 将在这几个地方中的每一个中进行修改。但我希望将未修改的 DFA 传递给这些不同的函数。一种方法是创建此 DFA 的副本。这样做最优雅的方法是什么？所以它们都被初始化为 NULL 值或指向另一个状态的指针。

注意： 我希望在被调用函数中创建副本，即我传递 DFA，被调用函数创建其副本并对其进行操作。这样，我原来的 DFA 就不会被吓倒。

更多注意事项： 从 DFA 的每个节点，我可以有一条有向边将它与另一条边连接起来，如果在输入字母出现时发生转换，c那么state->next[c]将有一个指向下一个节点的指针。next数组的几个元素可能为 NULL。修改 NFA 意味着添加新节点以及更改现有节点。

4

2 回答 2

2

如果您在每次调用时都需要一个私有副本，并且由于这是一个链接的数据结构，我认为没有办法避免复制整个图（除非性能非常关键，可能对某些子分支进行写时复制，但复杂性很大，出现错误的可能性也很大）。

如果这是 c++，您可以在复制构造函数中完成此操作，但在 c 中您只需要在每个函数上进行克隆。一种方法是克隆整个结构（就像 Mark 建议的那样） - 这非常复杂，因为您需要跟踪图中的循环/后边缘（表现为指向您不想重新分配但重用的先前访问节点的指针'已经分配）。

如果您愿意更改数据结构，另一种方法是使用数组 - 将所有节点保存在单个节点类型的数组中。如果您知道限制，数组应该足够大以容纳所有节点，或者只是重新分配它以根据需要增加，并且每个“指针”都被一个简单的索引替换。

构建这个数组是不同的——不是分配一个新节点，而是使用下一个可用的索引（把它放在一边），或者如果你要动态添加/删除节点，你可以保留一个队列/堆栈" free" 索引（在开头填充 1..N，并在您需要新位置或即将释放旧位置时弹出/推送。

好处是复制会快得多，因为所有链接都是相对于数组的实例，你只需复制一块连续的内存（memcpy 现在可以正常工作）

另一个好处是使用这种数据结构的性能应该优于链接的，因为内存访问在空间上是接近的并且易于预取。

于 2013-09-10T19:01:53.253 回答
0

您需要编写一个递归函数来访问所有节点，并使用一个全局字典来跟踪从源图节点到复制的图节点的映射。这个字典基本上是一个将旧指针映射到新指针的表。

这是想法。我还没有编译它或调试它...

struct {
 node* existing;
 node* copy
} dictionary[MAX_NODES] = {0};

node* do_copy(node* existing) 
{
  node* copy;
  int i;
  for(i=0;dictionary[i].existing;i++) {
    if (dictionary[i].existing == existing) return dictionary[i].copy;
  }
  copy = (node*)malloc(sizeof(node));
  dictionary[i].existing = existing;
  dictionary[i].copy = copy;

  for(int j=0;j<255 && existing->next[j];j++) {
      node* child = do_copy(existing->next[j]);
      copy->next[j] = child;
  }
  copy->end_state = existing->end_state;
  copy->start_start = existing->start_state;
  return copy;

 }
于 2013-09-10T18:52:08.777 回答