异或运算特性 a ^ b = c 则 c ^ b = a , c ^ a = b， 双向链表需要两个指针，一个指向前一个结点，一个指向后一个结点， 异或双向链表只用一个指针，该指针等于 前后两两个结点指针的异或的结果，这样节省了空间，但增加了计算。
一般的双向链表节点中包含两个指针，分别指向前驱和后继。异或指针双向链表的节点只有一个“指针”，这个指针是另外两个指针的“异或”值，并利用以下运算得到其前驱和后继的指针：
a^(a^b)=b
(a^b)^b=a
在C语言中，可以先把指针转换为无符号整型数然后进行异或，另外还应保存指向链表头尾节点的指针。
按照这种思路，节点中的这一个指针还可以是“加法”值，或者其他指针运算得到的值。如果是加法，可以利用以下运算得到其前驱和后继指针：
(x+y)-x=y
(x+y)-y=x
需要注意的是，这样的“加法”运算或“异或”运算都是针对指针的值本身的，即指针转换为无符号整型后的运算。不能跟指针运算（如两个指针相减）混淆。
异或指针双向链表的建立、遍历等参考如下实现。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
//main.cpp
#include <iostream>
using namespace std;
#include "xorp.h"
int main(int argc, char *argv[])
{
XorLinkedList list;
char value[NUM+1]="abcdef";
if(!initList(&list, value)){
cout<<"initList error\n";
exit(-1);
}
traverse(&list, 'l');//从左到右的遍历
traverse(&list, 'r');//从右到左的遍历
destroy(&list);
system("PAUSE");
return true;
}
//xorp.h
#define NUM 6
typedef struct XorNode{
char data;
struct XorNode *LRPtr;
}XorNode, *XorPointer;
typedef struct{
XorPointer l, r;//分别指向双向链表的左端和右端
}XorLinkedList;
//异或运算
XorPointer XorP(XorPointer p, XorPointer q);
//建立双向链表
bool initList(XorLinkedList *pList, char value[NUM]);
//销毁链表
void destroy(XorLinkedList *pList);
//遍历
void traverse(const XorLinkedList *pList, char direction);
//xorp.cpp
#include <iostream>
#include "xorp.h"
using namespace std;
//异或运算
XorPointer XorP(XorPointer p, XorPointer q){
return (XorPointer)((unsigned)p^(unsigned)q);
}
//建立异或指针双向链表
bool initList(XorLinkedList *pList, char value[NUM]){
if(NUM<1)
return false;
XorPointer pl, p, pr;
int i=0;
p=(XorPointer)malloc(sizeof(XorPointer));
if(!p)
return false;
pl=p;
p->data=value[i++];
pList->l=p;
pr=NULL;
for(; i<NUM; ++i){
pr=(XorPointer)malloc(sizeof(XorPointer));
if(!p)
return false;
pr->data=value[i];
p->LRPtr=XorP(pl, pr);
pl=p;
p=pr;
}
pList->r=p;
if(pr!=NULL)
p->LRPtr=XorP(pl, pr);
return true;
}
//销毁异或指针双向链表
void destroy(XorLinkedList *pList){
XorPointer m, n, p;
XorPointer head=pList->l;
XorPointer tail=pList->r;
m=n=head;
cout<<"free:";
while(n!=tail){
p=XorP(m, n->LRPtr);
cout<<n->data<<" ";
free(n);//释放n指向的内容，但n的值本身不变
m=n;
n=p;
}
cout<<n->data<<" ";
free(n);
cout<<endl;
}
//遍历异或指针双向链表
void traverse(const XorLinkedList *pList, char direction){
XorPointer m, n, p;
XorPointer head=(direction=='l')?pList->l:pList->r;
XorPointer tail=(direction=='r')?pList->l:pList->r;
cout<<"traverse:";
m=n=head;
cout<<m->data;
while(n!=tail){
p=XorP(m, n->LRPtr);
cout<<p->data;
m=n;
n=p;
}
cout<<endl;
}
|
