Разделение списка на два отдельных положительных и отрицательных списка

Question

Разделение списка на два отдельных положительных и отрицательных списка

Я написал функцию, разделяющую один связанный список на два, где переданный список хранит положительные числа и возвращает список отрицательных чисел.

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 в качестве первого значения, независимо от того, какие значения содержит переданный список до использования функции. Как это исправить?

# c linked-list split singly-linked-list function-definition

Vlad from Moscow16 дек. 2020, в 16:50

Источник

0

Kindle вставить весь код Deepak Tatyaji Ahire 16 дек. 2020, в 16:54
0

Поскольку addToEnd делает именно это, добавляет значения в конец. Поскольку это первое, что вы делаете в split, он только добавляет элементы к положительному, не делая ничего для первого элемента. Yazan Alsalem 16 дек. 2020, в 16:55
1

addToEnd не работает, если список пуст. Он устанавливает list = new_list , но list является локальным для addToEnd . Либо объявите первый параметр как struct elem **list либо верните обновленный list . Ian Abbott 16 дек. 2020, в 17:09
0

Я думаю, это должно сработать. Deepak Tatyaji Ahire 16 дек. 2020, в 17:12
0

@IanAbbott, спасибо, я решил, что функция addToEnd будет создавать новый список на случай, если список пуст, но совершенно забыл, что то, что я написал, работает только локально. Исправлено, и все работает так, как я хотел. jikix 16 дек. 2020, в 17:20

Поделиться в социальных сетях:

Скопировать адрес страницы:

Ответы 1

Смежные вопросы

Поскольку addToEnd делает именно это, добавляет значения в конец. Поскольку это первое, что вы делаете в split, он только добавляет элементы к положительному, не делая ничего для первого элемента.
addToEnd не работает, если список пуст. Он устанавливает list = new_list , но list является локальным для addToEnd . Либо объявите первый параметр как struct elem **list либо верните обновленный list .
@IanAbbott, спасибо, я решил, что функция addToEnd будет создавать новый список на случай, если список пуст, но совершенно забыл, что то, что я написал, работает только локально. Исправлено, и все работает так, как я хотел.

Vlad from Moscow · Accepted Answer · 2020-12-16T14-22-10.000Z

Функция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

Вы имеете в виду - «Я выделил каждый узел дважды - и он все еще не работает ??»
@ DavidC.Rankin Я имею в виду, что ни один новый узел не должен выделяться в разделении функций. :)