12

XORリンクリストとその操作を実装しようとしましたが、正しく実行できませんでした。

XORリンクリストにはアドレスの操作が含まれるため、Cで実装することは可能ですか？

実際に動作するコードが提供されれば、とてもありがたいです。

4

3 に答える 3

19

それは私が前に見たことがない興味深い考えです。今日のかなり豊富なメモリでは、わずかな利益のために多くの複雑さのように見えます（ただし、すべてのプラットフォームがメモリと同じ高さであるとは限りません）。 編集実際の作業をしている間、頭がどんどん戻ってきたので、新しいノードを作成して指定された端に配置する関数を追加しました。今よりきれい。addnode関数とtraverse関数の両方が対称的であるのはかなりクールです。どちらも方向を知る必要はありません。リストの一方の端を指定するだけで、正しく動作します。

そして、Darronのコメント（ありがとう）に基づいてintptr_t、移植性のためにintをに変更しました。

#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 );


}
于 2010-08-20T15:39:47.103 に答える
9

ポインターに対してxor演算を実行できないため、xorを実行し、結果を右ポインター型に戻すには、アドレスを整数型に変換する必要があります。

私の知る限り、C99には、定義された動作（=元のポインターを取り戻す）を持つポインターとの間の変換を保証する2つの整数型しかありintptr_tませuintptr_tん<stdint.h>。どちらのタイプもオプションであるため、実装にそれらがない場合があることに注意してください。

aとが：bへの有効なポインタであると仮定した場合の変換の例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);

追加のキャストが必要かどうかは100％void *わかりません。そうでない場合は、誰かが修正してください。タイプの詳細については、C99標準の§7.18.1.4を参照してください(u)intptr_t。

于 2010-08-20T15:36:24.063 に答える
5

XORリンクリストにはアドレスの操作が含まれるため、Cで実装することは可能ですか？

はい、そうです。アドレスはポインタであり、ポインタは数値*であり、数値はXOR（つまりa ^ b）を許可します。

何が行われたかを調べれば、実装ができるはずです。

*少なくとも、それらは数字と考えることができますが、明示的なキャストが必要になる場合があります。

于 2010-08-20T14:49:06.870 に答える