通过它们在后备数组中的索引交换双向链表中的项目 [英] Swap items in doubly-linked list by their indices in the backing array

问题描述

我有以下类型的对象数组:

I have an array of objects of the following type:

struct Node {
    Node *_pPrev, *_pNext;
    double *_pData;
};

一些节点参与一个双向链表，对于这样的节点，_pData!=nullptr.还有一个虚拟头节点，_pNext 指向列表的开头，_pPrev 指向列表的结尾.列表开始时只包含这个头节点，永远不应该从列表中删除它.

Some of the nodes participate in a doubly-linked list, with _pData!=nullptr for such nodes. There is also a dummy head node with _pNext pointing to the beginning of the list, and _pPrev pointing to the end. The list starts with containing only this head node, and it should be never removed from the list.

双向链表由一个数组支持，初始大小等于列表中的最大节点数.

The doubly-linked list is backed by an array, with initial size equal to the maximum number of nodes in the list.

struct Example {
    Node _nodes[MAXN];
    Node _head;
};

现在我想对这个数据结构执行以下操作:给定 2 个索引 i 和 j 到 _nodes 数组，交换数组中的节点，但保留它们在双向链表中的位置.这个操作需要更新_nodes[i]._pPrev->_pNext、_nodes[i]._pNext->_pPrev，节点j也一样代码>.

Now I want to perform the following operation on this data structure: given 2 indices i and j to the _nodes array, swap the nodes in the array, but preserve their positions in the doubly-linked list. This operation needs updating _nodes[i]._pPrev->_pNext, _nodes[i]._pNext->_pPrev and the same for node j.

一个问题是节点 i 和 j 彼此相邻时的极端情况.另一个问题是，原始代码涉及很多 if(检查每个节点的 _pData==nullptr 并以不同方式处理 3 种情况，并检查是否节点彼此相邻)，因此效率低下.

One problem is the corner cases when nodes i and j are next to each other. Another problem is that the naive code involves a lot of ifs (to check for _pData==nullptr for each node and handle the 3 cases differently, and to check whether the nodes are next to each other), thus becoming inefficient.

如何有效地做到这一点?

How to do it efficiently?

这是我目前在 C++ 中的内容:

Here is what I have so far in C++:

assert(i!=j);
Node &chI = _nodes[i];
Node &chJ = _nodes[j];
switch (((chI._pData == nullptr) ? 0 : 1) | ((chJ._pData == nullptr) ? 0 : 2)) {
case 3:
    if (chI._pNext == &chJ) {
        chI._pPrev->_pNext = &chJ;
        chJ._pNext->_pPrev = &chI;
        chI._pNext = &chI;
        chJ._pPrev = &chJ;
    }
    else if (chJ._pNext == &chI) {
        chJ._pPrev->_pNext = &chI;
        chI._pNext->_pPrev = &chJ;
        chJ._pNext = &chJ;
        chI._pPrev = &chI;
    } else {
        chI._pNext->_pPrev = &chJ;
        chJ._pNext->_pPrev = &chI;
        chI._pPrev->_pNext = &chJ;
        chJ._pPrev->_pNext = &chI;
    }
    break;
case 2:
    chJ._pNext->_pPrev = &chI;
    chJ._pPrev->_pNext = &chI;
    break;
case 1:
    chI._pNext->_pPrev = &chJ;
    chI._pPrev->_pNext = &chJ;
    break;
default:
    return; // no need to swap because both are not in the doubly-linked list
}
std::swap(chI, chJ);

推荐答案

• 两个节点的节点内容可以互换，不改变意义；只有他们的地址会改变
• 由于地址已更改，因此所有对两个节点的引用也必须更改，包括碰巧指向两个节点之一的节点内部的指针.
• The node contents of two nodes can be swapped, without changing their meaning; only their addresses will change
• since the addresses have changed, all references to the two nodes must change, too, including pointers inside the nodes that happen to point to one of the two nodes.

