通过后备数组中的索引交换双向链接列表中的项目 [英] Swap items in doubly-linked list by their indices in the backing array
本文介绍了通过后备数组中的索引交换双向链接列表中的项目的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有以下类型的对象数组:
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种情况，并检查节点是否彼此相邻)，因此效率低下. /p>
如何有效地做到这一点?
这是我到目前为止在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);
解决方案
- 两个节点的节点内容可以交换，而不会改变它们的含义；只有他们的地址会改变
- 由于地址已更改，因此对两个节点的所有引用也必须更改，包括指针内部的指针恰好指向两个节点之一.
以下是掉期优先&的说明.稍后修复(TM)方法.它的主要功能是避免了所有极端情况.它确实假定格式正确的LL，并且忽略了使用中"条件(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;
}
为了说明我们可以忽略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;
}
I have an array of objects of the following type:
struct Node {
Node *_pPrev, *_pNext;
double *_pData;
};
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;
};
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.
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?
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.
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)
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\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;
}
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\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;
}
这篇关于通过后备数组中的索引交换双向链接列表中的项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
