Contar células de uma lista encadeada

1. Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 18/04/2019 - 16:27h

Estou tentando contar o número de células em uma lista encadeada. Criei a função contaRecursiva. Ao chama-la recebo a mensagem: falha de segmentação. Será que alguém pode mim ajudar?

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

typedef struct registro celula;
struct registro
{
int x;
celula *prox;
};

void insere(int n, celula *p);
void contaRecursiva(celula *p);

int main()
{
int n1;
celula atual;
int tecla = 10;
celula *pointer;

pointer = &atual;

while(tecla != 0)
{
printf("====== MENU ======\n");
printf("1 - para inserir um número\n");
printf("2 - para ver a quantidade de elementos\n\n");
scanf("%d", &tecla);
getchar();
printf("\n");

if(tecla == 1)
{
printf("Digite um numero\n");
scanf("%d", &n1);
getchar();
insere(n1, &atual);
printf("\n");
}
else if(tecla == 2)
{
contaRecursiva(&atual);
}
}
}

void insere(int n, celula *p)
{
celula *nova;
nova = (celula *) malloc(sizeof(celula));
nova->x = n;
nova->prox = p->prox;
p->prox = nova;
}

void contaRecursiva(celula *p)
{
int numCel;
if(p != NULL)
{
numCel++;
contaRecursiva(p->prox);
}
printf("%d celulas", numCel);
}



  


2. Re: Contar células de uma lista encadeada

???
gokernel

(usa Linux Mint)

Enviado em 18/04/2019 - 20:03h

Ver se isso ajuda:

https://github.com/gokernel2017/C_COLECTION/blob/master/DoubleLinkedList.c


3. Re: Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 18/04/2019 - 20:35h

Eu só queria uma coisa relativamente simples. Contar a quantidade de células em um lista encadeada.


4. Re: Contar células de uma lista encadeada

Paulo
paulo1205

(usa Ubuntu)

Enviado em 19/04/2019 - 00:18h

O valor inicial de atual.prox é indefinido. Deveria ser NULL.

Essa é a causa do SIGSEGV. Mas o programa tem outros erros.


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)


5. Re: Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 19/04/2019 - 00:59h

Pode dizer quais os erros? Gostei da tua resposta.



6. Re: Contar células de uma lista encadeada

???
gokernel

(usa Linux Mint)

Enviado em 19/04/2019 - 02:20h

"dalison" escreveu:


Eu só queria uma coisa relativamente simples. Contar a quantidade de células em um lista encadeada.


Ok !

É que geralmente faço as coisas de um modo que ajude a pessoa a pensar ! ...

Eu não estaria te ajudando se te desse a resposta definitiva/direta para resolver esse seu problema.

É mais construtivo ajudar a fazer você pensar !

Felicidades ... e bota a cabeça para funcionar !!!




7. Re: Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 19/04/2019 - 18:16h

Fiz o código, ele não dá nehum erro. Quando executo ele mostra 32527 celulas, sendo que só inserir um elemento. Eu preciso saber onde estou errando.

void conta(celula *p)
{
int cont;
celula *aux;
if(p != NULL)
{
aux = p;
while(aux != NULL)
{
cont++;
aux = aux->prox;
}
}
printf("%d celulas\n", cont);
}



8. Re: Contar células de uma lista encadeada

???
gokernel

(usa Linux Mint)

Enviado em 19/04/2019 - 20:04h

int cont; // <<<<<<<<<<< !!! erro aqui "no seu código !!!

Para usar uma variável local primeiro precisa setar o valor para ( 0 ) !!!

Variável local o valor inicial é indefinido ... diferente de variável global.

Modifiquei o seu código só para vc perceber: OBS: ainda tem erro... setar o valor de cont para 0.

void conta(celula *p)
{
int cont;
celula *aux;

printf ("Valor inicial de count: %d\n", cont);

if(p != NULL)
{
aux = p;
while(aux != NULL)
{
cont++;
aux = aux->prox;
}
}
printf("%d celulas\n", cont);
}





