C-Code für XOR-verknüpft Liste

Question

Ich habe versucht, XOR verknüpfte Liste und seine Operationen zu implementieren, aber ich habe nicht gewesen die Lage, es richtig zu machen.

Ist es möglich, sie in C zu implementieren, da XOR-Verknüpfung Liste beinhaltet Operationen auf Adressen?

Ich wäre sehr dankbar, wenn einiger tatsächlicher Arbeitscode gegeben ist.

Answer 1

Das ist eine interessante Idee, dass ich noch nicht gesehen habe. Mit dem heutigen ziemlich reichlich Speicher, scheint es, wie viel Aufwand für wenig Gewinn (wenn auch nicht alle Plattformen mit Speicher bündig sind). Bearbeiten Während meine eigentliche Arbeit zu tun, mein Geist zurück, um es gehalten treiben, so dass ich die Funktion hinzugefügt, um den neuen Knoten zu erstellen und es auf dem gegebenen Ende zu setzen. Prettier jetzt. Es ist ziemlich cool, dass sowohl die addnode und Quer Funktionen symmetrisch sind. braucht weder die Richtung kennen. Probieren Sie es einfach ein Ende der Liste und sie korrekt funktionieren.

Und auf Basis von Darron Kommentar (danke), ich die int intptr_t für Portabilität geändert.

#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

Da Sie nicht xor Operationen auf Zeiger durchführen können, finden Sie die Adressen in einen Integer-Typ umwandeln müssen, um die xor durchzuführen und das Ergebnis zurück zu nach rechts Zeigertyp umwandeln.

Soweit ich weiß, C99 hat nur zwei Integer-Typen, dass Garantie Konvertierung zu und von Zeigern mit definiertem Verhalten (= ursprüngliche Zeiger zurück bekommen): intptr_t und uintptr_t von <stdint.h>. Beachten Sie, dass beide Typen sind optional, so dass Ihre Implementierung sie nicht haben könnte.

Beispiel von Umwandlungen, 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. Siehe §7.18.1.4 des C99-Standard für weitere Informationen über die (u)intptr_t Typen.

Answer 3

  

Ist es möglich, sie in C zu implementieren, da XOR-Verknüpfung Liste Operationen auf Adressen beinhaltet ??

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

Suchen was ist getan, und Sie sollten die Implementierung der Lage zu tun.

* Mindestens können Sie von ihnen als Zahlen denken -. Explizite Casts könnte jedoch erforderlich sein