Uma ajuda em C!

7 de outubro de 2008 8 respostas

Valder_Olmo_Correa 7 de outubro de 2008

Pessoal, sei que esse fórum é sobre Java, e foge do foco da proposta dele postarmos algo em outras linguagens.
Mas estou com uma dúvida cruel e um problema sério em linguagem C, sendo que os outros fóruns que pesquisei não são tão ativos e dinâmicos quanto o GUJ. Por isso pediria a gentileza de, se alguém aqui entender de linguagem C, mais especificamente de árvores binárias, que me ajudasse a implementar alguns métodos (tá, sei que em C são funções, mas gosto da nomenclatura do Java :D).

Tenho que construir uma árvore onde deve implementar os métodos de inserir, excluir, pesquisar, listar, e contar elementos. Já consegui fazer inserir, listar, contar. Falta pesquisar e excluir.

Na rotina de pesquisar estou perdendo os cabelos, pois não sei trabalhar com ponteiros direito, dá erro no método main() na linha 118 , o erro é o seguinte:

syntaxe error before “struct”

Alguém pode ajudar aí ?

O código está logo abaixo:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h> 
#include <malloc.h>

struct no
{
     char chave[20];
     int dado;
     struct no *esq;
     struct no *dir;
};

// Rotina para se inserir elementos na árvore

void inserir(struct no **r, char *chave, int dado)
{
     int cmp;
     
     if(*r==0)
     {
         // Temos aqui uma árvore vazia
         *r = malloc(sizeof(struct no));
         strcpy((*r)->chave, chave);
         (*r)->dado = dado;
         (*r)->esq = 0;
         (*r)->dir = 0;
         return;
     }
     
     cmp = strcmp((*r)->chave, chave);
     if(cmp==0)
     {
         (*r)->dado = dado;
         return;
     }

     if(cmp>0)
     {
         inserir(&((*r)->esq),chave,dado);
         return;
     }
     
     inserir(&((*r)->dir),chave,dado);
     return;  
}

// Método para se pesquisar um elemento na árvore

struct no *pesquisa(struct no **r, char *chave)
{
     int comp;
     if(r == 0) // Não olhar elemento
        return 0;

     comp = strcmp(chave,(*r)->chave);
     if(comp == 0) // elemento na raiz
            return(*r);

     if(comp >0)
             return(pesquisa(&((*r)->esq), chave));
     else
         return(pesquisa(&((*r)->dir), chave)); 
}


// Rotina para se listar a árvore

void imprimir(struct no *v)
{
     if(v!=NULL)
     {
          printf("%s %d\n", v->chave, v->dado);
          imprimir(v->esq);
          imprimir(v->dir);
     }
}

// Método para se buscar o tamanho da árvore

int tamanho(struct no *r)
{
    if(r==0)return 0;
    return (1+tamanho(r->esq)+tamanho(r->dir));
}


main()
{
     int altura;
     struct no *raiz = 0;
     struct no *pesq;
     
     // Invoca-se método para se inserir elementos na árvore
     
     inserir(&raiz, "J", 1);
     inserir(&raiz, "O", 2);
     inserir(&raiz, "D", 3);
     inserir(&raiz, "Q", 4);
     inserir(&raiz, "G", 5);
     inserir(&raiz, "L", 6);
     inserir(&raiz, "C", 7);
         
     // Invoca método para se listar os elementos da árvore
     
     imprimir(raiz);
     
          // Invoca-se método para se saber a altura da árvore
     altura = tamanho(raiz);
     
     // Imprime-se a altura da árvore
     
     printf("\nO tamanho da arvore e %d\n", altura);
     
     // Invoca método para se pesqisar um elemento na árvore
     
     pesq = struct no *pesquisa(&raiz,"O");
     
     // Lista-se o elemento pesquisado
     
     printf("%s %d", (pesq)->chave, (pesq)->dado);
     
     getch();
}

8 Respostas

Diegomoco 7 de out. de 2008

struct no *pesquisa(struct no **r, char *chave)  

________________________________________________________
   
      // Invoca método para se pesqisar um elemento na árvore  
        
      pesq = struct no *pesquisa(&raiz,"O");  
        
     
 }

Pow cara faz tempo que não mexo com C, mas pra que é esse * aí? acho que não tem isso pelo menos na hora que você chama a função. Tipo assim na linha 51 creio que tem que ter por ser um ponteiro para struct, mas na linha 118 acho que não precisa não.
Não sei se é isso.

