algorithm - 通过后备数组中的索引交换双向链表中的项目

Question

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

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

一些节点参与双向链表，_pData!=nullptr 用于此类节点。还有一个虚拟头节点，其中 _pNext 指向列表的开头，_pPrev 指向结尾。该列表以仅包含此头节点开始，并且永远不应将其从列表中删除。

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

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

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

一个问题是当节点 i 和 j 彼此相邻时的极端情况。另一个问题是天真的代码涉及很多if(检查每个节点的_pData==nullptr并以不同方式处理3种情况，并检查是否节点彼此相邻)，从而变得低效。

如何高效地做到这一点？

这是我目前在 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);

Answer 1

• 两个节点的节点内容可以互换，不改变它们的含义；只有他们的地址会改变
• 由于地址已经改变，对这两个节点的所有引用也必须改变，包括节点内部恰好指向这两个节点之一的指针。

这是先交换后修复 (TM) 方法的说明。它的主要功绩是避免了所有极端情况。它确实假设了一个格式良好的 LL ，并且忽略了“in_use”条件(恕我直言，该条件与 LL 交换问题正交)

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

---

已编辑(现在它真的有效了!)

---

#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\n", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p\n", 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\n", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %d\n", ptr, ptr->prev, ptr->next, ptr->val);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %d\n", 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 列表和广告免费 列表。

---

#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\n", nfix);
for(ifix=0; ifix < nfix; ifix++) {
        fprintf(stderr, "%p --> %p\n", 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\n", msg);
ptr = &example.head;
printf("Head: %p {%p,%p} %s\n", ptr, ptr->prev, ptr->next, ptr->payload);
ptr = &example.free;
printf("Free: %p {%p,%p} %s\n", ptr, ptr->prev, ptr->next, ptr->payload);

for (i=0; i < MAXN; i++) {
        ptr = example.nodes+i;
        printf("# %u # %p {%p,%p} %s\n", 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;
}