1

Data Structures and Algorithms Made Easyでは、struct次のように指定されたメモリ効率の高いメモリ リストについて、

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

ではptrdiff、前のノードと次のノードの xor が実行されます。たとえば、前のノードのアドレスは100で、次のノードのアドレスは500です。

したがって、ptrdiff のアドレスは400になります。アドレスの xor を知るだけで、どのようにして次または前のノードに移動できるのでしょうか (二重リンク リストで行うように)。

ここで何かステップがありませんか？

4

2 に答える 2

5

最初のノードには前のノードがなく、最後のノードには次のノードがないため、最初のノードの前のノードと最後のノードの後のノードのアドレスを 0 と考えてください。トラバーサルを開始するにはこれで十分です。 traverse では常に前のノードのアドレスを手元に持っているため、後続のノードのアドレスを決定できます。このようなリストをトラバースしてデータを出力する例を次に示します... 最初または最後のノードのアドレスを 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 に答える