Codice C per XOR elenco collegato

Question

Ho cercato di implementare XOR linked list e le sue operazioni, ma non sono stato in grado di farlo correttamente.

È possibile implementarlo in C poiché la lista di collegamenti XOR comporta operazioni sugli indirizzi?

Sarei molto grato se viene fornito un codice di lavoro effettivo.

Answer 1

Questa è un'idea interessante che non ho mai visto prima. Con la memoria abbastanza abbondante di oggi, sembra un sacco di complessità per poco guadagno (sebbene non tutte le piattaforme siano a filo con la memoria). Modifica Mentre svolgevo il mio vero lavoro, la mia mente continuava ad andare alla deriva, così ho aggiunto la funzione per creare il nuovo nodo e metterlo sulla data fine. Più carina ora. È piuttosto interessante che entrambe le funzioni addnode e traverse siano simmetriche. Nessuno dei due ha bisogno di sapere la direzione. Basta dare una fine alla lista e funzionano correttamente.

E in base al commento di Darron (grazie), ho modificato l'int a intptr_t per la portabilità.

#include <stdio.h> 
#include <malloc.h> 
#include <stdint.h> // gcc needs this for intptr_t. 

typedef struct xorll { 
    int value; 
    struct xorll *np; 
} xorll; 


// traverse the list given either the head or the tail 
void traverse(xorll *start) // point to head or tail 
{ 
    xorll *prev, *cur; 

    cur = prev = start; 
    while (cur) 
     { 
     printf("value = %d\n", cur->value); 
     if (cur->np == cur) 
     // done 
     break; 
     if (cur == prev) 
     cur = cur->np; // start of list 
     else { 
     xorll *save = cur; 
     cur = (xorll*)((uintptr_t)prev^(uintptr_t)cur->np); 
     prev = save; 
     } 
     } 
} 

// create a new node adding it to the given end and return it 
xorll* newnode(xorll *prev, xorll *cur, int value) 
{ 
    xorll *next; 

    next = (xorll*)malloc(sizeof(xorll)); 
    next->value = value; 
    next->np = cur; // end node points to previous one 

    if (cur == NULL) 
     ; // very first node - we'll just return it 
    else if (prev == NULL) { 
     // this is the second node (they point at each other) 
     cur->np = next; 
     next->np = cur; 
     } 
    else { 
     // do the xor magic 
     cur->np = (xorll*)((uintptr_t)prev^(uintptr_t)next); 
     } 

    return next; 
} 



int main(int argc, char* argv[]) 
{ 
    xorll *head, *tail; 
    int value = 1; 

    // the first two nodes point at each other. Weird param calls to 
    // get the list started 
    head = tail = newnode(NULL, NULL, value++); 
    tail = newnode(NULL, tail, value++); 

    // now add a couple to the end 
    tail = newnode(tail->np, tail, value++); 
    tail = newnode(tail->np, tail, value++); 

    // this is cool - add a new head node 
    head = newnode(head->np, head, 999); 


    printf("Forwards:\n"); 
    traverse(head); 
    printf("Backwards:\n"); 
    traverse(tail); 


} 

Answer 2

È possibile implementarlo in C poiché la lista di collegamenti XOR comporta operazioni sugli indirizzi ??

Sì, lo è. Gli indirizzi sono puntatori, i puntatori sono numeri * e i numeri consentono XOR (ad esempio a^b).

Look upche cosa è e che si dovrebbe essere in grado di eseguire l'implementazione.

* Almeno, puoi pensare a loro come a numeri - potrebbero tuttavia essere necessari cast espliciti.

Answer 3

Poiché non è possibile eseguire operazioni xor sui puntatori, sarà necessario convertire gli indirizzi in un tipo intero per eseguire xor e convertire il risultato in puntatore a destra.

Per quanto ne so C99 ha solo due tipi interi che garantiscono la conversione da e puntatori con comportamento definito (= ottenere il vostro puntatore posteriore originale): intptr_t e uintptr_t da <stdint.h>. Nota che entrambi i tipi sono opzionali, quindi la tua implementazione potrebbe non averli.

Esempio di conversioni, assumendo a e b sono puntatori validi per struct node:

#include <stdint.h> 

/* creating an xor field */ 
uintptr_t x = (uintptr_t) (void *) a^(uintptr_t) (void *) b; 
/* reconstructing an address */ 
a = (void *) (x^(uintptr_t) (void *) b); 

io non sono sicuro al 100% sono necessari i calchi in più per void *, qualcuno si prega di correggermi se non lo sono. Vedere §7.18.1.4 dello standard C99 per ulteriori informazioni sui tipi (u)intptr_t.