异或链表
 | 此條目没有列出任何参考或来源。 (2014年8月5日) |
异或链表（英語：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); } C++ 範例
[编辑]- XORList: Efficient C++ Linked List (MIT License) （页面存档备份，存于互联网档案馆） - A GitHub repository providing an efficient implementation of XOR linked lists in C++.