1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Prova especial, guardar lista em arvore ou vice-versa(Linguagem C)

Discussão em 'Programação' iniciada por Northuber, 29 de Junho de 2008. (Respostas: 3; Visualizações: 1019)

  1. Olá amigos, sou novo no fórum, estou precisando achar alguém que possa me ajudar no problema seguinte:
    Faco faculdade e vou ter que fazer prova especial, meu professor disse que vai dar na prova um pequeno exercício onde eu vou ter que guardar uma lista em uma árvore ou então uma árvore em uma lista.
    mas durante o semestre inteiro ele deixou consultar outros exemplos de exercícios que ele tinha dado na sala, só que para essa prova especial ele não deu nenhum exercício para treinar.
    E eu não tenho nenhum exemplo(ele sempre deixou consultar durante a prova os exerc que ele tinha dado na sala), eu só conseguia fazer os programas que ele mandava graças aos exemplos, alguem tem algum exemplo qualquer onde uma lista é guardada em uma arvore e também um exemplo onde uma árvore é guardada em uma lista?
    Obrigado.
     
  2. Só tens de iterar sobre todos os elementos da lista e adicioná-los a uma árvore.
     
  3. ravager

    ravager Power Member

    E tens de ter atenção ao critério de ordenação da árvore.
     
  4. Eu fiz mas nao esta dando certo e nao sei onde errei

    Eu fiz o que está abaixo, mas não sei onde está o erro. Esse e para guardar uma lista em uma arvore. (eu nao sei se eu posso colar o codigo aqui, ou se tem que ser em um site especifico, qualquer coisa me digam o site e eu edito e passo para um site)

    Código:
    #include<iostream.h>
    #include<conio.h>
    #include<alloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    
    //------------Lista
    typedef struct CelulaLista * ApontadorLista;
    
    struct DadosLista{
        int CHAVE;
    };
    
    struct CelulaLista{
        DadosLista REG;
        ApontadorLista PROX;
    };
    
    struct Lista{
        ApontadorLista PRI;
        ApontadorLista ULT;
        int TAM;
    };
    
    void FLVazia (Lista *l){
        l->PRI = NULL;
        l->ULT = l->PRI;
        l->TAM = 0;
    }
    
    int Vazia (Lista l){
        return (l.PRI == NULL);
    }
    
    int Tamanho (Lista l){
        return (l.TAM);
    }
    
    
    void InserirLista (DadosLista r, Lista *l){
        ApontadorLista aux;
        aux = (ApontadorLista) malloc (sizeof(CelulaLista));
        if(aux == NULL){
            cout<<"Erro, sem memoria para inserir";
            return;
        }
        aux->REG = r;
        aux->PROX = NULL;
        l->TAM++;
        if(Vazia(*l)){
            l->PRI = aux;
            l->ULT = l->PRI;
        }
        else{
            l->ULT->PROX = aux;
            l->ULT = aux;
        }
    }
    
    void Retirar(Lista *l, int chave){
        ApontadorLista aux, aux_ant;
        if (Vazia (*l)){
            cout<<"Lista Vazia!";
            return;
        }
        aux = l->PRI;
        if(aux==l->ULT){
            if(chave == aux->REG.CHAVE){
                cout<<"Chave Excluida";
                free(aux);
                FLVazia(l);
                return;
            }
            else{
                cout<<"Chave não encontrada";
                return;
            }
        }
        if(chave == l->PRI->REG.CHAVE){
            l->PRI=aux->PROX;
            cout<<"Chave Excluida";
            free(aux);
            l->TAM--;
            return;
        }
        aux_ant=aux;
        aux=aux->PROX;
        while(aux!=NULL){
            if(chave == aux->REG.CHAVE){
                if(aux == l->ULT){
                    aux_ant->PROX = NULL;
                    l->ULT = aux_ant;
                    l->TAM--;
                    free(aux);
                    cout<<"Chave excluida";
                    return;
                }
                aux_ant->PROX = aux->PROX;
                l->TAM--;
                free(aux);
                cout<<"Chave excluida";
                return;
            }
            aux_ant=aux;
            aux=aux->PROX;
        }
        cout<<"Chave não encontrada";
    }
    
    void MostrarLista(Lista *l, int *vetor){
           int i=0;
           ApontadorLista aux;
           aux = l->PRI;
           while(aux!=NULL){
                   cout<<aux->REG.CHAVE<<"\n";
                   vetor[i]=aux->REG.CHAVE;
                   i++;
                   aux = aux->PROX;
           }
    }
    
    
    
    void Consultar(Lista *l, int chave){
           ApontadorLista aux;
           if(Vazia(*l)){
                   cout<<"Lista Vazia";
                   return;
           }
           aux = l->PRI;
           while(aux!=NULL){
                   if(aux->REG.CHAVE == chave){
                           cout<<"Chave Encontrada: "<<aux->REG.CHAVE;
                           return;
                   }
                   aux = aux->PROX;
           }
    }
    
    //------------Árvore
    typedef struct CelulaArvore *ApontadorArvore;
    
    struct DadosArvore{
        int CHAVE;
    };
    
    struct CelulaArvore {
        DadosArvore  REG;
        ApontadorArvore ESQ, DIR;
    };
    
    void InserirArvore(ApontadorArvore raiz, DadosArvore r){
        ApontadorArvore novo;
        if(r.CHAVE < raiz->REG.CHAVE){
            if(raiz->ESQ == NULL){
                novo = (ApontadorArvore) malloc(sizeof(CelulaArvore));
                raiz->ESQ = novo;
                novo->REG = r;
                novo->ESQ = novo->DIR = NULL;
            }else
                InserirArvore(raiz->ESQ, r);
        }else if(r.CHAVE > raiz->REG.CHAVE){
                    if(raiz->DIR== NULL){
                        novo = (ApontadorArvore) malloc(sizeof(CelulaArvore));
                        raiz->DIR = novo;
                        novo->REG = r;
                        novo->ESQ = novo->DIR = NULL;
                    }else
                        InserirArvore(raiz->DIR, r);
                }else
                    cout<<"Chave duplicada";
                    getch();
    }
    
    int ContaNodos(ApontadorArvore raiz) {
         if (raiz == NULL)
             return 0;
         return ContaNodos(raiz->ESQ) + ContaNodos(raiz->DIR) + 1;
    }
    
    void BuscaOrdem(ApontadorArvore raiz){
        if(raiz == NULL)
            return;
        BuscaOrdem(raiz->ESQ);
        cout<<"\n"<<raiz->REG.CHAVE;
        BuscaOrdem(raiz->DIR);
    
    }
    
    //------------Main
    int main(){
       ApontadorArvore RAIZ = NULL;
       DadosArvore REG, vetArvore[10];
       int OP,CHAVE, vetor[10];
       DadosLista D;
       Lista L;
       DadosLista vet[10];
     
       FLVazia(&L);
      
        do{
            system("cls");
            cout<<"\n1-Inserir";
            cout<<"\n2-Listar";
            cout<<"\n3-Tamanho";
            cout<<"\n4-Sair da lista";
            cout<<"\nDigite a sua opcao:" ;
            cin>>OP;
    
            switch(OP){
                       case 1:
                            cout<<"\nDigite uma chave: ";
                            cin>>D.CHAVE;
                            InserirLista(D,&L);
                            break;
                       case 2:
                            MostrarLista(&L, vetor);
                            getch();
                            break;
                       case 3:
                            cout<<"\nTamanho: "<<Tamanho(L);
                            getch();
                            break;
                      case 4:
                            cout<<"\nFIM!";
                            getch();
                            break;
                      default:
                            cout<<"Opcao invalida!";
                            break;
            }
    
        }while(OP!=4);
       
        //Passa os dados do vetor do tipo int para o tipo DadosArvore
        for (int i=0; i<10; i++){
            vetArvore[i].CHAVE=vetor[i];
        }
       
        //Passa os dados do vetor para uma árvore.
       
        for (int j=0; j<10; j++){
            while(vetArvore[j].CHAVE != 0){
                if(RAIZ == NULL){
                    RAIZ = (ApontadorArvore) malloc(sizeof(CelulaArvore));
                    RAIZ->REG = vetArvore[j];
                    RAIZ->ESQ = RAIZ->DIR = NULL;
                    getch();
                }
               
                else{
                    InserirArvore(RAIZ, vetArvore[j+1]);
                }
            }
        }
        cout<<"A arvore tem "<<ContaNodos(RAIZ)<<" nodos";
        cout<<"\n\n Busca Ordenada: \n";
        BuscaOrdem(RAIZ);
        getch();
        MostrarLista(&L, vetor);
        getch();
        return 0;
    }
     
    Última edição pelo moderador: 30 de Junho de 2008

Partilhar esta Página