Ordenação e pesquisa binária em C. [RESOLVIDO]

trust
(usa Kurumin)

Enviado em 01/12/2015 - 16:53h

Boa tarde.
Preciso criar um programa que oderne um vetor em linguagem C e realizar pesquisa binária nele.
Os campos são nome e telefone.
Até consegui fazer o cadastro do vetor e a pesquisa de um campo, mas não consigo ordenar nem mostrar o nome o telefone na busca binária.
Alguém tem algum exemplo para que eu possa ver como funciona.
Montei o programa já a partir de exemplos, já que não mexo com programação.

Obrigado.

uilianries
(usa Linux Mint)

Enviado em 01/12/2015 - 21:00h

Pode ordenar utilizando quick sort, a biblioteca do C já possui uma função com o algoritmo de quick:

http://linux.die.net/man/3/qsort

Após ordená-lo, pode usar o binary search. A biblioteca do C também já possui uma função com o algoritmo:

http://linux.die.net/man/3/bsearch

#include <stdlib.h>



int pstrcmp(const void *p1, const void *p2)

{

	return strcmp(*(char * const *)p1, *(char * const *)p2);

}



int main()

{

    char* strings[100];

    int nstrings;

    qsort(strings, nstrings, sizeof(char *), pstrcmp);



    //Aplique bsearch aqui ...





    return 0;

}

 

Não utilize strcmp diretamente com qsort, aqui tem a explicação:
http://c-faq.com/lib/qsort1.html

trust
(usa Kurumin)

Enviado em 02/12/2015 - 22:39h

Tenho este código abaixo fazendo mais ou menos o que eu expliquei anteriormente.
Preciso que ao invés do vetor que ele lê e processa, seja lido e processado o struct do início do código. Após preciso que a ordenação seja feita pelo número do telefone e na pesquisa pelo telefone apareça o nome da pessoa.
Já testei mas não tem jeito de funcionar.

#include <stdio.h>

#include <stdlib.h>

#define max 10



void le_vetor(int v[]);

int le_valor();

void ordena(int v[]);

int pesq_bin(int v[],int n, int comeco, int fim);



int main()

{	int /*v[max]*/num,p;

    struct pessoa

    {

     char nome[30];

     int telefone;

     };

    struct pessoa v[max];



	le_vetor(v);

	num=le_valor();

	ordena(v);

	p=pesq_bin(v,num,0,max-1);

	if (p>=0)

	  printf("\nEncontrado, na posicao: %i do vetor",p);

	else

	  printf("\nNao foi encontrado!");

    return 0;

}

void le_vetor(int v[])

{	int x;

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

	{	printf("Digite o telefone %d: ",x+1);

		scanf("%d",&v[x]);

	}

}

int le_valor()

{ int n;

  printf("Digite o valor a procurar:");

  scanf("%d",&n);

  return n;

}

void ordena(int v[])

{

	int x,y,aux;

	for(x=0;x<max-1;x++)

	 for (y=x+1;y<max;y++)

	  if (v[x]>v[y])

	  {  aux=v[x];

	     v[x]=v[y];

	     v[y]=aux;

	  }

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

		printf("Vetor ordenado: %d: \n",v[x]);



}

int pesq_bin(int v[],int n, int comeco, int fim)

{	int meio,achou=-1;

	meio=(comeco+fim)/2;

	if (comeco<=fim)

    {   if (n==v[meio])

        {   achou=meio;

            return achou;

        }

        else

            if(n<v[meio])

                pesq_bin(v,n,comeco,meio-1);

            else

                pesq_bin(v,n,meio+1,fim);



    }

    else

        return achou;

 } 

vandcarlos
(usa Slackware)

Enviado em 03/12/2015 - 11:25h

Seguinte, você não está dizendo para o seu código quais campos da stuct ele deve acessar para fazer as comparações ou a pesquisa.
troque por exemplo

v[x]>v[y] 

para:

v.telefone[x]>v.telefone[y] 

mas somente nas comparações, quando for ordenar deixa do jeito que está se não o telefone do registro 1 vai para o 2 por exemplo

Outra coisa é quando você for invocar a função de forma recursiva
troque:

else

   if(n<v[meio])

        pesq_bin(v,n,comeco,meio-1);

     else

        pesq_bin(v,n,meio+1,fim);

 

para :

else{

    if(n<v[meio])

       return  pesq_bin(v,n,comeco,meio-1);

    else

       return  pesq_bin(v,n,meio+1,fim);

}

 

Por que se não, tirando o melhor caso todos os outros ficarão "travados" pois não tem nenhum outro comando a ser executado naquela função e não tem um return para a anterior :D