使用双指针在链表之间插入一个新节点
Inserting a new node between a linked list using double pointer
下面的函数应该将一个新节点插入到有序列表中的适当位置,返回指向修改列表中第一个节点的指针。不幸的是,该功能并非在所有情况下都能正常工作。解释它有什么问题并展示如何修复它。假设节点结构是第 17.5 节中定义的那个。
struct node {
int value;
struct node *next;
};
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node *cur = list, *prev = NULL;
while (cur->value <= new_node->value) {
prev = cur;
cur = cur->next;
}
prev->next = new_node;
new_node->next = cur;
return list;
}
上面一道是k.n.king C编程第17章练习13的问题,我把它编码成下面一道。
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node **pp = &list;
while (list != NULL) {
if (list->value >= new_node->value)
break;
pp = &list->next;
list = list->next;
}
list = new_node;
return list;
}
它没有出现任何编译错误,但是我在链表中以正确的方式使用了双指针吗?我用它来跟踪列表,直到找到插入 new_node 的正确位置,找到它后,循环终止,然后将 new_node 分配给列表。但是好像不能正常使用,请告诉我是什么地方出错了。
这个函数
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node **pp = &list;
while (list != NULL) {
if (list->value >= new_node->value)
break;
pp = &list->next;
list = list->next;
}
list = new_node;
return list;
}
更改局部变量list
。注意函数参数是函数局部变量
按以下方式更改函数
struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
struct node **pp = &list;
while ( *pp != NULL && !( new_node->value < ( *pp )->value ) )
{
pp = &( *pp )->next;
}
new_node->next = *pp;
*pp = new_node;
return list;
}.
这是一个演示程序。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node
{
int value;
struct node *next;
};
struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
struct node **pp = &list;
while ( *pp != NULL && !( new_node->value < ( *pp )->value ) )
{
pp = &( *pp )->next;
}
new_node->next = *pp;
*pp = new_node;
return list;
}
FILE * display( const struct node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->value );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
struct node *head = NULL;
const size_t N = 10;
srand( ( unsigned int )time( NULL ) );
for ( size_t i = 0; i != N; i++ )
{
struct node *new_node = malloc( sizeof( *new_node ) );
new_node->value = rand() % N;
new_node->next = NULL;
head = insert_into_ordered_list( head, new_node );
}
fputc( '\n', display( head, stdout ) );
return 0;
}
程序输出可能看起来像
0 -> 0 -> 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 6 -> 8 -> null
当然你需要自己编写一个函数来清除列表,即释放所有分配的内存。
那么对于我来说,我将按照以下方式声明和定义函数,如下一个演示程序所示。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node
{
int value;
struct node *next;
};
int insert_into_ordered_list( struct node **head, int value )
{
struct node *new_node = malloc( sizeof( *new_node ) );
int success = new_node != NULL;
if ( success )
{
new_node->value = value;
while ( *head != NULL && !( new_node->value < ( *head )->value ) )
{
head = &( *head )->next;
}
new_node->next = *head;
*head = new_node;
}
return success;
}
FILE * display( const struct node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->value );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
struct node *head = NULL;
const size_t N = 10;
srand( ( unsigned int )time( NULL ) );
for ( size_t i = 0; i != N; i++ )
{
insert_into_ordered_list( &head, rand() % N );
}
fputc( '\n', display( head, stdout ) );
return 0;
}
下面的函数应该将一个新节点插入到有序列表中的适当位置,返回指向修改列表中第一个节点的指针。不幸的是,该功能并非在所有情况下都能正常工作。解释它有什么问题并展示如何修复它。假设节点结构是第 17.5 节中定义的那个。
struct node {
int value;
struct node *next;
};
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node *cur = list, *prev = NULL;
while (cur->value <= new_node->value) {
prev = cur;
cur = cur->next;
}
prev->next = new_node;
new_node->next = cur;
return list;
}
上面一道是k.n.king C编程第17章练习13的问题,我把它编码成下面一道。
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node **pp = &list;
while (list != NULL) {
if (list->value >= new_node->value)
break;
pp = &list->next;
list = list->next;
}
list = new_node;
return list;
}
它没有出现任何编译错误,但是我在链表中以正确的方式使用了双指针吗?我用它来跟踪列表,直到找到插入 new_node 的正确位置,找到它后,循环终止,然后将 new_node 分配给列表。但是好像不能正常使用,请告诉我是什么地方出错了。
这个函数
struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
struct node **pp = &list;
while (list != NULL) {
if (list->value >= new_node->value)
break;
pp = &list->next;
list = list->next;
}
list = new_node;
return list;
}
更改局部变量list
。注意函数参数是函数局部变量
按以下方式更改函数
struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
struct node **pp = &list;
while ( *pp != NULL && !( new_node->value < ( *pp )->value ) )
{
pp = &( *pp )->next;
}
new_node->next = *pp;
*pp = new_node;
return list;
}.
这是一个演示程序。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node
{
int value;
struct node *next;
};
struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
struct node **pp = &list;
while ( *pp != NULL && !( new_node->value < ( *pp )->value ) )
{
pp = &( *pp )->next;
}
new_node->next = *pp;
*pp = new_node;
return list;
}
FILE * display( const struct node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->value );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
struct node *head = NULL;
const size_t N = 10;
srand( ( unsigned int )time( NULL ) );
for ( size_t i = 0; i != N; i++ )
{
struct node *new_node = malloc( sizeof( *new_node ) );
new_node->value = rand() % N;
new_node->next = NULL;
head = insert_into_ordered_list( head, new_node );
}
fputc( '\n', display( head, stdout ) );
return 0;
}
程序输出可能看起来像
0 -> 0 -> 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 6 -> 8 -> null
当然你需要自己编写一个函数来清除列表,即释放所有分配的内存。
那么对于我来说,我将按照以下方式声明和定义函数,如下一个演示程序所示。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node
{
int value;
struct node *next;
};
int insert_into_ordered_list( struct node **head, int value )
{
struct node *new_node = malloc( sizeof( *new_node ) );
int success = new_node != NULL;
if ( success )
{
new_node->value = value;
while ( *head != NULL && !( new_node->value < ( *head )->value ) )
{
head = &( *head )->next;
}
new_node->next = *head;
*head = new_node;
}
return success;
}
FILE * display( const struct node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->value );
}
fputs( "null", fp );
return fp;
}
int main(void)
{
struct node *head = NULL;
const size_t N = 10;
srand( ( unsigned int )time( NULL ) );
for ( size_t i = 0; i != N; i++ )
{
insert_into_ordered_list( &head, rand() % N );
}
fputc( '\n', display( head, stdout ) );
return 0;
}