发布于 2010-08-20 23:39:47
这是一个有趣的想法,我以前从未见过。有了今天相当丰富的内存,它看起来很复杂,但收益很小(尽管并不是所有的平台都有充足的内存)。编辑在做实际工作的时候,我的大脑一直在想它,所以我添加了创建新节点的功能,并将其放在给定的一端。现在更漂亮了。addnode和traverse函数都是对称的,这是相当酷的。两者都不需要知道方向。只要把它放在列表的一端,它们就能正常运行。
基于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 );
}发布于 2010-08-20 23:36:24
由于不能对指针执行xor操作,因此必须将地址转换为整数类型才能执行xor操作,并将结果转换回右指针类型。
据我所知,C99只有两个整数类型可以保证在具有定义行为(=获取原始指针)的指针之间进行转换:来自<stdint.h>的intptr_t和uintptr_t。请注意,这两种类型都是可选的,因此您的实现可能没有这两种类型。
转换示例,假设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 *进行额外的强制转换,如果不需要,请有人纠正我。有关(u)intptr_t类型的更多信息,请参阅C99标准的§7.18.1.4。
发布于 2010-08-20 22:49:07
由于异或链表涉及对地址的操作,它可以用C语言实现吗?
是的。地址是指针,指针是数字*,数字允许异或(即a ^ b)。
已经做了什么,你应该能够进行实现。
*至少,您可以将它们视为数字-尽管可能需要显式强制转换。
https://stackoverflow.com/questions/3531972
复制相似问题