E cadê os protótipos das sua funções?

fiaux 7 de out. de 2008

Diegomoco:

E cadê os protótipos das sua funções?

Se você cria a função main como última não precisa dos protótipos de função.
Faça o que Diegomoco disse, na linha 118 remova o *.

OBS: poste isso em Outras Linguagens

jorgefrancisco 7 de out. de 2008

Creio que remover o * não vai adiantar… não faz sentido nenhum essa sintaxe…

é só fazer:

pesq = pesquisa(raiz,"string procurada");

Mas mesmo assim creio que não vai funcionar pois tem muita coisa estranho no seu código. Tente rever alguns conceitos de ponteiros…

ps.: não é necessário usar ponteiro de ponteiro na função pesquisar, pois você não vai mudar o valor (endereço) da raiz…

Abraços!

Diegomoco 7 de out. de 2008

Se você cria a função main como última não precisa dos protótipos de função.
Faça o que Diegomoco disse, na linha 118 remova o *.

OBS: poste isso em Outras Linguagens

Hum ta não sabia ou não lembrava disso hehehe
Mas até que ta bom, acertei o que tava errado, faz tempo que não mecho com C.

Valder_Olmo_Correa 7 de out. de 2008

Olá, galera, obrigado pela ajuda.
Fiz aí o que vocês propuseram, mas continuava a dar problema.
Aí refiz o método pesquisa, mudei os ponteiros e deu certo.
O problema é que nem sei o por que deu certo, a invocação do método está ok, entendi, mas os ponteiros continuam sendo um parto.
Sei que tenho que estudar bastante isso, mas meu tempo é curto.
Bem, de qualquer forma, muito obrigado pela ajuda, espero agora que me ajudem com o método de se excluir um elemento do árvore, posarei meu código aqui daqui a pouco.
Se alguém pudesse me explicar como funcionam esses ponteiros de uma forma mais simples, agradeceria.
Bem, vejam como ficou o método pesquisa e sua invocação:

struct no *pesquisa(struct no **r, char *chave)
{
     int comp;
     if(r == 0) // Não olhar elemento
        return 0;

     comp = strcmp((*r)->chave, chave);
     if(comp == 0) // elemento na raiz
            return(*r);

     if(comp >0)
             return(pesquisa(&((*r)->esq), chave));
     else
         return(pesquisa(&((*r)->dir), chave)); 
}

Invocação do método pesquisa e impressão do elemento pesquisado:

pesq = pesquisa(&raiz,"O");
     
     // Lista-se o elemento pesquisado

         printf("%s %d", (pesq)->chave, (pesq)->dado);

Valder_Olmo_Correa 7 de out. de 2008

Jorge, sei que não é necessáro usar ponteiro de ponteiro, mas foi a única maneira que consegui fazer isso funcionar :shock:

Valder_Olmo_Correa 7 de out. de 2008

Agora estou com dúvida no método de remoção, acho que este é o mais complicado.

Está dando muitos erros. Se alguém pudesse dar ma força, agradeceria mais uma vez.

Vejam o código:

void remove(struct no **r, char *ele)
{
     struct no *p;
     if(*r==NULL)
     {
         return (1); // elemento encontrado
     }
     if(*ele = = (*r)->chave == ele) // Elemento encontrado na raiz
     {
         p = *r;
         if((*r)->esq == NULL)
         {
            *r = (*r)->dir; // Raiz não tem filho esquerdo
         }
         else
         {
             if((*r)->dir == NULL)
             {
                *r = (*r)->esq; // Raiz não tem filho direito
                                // Raiz tem ambos filhos
             }
             else
             {
                    p = Tmenor(&((*r)->esq));
                    (*r)->chave = p->chave;
             }
             free(p);
             printf("\n O elemento achado foi removido");
         }
     }
     else
     {
        if((*ele<(*r)->chave == 1))
        {
            return(&((*r)->esq),chave); // procura na árvore da esquerda
        }
        else
        {
            return(&((*r)->dir),chave); // procura na árvore da direita
        }
     }
  }
}

O seguinte método é auxiliar para o método remove

// Método auxiliar do método remove

void del(struct no **q, struct no **v)
{
     if((*v)->dir!=NULL)
     {
         del(q,&((*v)->dir));
     }
     else
     {
         (*q)->chave = (*v)->chave;
         (*q) = *v;
         *v = (*v)->esq;
     }
     return;
}

Invocação do método remove

remove(&raiz, "J");

Aqui estou bem mais perdido !

