交换项目通过其索引的支持数组中

Question

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

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

某些节点参与双向链表，与​​为这样的节点。还有一个虚拟头节点，其中_pNext指向列表的开始，_pPrev指向结束。该列表以仅包含此头节点开始，并且不应从列表中删除。

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

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

现在，我想在这个数据结构进行以下操作：给予2个指数i和j到_nodes阵列，交换阵列中的节点，但保留在双向链表自己的立场。此操作需要更新_nodes[i]._pPrev->_pNext,_nodes[i]._pNext->_pPrev和节点j相同。

一个问题是当节点i和j彼此相邻时的拐角情况。另一个问题是，天真的代码涉及很多if（为了检查每个节点的_pData==nullptr并且以不同的方式处理这三种情况，并且检查节点是否彼此相邻），因此变得效率低下。

如何有效地做到这一点？

这里是我迄今为止在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

• 两个节点的节点内容可以互换，而不改变其含义;只有他们的地址将改变
• 由于地址发生了变化，所有引用到两个节点必须改变，也包括指针内恰巧指向两个节点中的一个节点。

以下是先交换& fixup later（TM）方法的说明。它的主要特点是避免了所有的角落案例。它确实假定了一个良好的LL，并且它忽略了“in_use”条件（其中，IMHO与LL交换问题正交）

注意我做了一些重命名，添加了测试数据并转换为Pure 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; 
} 

---

为了说明一个事实，即我们可以ignor e 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; 
}