Simulação de msdos utilizando árvore binária

[Antoniazzi 0]

Olá, pessoal.

 

Estou com um grande problema num trabalho da graduação.

Precisamos projetar uma espécie de msdos em linguagem c utilizando árvore binária, com comandos como mkdir, edit, cd, cd.., rmdir, etc.

O problema é que não consigo colocar em código uma estrutura de árvore que difira arquivos de diretórios. Sei que preciso colocar uma variável na estrutura da minha árvore quando selecionar um comando mkdir diretorio1, por exemplo, setar essa flag de uma maneira que eu consiga manipular esse nó depois e saber se ele é um diretório ou um arquivo.

A estrutura da minha árvore binária é: cada pai pode ter apenas dois filhos (árvore binária), esses filhos podem ou ser dois diretórios, ou dois arquivos, ou um arquivo e um diretório. A condição para um arquivo ser um arquivo é ele não possuir filhos.

E preciso implementar isto com alguma função que fique printando a hierarquia do diretório atual (c:\d\e\)constantemente.

 

Acredito que a estrutura da minha árvore seria parecida come essa, onde a variável isFile seria o meu flag sinalizador de diretório (isFile=0) e arquivo (isFile=1)

typedef struct nodo{
 int isFile;
 char parametro;
 struct nodo * esquerda;
 struct nodo * direita;
}nodo;

 

Essa variável parâmetro é o parâmetro que passo pra função de criar nó e atribuindo assim o nome do possível diretório ou arquivo.

 

Espero que alguém possa me dar uma luz.

 

 

Obrigado.

[GBecker 51]

Antoniazzi,

 

Se você está pensando em armazenar o nome do arquivo ou diretório na variável char parâmetro, não vai dar certo. Pois ela só armazena 1 caracter.

 

Acho que você pode pensar na estrutura e implementação parecido com uma lista encadeada. Só mudaria um pouco o código.

 

Outra coisa, não está faltando um ponteiro nesta sua estrutura de nodo? Um ponteiro que aponte para o nodo pai??

Se lá no teu algoritmo de busca ou remoção, como vai saber quem é o pai do nodo??

 

Espero ter ajudado, FLW!

[Antoniazzi 0]

Não posso passar uma palavra por aquela variável parâmetro?

Como assim ponteiro para o nodo pai?

Infelizmente estou perdido.

[GBecker 51]

Antoniazzi,

 

Não, pois char só armazena um caracter. Para armazenar uma string você deve utilizar vetor de char.

char strString[80];

 

Quanto a segunda dúvida, não precisa do ponteiro. Mas deve ter cuidado para não perder a referência à base da árvore.

 

http://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria

[Antoniazzi 0]

Irei declarar a minha struct assim:

typedef struct nodo{
 char parametro[80];
 int isFile;
 struct nodo * esquerda;
 struct nodo * direita;
}nodo;

 

A minha inicialização de nódulo assim:

//inicialização de um nodo
nodo * cria_elemento(char parametro){
nodo * novo=malloc(sizeof(nodo));
   novo->parametro=parametro;
   novo->esquerda = NULL;
   novo->direita = NULL;
   novo->isFile= 0;
   return novo;
}

 

Eu poderia fazer uma coisa deste tipo?

