xor 연결된 목록에 항목을 추가하는 방법은 무엇입니까?

Question

저자 중 한 명이 Cormen 인 한 책에서 xor linked list의 흥미로운 문제가 있습니다.

나는이 항목을 xor 연결 목록에 추가하는 예제를 사용했습니다.

void insertAfter(plistNode pNew, T theElm) 
{ 
    plistNode pPrev, pCurrent, pNext; 
    pPrev = NULL; 
    pCurrent = pStart; 

    while (pCurrent) { 
     pNext = NextNode(pCurrent, pPrev); 
     if (pCurrent->elm == theElm) { 
     /* traversal is done */ 
     if (pNext) { 
      /* fix the existing next node */ 
      pNext->ptrdiff = 
       (plistNode) ((int) pNext->ptrdiff 
         ^(int) pCurrent 
         ^(int) pNew); 

      /* fix the current node */ 
      pCurrent->ptrdiff = 
       (plistNode) ((int) pNew^(int) pNext 
         ^(int) pCurrent->ptrdiff); 

      /* fix the new node */ 
      pNew->ptrdiff = 
       (plistNode) ((int) pCurrent 
         ^(int) pNext); 
     break; 
     } 
     pPrev = pCurrent; 
     pCurrent = pNext; 
    } 
} 

나는이 있어야 좋은 답변을

pNext-> ptrdiff = New Xor pNext[next] 

감사 같은 것을 제 생각에는이 코드

pNext-> ptrdiff = (plistNode) ((int) pNext-> ptrdiff 
          ^(Int) pCurrent 
          ^(Int) pNew); 

을 이해하지 않습니다. 죄송합니다 내 바보 같은 질문에, 왜 첫 번째 라인에 사용 pNext-> ptrdiff (pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew이 있음). 언뜻 보면 pNext-> ptrdiff과 관련이없는 pCurrent <====> pNew <====> pNext <====> (NextNode to pNext) pCurrent와 같은 것으로 보입니다. pCurrent <하십시오 < ===> B < ====> C

XOR C 자

을 함유한다

B,

1>에 대한 이전

Answer 1

XOR 논리 링크리스트 ===> pNext < ===> (pNext에 NextNode) (pNext에 NextNode)

그래서 pNext-> ptrdiff = pCurrent XOR

,

2> pCurrent 후 pNew를 삽입 한 후, 당신은해야합니다

pCurrent < ====> pNew < ====> pNext < ====> (NextNode pNext에) 그래서

, pNext-> ptrdiff 같아야

pNext-> ptrdiff = pNew XOR

그래서 코드가 달성된다 (NextNode pNext에) 그와

pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew 
       = pCurrent XOR (NextNode to pNext) XOR pCurrent XOR pNew [ replaced pNext->ptrdiff from 1 ] 
       = pCurrent XOR pCurrent XOR (NextNode to pNext) XOR pNew [ XOR is commutative ] 
       = 0 XOR (NextNode to pNext) XOR pNew [ A XOR A = NULL ] 
       = (NextNode to pNext) XOR pNew   [ 0 XOR A = A ] 

기대했던 것입니다. [2]