XOR 链表的 C 代码 [英] C code for XOR linked list

问题描述

我一直在尝试实现 XOR 链表 及其操作，但我一直无法实现正确地做到这一点.

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

是否可以用 C 语言实现，因为 XOR 链接列表涉及对地址的操作?

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

如果能提供一些实际的工作代码，我将不胜感激.

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

推荐答案

这是我以前从未见过的有趣想法.有了今天相当丰富的内存，似乎有很多复杂性却收效甚微(尽管并非所有平台都充满了内存).编辑 在做我真正的工作时，我的思绪不断地回到它上面，所以我添加了创建新节点的功能并将其放在给定的一端.现在更漂亮了.addnode 和 traverse 函数都是对称的，这很酷.两者都不需要知道方向.只需给它列表的一端，它们就可以正常运行.

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.

并且根据 Darron 的评论(谢谢)，为了可移植性，我将 int 更改为 intptr_t.

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

#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
", 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:
" );
   traverse( head );
   printf( "Backwards:
" );
   traverse( tail );


}

这篇关于XOR 链表的 C 代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！