C-код для связанного списка XOR
Я пытался реализовать связанный список XOR и его операции, но я не смог это сделать правильно.
Возможно ли реализовать его в C, поскольку список ссылок XOR включает операции с адресами?
Я был бы очень благодарен, если бы был дан какой-то фактический рабочий код.
3 ответа
Это интересная идея, которую я не видел раньше. При сегодняшнем изобилии памяти это кажется большой сложностью для небольшого выигрыша (хотя не все платформы обладают достаточным количеством памяти). Edit Пока я занимался реальной работой, мои мысли постоянно возвращались к этому, поэтому я добавил функцию для создания нового узла и поместил его на заданный конец. Теперь красивее. Очень здорово, что функции addnode и traverse симметричны. Ни одной из них не нужно знать направление. Просто укажите один конец списка, и они работают правильно.
И, основываясь на комментарии Даррона (спасибо), я изменил 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 );
}
Поскольку вы не можете выполнять операции xor с указателями, вам придется преобразовать адреса в целочисленный тип, чтобы выполнить xor и преобразовать результат обратно в тип правого указателя.
Насколько мне известно, в C99 есть только два целочисленных типа, которые гарантируют преобразование в указатели и обратно с определенным поведением (= возвращение исходного указателя): intptr_t и uintptr_t из . Обратите внимание, что оба типа являются необязательными, поэтому в вашей реализации их может не быть.
Пример преобразований, предполагая, что a и b являются действительными указателями на узел структуры :
#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 * необходимы, поправьте меня, если это не так. См. §7.18.1.4 стандарта C99 для получения дополнительной информации о типах (u) intptr_t .
Можно ли реализовать это на C, поскольку список ссылок XOR включает операции с адресами ??
Да, это так. Адреса - это указатели, указатели - это числа *, а числа допускают операцию XOR (т.е. a ^ b ).
Посмотрите , что сделано , и вы сможете выполнить реализацию.
* По крайней мере, вы можете думать о них как о числах - хотя может потребоваться явное приведение типов.