9. Re: Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 19/04/2019 - 21:50h

Estou tendo a impressão que p tá recebendo NULL e por isso não tá executando nada. Estou certo?


10. Re: Contar células de uma lista encadeada

???
gokernel

(usa Linux Mint)

Enviado em 20/04/2019 - 04:33h

"dalison" escreveu:

Estou tendo a impressão que p tá recebendo NULL e por isso não tá executando nada. Estou certo?


Sim, você está certo com essa sua "impressão" !!!

Seguindo a lógica do programa ... o erro está em ( "p := NULL" )... fora dessa função.


11. Re: Contar células de uma lista encadeada

Paulo
paulo1205

(usa Ubuntu)

Enviado em 20/04/2019 - 06:39h

dalison escreveu:

Pode dizer quais os erros? Gostei da tua resposta.


Uma forma razoável de detectar erros é fazer com que o compilador detecte esses erros para você.

Veja o que aconteceu quando eu copiei seu código (arquivo “x.c”) e mandei compilá-lo com opções que habilitam diagnóstico de código:
$ gcc -Wall -Werror -O2 -pedantic-errors x.cx.c: In function ‘main’:
x.c:19:13: error: variable ‘pointer’ set but not used [-Werror=unused-but-set-variable]
celula *pointer;
^~~~~~~
x.c:28:9: error: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Werror=unused-result]
scanf("%d", &tecla);
^~~~~~~~~~~~~~~~~~~
x.c:35:13: error: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Werror=unused-result]
scanf("%d", &n1);
^~~~~~~~~~~~~~~~
x.c: In function ‘contaRecursiva’:
x.c:61:14: error: ‘numCel’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
numCel++;
~~~~~~^~
cc1: all warnings being treated as errors


Antes de entrar nos erros em si, uma breve explicação das opções de compilação que eu usei com o GCC (se você usa outro compilador, pode ser que as opções sejam um pouco diferentes, mas possivelmente existem funcionalidades parecidas):

  • -Wall habilita todos (por isso o “all”) os alertas (warnings, por isso o “W”) sobre situações duvidosas que o compilador conseguir reconhecer no código (situações duvidosas são aquelas em que, embora o código seja sintaticamente válido, ele pode ser semanticamente inválido, ou violar algumas cláusulas de uso esperado de certas variáveis ou funções).

  • -Werror faz com que o compilador trate cada alerta emitido como se fosse um erro (por isso o “error”), impedindo a compilação de prosseguir (sem essa opção, o compilador pode até emitir os alertas, mas como o código possui sintaxe válida, ele assume que o programador sabe o que está fazendo, e deixa a compilação prosseguir, mesmo com alertas).

  • -O2 não propriamente é uma opção de diagnóstico, mas sim de otimização, mas como ela força o compilador a seguir o fluxo de vida de cada variável, a fim de minimizar a quantidade de operações que a envolvem, ela acaba ajudando a detectar casos de variáveis desnecessárias ou de variáveis que podem ser usadas antes de terem seu valor inicial explicitamente definido.

  • -pedantic-errors obriga o compilador a seguir estritamente (ou de modo poderia ser considerado pedante, por isso o “pedantic”) o padrão que define a linguagem, emitindo alertas caso se use alguma extensão exclusiva do GCC, que fuja do padrão. Além disso, trata também esses alertas como se fossem erros (por isso o “error”), não deixando que a compilação prossiga.

O primeiro alerta-erro indica que você criou uma variável na linha 19, mas nunca a usou.

