数据结构中的一道关于异或指针的题目

复习考研中。。数据结构后道关于异或指针的题目。
我把我的理解表达出来，不知道对不对，麻烦各位指正，谢谢～

比如说一个链表，mostleft和mostright分别指向链表头尾节点。
每个节点有两个域，一个存信息，另个存前驱和后继的异或值，如：
第一个节点 1 n+2   (1..n为链表各个节点代号，+暂时代替异或运算，不知道怎么打)
第二个节点 2 1+3
第三个节点 3 2+4
...
第n个节点  n （n-1)+(1)


假如我做遍历，从1开始，即从mostleft开始，
那么1的后继就为 n+(n+2)； //因为n我们知道，即为mostright，n+2是存在1号节点里的。（异或性质）
那么i的后继就为(i-1)+((i-1)+(i+1))；//同理，我们已经从1遍历到i节点，可以将（i-1）地址存下，
                                      而((i-1)+(i+1))就是在i里存着的。
....

n的前驱应为((n-1)+(1))+(1)；//因为1我们知道，即为mostleft，((n-1)+(1))是存在n号节点里的。（异或性质）


不知道是否表达清楚，见谅。

5 个解决方案

#1

sf

#2

..

#3

就是知道前驱可以算出后继
知道后继可以算出前驱

#4

引用 3 楼 hai040 的回复:

就是知道前驱可以算出后继 
知道后继可以算出前驱

那意思是我的理解还比较靠谱？

#5

这个是传说中的“异或指针双向链表”，也就是说：一个结构体只要两个域，一个放数据，一个放前驱后继的异或值（注意：指针和指针异或后依然是指针）；这样，如果当前某个指针ptr指向第i个结构体node[i]：
1) node[i].xor= node[i-1].addr + node[i+1].addr;
2) node[i].addr = ptr;
这里假设xor为异或值，addr为节点实际地址。
3) 另外，node[1].addr, node[n].addr 为已知。

那么:
由于node[1].xor = node[n].addr + node[2].addr，则
    node[n].addr + node[1].xor = node[n].addr + (node[n].addr + node[2].addr) = node[2].addr;
提示一下，上述能够成立是因为我们有：节点n的地址（node[n].addr）；节点1的地址node[1].addr得到的node[1].xor；

再进一步，如果我们知道，node[i-2].addr, node[i-1].addr，则：
    node[i-2].addr + node[i-1].xor = node[i-2].addr + (node[i-2].addr + node[i].addr) = node[i].addr;

差不多就这样了，如果还不明白，那么放弃考研吧。