0

I started with a programming assignment. I had to design a DFA based on graphs. Here is the data structure I used for it:

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;

Now I have a DFA graph-based structure ready with me. I need to utilize this DFA in several places; The DFA will get modified in each of these several places. But I want unmodified DFAs to be passed to these various functions. One way is to create a copy of this DFA. What is the most elegant way of doing this? So all of them are initialized either with a NULL value or some pointer to another state.

NOTE: I want the copy to be created in the called function i.e. I pass the DFA, the called function creates its copy and does operation on it. This way, my original DFA remains undeterred.

MORE NOTES: From each node of a DFA, I can have a directed edge connecting it with another edge, If the transition takes place when there the input alphabet is c then state->next[c] will have a pointer of the next node. It is possible that several elements of the next array are NULL. Modifying the NFA means both adding new nodes as well as altering the present nodes.

4

2 に答える 2

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