1

在 Cormen 的作者之一的书中，异或链表存在一个有趣的问题。

我举了一个将项目添加到异或链表的例子。

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 = (plistNode) ((int) pNext-> ptrdiff
                               ^ (Int) pCurrent
                               ^ (Int) pNew);

在我看来应该有类似的东西

pNext-> ptrdiff = New Xor pNext[next]

谢谢你的好答案。抱歉我的愚蠢问题，为什么在第一行使用pNext-> ptrdiff（pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew 在此）。乍一看，似乎当pCurrent <====> pNew <====> pNext <====> (NextNode to pNext)pCurrent 与pNext-> ptrdiff.

4

1 回答 1

1

A<===>B<====>C 的异或链表逻辑

B 应该包含 A XOR C

现在 ，

1>较早：pCurrent<====>pNext<====>（NextNode 到 pNext）

所以，pNext->ptrdiff = pCurrent XOR (NextNode to pNext)

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]

于 2013-06-02T15:09:05.597 回答