Classificação e Pesquisa

O desafio proposto é o de desenvolver um algoritmo que seja capaz de realizar a ordenação e busca de dados referente ao consumo de energia nas residências de um determinado município, dentro de um bairro com 1000 residências. O algoritmo criado para a realização desta ordenação e busca deve retornar todas as informações da residência, como número da casa, a rua, o número do medidor e a medida de consumo.

Para gerar números aleatórios foi dada a função randomInteger():

int RandomInterger(int low, int high){ int k; double d; d = (double) rand() / ((double) RAND_MAX + 1); k = d * (high - low + 1); return low + k; }

A função retorna um número inteiro dentro de um período LOW-HIGH.

Em seguida foi criada uma estrutura de dados para compor as informações de cada residência;

typedef struct{ char rua[25]; int numCasa; int numMedidor; float medidaConsumo; }estrutura;

E também uma estrutura do vetor que compõe a estrutura de cada residência, mais a chave de busca:

def struct{ int key; tipoResidencia estrutura; }vet;

MAIN()

Dentro da função principal do programa foi criado um vetor do tipo vet, composto de 1000 posições, o vetor recebe um sequencial para a chave e valores aleatórios para as informações da estrutura:

for(i=0; i < 1000; i++){ n = RandomInterger(0,1000); casa[i].key = i; casa[i].estrutura.numCasa = n; casa[i].estrutura.numMedidor = n; casa[i].estrutura.medidaConsumo = RandomInterger(0,5000); }

BUSCA SEQUENCIAL

Para a realização da busca sequencial foi criada uma função buscaSequencial().

Essa função recebe dois parâmetros, onde o primeiro parâmetro é um int do tipo chave, e o segundo é um ponteiro contendo o endereço da última posição do vetor:

int buscaSequencial(int c, int *p){ do{ if(c == *p){ return *p; } p--; }while(c != *p); }

A função percorrerá todo o vetor, até encontrar a chave e retornar um inteiro.

BUSCA BINÁRIA

Para busca binária foi criada uma função buscaBinaria().

Para a utilização desta ferramenta o vetor tem que estar ordenado. Essa função é básica, recebe como argumento a chave a ser encontrada:

int buscaBinaria(int c){ int ini = 0; int fim = 1000; int t; do{ t = (ini + fim) / 2; if(t == c){ return t; }

if(t < c){ ini = t; } if(t > c){ fim = t; } }while(c != t); }

Na função foram criadas duas variáveis: ini = primeira posição do vetor, fim = última posição do vetor. Também foi criada uma variável t que indica o meio.

Foi criada uma condição, enquanto t for diferente da chave. Os passos são:

 t recebe ini + fim / 2.

 Se essa divisão for igual a chave, se tem um retorno.

 Se t < c então o início passa a ser a divisão de t.

...