Głęboka kopia struktury wykresu

Question

Mam strukturę wykresu w C i chcę wykonać jej głęboką kopię (w tym węzły i krawędzie).

struktura wygląda następująco:

struct li_list { 
    struct li_node n; 
}; 

struct li_node { 
    struct li_node *next, *prev; 
}; 

struct gr_graph { 
    struct li_list nodes; 
    int nodecount; 
}; 

struct gr_node { 
    struct li_node node; 
    struct gr_graph *graph; 
    int pred_count, succ_count; 
    struct li_list pred, succ; 
}; 

struct gr_edge { 
    struct li_node succ, pred; 
    struct gr_node *from, *to; 
    unsigned long marks; 
}; 

te kodowanym nie istnieją jako siebie, ale „dziedziczona” w innej struktury, tak:

struct ex_node { 
    struct gr_node _; // "Superclass" 
    int id; 
    struct ex_node *union_find_parent; 
    ... 
} 

Czy istnieje eleganckie rozwiązanie tworzenie głębokiej kopii takiej struktury, w tym aktualizowanie odniesień do kopii?

Uwaga: Członkowie zagnieżdżonych kodowanym nie wskazują na struktury korzenia zawiera, ale ich powiązanej zagnieżdżonej struktury (np ex_node._.pred.n.next wskazuje na ex_edge._.pred). Oznacza to arytmetykę żmudnego wskaźnika, gdy trzeba je zaktualizować.

Moje rozwiązanie do tej pory jest

1. Memcopy wszystkie kodowanym
2. iterację wszystkich kopiach
3. połączeń grono makr dla wszystkich pól, które zawierają odniesienia (Z powodu braku RTTI w C, pewnie nie przyjdzie około tego)
4. makra używać
   • offsetof obliczyć adres struktury korzenia
   • Odzyskaj adres skopiowany odpowiednik
   • offsetof aby punkt wskaźnik do prawidłowego zagnieżdżonej struktury

Czy istnieje łatwiejszy sposób to zrobić? Obawiam się również, że zapomniałem dodać makro, gdy dodam więcej pól.

Answer 1

Nie sądzę, że można zrobić głęboki egzemplarz per se, ponieważ wskaźniki będą miały adres pamięci przypisany do wskaźników, najlepszym sposobem, w jaki mogę myśleć o głębokiej kopii jest po prostu przydzielenie nowego wykresu strukturyzuj i kopiuj dane (nie wskaźniki) i stwórz je stamtąd przez malloc nowych wskaźników i dopasuj wskaźniki w strukturze ex_node. To byłoby bardziej szczegółowe rozwiązanie ...

Mam nadzieję, że to pomoże, Pozdrawiam, Tom.

Answer 2

Brzmi ok. My $ ,02:

• Nie wiem, dlaczego trzeba zarówno li_list i li_node. Co więcej, nie potrzebujesz członka danych dla li_node?
• Ogólna struktura wygląda nieco skomplikowane (oczywiście, nie wiem swoje wymagania) i pachnie C++ styl projektowania (pardon, jeśli się mylę)
• memcpy nie jest wymagane. Wystarczy proste zadanie.
• Definiowanie elementu wskaźnik funkcji dla każdej struktury z członkami wskaźnik, tak że można zrobić:

Więc:

struct foo { 
    int datum; 
    int *p; 
    foo_copy pfoo; 
}; 

typedef void (*foo_copy)(const struct foo *src, struct foo *dst); 

void foo_cp(const struct foo *src, struct foo *dst) 
{ 
    *dst = *src; // copy non-pointer data 
    dst->p = malloc(sizeof *dst->p); 
    dst->p = *src->p; 
} 


// somewhere else 
struct foo s; 
// initalize 
struct foo *t = malloc(sizeof *t); 
s.copy(&s, &t); 

i zagnieżdżone typy wywołać odpowiednie metody członkiem kopiowania ...

Answer 3

zapisz wszystkie struktury i utwórz posortowaną listę, w której każdy wpis zawiera adres oryginalnej struktury i adres kopii struktury.

Teraz przejrzyj wszystkie kopie. Dla każdego wskaźnika zmienne we wszystkich skopiowanych strukturach wyszukaj wskaźnik na posortowanej liście i zastąp go adresem jego kopii.

Answer 4

Tak, istnieje eleganckie rozwiązanie wykorzystujące drzewa opasujące i wzór dekoratora.

-Pierwsze, zbuduj drzewo opinające wykres. Możesz użyć DFS (Głębokie pierwsze wyszukiwanie) lub BFS (pierwsze wyszukiwanie szerokości), aby to osiągnąć. Użyj wzoru dekoratora, aby każdy z odwiedzonych węzłów miał niepowtarzalny identyfikator.

-Dalej (lub w tym samym czasie) przemierzać drzewo rozpinające od początku do końca i rozpocząć budowanie swojego drugiego drzewa poprzez przydzielenie nowych węzłów i podłączenie krawędzie, które tworzą drzewa rozpinającego.

-Wreszcie, jeszcze jeden przechodzą przez drzewa rozpinającego, a za pomocą zsynchronizowanych identyfikatory, podłącz pozostałe brakujące krawędzie w nowym wykresie, tak aby dopasować łączność starego wykresu. (np. Jeśli węzeł5 na wykresie 1 ma krawędzie łączące się z węzłem 7 i węzłem 11, wówczas korzysta z kolejności wykresu 2 do połączenia węzła5 z węzłem7 i 11.)