问题描述
我试图制作用于交换链表中节点的函数(swapNodes).在这里，我存储了要交换的节点的上一个和下一个地址.但是我的代码陷入了无限循环.
可以将此代码制作为可工作的代码，还是错误的方法?
I tried to make function(swapNodes) for swapping nodes in linked list.Here i stored previous and next addresses of nodes which are to be swapped.But my code stucked in infinite loop.
Can this code be made as working one or it is a wrong approach?
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
void swapNodes(struct Node** headr,int key1,int key2)
{
struct Node* temp1 = *headr;
struct Node* temp2 = *headr;
if(key1 == key2)
return;
struct Node* prev1 =NULL;
struct Node* next1 =temp1;
while(temp1->data !=key1 && next1 !=NULL)
{
prev1 =temp1;
temp1 =temp1->next;
next1 =temp1->next;
}
struct Node* prev2 =NULL;
struct Node* next2 =temp2;
while(temp2->data !=key2 && next2 !=NULL)
{
prev2 =temp2;
temp2 =temp2->next;
next2 =temp2->next;
}
if(next1 == NULL||next2 == NULL)
return;
prev1->next =temp2;
temp2->next =next1;
prev2->next =temp1;
temp1->next =next2;
}
int main()
{
struct Node *start = NULL;
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling swapNodes() ");
printList(start);
swapNodes(&start, 4, 3);
printf("\n Linked list after calling swapNodes() ");
printList(start);
return 0;
}
推荐答案
该函数具有未定义的行为，因为它没有考虑例如 headr 可以等于 NULL 或 prev1 和 prev2 可以等于 NULL .
The function has undefined behavior because it does not take into account that for example headr can be equal to NULL or prev1 and prev2 can be equal to NULL.
最好再编写一个函数来查找与给定数据对应的节点.
It would be good to write one more function that finds the node that corresponds to the given data.
尽管如此，函数 swapNodes 可以通过以下方式编写.它找到要交换的节点，然后交换指向该节点及其数据成员的指针 next .
Nevertheless the function swapNodes can be written the following way. It finds nodes to be swapped and then swaps pointers to the nodes and their data members next.
您在这里
void swap( struct Node **first, struct Node **second )
{
struct Node *tmp = *first;
*first = *second;
*second = tmp;
}
void swapNodes( struct Node **headr, int key1, int key2 )
{
if ( key1 == key2 ) return;
struct Node **first = headr;
while ( *first && ( *first )->data != key1 ) first = &( *first )->next;
if ( *first == NULL ) return;
struct Node **second = headr;
while ( *second && ( *second )->data != key2 ) second = &( *second )->next;
if ( *second == NULL ) return;
swap( first, second );
swap( &( *first )->next, &( *second )->next );
}
这是一个演示程序.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
void swap( struct Node **first, struct Node **second )
{
struct Node *tmp = *first;
*first = *second;
*second = tmp;
}
void swapNodes( struct Node **headr, int key1, int key2 )
{
if ( key1 == key2 ) return;
struct Node **first = headr;
while ( *first && ( *first )->data != key1 ) first = &( *first )->next;
if ( *first == NULL ) return;
struct Node **second = headr;
while ( *second && ( *second )->data != key2 ) second = &( *second )->next;
if ( *second == NULL ) return;
swap( first, second );
swap( &( *first )->next, &( *second )->next );
}
int main( void )
{
struct Node *start = NULL;
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling swapNodes() ");
printList(start);
swapNodes(&start, 4, 3);
printf("\n Linked list after calling swapNodes() ");
printList(start);
return 0;
}
其输出为
Linked list before calling swapNodes() 1 2 3 4 5 6 7
Linked list after calling swapNodes() 1 2 4 3 5 6 7
实际上，函数 swapNodes 编写时(没有单独的函数来查找给定数据的节点)有两件事:1)找到两个节点，2)交换它们.节点搜索可能不成功.因此，该功能应向用户报告是否交换了节点.在这种情况下，最好将函数声明为具有返回类型 int .
In fact the function swapNodes as it is written (without a separate function that finds nodes for a given data) does two things: it 1) finds two nodes and it 2) swaps them. Searching of the nodes can be unsuccessful. So the function should report to the user whether nodes were swapped. In this case it is desirable to declare the function as having return type int.
例如
int swapNodes( struct Node **headr, int key1, int key2 )
{
int success = key1 != key2;
if ( success )
{
struct Node **first = headr;
struct Node **second = headr;
while ( *first && ( *first )->data != key1 ) first = &( *first )->next;
success = *first != NULL;
if ( success )
{
while ( *second && ( *second )->data != key2 ) second = &( *second )->next;
success = *second != NULL;
}
if ( success )
{
swap( first, second );
swap( &( *first )->next, &( *second )->next );
}
}
return success;
}
如果要编写一个如上所述的搜索节点的单独函数，那么交换节点的函数将看起来更清晰，更简单.
If to write a separate function that searches a node as it was mentioned above then the function that swaps nodes will look more clear and simpler.
例如
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
void swap( struct Node **first, struct Node **second )
{
struct Node *tmp = *first;
*first = *second;
*second = tmp;
}
struct Node ** find( struct Node **headr, int data )
{
while ( *headr && ( *headr )->data != data ) headr = &( *headr )->next;
return headr;
}
void swapNodes( struct Node **first, struct Node **second )
{
swap( first, second );
swap( &( *first )->next, &( *second )->next );
}
int main( void )
{
struct Node *start = NULL;
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling swapNodes() ");
printList(start);
struct Node **first;
struct Node **second;
if ( ( first = find( &start, 4 ) ) && ( second = find( &start, 3 ) ) ) swapNodes( first, second );
printf("\n Linked list after calling swapNodes() ");
printList(start);
return 0;
}
这篇关于交换链表中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！