O segundo e o terceiro alertas-erros se referem ao fato de que você não verifica se a leitura com scanf() foi bem sucedida antes de usar o valores que deveriam ter sido lidos. A forma de evitar tais alertas seria verificar o valor de retorno da função, que indica quantas das conversões especificadas na string de formatação puderam ser realmente convertidas com sucesso e salvas nos ponteiros para os locais de destino. A forma segura de fazer tais leituras seria parecida com o seguinte (usando como exemplo a leitura na linha 28).
  if(scanf("%d", &tecla)!=1){  // String tem uma conversão ("%d"), por isso a comparação com 1.
fprintf(stderr, "Erro de leitura. Abortando o programa.\n");
exit(1);
// Se abortar o programa for muito radical, você pode tentar outras abordagens,
// tentando ver o que causou o erro de leitura, e tentando repetir a operação, se
// a causa do erro não tiver sido grave. Por exemplo, se a leitura tiver falhado porque
// o usuário digitou caracteres não-numéricos, você pode tentar descartar tais carac-
// teres e fazer uma nova leitura “limpa”. Por outro lado, se a falha tiver sido causada
// por uma queda da conexão do usuário, não há como recuperar-se dessa situação,
// e abortar a execução é a melhor coisa a fazer.
}


O quarto alerta-erro indica justamente que a variável que você usou para fazer a contagem estava com um valor inicial indefinido. Desse modo, a operação de incrementar esse valor, que você faz ao percorrer cada nó da lista, pode ficar com um resultado que não representa nenhuma informação válida. [Eu não sei você está acostumado a usar alguma outra linguagem de programação que trate todos os valores iniciais de variáveis como se fossem iguais a zero (ou texto vazio, no caso de strings), mas esse não é o caso do C: o compilador só vai colocar alguma coisa na memória referente a variáveis não-estáticas se você explicitamente pedir para colocar tais valor lá.]


Note que o compilador não indicou o erro que eu apontei em minha primeira resposta, embora aquela fosse realmente a causa da falha de segmentação. Por mais espertos que sejam os compiladores modernos, eles são voltados para fazer análise sintática e léxica do código, a fim de traduzi-lo para linguagem de máquina. Análise semântica feita pelo compilador geralmente pega apenas casos mais triviais, e quase sempre apenas no entorno do código que está sendo sintaticamente analisado naquele momento. A falha de segmentação do seu programa era causada pelo esquecimento de uma inicialização dentro de main(), mas acontecia na função contaRecursiva(), com uma passagem de argumento como ponteiro. É quase impossível fazer com que o compilador consiga contexto suficiente para perceber um erro assim.

Felizmente, para isso, existem pessoas com um pouquinho mais de experiência. :)

Mas há, ainda, outros erros, além do apontado originalmente e daqueles que o compilador pode perceber. Abaixo eu listo alguns.

  • Você chama contaRecursiva() de um jeito tal que, no fim das contas, em lugar de imprimir apenas o valor final da contagem, todos os valores intermediários acabam impressos também.

  • Se bem que, analisando melhor, que valores intermediários seriam esses? Você chama a função contaRecusiva() recursivamente com nós sucessivos da lista, o que está certo, mas em nenhum lugar você passa a diante a informação de quantos nós já foram processados até o momento. Parece que você tentou fazer isso ao incrementar a variável local automática numCel, mas isso não funciona porque cada invocação da função produz uma instância nova de numCel, distinta das invocações anteriores (e como você esqueceu de lhe atribuir um valor inicial, cada uma dessas instâncias pode ter um valor inicial indefinido diferente dos valores indefinidos das instâncias anteriores).

  • A conversão do valor de retorno de malloc() é desnecessária em C (pois malloc() retorna um valor do tipo void *, que pode ser automaticamente convertido em qualquer outro tipo de ponteiro) e acaba atrapalhando a manutenção de código, de modo que é seguro removê-la. (Isso não chega a ser um erro mas, sendo uma redundância, é inútil, e é melhor eliminá-la.) (Tal conversão seria necessária em C++ (que não aceita a conversão automática a partir de void *), mas em C++ geralmente se evita o uso de malloc(), dando-se preferência ao operador new ou a uma classe de containers para alocação dinâmica.)

  • Ainda nessa mesma linha de código, você fez um acoplamento manual entre o ponteiro que está recebendo a alocação e o tipo de dado a ser usado como argumento de sizeof, para determinar o tamanho da região a ser alocada. Eu recomendo que, em lugar de informar separadamente o ponteiro e seu tipo, você informe apenas o ponteiro, deixando a linha com o formato abaixo. (De novo, o jeito como você fez não está propriamente errado, mas construções semelhantes em programas grandes ficam mais propensas a erros cometidos por distração ou por eventuais transformações de tipo que os objetos venham a sofrer ao longo do ciclo de vida do programa.)
  nova=malloc(sizeof *nova);  // Deixo que o compilador infira o tipo de “*nova”, em vez de eu o especificar manualmente. 


  • A declaração de main() foge do que o padrão do C prescreve. Você de usar “int main(void)” se não quiser receber argumentos do sistema operacional, ou “int main(int argc, char **argv)” se quiser recebê-los. O jeito como você fez significa, em C, que a função main pode ser chamada com uma quantidade qualquer de argumentos de quaisquer tipos. (Não confunda C com C++ ou com Java. Em C++ e Java, “int main()” declara que a função não recebe argumentos. Em C, se você quiser que uma função seja proibida de receber argumentos ao ser invocada, você tem de colocar a palavra-chave void, que significa “vazio”, na lista de parâmetros na hora de declarar a função.)


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)


