c-反转偶数的子列表

Question

我正在尝试反转偶数的子列表。代码中似乎有一个逻辑错误，但我找不到。

node *sublist_reverse(node *head)
{
node *temp=head,*wrking,*wrking_bfr,*node_tobe_ext;
while(temp!=NULL)
{
if(temp->link->data%2==0)
{
while(temp->link->data%2==0)
{
if(temp->data%2!=0)
{
wrking_bfr=temp;
wrking=wrking_bfr->link;
}
node_tobe_ext=wrking->link;
wrking->link=node_tobe_ext->link;
node_tobe_ext->link=wrking_bfr->link;
wrking_bfr->link=node_tobe_ext;
temp=wrking->link;
}
}
else
{
temp=temp->link;
}
}
return head;
}

Answer 1

我正在尝试反转偶数的子列表。

从所提供的代码来看，您试图做的是反转连续偶数的每个最大子列表，而不仅仅是一个。此外，这显然是在单链表的上下文中，而不是数组或双链表。此外，我从您的代码中推断，node被定义为一种结构类型，至少包含成员data和link，所以可能是

struct node {
int data;
struct node *link;
};
typedef struct node node;

有了这些理解，你的想法似乎是扫描列表，找到偶数子列表的开头，反转该子列表，然后重复。这就产生了代码中呈现的嵌套循环结构，这是解决问题的可行方法。

请告诉我我的逻辑错误是什么。

目前尚不清楚您在实现中发现了哪些具体问题或不当行为，但以下是代码中明显的问题：

• 当外循环到达列表末尾时，当函数评估时，会发生坏事

  if(temp->link->data%2==0)
  

  这是因为当temp指向最后一个节点时，temp->link不是有效的节点指针。

• 当内部循环到达列表的末尾时也会发生坏事，当最后一个元素为偶数时也会出现这种情况。这些是有问题的线路：

  node_tobe_ext=wrking->link;
  wrking->link=node_tobe_ext->link;
  

  当wrking指向最后一个节点时，node_tobe_ext不是有效的节点指针。

• 当列表包含一个包含两个或多个偶数的初始子列表时，这是不正确反转的。可以看出，情况肯定是这样的，因为第一个列表元素的奇偶校验从未被检查过，而且函数总是返回原始的head指针。(如果有一个包含两个或更多偶数的初始子列表，那么原始头节点将不会是最终列表的头。(

Answer 2

对于你我这样的初学者来说，这不是一项简单的任务。

您的函数不正确，至少是因为在函数中，指针head没有被更改，尽管列表可以从包含偶数的节点开始。在这种情况下，指针head的值将被更改。但这不会发生在你的功能中。函数中没有任何语句会更改指针head的值。

我可以提出一个更通用的解决方案。对于初学者来说，函数通过引用(通过指向头部节点的指针(接受指向该节点的指针，并且还有一个指定谓词的参数。如果节点的子序列满足谓词，则它被反转。特别地，谓词可以确定例如存储在节点中的数字是否为偶数。

给你。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node
{
int data;
struct node *link;
} node;
int push_front( node **head, int data )
{
node *new_node = malloc( sizeof( *new_node ) );
int success = new_node != NULL;

if ( success )
{
new_node->data = data;
new_node->link = *head;
*head = new_node;
}

return success;
}
FILE * display( const node *head, FILE *fp )
{
for ( ; head != NULL; head = head->link )
{
fprintf( fp, "%d -> ", head->data );
}

fputs( "null", fp );

return fp;
}
void reverse_ranges( node **head, int predicate( int ) )
{
while ( *head )
{
if ( predicate( ( *head )->data ) )
{
node **current = head;
head = &( *head )->link;

while ( *head != NULL && predicate( ( *head )->data ) )
{
node *tmp = *current;
*current = *head;
*head = ( *head )->link;
( *current )->link = tmp;
}                   
}
else
{
head = &( *head )->link;
}
}
}
int even( int data ) 
{ 
return data % 2 == 0; 
}
int main(void) 
{
node *head = NULL;

srand( ( unsigned int )time( NULL ) );
const int N = 15;
for ( int i = 0; i < N; i++ )
{
push_front( &head, rand() % N );
}
fputc( 'n', display( head, stdout ) );

reverse_ranges( &head, even );

fputc( 'n', display( head, stdout ) );
return 0;
}

程序输出可能看起来像

8 -> 10 -> 12 -> 7 -> 5 -> 10 -> 4 -> 8 -> 2 -> 6 -> 7 -> 1 -> 0 -> 4 -> 6 -> null
12 -> 10 -> 8 -> 7 -> 5 -> 6 -> 2 -> 8 -> 4 -> 10 -> 7 -> 1 -> 6 -> 4 -> 0 -> null

我认为，释放列表中所有分配内存的函数将由您自己编写。