交換項目通過其索引的支持數組中

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; 
}