Я написал функцию, разделяющую один связанный список на два, где переданный список хранит положительные числа и возвращает список отрицательных чисел.
struct elem {
int val;
struct elem *next;
};
struct elem *create(int val) {
struct elem *temp;
temp=(struct elem*) malloc(sizeof(struct elem));
temp->val = val;
temp->next = NULL;
return temp;
}
void addToEnd(struct elem* list, int nval) {
struct elem *temp = list;
struct elem *new_list = create(nval);
if(temp == NULL) {
list = new_list;
return;
}
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = new_list;
}
struct elem* split(struct elem** list) {
struct elem* prev;
struct elem* temp = *list;
struct elem* positive = (struct elem*) malloc(sizeof(struct elem));
struct elem* negative = (struct elem*) malloc(sizeof(struct elem));
while(temp != NULL) {
if(temp->val > 0) addToEnd(positive, temp->val);
else if(temp->val < 0) addToEnd(negative, temp->val);
prev = temp;
temp = temp->next;
free(prev);
}
*list = positive;
return negative;
}
После использования этой функции оба моих списка содержат 0 в качестве первого значения, независимо от того, какие значения содержит переданный список до использования функции. Как это исправить?
ФункцияaddToEnd
принимает указатель на головной узел в списке по значению.
void addToEnd(struct elem* list, int nval) {
^^^^^^^^^^^^^^^^^
То есть функция имеет дело с копией значения указателя на головной узел.
Итак, присваивая копии аргумента новое значение в этом операторе if
if(temp == NULL) {
list = new_list;
return;
}
не изменяет исходный указатель на головной узел.
Вам нужно передать указатель на головной узел по ссылке через указатель на него.
Внутри функцииsplit
выделение памяти, как, например, в этих объявлениях
struct elem* positive = (struct elem*) malloc(sizeof(struct elem));
struct elem* negative = (struct elem*) malloc(sizeof(struct elem));
или в этих заявлениях
if(temp->val > 0) addToEnd(positive, temp->val);
else if(temp->val < 0) addToEnd(negative, temp->val)
не имеет смысла, потому что узлы уже были выделены. Вам нужно переместить узлы с отрицательными значениями в новый список.
Вот наглядная программа, которая показывает, как это можно сделать.
#include <stdio.h>
#include <stdlib.h>
struct elem
{
int val;
struct elem *next;
};
struct elem * create( int val )
{
struct elem *temp = malloc( sizeof( *temp ) );
if ( temp != NULL )
{
temp->val = val;
temp->next = NULL;
}
return temp;
}
int addToEnd( struct elem **list, int val )
{
struct elem *temp = create( val );
int success = temp != NULL;
if ( success )
{
while ( *list ) list = &( *list )->next;
*list = temp;
}
return success;
}
struct elem* split( struct elem **list )
{
struct elem *new_list = NULL;
struct elem **current = &new_list;
while ( *list )
{
if ( ( *list )->val < 0 )
{
*current = *list;
*list = ( *list )->next;
( *current )->next = NULL;
current = &( *current )->next;
}
else
{
list = &( *list )->next;
}
}
return new_list;
}
void display( const struct elem *list )
{
for ( ; list != NULL; list = list->next )
{
printf( "%d -> ", list->val );
}
puts( "null" );
}
int main(void)
{
struct elem *list = NULL;
const int N = 10;
for ( int i = 0; i < N; i++ )
{
addToEnd( &list, i % 2 != 0 ? -i : i );
}
display( list );
struct elem *new_list = split( &list );
display( list );
display( new_list );
return 0;
}
Вывод программы:
0 -> -1 -> 2 -> -3 -> 4 -> -5 -> 6 -> -7 -> 8 -> -9 -> null
0 -> 2 -> 4 -> 6 -> 8 -> null
-1 -> -3 -> -5 -> -7 -> -9 -> null
addToEnd
не работает, если список пуст. Он устанавливаетlist = new_list
, ноlist
является локальным дляaddToEnd
. Либо объявите первый параметр какstruct elem **list
либо верните обновленныйlist
. Ian Abbott