int isFile = 0;
if(parametro<(*arv)->parametro)&&((*arv->)isFile == 0){ //testa se a informação é menor que a informação anterior,
// que é a informação que está na memória, testa se o nodo pai é um diretório
           printf("Inserindo na esquerda");
           insere_folha(&(*arv)->esquerda,info,isFile);//insere arquivo no nodo da esquerda,seta nodo como arquivo

 

Este é um trecho da minha lógica de inserção de diretórios (a partir da estrutura básica de uma árvore binária) com as soluções técnicas emergenciais necessárias para o código conseguir verificar a diferença entre arquivos e diretórios.

[Vernon 0]

Galera, estou com um problemão para quinta de manhã.

 

Preciso fazer uma árvore binária que represente o organograma de uma empresa de atacado e varejo. Aí, que os setores (folhas) podem vender produtos, que serão registrados no momento da venda em uma lista duplamente encadeada. funciona assim: tu cria a árvore (C,D,B,A,E, por exemplo), depois decide que o setor B vai vender algum produto. aí que se cria a lista dupla para receber este produto. aí é que está morando o problema, não to conseguindo 'encadear' a lista ao setor responsável por ela. Em teoria, deve-se fazer uma pesquisa pela árvore que retorne apenas o setor pesquisado. Este setor retornado deve ser inserido (penso eu) lista->anterior da lista de produtos.

 

Alguém me quebra esse galho aí? (¬¬ galho... árvore... o trocadilho infame....XD)

 

Valewww

[GBecker 51]

Vernon,

 

Acho que você está confundindo os conceitos. Lista encadeada é uma coisa e Árvore binária é outra.

 

O modo de implementá-las pode ser parecido, mas o conceito que deve vê-las é diferente.

 

http://pt.wikipedia.org/wiki/Lista_ligada

 

http://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria

 

Espero ter ajudado, FLW! :grin:

[Vernon 0]

Infelizmente, não estou não. É o que minha professora está pedindo. Na estrutura da folha tem a sigla, que serve para localizar a folha e um ponteiro para uma lista duplamente encadeada, que receberá os produtos a serem vendidos.

   //Operacoes sobre arvore de busca binaria  
#include<stdio.h>  
#include<stdlib.h> 


barra() {printf("#################################################### \n"); }
//Definicao da lista de produtos  
typedef struct No_Produto{ 
   int codigo;
   char descricao[30]; 
   float  preco; 
   int    qtd;  
   struct No_Produto *ant; 
   struct No_Produto *prox;  
} No_Produto; 

// Criação do produto
No_Produto * criar_elemento(int codigo, char descricao[30], float preco,int qtd){
//  printf("criado. \n");
 No_Produto *novo;
 novo = (No_Produto *) malloc(sizeof(No_Produto));
 novo->codigo = codigo;
 strcpy(novo->descricao, descricao);
 novo->preco = preco;
 novo->qtd = qtd;
 novo->prox  = NULL;
 novo->ant = NULL;
 return novo;
}

//A inserção de produto na lista será sempre na ultima posição.
No_Produto * insere_primeiro(No_Produto * lista, No_Produto * novo){
  if (lista != NULL){
    lista->ant = novo;
    novo->prox = lista;
  }
  return novo;
}

No_Produto * retorna_ultimo_da_lista(No_Produto * lista){
 while (lista->prox != NULL){
   lista = lista->prox;
 }
 return lista;
}

No_Produto * insere_ultimo(No_Produto * lista, No_Produto * novo){
 if (lista != NULL) {
   No_Produto * n = retorna_ultimo_da_lista(lista);
   n->prox = novo;
   novo->ant = n;
   return lista;
 }else{
   return novo;
 }
}
/**/

void apresenta_lista(No_Produto * lista){
 //Percorrendo os elementos da lista
  int cont = 0;
  if (lista == NULL) {
      barra(); 
      printf("\n\n\n\t Lista de produtos esta vazia!\n\n\n");
        barra(); 
  }
  while (lista != NULL){
     printf("Produto %d: \n\t Codigo: %d \t - Descricao: %s\t Preco: %.2f \t Quantidade: %d\n",(cont+1),lista->codigo, lista->descricao, lista->preco,lista->qtd);
     cont++;
     lista = lista->prox;
  }
}

void lista_inversa (No_Produto *lista) {}
//Definicao da arvore 
typedef struct nodo{  
  struct No_Produto * lista_produtos;   
  struct nodo * esq;  
  char   sigla; 
   struct nodo * dir; 
} nodo; 


//-------------- ÁRVORE ---------------------------// 
//Criacao de um nodo da arvore 
nodo * cria_elemento(char sigla){  
  nodo * novo = malloc(sizeof(nodo));  
  novo->sigla = sigla; 
  novo->esq = NULL; 
  novo->dir = NULL;  
  novo->lista_produtos = NULL;  
  return novo; 
} 

//Inclusao de um nodo na arvore 
void insere_nodo(nodo ** arv, char sigla){ 

   if (*arv == NULL){  
     *arv = cria_elemento(sigla);

   }else{  
     if(sigla < (*arv) ->sigla){ 
     printf("Inserindo na Esquerda. \n"); 
     insere_nodo(&(*arv) ->esq, sigla); 
     }else if (sigla > (*arv)->sigla){ 
       printf("Inserindo na Direita. \n"); 
       insere_nodo(&(*arv) ->dir, sigla);  
     } 
   } 
}

void ve_arvore(nodo * arv){
 if (arv != NULL) {
    printf("%c \n",arv->sigla);
    if (arv->esq != NULL){
       printf("Nodo Esquerdo. \n");
       ve_arvore(arv->esq);
        if (arv -> lista_produtos == NULL ) {
           printf ("\nLista de Produtos vazia\n");
        }   
    }
    if(arv->dir != NULL){
       printf("Nodo Direito. \n");
       ve_arvore(arv->dir);
        if (arv -> lista_produtos == NULL ) {
        printf ("\nLista de Produtos vazia\n");
    }
 }  
 } else {
    barra(); 
    printf("\n\n\t\t Lista de Setores Vazia\n\n\n");
    printf("#################################################### \n"); 
 }
}
/*
nodo * vende (nodo * arv,No_Produto * lista,setor) {
   nodo *aux = NULL;
//    return aux;
   aux = pesquisar_nodo(nodo *arv,setor);
}
*/
/*transformar em função para que retorne apenas o setor encontrado. Nesse setor, 
inserir a lista de produtos.
*/
nodo * pesquisar_nodo(nodo * arv, char pesq){//onde começa e a informação a ser inserida.
 nodo * aux = arv;
 if (arv != NULL){
    if (arv->sigla == pesq){
       aux->sigla = arv->sigla;
       return aux;

    }else{
      if (pesq > arv->sigla){
         printf("Pesquisando a direita. \n");
         pesquisar_nodo(arv->dir, pesq);
      }else{
         printf("Pesquisando a esquerda. \n");
         pesquisar_nodo(arv->esq, pesq);
      }
    }
 }else{
           return 0;
 }
}

//Monta o menu do programa  
void monta_menu(){  
   barra();
   printf("Manutencao de Setores e Produtos Comercializados  \n"); 
   printf("\tSelecione a Opcao Desejada: \n"); 
   printf("\t   1  -  Incluir Setor \n"); // ok
   printf("\t   2  -  Vender produto no setor informado\n"); 
   printf("\t   3  -  Apresentar total de vendas no setor informado  \n"); 
   printf("\t   4  -  Apresentar total de venda por setor (todos setores)\n"); 
   printf("\t   5  -  Verificar se o produto informado foi vendido no setor informado \n"); 
   printf("\t   6  -  Verificar se o produto informado foi vendido em algum dos setores\n");
   printf("\t   7  -  Verificar arvore inteira\n");
   printf("\t   8  -  Ajuda\n");  
/*  printf("\t   7  -  Cadastrar Produtos\n"); //ok - 
   printf("\t   8  -  Mostrar Lista de Produtos\n"); //ok*/
   printf("\t   0  -  Sair \n"); 
      barra();
} 

void help() {
    system ("cls");
    barra();
    printf ("\tTabela de ajuda\n\n");
    printf("\t   1  -  Incluir Setor: inclusao de setores no organograma. Inclui tambem produtos, quanto este setor realizar vendas \n");
    printf("\t   2  -  Pesquisa por setor, para acionar o sistema de vendas \n");
    printf("\t   3  -  Apresenta o total de vendas no setor informado\n");
    printf("\t   4  -  Apresenta o total de vendas em todos os setores\n");
    printf("\t   5  -  Verifica se o produto foi vendido naquele setor\n");
    printf("\t   6  -  Verifica se o produto foi vendido em algum setor\n");
    printf("\t   7  -  Verifica todos os setores e mostra os produtos vendidos em cada um\n");
    printf("\t   8  -  Chama este painel de ajuda\n");
    printf("\t   Comandos Ocultos:\n");
    printf("\t   9  -  Apresenta a lista inversa de produtos dentro de um setor.\n");
    printf("\t   10  - apresenta todos os setores e mostra os produtos vendidos em cada um em ordem inversa\n");
    barra();
    system ("pause");
    system ("cls"); 
}

int main(){    
  int op,codigo,qtd, opt;
  float preco;
  char sigla,setor;  
  nodo * arv = NULL; 
  No_Produto *lista = NULL;


  do{ 
   monta_menu(); 
   printf ("Agora, entre com a sua opcao: \a");
   scanf("%d", &opt);  
     system("cls"); 
   switch(opt){  
       case 1: 

            sigla = '\0';
          while (sigla != '@'){

           if (sigla != '@'){
             if (arv == NULL) {
                insere_nodo(&arv, sigla);
                printf("Digite a sigla do Setor: ");
                scanf(" %s", &sigla);
             } else if (arv != NULL) {
               insere_nodo(&arv, sigla);
               printf("Digite a sigla do Setor: ");
               scanf(" %s", &sigla);    
             }
           }    
       } system ("cls");

       break;  
       case 2: 
        printf("Informe a letra a ser pesquisada na Arvore: \n");
         scanf(" %c", &setor);
         //pesquisar_nodo(arv, setor);
         /*No_Produto *n = criar_elemento(1,"caneta",5.2,50);
          lista = insere_ultimo(lista, n);*/
          //vende (arv,lista,setor);

          break;  
       case 3: 
          break;
       case 4: 
          break;
       case 5: 
          break;
       case 6:
          break;
       case 7:
         ve_arvore (arv);
          break;
       case 9: apresenta_lista(lista);
          break;
       case 11: lista_inversa (lista);
          break;
       default : printf("Opcao Invalida\n"); break;
      case 8:help();
         break;
   } 
  }while (opt != 0);
  monta_menu();  
}