Recursive function to remove from a headless chained list

Question

Recursive function to remove from a headless chained list

Asked 9 years ago

Viewed 1,491 times

2

I was looking for the minimum first to then remove it. Someone helps?

 /*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;
}

1 answer

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.

by Victor Stafusa • **63,338** points · Answer 1 · 2015-11-10T08:40:19+00:00

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

Let’s see this stretch:

        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 ele adequadamente:

    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;

whereas q = (*lst)->seg and p = (*lst), then it is correct to state that q = p->seg. So if we replace the p = p->seg for p = q, the program continues to work 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;

What if the contents of if and of else are equal, so you can eliminate the if:

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

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

And that’s clearly not what you want. It will go through the list until it shows "Lista vazia" and return 0.

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

Another problem I’ve seen is yours #includes:

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

You are including string.h twice and not including stdio.h! Besides, this N is useless because you never use it.

And you also declared it:

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 function destruir, that destroys the list and the function mostrarLista that prints it on the screen. In the function main i put 9 different scenarios to test, and as you can see in the program output, 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 functions buscaMenor and buscaMenor_Remove deserve further explanations. The buscaMenor goes through the list looking for the smallest element and places it inside the pointer menor. Then the buscaMenor_Remove use this pointer³ to remove the element from the list and return the content. I thought it best to separate these concepts because first you should find the smallest element (buscaMenor) and then remove it.

The guy’s a pointer³ because inside buscaMenor_Remove:

List nodes are accessed by pointers. Each element of the list uses a pointer to point to the next.
To change the pointer from one item in the list to the next, I have to change the pointer destination, and with that I end up pointing to the pointer, creating a pointer.
The pointer is represented by a variable of this type within buscaMenor_Remove. How I want her to be changed inside buscaMenor, then I pass the address of this variable, which is a pointer-pointer-pointer.

Behold functioning on the ideone.