C-Code für XOR verkettete Liste

Question

Ich habe versucht, XOR linked list und seine Operationen zu implementieren, aber ich war nicht in der Lage, es richtig zu machen.

Ist es möglich, es in C zu implementieren, da die XOR-Linkliste Operationen mit Adressen beinhaltet?

Ich wäre sehr dankbar, wenn einige tatsächliche Arbeitscode gegeben wird.

Answer 1

Das ist eine interessante Idee, die ich vorher nicht gesehen habe. Mit dem heutigen reichlich vorhandenen Speicher scheint es eine Menge Komplexität für wenig Gewinn zu sein (obwohl nicht alle Plattformen mit dem Speicher bündig sind). Bearbeiten Während ich meine eigentliche Arbeit machte, driftete mein Geist immer wieder darauf zurück, also fügte ich die Funktion hinzu, um den neuen Knoten zu erstellen und ihn auf das gegebene Ende zu setzen. Jetzt schöner. Es ist ziemlich cool, dass sowohl die addnode- als auch die traverse-Funktion symmetrisch sind. Beide müssen die Richtung nicht kennen. Geben Sie es nur ein Ende der Liste und sie funktionieren korrekt.

Und basierend auf Darrons Kommentar (danke), änderte ich die Int intptr_t für die Portabilität.

#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

Ist es möglich, es in C zu implementieren, da die XOR-Linkliste Operationen mit Adressen beinhaltet ??

Ja ist es. Adressen sind Zeiger, Zeiger sind Zahlen * und Zahlen erlauben XOR (d.h. a^b).

Look upwas ist getan, und Sie sollten in der Lage sein, die Implementierung zu tun.

* Zumindest können Sie sie als Zahlen betrachten - explizite Umwandlungen sind jedoch möglicherweise erforderlich.

Answer 3

Da Sie keine XOR-Operationen auf Zeigern ausführen können, müssen Sie die Adressen in einen Integer-Typ konvertieren, um den Xor auszuführen und das Ergebnis zurück in den rechten Zeigertyp zu konvertieren.

Soweit ich weiß, C99 hat nur zwei Integer-Typen, die Umwandlung zu und von Zeigern mit definiertem Verhalten (= immer Ihre ursprünglichen Zeigern zurück) garantieren: intptr_t und uintptr_t von <stdint.h>. Beachten Sie, dass beide Typen optional sind, sodass Ihre Implementierung diese möglicherweise nicht enthält.

Beispiel für Konvertierungen, unter der Annahme, a und b gelten Zeiger auf 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); 

Ich bin nicht 100% sicher, dass die zusätzlichen Würfe zu void * benötigt werden, jemand bitte korrigieren Sie mich, wenn sie nicht sind. Weitere Informationen zu den Typen (u)intptr_t finden Sie in Abschnitt 7.18.1.4 des C99-Standards.