12. Re: Contar células de uma lista encadeada

Dalison
dalison

(usa Slackware)

Enviado em 20/04/2019 - 12:11h

O programa tá funcionando bem. Fiz quase todos os ajustes (pelo menos eu acho). A questão de iniciar a variável cont em contaRecursiva que atualmente é só conta, gokernel já tinha mim dito. Eu tenho 10 questões pra resolver. Pretendo fazer tudo em um único programa. Na primeira questão quer que eu conte o número de células de forma recursiva e interativa. Só consegui de forma interativa e mesmo assim não sei se tá certo. Sobre o uso da função malloc, estou com medo de remove-la e dá bronca. Segue abaixo o código atualizado.

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

typedef struct registro celula;
struct registro
{
int x;
celula *prox;
};

celula* iniciar();
void insere(int n, celula *p);
void conta(celula *p);
void altura(int n, celula *p);

int main(void)
{
int n1, cont;
celula *lista = iniciar();
int tecla = 10;

while(tecla != 0)
{
printf("====== MENU ======\n");
printf("1 - para inserir um número\n");
printf("2 - para ver a quantidade de elementos\n");
printf("3 - contar elementos de forma recursiva\n");
scanf("%d", &tecla);
fflush(stdin);
printf("\n");
if(scanf("%d", &tecla) == 1)
{
fprintf(stderr, "Erro de leitura. Abortando programa.");
exit(1);
}
if(tecla == 1)
{
printf("Digite um numero\n");
scanf("%d", &n1);
if(scanf("%d", &n1) == 1)
{
fprintf(stderr, "Erro de leitura. Abortando programa.");
exit(1);
}
exit(1);
fflush(stdin);
insere(n1, lista);
printf("\n");
}
else if(tecla == 2)
{
conta(lista);
}
else if(tecla == 3)
{
altura(n1, lista);
}
}
}

celula* iniciar()
{
celula *lista = (celula *) malloc(sizeof(celula));
lista->prox = NULL;
return lista;
}
void insere(int n, celula *p)
{
celula *nova = (celula*) malloc(sizeof(celula));
nova->x = n;
nova->prox = p->prox;
p->prox = nova;
}

void conta(celula *p)
{
int cont = 0;
celula *aux;
if(p != NULL)
{
for(aux = p; aux->prox != NULL; aux = aux->prox)
{
cont++;
}
printf("%d celulas\n", cont);
}
}

void altura(int n, celula *p)
{
celula *aux;
celula *atual;
int cont = 0;
aux = p;

while(aux != NULL && aux->x != n)
{
aux = aux->prox;
}
for(atual = aux; atual != NULL; atual = atual->prox)
{
cont++;
}
printf("%d celulas para o final da lista.", cont);

}






01 02



Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts