Lista de división en dos listas positivas y negativas separadas

Question

Escribí una función dividiendo una lista enlazada en dos, donde la lista pasada guarda positivo números y retornos negativo lista de números. 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; } Después de usar esta función, ambas listas contienen 0 como primer valor, no importa qué valores contenga la lista pasada antes de usar la función. ¿Cómo arreglar esto?

techtrailblazer · Accepted Answer

La función addToEnd acepta el puntero al nodo cabeza en la lista por valor. void addToEnd(struct elem* list, int nval) { ^^^^^^^^^^^^^^^^^ Esa es la función trata de una copia del valor del puntero al nodo cabeza. Así que asignar a la copia del argumento un nuevo valor en esta declaración if(temp == NULL) { list = new_list; return; } no cambia el puntero original al nodo cabeza. Usted necesita pasar el puntero al nodo de la cabeza por referencia a través de un puntero a él. Dentro de la función split asignar memoria como por ejemplo en estas declaraciones struct elem* positive = (struct elem*) malloc(sizeof(struct elem)); struct elem* negative = (struct elem*) malloc(sizeof(struct elem)); o en estas declaraciones if(temp->val > 0) addToEnd(positive, temp->val); else if(temp->val < 0) addToEnd(negative, temp->val) no tiene sentido porque los nodos ya fueron asignados. Lo que necesitas es mover nodos con valores negativos en una nueva lista. Aquí hay un programa demostrativo que muestra cómo se puede hacer. #include #include 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; } La salida del programa es 0 -> -1 -> 2 -> -3 -> 4 -> -5 -> 6 -> -7 -> 8 -> -9 -> null 0 -> 2 -> 4 -> 6 -> 8 -> null -1 -> -3 -> -5 -> -7 -> -9 -> null

Gpt · Answer

El problema principal en tu código es cómo estás manejando la creación de las listas positive y negative. En lugar de asignarles un nodo vacío al principio, debes inicializarlos como NULL para que luego puedas agregar nodos de forma adecuada. Además, necesitas asegurarte de que al modificar el puntero list en la función split, realmente estás cambiando la lista original que se pasa como parámetro.

Aquí te muestro una posible solución al problema:

c
struct elem split(struct elem list) {
    struct elem temp = list;
    struct elem positive = NULL;
    struct elem negative = NULL;

    struct elem prev;

    while (temp != NULL) {
        // Guardar el próximo nodo antes de hacer cambios
        prev = temp->next;

        // Remover el nodo de la lista original
        temp->next = NULL;

        if (temp->val > 0) {
            addToEnd(&positive, temp->val);
        } else if (temp->val < 0) {
            addToEnd(&negative, temp->val);
        }

        // Mover al siguiente nodo
        temp = prev;
    }

    // Liberar memoria de la lista original
       list = NULL;
    return negative;
}

En esta solución, estamos utilizando un enfoque más seguro para separar la lista original en las listas positivas y negativas. También estamos liberando la memoria de la lista original al final de la función. Además, asegúrate de pasar la dirección de memoria de positive y negative al llamar a la función addToEnd.

Espero que esta solución te ayude a resolver el problema que estás experimentando. ¡Déjame saber si necesitas más ayuda!

Respondida el Dec 17, 2020 a las 17:00 - por Gpt

Gemini · Answer

El problema con el código proporcionado es que no inicializa correctamente las listas positivas y negativas. Como resultado, ambas listas contienen 0 como primer valor.

Para solucionar este problema, puedes inicializar las listas positivas y negativas con nodos ficticios que tengan valores que no afecten el resultado. Aquí tienes el código actualizado:

c
include include 
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) {
    // Inicializar listas positivas y negativas con nodos ficticios
    struct elem positive = create(INT_MAX);
    struct elem negative = create(INT_MIN);

    struct elem prev;
    struct elem temp = list;

    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->next;
    return negative->next;
}

int main() {
    struct elem head = NULL;
    addToEnd(head, 5);
    addToEnd(head, -3);
    addToEnd(head, 2);
    addToEnd(head, -7);

    struct elem positive = split(&head);

    // Imprimir la lista positiva
    struct elem temp = positive;
    while(temp != NULL) {
        printf("%d ", temp->val);
        temp = temp->next;
    }
    printf("\n");

    // Imprimir la lista negativa
    temp = negative;
    while(temp != NULL) {
        printf("%d ", temp->val);
        temp = temp->next;
    }
    printf("\n");

    return 0;
}

Explicación de los cambios:

Inicializamos las listas positivas y negativas con nodos ficticios que tienen valores muy grandes (INTMAX) y muy pequeños (INTMIN), respectivamente. Estos valores no afectarán el resultado final. Modificamos el bucle while para liberar el nodo temp actual después de procesarlo. Esto libera la memoria asignada a los nodos de la lista original. Actualizamos el puntero head para que apunte al siguiente nodo después del nodo ficticio en la lista positiva. Devolvemos la lista negativa como negative->next para omitir el nodo ficticio.

Con estos cambios, el código debería dividir correctamente la lista en listas positivas y negativas sin valores 0 iniciales.

Respondida el Dec 17, 2020 a las 17:05 - por Gemini

Lista de división en dos listas positivas y negativas separadas

3 Respuestas: