2

Eu estava procurando o mínimo primeiro para depois remover ele. Alguém ajuda?

 /*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 Resposta 1

2

Sua função inserir parece correta, mas a sua função buscaMenor_Remove está bastante errada.

Vamos ver este trecho:

        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;

Considerando que q = (*lst)->seg e p = (*lst), então é correto afirmar que q = p->seg. Sendo assim, se substituirmos o p = p->seg por p = q, o programa continua funcionando da mesma maneira:

    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;

E se o conteúdo do if e do else são iguais, então dá para eliminar o if:

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

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

E isso claramente não é o que você quer. Ele vai percorrer a lista até mostrar "Lista vazia" e retornar 0.

Além disso, o seu programa tem o grave problema de não desalocar (com free) a memória alocada, causando memory leaks.

Outro problema que vi são os seus #includes:

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

Você está incluindo string.h duas vezes e não está incluindo stdio.h! Além disso, esse N é inútil, pois você nunca o usa.

E você também declarou isto:

void Remover (cel * p);

Só que essa função não existe. Então eu removi esta declaração.

Acho que o que você quer é isso:

#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;
}

Acrescentei a função destruir, que destroi a lista e a função mostrarLista que a imprime na tela. Na função main eu coloquei 9 diferentes cenários para testar, e como você pode ver na saída do programa, todos funcionam como esperado. Eis a saída:

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

Bem, as funções buscaMenor e buscaMenor_Remove merecem mais explicações. A buscaMenor percorre a lista procurando pelo menor elemento e a coloca dentro do ponteiro-de-ponteiro-de-ponteiro menor. Depois a buscaMenor_Remove utiliza esse ponteiro3 para remover o elemento da lista e retornar o conteúdo. Achei melhor separar estes conceitos porque primeiro você deve encontrar o menor elemento (buscaMenor) para depois então removê-lo.

O tipo é um ponteiro3 porque dentro de buscaMenor_Remove:

  • Os nós da lista são acessados por ponteiros. Cada elemento da lista usa um ponteiro para apontar para o próximo.

  • Para mudar o apontamento de um item da lista para o próximo, eu tenho que alterar o destino do ponteiro, e com isso eu acabo apontando para o ponteiro, criando um ponteiro-de-ponteiro.

  • O ponteiro-de-ponteiro é representado por uma variável deste tipo dentro de buscaMenor_Remove. Como eu quero que ela seja alterada dentro de buscaMenor, então eu passo o endereço desta variável, que é um ponteiro-de-ponteiro-de-ponteiro.

Veja funcionando no ideone.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .