XOR 링크 된 목록에 대한 C 코드

Question

XOR linked list과 그 작업을 구현하려고했지만 올바르게 수행하지 못했습니다.

XOR 링크 목록에 주소 작업이 포함되어 있기 때문에 C로 구현할 수 있습니까?

실제 작업 코드가 있으면 감사하게 생각합니다.

Answer 1

이전에 보지 못한 흥미로운 아이디어입니다. 오늘날의 상당히 풍부한 메모리로 인해, 모든 플랫폼이 메모리와 동일하지는 않지만 약간의 이득을 위해 많은 복잡성이있는 것처럼 보입니다. 편집 실제 작업을하는 동안 내 마음이 계속해서 떠돌 았기 때문에 새 노드를 만들고 주어진 끝에 놓는 기능을 추가했습니다. 더 예뻐. 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); 


} 

Answer 2

XOR 링크 목록에 주소 연산이 포함되어 있으므로 C로 구현할 수 있습니까 ??

예 그렇습니다. 주소는 포인터이고 포인터는 숫자 *이며 숫자는 XOR을 허용합니다 (즉 a^b).

Look up이 수행되고 구현을 수행 할 수 있어야합니다.

적어도 숫자로 생각할 수 있습니다. 명시 적 캐스트가 필요할 수도 있습니다.

Answer 3

포인터에 대해 xor 연산을 수행 할 수 없기 때문에 xor을 수행하고 결과를 오른쪽 포인터 유형으로 변환하려면 주소를 정수 유형으로 변환해야합니다. intptr_t 및 <stdint.h>에서 uintptr_t :

은 내가 아는 한 C99은과 (백 = 점점 원래 포인터) 정의 행동 포인터에서 변환을 보장하는 두 개의 정수 유형이 있습니다. 두 유형 모두 선택 사항이므로 구현에 포함되지 않을 수 있습니다. 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); 

내가 void *에 추가 캐스트가 필요하다 100 % 확실하지 않다, 사람이 그렇지 않은 경우에 저를 수정하시기 바랍니다. (u)intptr_t 유형에 대한 자세한 내용은 C99 표준의 §7.18.1.4를 참조하십시오.