XOR链表的C代码

I have been trying to implement XOR linked list and its operations but I have not been able to do it properly.

我一直在尝试实现XOR链接列表及其操作,但我无法正确执行。

Is it possible to implement it in C since XOR link list involves operations on addresses?

是否可以在C中实现它,因为XOR链接列表涉及对地址的操作?

I would be very thankful if some actual working code is given.

如果给出一些实际的工作代码,我将非常感激。

3 个解决方案

#1

That's an interesting idea that I have not seen before. With today's fairly abundant memory, it seems like a lot of complexity for little gain (although not all platforms are flush with memory). Edit While doing my real work, my mind kept drifting back to it, so I added the function to create the new node and put it on the given end. Prettier now. It's rather cool that both the addnode and traverse functions are symmetrical. Neither needs to know the direction. Just give it one end of the list and they operate correctly.

这是一个我以前从未见过的有趣想法。凭借今天相当丰富的内存,它看起来很复杂,但收益微不足道(尽管并非所有平台都充满了内存)。编辑在完成我的实际工作时,我的思绪一直在回归,所以我添加了创建新节点并将其放在给定端的功能。现在更漂亮。 addnode和traverse函数都是对称的,这很酷。两者都不需要知道方向。只需给它列表的一端,它们就能正常运行。

And based on Darron's comment (thanks), I changed the int to intptr_t for portability.

根据Darron的评论(谢谢),我将int更改为intptr_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 );


}

#2

Since you cannot perform xor operations on pointers, you will have to convert the addresses to an integer type to perform the xor and convert the result back to to right pointer type.

由于无法对指针执行xor操作,因此必须将地址转换为整数类型以执行xor并将结果转换回右指针类型。

As far as I know C99 has only two integer types that guarantee conversion to and from pointers with defined behaviour (= getting your original pointer back): intptr_t and uintptr_t from <stdint.h>. Note that both types are optional, so your implementation might not have them.

据我所知,C99只有两种整数类型,可以保证与具有已定义行为的指针之间的转换(=将原始指针返回):来自的intptr_t和uintptr_t。请注意,这两种类型都是可选的,因此您的实现可能没有它们。

Example of conversions, assuming a and b are valid pointers to struct node:

转换示例,假设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);

I'm not 100% sure the extra casts to void * are needed, somebody please correct me if they are not. See §7.18.1.4 of the C99 standard for more information on the (u)intptr_t types.

我不是百分之百确定需要额外的演员来取消*,如果他们不是,请有人纠正我。有关(u)intptr_t类型的更多信息,请参见C99标准的第7.18.1.4节。

#3

Is it possible to implement it in C since XOR link list involves operations on addresses??

是否可以在C中实现它,因为XOR链接列表涉及对地址的操作?

Yes it is. Addresses are pointers, pointers are numbers* and numbers allow XOR (i.e. a ^ b).

是的。地址是指针,指针是数字*,数字允许XOR(即a ^ b)。

Look up what is done, and you should be able to do the implementation.

查看已完成的工作,您应该能够执行。

*At least, you can think of them as numbers - explicit casts might be required though.

*至少,您可以将它们视为数字 - 但可能需要显式强制转换。

#1