问题描述
我正在尝试在双向链表中交换两个节点。以下是具有交换功能的程序部分。
I am trying to swap two nodes in a doubly linked list. Below is the part of program having swap function.
int swap (int x, int y)
{
struct node *temp = NULL ;
struct node *ptr1, *ptr2;
temp = (struct node *)malloc(sizeof(struct node));
if (head == NULL )
{
printf("Null Nodes");
}
else
{
ptr1 = ptr2 = head;
int count = 1;
while (count != x)
{
ptr1 = ptr1->next;
count++;
}
int count2 = 1;
while (count2 != y)
{
ptr2 = ptr2->next;
count2++;
}
ptr1->next->prev = ptr2;
ptr1->prev->next = ptr2;
ptr2->next->prev = ptr1;
ptr2->prev->next = ptr1;
temp->prev = ptr1->prev;
ptr1->prev = ptr2->prev;
ptr2->prev = temp->prev;
temp->next = ptr1->next;
ptr1->next = ptr2->next;
ptr2->next = temp->next;
}
return 0;
}
当我运行此程序时，在第一个节点和第二个节点的情况下崩溃。对于其他节点，则给出无限循环输出。 （例如：-2-> 4 2-> 4 2-> 4 ....等等）。
When I run this program, in case of 1st and 2nd node, it crashes. while in case of any other nodes, it gives infinite loop output. (eg:- 2->4 2->4 2->4....so on)`.
我知道关于节点交换还有更多问题，但没有找到与我的问题类似的任何东西。请帮帮我.. !!
I know there are some more questions about node swappings, but I didn't find any one similar to my problem. Please help me out..!!
预先感谢。
推荐答案
如果ptr1 == head（ptr1-> prev == NULL）或ptr2 == head（ptr2-> prev == NULL），则代码将失败，因为它最终会尝试使用head-> next，而不会不存在。如果ptr1-> next == NULL或ptr2-> next == NULL，也需要检查列表的末尾，可以使用本地尾指针进行处理。使用指向节点的指针可以简化代码。例如，指向ptr1的下一个指针的指针可以是& ptr1-> prev-> next或& head。指向ptr2的上一个指针的指针可以是& ptr2-> next-> prev或& tail（并设置tail = ptr2）。
The code will fail if ptr1 == head (ptr1->prev == NULL) or ptr2 == head (ptr2->prev == NULL), because it ends up trying to use head->next, which doesn't exist. There also needs to be a check for the end of a list, if ptr1->next == NULL or ptr2->next == NULL, which can be handled using a local tail pointer. Using pointers to pointer to node can simplify the code. For example the pointer to next pointer to ptr1 could be &ptr1->prev->next or &head. The pointer to prev pointer to ptr2 could be &ptr2->next->prev or &tail (and set tail = ptr2).
使用指向的指针节点解决了交换相邻节点的问题。
Using pointers to pointer to node fixes the issue with swapping adjacent nodes. Also temp can be a pointer to node.
示例代码使用指向节点的指针（而不是计数）进行交换：
Example code using pointers to nodes (instead of counts) to swap:
typedef struct node NODE;
/* ... */
NODE * SwapNodes(NODE *head, NODE *ptr1, NODE *ptr2)
{
NODE **p1pn; /* & ptr1->prev->next */
NODE **p1np; /* & ptr1->next->prev */
NODE **p2pn; /* & b->prev->next */
NODE **p2np; /* & b->next->prev */
NODE *tail; /* only used when x->next == NULL */
NODE *temp; /* temp */
if(head == NULL || ptr1 == NULL || ptr2 == NULL || ptr1 == ptr2)
return head;
if(head == ptr1)
p1pn = &head;
else
p1pn = &ptr1->prev->next;
if(head == ptr2)
p2pn = &head;
else
p2pn = &ptr2->prev->next;
if(ptr1->next == NULL){
p1np = &tail;
tail = ptr1;
} else
p1np = &ptr1->next->prev;
if(ptr2->next == NULL){
p2np = &tail;
tail = ptr2;
}else
p2np = &ptr2->next->prev;
*p1pn = ptr2;
*p1np = ptr2;
*p2pn = ptr1;
*p2np = ptr1;
temp = ptr1->prev;
ptr1->prev = ptr2->prev;
ptr2->prev = temp;
temp = ptr1->next;
ptr1->next = ptr2->next;
ptr2->next = temp;
return head;
}
这篇关于交换双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！