Função para calcular o tempo gasto para inserções e pesquisas em arvore Binária

GordonFreeman
(usa Ubuntu)

Enviado em 11/04/2012 - 22:39h

Pessoal tudo bem ?
É o seguinte tenho que criar uma função em C para medir o tempo gasto nas inserções e pesquisas em um árvore binária , esse tempo será usado como parâmetro para estudar a complexidade dessas funções inserção e busca na árvore balanceada e sem balancear. Vou ser sincero, se vocês pudessem me ajudar com o código seria bom, pois eu já li bastante sobre complexidade e tal, mas não sei nem onde começar, para criar essa função na prática. As funções inserção e pesquisa já estão prontas e tal , mas essa de calcular o tempo gasto não faço nem idéia.Se ajudar, posso postar o código da árvore se necessário.
Estruturas

typedef long TipoChave;

typedef struct Registro {

  TipoChave Chave;

  /* outros componentes */

} Registro;

typedef struct No * Apontador;

typedef struct No {

  Registro Reg;

  Apontador Esq, Dir;

} No;

typedef Apontador TipoDicionario; //Estrutura que representa  a árvore

 

pesquisa

void Pesquisa(Registro *x, Apontador *p)

{ if (*p == NULL) 

  { printf("Erro : Registro não esta presente na arvore\n");

    return;

  }

  if (x->Chave < (*p)->Reg.Chave) 

  { Pesquisa(x, &(*p)->Esq);

    return;

  }

  if (x->Chave > (*p)->Reg.Chave)

  Pesquisa(x, &(*p)->Dir);

  else

    *x = (*p)->Reg;

}

 

Inserção

void Insere(Registro x, Apontador *p)

{ if (*p == NULL) 

  { *p = (Apontador)malloc(sizeof(No));

    (*p)->Reg = x; (*p)->Esq = NULL; (*p)->Dir = NULL;

    return;

  }

  if (x.Chave < (*p)->Reg.Chave) 

  { Insere(x, &(*p)->Esq); return; }

  if (x.Chave > (*p)->Reg.Chave)

  Insere(x, &(*p)->Dir);

  else

    printf("Erro : Registro ja existe na arvore\n");

}

 

Código Função main Gera chaves aleatórias para inserção

for (i = 0; i < max; i++) 

    { x.Chave = vetor[i];    //vetor [i] é a chave aleatória que é gerada por outra função

       Insere(x, &Dicionario);  //Chama função e passa a chave e a árvore parar inserir

      printf("Inseriu chave: %d\n", x.Chave);

 }

 

Desde já, muito obrigado pessoal.

gokernel
(usa Linux Mint)

Enviado em 12/04/2012 - 12:13h

Tenta comparar o tempo com a função ( clock() );

Pega o valor ( long v1 = clock(); ) antes de rodar a sua funcao;
.... Execute a funcao ....
Pega o novo valor ( long v2 = clock(); ) e faça a comparacao dos 2 valores.

Ou use ( long v1 = time(NULL); ) ...

Estou no smart agora e não estou com vontade de ligar o note para testar. ;)

GordonFreeman
(usa Ubuntu)

Enviado em 12/04/2012 - 13:24h

gokernel valeu pela ajuda !!!Acho que essa função vai resolver meu problema , não conhecia funções desse tipo em C.Bom, vou estudar um pouco e implementar.Cara valeu mesmo, por ter ajudado, eu não tinha nem idéia de como fazer.