Doppi elenchi collegati in C++

Question

Ho un incarico che richiede l'implementazione di una classe di elenchi doppiamente collegata. Per qualche motivo hanno definito il nodo struct come segue:

struct node { 
    node *next; 
    node *prev; 
    T  *o; 
}; 

Mi sembra che sarebbe stato molto più facile di scrivere la classe se la 'data' membro struct non fosse un puntatore. Inutile dire che non posso cambiarlo, quindi dovrò solo aggirarlo. Ho provato l'attuazione del metodo che aggiunge un elemento all'inizio della lista come segue:

template <typename T> 
void Dlist<T>::insertFront(T *o) { 
    node *np = new node; 
    T val = *o; 

    np->o = &val; 
    np->prev = NULL; 
    np->next = first; 

    if (!isEmpty()) { 
     first->prev = np; 
    } else { 
     last = np; 
    } 
    first = np; 
} 

durante l'utilizzo di ddd per eseguire il debug ho capito che tutto funziona bene la prima volta che si inserisce un numero, ma la seconda volta tutto diventa avvitato poiché non appena si imposta 'val' sul nuovo elemento esso "sovrascrive" il primo poiché è stato utilizzato l'indirizzo di memoria di val. Ho provato a fare altre cose come invece di avere la variabile 'val' facendo quanto segue:

T *valp = new T; 
T val; 
valp = &val; 
val = *o; 

np->o = valp 

Anche questo non sembra funzionare. Penso che sia perché è solo una forma più complicata di ciò che ho fatto sopra solo con una perdita di memoria aggiuntiva :)

Qualsiasi idea/puntatore nella giusta direzione sarebbe ottima.

Answer 1

il T val creato è una variabile automatica. Il tuo errore sta memorizzando l'indirizzo in quella variabile stack.

Si dovrebbe utilizzare new per allocare spazio nell'heap, come si sospetta, ma il puntatore dei dati deve puntare direttamente all'indirizzo restituito da new.

Il tuo errore nel suo ultimo tentativo è qui:

valp = &val; 

State cambiando valp a punto da qualche altra parte (l'indirizzo della val), quando si sta probabilmente tentando di dati copia di val, non il suo indirizzo.

I dati trasmessi alla funzione devono essere copiati nella nuova memoria in cui punti valp.

Answer 2

T val = *o; 

    np->o = &val; 

Questa parte è sospetta. Il suggerimento è che la memoria allocata sullo stack in una funzione non sarà disponibile una volta che la funzione non rientra nello scope.

Answer 3

Non credo che si dovrebbe fare questo:

T val = *o; 

Dal momento che il membro o nella struttura nodo è un puntatore, e il parametro da insertFront è anche un puntatore, il vostro istruttore probabilmente intende per voi prendere il puntatore che ti è stato dato e memorizzarlo nell'elenco, non creare una copia dell'oggetto e memorizzare un puntatore. È sufficiente memorizzare il puntatore o passato in insertFront come membro del nodo o e si dovrebbe essere OK.

Answer 4

Il codice non si adatta la tua definizione di node - in node si sta definendo un membro data, ma nel codice che si sta utilizzando, invece o.

In ogni caso, è necessario eseguire due allocazioni dinamiche per aggiungere ciascun nodo, uno per il nodo stesso e uno per l'oggetto dati a cui verrà indirizzato. Quando si assegna l'oggetto dati, è possibile assegnare il valore restituito da new direttamente al puntatore nel nodo. Quindi dovrai copiare l'oggetto dati il ​​cui puntatore è stato passato nell'oggetto dati appena assegnato, a cui punta il puntatore nel nodo.

Answer 5

Si si pensa il carico utile del puntatore è inopportuno. Ma forse l'elenco è destinato a essere utilizzato per creare un collegamento in cima oggetti esistenti, come in:

struct A { int i; }; 
A as[10] = { 1,2,3,4,5,6,7,8,9,10 }; 

LinkedList primes_in_my_data; 
insertFront(primes_in_my_data, &as[1]); 
insertFront(primes_in_my_data, &as[2]); 
insertFront(primes_in_my_data, &as[3]); 
insertFront(primes_in_my_data, &as[5]); 
insertFront(primes_in_my_data, &as[7]); 

// now I have a linked list of primes, and caused no extra memory allocation 
// (except for the list overhead)