Valeu aí, galera !!!

Valder_Olmo_Correa 12 de out. de 2008

Galera, está dando um errinho só na rotina auxiliar (del) da rotina para se excluir um elemento (excluir).

Será que alguém poderia dar mais essa mãozinha em C, por favor ?
O método excluir, em um determinado momento invoca o método del para fazer fazer a procura do elemento sucessor, mas nesse método, del, está dando um erro que não consigo resolver. Alguém por favor me ajude.

Está dadno o seguinte erro na linha 103:

Incompatible types in assignment

Vejam o código abaixo:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h> 
#include <malloc.h>

struct no
{
     char chave[20];
     int dado;
     struct no *esq;
     struct no *dir;
};

typedef struct no *arvore;
arvore root = NULL;



// Rotina para se inserir elementos na árvore

void poe(struct no **r, char *chave, int dado)
{
     int cmp;
     
     if(*r==0)
     {
         // Temos aqui uma árvore vazia
         *r = malloc(sizeof(struct no));
         strcpy((*r)->chave, chave);
         (*r)->dado = dado;
         (*r)->esq = 0;
         (*r)->dir = 0;
         return;
     }
     
     cmp = strcmp((*r)->chave, chave);
     if(cmp==0)
     {
         (*r)->dado = dado;
         return;
     }

     if(cmp>0)
     {
         poe(&((*r)->esq),chave,dado);
         return;
     }
     
     poe(&((*r)->dir),chave,dado);
     return;
}

// Método para se pesquisar um elemento na árvore

struct no *pesquisa(struct no **r, char *chave)
{
     int comp;
     if(*r == 0) // Não olhar elemento
        return 0;

     comp = strcmp(chave,(*r)->chave);
     if(comp == 0) // elemento na raiz
            return(*r);

     if(comp >0)
             return(pesquisa(&((*r)->dir), chave));
     else
         return(pesquisa(&((*r)->esq), chave)); 
}


// Rotina para se listar a árvore

void imprimir(struct no *v)
{
     if(v!=NULL)
     {
          printf("%s %d\n", v->chave, v->dado);
          imprimir(v->esq);
          imprimir(v->dir);
     }
}

// Método para se buscar o tamanho da árvore

int tamanho(struct no *r)
{
    if(r==0)return 0;
    return (1+tamanho(r->esq)+tamanho(r->dir));
}

// Método auxiliar para o método excluir

void del(struct no **q, struct no **r)
{
     if((*r)->dir!=NULL)
     {
         del(q,&((*r)->dir));
     }
     else
     {
         (*q)->chave = (*r)->chave;
         (*q) = *r;
          *r = (*r)->esq;
     }
     return;
}

// Método para se excluir elemento da árvore

void excluir(struct no **p, char *chave)
{
     struct no *q;
     if(*p == NULL)
     {
           printf("\n Elemento não existe");
     }
     else if(chave<(*p)->chave)
     {
          excluir(&((*p)->esq),chave);
     }
     else if(chave>(*p)->chave)
     {
          excluir(&((*p)->dir),chave);
     }
     else
     {
         q = *p;
         if(q->dir==NULL)
         {
             *p = q->esq;
         }
         else if(q->esq==NULL)
         {
              *p = q->dir;
         }
         else
         {
             del(&q,&(q->esq));
         }
         free(q);
     }
     return;
}

main()
{
     struct no *pesq;
     struct no *raiz = 0;
     int altura;
     poe(&raiz, "J", 1);
     poe(&raiz, "O", 2);
     poe(&raiz, "D", 3);
     poe(&raiz, "Q", 4);
     poe(&raiz, "G", 5);
     poe(&raiz, "L", 6);
     poe(&raiz, "C", 7);
     
     
     // Invoca-se método para se lisar os elementos da árvore
     imprimir(raiz);
     
     // Invoca-se método para se saber a altura da árvore
     altura = tamanho(raiz);
     
     // Imprime-se a altura da árvore
     pesq = pesquisa(&raiz,"D");
     
     printf("\nO tamanho da arvore e %d\n", altura);
     
     if(pesq == NULL)
        printf("\nElemento nao encontrado\n");
     else
     printf("%s %d\n", pesq->chave, pesq->dado);
     
     // Invoca método para se remover elemento da árvore
     
     excluir(&raiz, "C");
     
     getch();
}

Criado 7 de outubro de 2008

Ultima resposta 12 de out. de 2008

Respostas 8

Participantes 4

8 Respostas

Topicos relacionados