C中链表的插入排序
Insertion Sort on Linked List in C
我正在尝试使用以下函数对 C 中的链表执行插入排序,它陷入了无限循环。我调试了代码,发现它在第一次通过时有效,在第二次通过时陷入无限循环。
void insertion_sort()//Insertion Sort function
{
struct Node *p = root->next;
struct Node *a = NULL, *b = NULL;
while(p != NULL)
{
a = root;
while(a != p)
{
b = a;
a = a->next;
}
if(b != NULL)
b->next = a->next;
a->next = NULL;
struct Node *q = root;
struct Node* r = NULL;
while(p->data > q->data)
{
r = q;
q = q->next;
}
p->next = q;
if(r != NULL)
r->next = p;
p = p->next;
}
}
对于初学者来说,函数依赖于全局变量是个坏主意。对于您的程序,这意味着您不能在一个程序中有两个列表。
我没有看到指针 root
在函数 insertion_sort
中的位置发生了变化。因此,即使所有其他代码都有效,该函数也不正确,因为当指向的节点的值无序时,它不会更改指针 root
。
我可以建议下面的演示程序中显示的以下解决方案。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Node
{
int data;
struct Node *next;
};
int push_front( struct Node **head, int data )
{
struct Node *node = malloc( sizeof( struct Node ) );
int success = node != NULL;
if ( success )
{
node->data = data;
node->next = *head;
*head = node;
}
return success;
}
void insertion_sort( struct Node **head )
{
for ( struct Node **current = head; *current != NULL; )
{
struct Node **sorted = head;
while ( *sorted != *current && !( ( *current )->data < ( *sorted )->data ) )
{
sorted = &( *sorted )->next;
}
if ( *sorted != *current )
{
struct Node *tmp = *current;
*current = ( *current )->next;
tmp->next = *sorted;
*sorted = tmp;
}
else
{
current = &( *current )->next;
}
}
}
FILE * output( struct Node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->data );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
enum { N = 13 };
struct Node *head = NULL;
srand( ( unsigned int )time( NULL ) );
for ( int i = 0; i < N; i++ )
{
push_front( &head, rand() % N );
}
fputc( '\n', output( head, stdout ) );
insertion_sort( &head );
fputc( '\n', output( head, stdout ) );
return 0;
}
程序输出可能看起来像
1 -> 12 -> 0 -> 4 -> 0 -> 12 -> 3 -> 7 -> 12 -> 2 -> 5 -> 9 -> 7 -> null
0 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 7 -> 9 -> 12 -> 12 -> 12 -> null
我正在尝试使用以下函数对 C 中的链表执行插入排序,它陷入了无限循环。我调试了代码,发现它在第一次通过时有效,在第二次通过时陷入无限循环。
void insertion_sort()//Insertion Sort function
{
struct Node *p = root->next;
struct Node *a = NULL, *b = NULL;
while(p != NULL)
{
a = root;
while(a != p)
{
b = a;
a = a->next;
}
if(b != NULL)
b->next = a->next;
a->next = NULL;
struct Node *q = root;
struct Node* r = NULL;
while(p->data > q->data)
{
r = q;
q = q->next;
}
p->next = q;
if(r != NULL)
r->next = p;
p = p->next;
}
}
对于初学者来说,函数依赖于全局变量是个坏主意。对于您的程序,这意味着您不能在一个程序中有两个列表。
我没有看到指针 root
在函数 insertion_sort
中的位置发生了变化。因此,即使所有其他代码都有效,该函数也不正确,因为当指向的节点的值无序时,它不会更改指针 root
。
我可以建议下面的演示程序中显示的以下解决方案。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Node
{
int data;
struct Node *next;
};
int push_front( struct Node **head, int data )
{
struct Node *node = malloc( sizeof( struct Node ) );
int success = node != NULL;
if ( success )
{
node->data = data;
node->next = *head;
*head = node;
}
return success;
}
void insertion_sort( struct Node **head )
{
for ( struct Node **current = head; *current != NULL; )
{
struct Node **sorted = head;
while ( *sorted != *current && !( ( *current )->data < ( *sorted )->data ) )
{
sorted = &( *sorted )->next;
}
if ( *sorted != *current )
{
struct Node *tmp = *current;
*current = ( *current )->next;
tmp->next = *sorted;
*sorted = tmp;
}
else
{
current = &( *current )->next;
}
}
}
FILE * output( struct Node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->data );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
enum { N = 13 };
struct Node *head = NULL;
srand( ( unsigned int )time( NULL ) );
for ( int i = 0; i < N; i++ )
{
push_front( &head, rand() % N );
}
fputc( '\n', output( head, stdout ) );
insertion_sort( &head );
fputc( '\n', output( head, stdout ) );
return 0;
}
程序输出可能看起来像
1 -> 12 -> 0 -> 4 -> 0 -> 12 -> 3 -> 7 -> 12 -> 2 -> 5 -> 9 -> 7 -> null
0 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 7 -> 9 -> 12 -> 12 -> 12 -> null