Создайте новую копию структуры данных на основе указателей

Question

Я начал с назначения программирования. Мне пришлось составлять 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 означает как добавление новых узлов, так и изменение существующих узлов.

Answer 1

Вам нужно будет написать рекурсивную функцию, которая посещает все узлы, с глобальным словарем, который отслеживает отображение из узлов исходного графа в скопированные узлы графа. Этот словарь будет в основном таблицей, которая отображает старые указатели на новые указатели.

Вот эта идея. Я не скомпилирован или отладкой его ...

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; 

} 

Answer 2

Если вам нужен частный экземпляр при каждом вызове, и так как это связано структура данных, я не вижу никакого способа, чтобы избежать копирования весь граф (кроме возможно, сделать копию на запись в некоторые дочерние ветви, если производительность критическая, но сложность значительна, а также вероятность ошибок).

Если бы это было C++, вы могли бы сделать это в конструкторе копирования, но в c вам просто нужно клонировать каждую функцию. Один из способов - клонировать всю структуру (как и Mark Mark) - это довольно сложно, так как вам нужно отслеживать циклы/обратные грани в графике (которые проявляются как указатели на ранее посещаемые узлы, которые вы не хотите перераспределять, но повторно используете то, что вы уже выделено).

Другой способ, если вы хотите изменить структуру данных, заключается в работе с массивами - сохранить все узлы в одном массиве узлов типа. Массив должен быть достаточно большим для размещения всех узлов, если вы знаете предел, или просто перераспределите его для увеличения по требованию, и каждый «указатель» заменяется простым индексом.

Построение этого массива отличается: вместо того, чтобы раскладывать новый узел, используйте следующий доступный индекс (держите его сбоку), или если вы собираетесь добавлять/удалять узлы «на лету», вы можете сохранить очередь/stack из «свободных» индексов (заполняется в начале с 1..N и pop/push там всякий раз, когда вам нужно новое место или около того, чтобы освободить старый.

Достоинства является то, что копирование будет намного быстрее, так как все ссылки по отношению к экземпляру массива, вы просто скопировать кусок непрерывной памяти (тетср будет работать нормально)

Другое Достоинством является то, что производительность использования этой структуры данных должна быть выше связанной, поскольку доступ к памяти пространственно близок и легко предзачитывается.