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 回答