Recursive function to remove from a chained headless list

Question

Recursive function to remove from a chained headless list

Navigation

#1 by (2 votes)

2

I was looking for the first minimum and then removing it. Someone help?

 /*Escreva uma função recursiva para remover de uma lista encadeada
    sem cabeça uma célula que contêm um valor mínimo.*/

#include <stdlib.h>
#include <string.h>
#include <string.h>
#define N 1000

struct celula{
    int conteudo;
    struct celula *seg;
}; typedef struct celula cel;

void inserir(int x, cel **lst);
cel *buscaMenor_Remove(cel **lst);
void Remover (cel * p);

int main() {

    cel *lst = NULL;

    inserir(4, &lst);
    inserir(2, &lst);
    inserir(9, &lst);
    inserir(-1, &lst);

    printf("Conteudo: %d", buscaMenor_Remove(&lst)->conteudo);

    return 0;
}

void inserir(int x, cel **lst){

    cel *p, *nova;
    nova = (cel*) malloc(sizeof(cel*));
    nova->conteudo = x;
    nova->seg = NULL;
    p = (*lst);
    if(p == NULL){
        (*lst) = nova;
    }else{
        while(p->seg != NULL){
            p = p->seg;
        }
        p->seg = nova;
    }
}

cel *buscaMenor_Remove(cel **lst){
    cel *p;
    cel *q;
   cel *head;
    if((*lst) == NULL){
        printf("Lista Vazia!\n");
        return 0;
    }
        q = (*lst)->seg;
        p = (*lst);

            if(q->conteudo < p->conteudo){
                p = q;

             head =   buscaMenor_Remove(&p);
        }else{
            p=p->seg;
        head = buscaMenor_Remove(&p);
        }



    return head;
}

c

asked by anonymous 10.11.2015 / 07:25

1 answer

Select element by part of attribute contained in it How to check the size of a javascript object (in memory)

score 2 · Accepted Answer

Its inserir function seems correct, but its buscaMenor_Remove function is quite wrong.

Let's see this excerpt:

        q = (*lst)->seg;
        p = (*lst);

            if(q->conteudo < p->conteudo){
                p = q;

             head =   buscaMenor_Remove(&p);
        }else{
            p=p->seg;
        head = buscaMenor_Remove(&p);
        }



    return head;

Identando it properly:

    q = (*lst)->seg;
    p = (*lst);

    if (q->conteudo < p->conteudo) {
        p = q;
        head = buscaMenor_Remove(&p);
    } else {
        p = p->seg;
        head = buscaMenor_Remove(&p);
    }
    return head;

Considering that q = (*lst)->seg and p = (*lst) , then it is correct to say that q = p->seg . Therefore, if we replace p = p->seg with p = q , the program continues to function in the same way:

    q = (*lst)->seg;
    p = (*lst);

    if (q->conteudo < p->conteudo) {
        p = q;
        head = buscaMenor_Remove(&p);
    } else {
        p = q;
        head = buscaMenor_Remove(&p);
    }
    return head;

And if the contents of if and else are equal, then you can delete if :

    q = (*lst)->seg;
    p = (*lst);

    p = q;
    head = buscaMenor_Remove(&p);
    return head;

And this is clearly not what you want. It will scroll through the list until it displays "Lista vazia" and returns 0.

In addition, your program has the serious problem of not deallocating (with free ) the allocated memory, causing memory leaks .

Another problem I saw is your% s of% s:

#include <stdlib.h>
#include <string.h>
#include <string.h>
#define N 1000

You are including #include twice and you are not including string.h ! Also, this stdio.h is useless since you never use it.

And you also stated this:

void Remover (cel * p);

Only this function does not exist. So I removed this statement.

I think what you want is this:

#include <stdlib.h>
#include <stdio.h>

struct celula {
    int conteudo;
    struct celula *seg;
};
typedef struct celula cel;

void inserir(int x, cel **lst);
void destruir(cel *p);
void mostrarLista(cel *lst);
void buscaMenor(cel **lst, cel ***menor);
int buscaMenor_Remove(cel **lst);

