C语言异或指针双向链表

一般的双向链表节点中包含两个指针，分别指向前驱和后继。异或指针双向链表的节点只有一个“指针”，这个指针是另外两个指针的“异或”值，并利用以下运算得到其前驱和后继的指针：

a^(a^b)=b

(a^b)^b=a

在C语言中，可以先把指针转换为无符号整型数然后进行异或，另外还应保存指向链表头尾节点的指针。

按照这种思路，节点中的这一个指针还可以是“加法”值，或者其他指针运算得到的值。如果是加法，可以利用以下运算得到其前驱和后继指针：

(x+y)-x=y

(x+y)-y=x

需要注意的是，这样的“加法”运算或“异或”运算都是针对指针的值本身的，即指针转换为无符号整型后的运算。不能跟指针运算（如两个指针相减）混淆。

异或指针双向链表的建立、遍历等参考如下实现。

//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;
}