1

In Data Structures and Algorithms Made Easy, struct of memory efficient memory list given as follows,

struct LinkNode
{
 int data;
 struct LinkNode* ptrdiff;
}

In ptrdiff, there will be xoring of previous and next node is done. For example, previous node have address 100 and next node address is 500.

So, in ptrdiff address will be 400. Now how it is possible to move to next or previous node (as we do in doubly link list), just by knowing xoring of their addresses?

Am I missing any step here?

4

2 回答 2

5

第一个节点没有前一个节点，最后一个节点没有下一个节点......所以将第一个节点之前的节点的地址和最后一个节点之后的节点的地址视为0。这足以开始遍历，并且当你遍历你总是手头有前一个节点的地址，这样你就可以确定后一个节点的地址。这是一个遍历这样一个列表并打印数据的示例......将第一个或最后一个节点的地址传递给 printxorlist，它将向前或向后打印它：

void printxorlist(struct LinkNode* node)
{
    struct LinkNode* prev = NULL;
    while (node)
    {
        printf("%d\n", node->data);
        struct LinkNode* next = (struct LinkNode*)((intptr_t)node->ptrdiff ^ (intptr_t)prev);
        prev = node;
        node = next;
    }
}

请注意，我们必须强制转换，node->ptrdiff因为它实际上没有正确的类型。最好正确声明它：

struct LinkNode
{
    int data;
    intptr_t ptrdiff;
}

然后

void printxorlist(struct LinkNode* node)
{
    struct LinkNode* prev = NULL;
    while (node)
    {
        printf("%d\n", node->data);
        struct LinkNode* next = (struct LinkNode*)(node->ptrdiff ^ (intptr_t)prev);
        prev = node;
        node = next;
    }
}
于 2014-09-13T05:49:39.767 回答
0

在这种类型的链表中，不能从任意节点的地址开始遍历。因为您需要一些关于前任地址或后继地址的额外信息。但是从第一个节点（前任地址=0，因为不是任何前任）或最后一个节点（后继地址=0，因为不是任何后继）是可能的。

于 2014-09-13T16:37:21.970 回答