異或鍊表

異或鍊表（英語：XOR linked list）是數據結構裡面的一種鏈式存儲結構。

基本介紹

• 中文名：異或鍊表
• 外文名：XOR linked list
• 屬性：鏈式存儲結構
• 作用：降低空間複雜度
• 學科：數據結構
• 領域：數據結構

簡介

異或鍊表（英語：XOR linked list）是數據結構裡面的一種鏈式存儲結構，可以在降低空間複雜度的情況下達到和雙向鍊表一樣的目的，使得在任何一個結點都能方便地訪問它的前驅結點和後繼結點。

概述

普通雙向鍊表的每個結點有三個域 ，分別存儲著前一個結點的地址、後一個點的地址，以及數據

...  A       B         C         D         E  ...          –>  next –>  next  –>  next  –>          <–  prev <–  prev  <–  prev  <–

異或鍊表通過異或操作（這裡用⊕表示）把前一個結點的地址和後一個結點的地址變成一個地址

 ...  A         B               C                D            E  ...          <–>  A⊕C     <->    B⊕D     <->      C⊕E  <->        link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), …

當從左往右遍歷的時候，如果當前結點是C，指針域是內容是B⊕D,通過和前一個結點B的地址做異或操作就能得到下一個結點D的地址，如此重複便能遍歷整個鍊表。

C語言示例

//異或鍊表結點結構typedef struct XorNode{    char data;    struct XorNode *LRPtr;}XorNode,*XorPointer;//異或指針雙向鍊表結構typedef struct  XorLinkedList{    XorPointer left,right;}XorLinkedList;//異或操作XorPointer xor(XorPointer a,XorPointer b){    return (XorPointer)((unsigned long)(a) ^ (unsigned long)(b));}//創建異或雙向鍊表void createXorLinkedList(XorLinkedList *list){    char ch;    XorPointer lastNode=NULL;    int isFirstNode=1;    while ((ch=getchar())!='\n') {        XorPointer newNode=(XorPointer)malloc(sizeof(XorNode));        newNode->data=ch;        newNode->LRPtr=NULL;        if (lastNode) {            newNode->LRPtr=xor(lastNode, NULL);            lastNode->LRPtr=xor(xor(lastNode->LRPtr,NULL), newNode);        }        lastNode=newNode;        if (isFirstNode) {            isFirstNode=0;            list->left=newNode;        }    }    list->right=lastNode;}//按任意方向依次輸出各結點值void print(XorPointer a,XorPointer b){    XorPointer nullFirst=a==NULL?a:b;    XorPointer nonNullFirst=a!=NULL?a:b;    XorPointer tmp=NULL;    do{        printf("%c ",nonNullFirst->data);        tmp=nonNullFirst;        nonNullFirst=xor(nullFirst, nonNullFirst->LRPtr);        nullFirst=tmp;    }while(nonNullFirst!=NULL);}//在第i個結點之前插入一個結點void XorLinkedListInsert(XorLinkedList *list,int pos,char data){    XorPointer node=list->left,tmp=NULL;    XorPointer last=NULL;    XorPointer newNode=NULL;    int i=1;    while (i<pos && node!=NULL) {        tmp=node;        node=xor(last, node->LRPtr);        last=tmp;        i++;    }    newNode=(XorPointer)malloc(sizeof(XorNode));    newNode->data=data;    newNode->LRPtr=xor(last, node);    if (node!=NULL) {        node->LRPtr=xor(newNode, xor(last, node->LRPtr));    }    if (last!=NULL) {        last->LRPtr=xor(xor(last->LRPtr, node), newNode);    }    if (pos==1) {        list->left=newNode;    }}//刪除第i個結點void XorLinkedListDelete(XorLinkedList *list,int pos){    XorPointer node=list->left,last=NULL,next=NULL,tmp=NULL;    int i=1;    while (i<pos && node!=NULL) {        i++;        tmp=node;        node=xor(last, node->LRPtr);        last=tmp;    }    next=xor(last, node->LRPtr);    if (last!=NULL) {        last->LRPtr=xor(xor(last->LRPtr, node), next);    }    if (next!=NULL) {        next->LRPtr=xor(last, xor(node, next->LRPtr));    }else{        list->right=last;//刪除了最後一個結點    }    if (pos==1) {        list->left=next;    }    free(node);}