int main() {

    printf("Teste 1: Lista em ordem decrescente\n");
    cel *lst1 = NULL;
    inserir(9, &lst1);
    inserir(4, &lst1);
    inserir(2, &lst1);
    inserir(-1, &lst1);
    mostrarLista(lst1);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst1));
    mostrarLista(lst1);
    destruir(lst1);

    printf("\nTeste 2: Lista em ordem crescente\n");
    cel *lst2 = NULL;
    inserir(-5, &lst2);
    inserir(2, &lst2);
    inserir(9, &lst2);
    inserir(21, &lst2);
    mostrarLista(lst2);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst2));
    mostrarLista(lst2);
    destruir(lst2);

    printf("\nTeste 3: Lista fora de ordem com menor no final\n");
    cel *lst3 = NULL;
    inserir(15, &lst3);
    inserir(21, &lst3);
    inserir(9, &lst3);
    inserir(-5, &lst3);
    mostrarLista(lst3);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst3));
    mostrarLista(lst3);
    destruir(lst3);

    printf("\nTeste 4: Lista fora de ordem com menor no inicio\n");
    cel *lst4 = NULL;
    inserir(-6, &lst4);
    inserir(15, &lst4);
    inserir(21, &lst4);
    inserir(9, &lst4);
    mostrarLista(lst4);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst4));
    mostrarLista(lst4);
    destruir(lst4);

    printf("\nTeste 5: Lista fora de ordem com menor no meio\n");
    cel *lst5 = NULL;
    inserir(15, &lst5);
    inserir(-6, &lst5);
    inserir(21, &lst5);
    inserir(-8, &lst5);
    inserir(9, &lst5);
    inserir(4, &lst5);
    mostrarLista(lst5);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst5));
    mostrarLista(lst5);
    destruir(lst5);

    printf("\nTeste 6: Lista fora de ordem com menor no meio e repetido\n");
    cel *lst6 = NULL;
    inserir(15, &lst6);
    inserir(-8, &lst6);
    inserir(21, &lst6);
    inserir(-8, &lst6);
    inserir(9, &lst6);
    inserir(4, &lst6);
    mostrarLista(lst6);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst6));
    mostrarLista(lst6);
    destruir(lst6);

    printf("\nTeste 7: Lista unitaria\n");
    cel *lst7 = NULL;
    inserir(44, &lst7);
    mostrarLista(lst7);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst7));
    mostrarLista(lst7);
    destruir(lst7);

    printf("\nTeste 8: Lista vazia\n");
    cel *lst8 = NULL;
    mostrarLista(lst8);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst8));
    mostrarLista(lst8);
    destruir(lst8);

    printf("\nTeste 9: Lista com todos os elementos iguais\n");
    cel *lst9 = NULL;
    inserir(15, &lst9);
    inserir(15, &lst9);
    inserir(15, &lst9);
    inserir(15, &lst9);
    mostrarLista(lst9);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst9));
    mostrarLista(lst9);
    destruir(lst9);

    return 0;
}

void mostrarLista(cel *lst) {
    if (lst == NULL) {
        printf("NULL\n");
    } else {
        printf("%d->", lst->conteudo);
        mostrarLista(lst->seg);
    }
}

void inserir(int x, cel **lst) {
    cel *nova = (cel*) malloc(sizeof(cel*));
    nova->conteudo = x;
    nova->seg = NULL;
    cel *p = *lst;
    if (p == NULL) {
        *lst = nova;
    } else {
        while (p->seg != NULL) {
            p = p->seg;
        }
        p->seg = nova;
    }
}

void destruir(cel *lst) {
    if (lst == NULL) return;
    cel *p = lst->seg;
    free(lst);
    destruir(p);
}

void buscaMenor(cel **lst, cel ***menor) {
    if ((*lst) == NULL) return;
    if ((*lst)->conteudo < (**menor)->conteudo) *menor = lst;
    buscaMenor(&(*lst)->seg, menor);
}

int buscaMenor_Remove(cel **lst) {
    if (*lst == NULL) {
        printf("Lista Vazia!\n");
        return 0;
    }

    cel **menor = lst;
    buscaMenor(lst, &menor);
    cel *p = *menor;
    if (menor == lst) *lst = p->seg;
    *menor = p->seg;
    int v = p->conteudo;
    free(p);
    return v;
}

I added the N function, which destroys the list and the destruir function that prints it on the screen. In the mostrarLista function I put 9 different scenarios to test, and as you can see in the output of the program, all work as expected. Here's the output:

Teste 1: Lista em ordem decrescente
9->4->2->-1->NULL
Conteudo: -1
9->4->2->NULL

Teste 2: Lista em ordem crescente
-5->2->9->21->NULL
Conteudo: -5
2->9->21->NULL

Teste 3: Lista fora de ordem com menor no final
15->21->9->-5->NULL
Conteudo: -5
15->21->9->NULL

Teste 4: Lista fora de ordem com menor no inicio
-6->15->21->9->NULL
Conteudo: -6
15->21->9->NULL

Teste 5: Lista fora de ordem com menor no meio
15->-6->21->-8->9->4->NULL
Conteudo: -8
15->-6->21->9->4->NULL

Teste 6: Lista fora de ordem com menor no meio e repetido
15->-8->21->-8->9->4->NULL
Conteudo: -8
15->21->-8->9->4->NULL

Teste 7: Lista unitaria
44->NULL
Conteudo: 44
NULL

Teste 8: Lista vazia
NULL
Lista Vazia!
Conteudo: 0
NULL

Teste 9: Lista com todos os elementos iguais
15->15->15->15->NULL
Conteudo: 15
15->15->15->NULL

Well, the main and buscaMenor functions deserve further explanation. buscaMenor_Remove traverses the list by looking for the smallest element and places it inside the pointer-pointer buscaMenor . Then menor uses this 3 pointer to remove the element from the list and return the contents. I found it better to separate these concepts because first you must find the smallest element ( buscaMenor_Remove ) and then remove it.

The type is a 3 pointer because within buscaMenor :

The nodes in the list are accessed by pointers. Each element in the list uses a pointer to point to the next one.
The pointer pointer is represented by a variable of this type within buscaMenor_Remove . As I want it to be changed within buscaMenor_Remove , then I pass the address of this variable, which is a pointer-pointer.

See running on ideone .