这是交换第一次的说明 &稍后修复 (TM) 方法.它的主要壮举是它避免了所有的极端情况.它确实假设了一个格式良好的 LL ，并且忽略了in_use"条件(恕我直言与 LL-swap-problem 正交)

Here is an illustration of the swap first & fixup later (TM) method. Its major feat is that it avoids all the corner cases. It does assume a well-formed LL , and it ignores the "in_use" condition (which IMHO is orthogonal to the LL-swap-problem)

注意我做了一些重命名，添加了测试数据，并转换为纯 C.

Note I did a bit of renaming, added test data, and converted to Pure C.

已编辑(现在它确实有效！)

EDITED (now it actually works!)

#include <stdio.h>

struct Node {
    struct Node *prev, *next;
    // double *_pData;
    int val;
        };

#define MAXN 5
struct Example {
    struct Node head;
    struct Node nodes[MAXN];
        };

        /* sample data */
struct Example example = {
        { &example.nodes[4] , &example.nodes[0] , -1} // Head
        ,{ { &example.head , &example.nodes[1] , 0}
        , { &example.nodes[0] , &example.nodes[2] , 1}
        , { &example.nodes[1] , &example.nodes[3] , 2}
        , { &example.nodes[2] , &example.nodes[4] , 3}
        , { &example.nodes[3] , &example.head , 4}
        }
        };

void swapit( unsigned one, unsigned two)
{
struct Node tmp, *ptr1, *ptr2;
        /* *unique* array of pointers-to pointer
         * to fixup all the references to the two moved nodes
         */
struct Node **fixlist[8];
unsigned nfix = 0;
unsigned ifix;

        /* Ugly macro to add entries to the list of fixups */

#define add_fixup(pp) fixlist[nfix++] = (pp)

ptr1 = &example.nodes[one];
ptr2 = &example.nodes[two];

        /* Add pointers to some of the 8 possible pointers to the fixup-array.
        ** If the {prev,next} pointers do not point to {ptr1,ptr2}
        ** we do NOT need to fix them up.
        */
if (ptr1->next == ptr2) add_fixup(&ptr2->next); // need &ptr2->next here (instead of ptr1)
else    add_fixup(&ptr1->next->prev);
if (ptr1->prev == ptr2) add_fixup(&ptr2->prev); // , because pointer swap takes place AFTER the object swap
else    add_fixup(&ptr1->prev->next);
if (ptr2->next == ptr1) add_fixup(&ptr1->next);
else    add_fixup(&ptr2->next->prev);
if (ptr2->prev == ptr1) add_fixup(&ptr1->prev);
else    add_fixup(&ptr2->prev->next);

fprintf(stderr,"Nfix=%u
", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p
", fixlist[ifix], *fixlist[ifix]);
        }

        /* Perform the rough swap */
tmp = example.nodes[one];
example.nodes[one] = example.nodes[two];
example.nodes[two] = tmp;

        /* Fixup the pointers, but only if they happen to point at one of the two nodes */
for(ifix=0; ifix < nfix; ifix++) {
        if (*fixlist[ifix] == ptr1) *fixlist[ifix] = ptr2;
        else *fixlist[ifix] = ptr1;
        }
}

void dumpit(char *msg)
{
struct Node *ptr;
int i;

printf("%s
", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %d
", ptr, ptr->prev, ptr->next, ptr->val);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %d
", i, ptr, ptr->prev, ptr->next, ptr->val);
        }
}

int main(void)
{
dumpit("Original");

swapit(1,2);
dumpit("After swap(1,2)");

swapit(0,1);
dumpit("After swap(0,1)");

swapit(0,2);
dumpit("After swap(0,2)");

swapit(0,4);
dumpit("After swap(0,4)");

return 0;
}

<小时>

为了说明我们可以忽略in_use条件这一事实，这里有一个新版本，在同一个数组中存在两个双链表.这可以是in_use 列表和广告免费 列表.

---

To illustrate the fact that we can ignore the in_use condition, here is a new version, with two double linked lists present in the same array. This could be an in_use list and ad free list.

#include <stdio.h>

struct Node {
    struct Node *prev, *next;
    // double *_pData;
    // int val;
    char * payload;
        };

#define MAXN 8
struct Example {
    struct Node head;
    struct Node free; /* freelist */
    struct Node nodes[MAXN];
        };

        /* sample data */
struct Example example = {
        { &example.nodes[5] , &example.nodes[0] , ""} /* Head */
        , { &example.nodes[6] , &example.nodes[2] , ""} /* freelist */

/* 0 */ ,{ { &example.head , &example.nodes[1] , "zero"}
        , { &example.nodes[0] , &example.nodes[3] , "one"}
        , { &example.free , &example.nodes[6] , NULL }
        , { &example.nodes[1] , &example.nodes[4] , "two"}
/* 4 */ , { &example.nodes[3] , &example.nodes[5] , "three"}
        , { &example.nodes[4] , &example.head , "four"}
        , { &example.nodes[2] , &example.free , NULL}
        , { &example.nodes[7] , &example.nodes[7] , "OMG"} /* self referenced */
          }
        };

void swapit( unsigned one, unsigned two)
{
struct Node tmp, *ptr1, *ptr2;
        /* *unique* array of pointers-to pointer
         * to fixup all the references to the two moved nodes
         */
struct Node **fixlist[4];
unsigned nfix = 0;
unsigned ifix;

        /* Ugly macro to add entries to the list of fixups */

#define add_fixup(pp) fixlist[nfix++] = (pp)

ptr1 = &example.nodes[one];
ptr2 = &example.nodes[two];

        /* Add pointers to some of the 4 possible pointers to the fixup-array.
        ** If the {prev,next} pointers do not point to {ptr1,ptr2}
        ** we do NOT need to fix them up.
        ** Note: we do not need the tests (.payload == NULL) if the linked lists
        ** are disjunct (such as: a free list and an active list)
        */
if (1||ptr1->payload) { /* This is on purpose: always True */
        if (ptr1->next == ptr2) add_fixup(&ptr2->next); // need &ptr2->next here (instead of ptr1)
        else    add_fixup(&ptr1->next->prev);
        if (ptr1->prev == ptr2) add_fixup(&ptr2->prev); // , because pointer swap takes place AFTER the object swap
        else    add_fixup(&ptr1->prev->next);
        }
if (1||ptr2->payload) { /* Ditto */
        if (ptr2->next == ptr1) add_fixup(&ptr1->next);
        else    add_fixup(&ptr2->next->prev);
        if (ptr2->prev == ptr1) add_fixup(&ptr1->prev);
        else    add_fixup(&ptr2->prev->next);
        }

fprintf(stderr,"Nfix=%u
", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p
", fixlist[ifix], *fixlist[ifix]);
        }

        /* Perform the rough swap */
tmp = example.nodes[one];
example.nodes[one] = example.nodes[two];
example.nodes[two] = tmp;

        /* Fixup the pointers, but only if they happen to point at one of the two nodes */
for(ifix=0; ifix < nfix; ifix++) {
        if (*fixlist[ifix] == ptr1) *fixlist[ifix] = ptr2;
        else *fixlist[ifix] = ptr1;
        }
}

void dumpit(char *msg)
{
struct Node *ptr;
int i;

printf("%s
", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %s
", ptr, ptr->prev, ptr->next, ptr->payload);
ptr = &example.free;
printf("Free: %p {%p,%p} %s
", ptr, ptr->prev, ptr->next, ptr->payload);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %s
", i, ptr, ptr->prev, ptr->next, ptr->payload);
        }
}

int main(void)
{
dumpit("Original");

swapit(1,2); /* these are on different lists */
dumpit("After swap(1,2)");

swapit(0,1);
dumpit("After swap(0,1)");

swapit(0,2);
dumpit("After swap(0,2)");

swapit(0,4);
dumpit("After swap(0,4)");

swapit(2,5); /* these are on different lists */
dumpit("After swap(2,5)");

return 0;
}

这篇关于通过它们在后备数组中的索引交换双向链表中的项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！