Funçoes importantes para prog.2

Prévia do material em texto

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 //Bolha para inteiros
static int compInt(int a,int b)
{
return a > b;
}
void bolhaInt(int* v, int n)
{
int i,j,haTroca;
int temp;
for (i=n-1;i>0;i--)
 {
 haTroca= 0;
 for (j=0;j<i;j++)
 {
 if (compInt(v[j],v[j+1]))
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 haTroca= 1;
 }
 }
if (haTroca==0)
 return;
 }
}
 //Bolha para strings
 
static int compStr(char * a,char * b)
{
 return (strcmp(a,b) > 0);
}
void bolhaStr(char ** v, int n)
1
{
 int i,j,haTroca;
 char *temp;
 for (i=n;i>0;i-)
 {
 haTroca=0;
 for (j=0;j<i;j++)
 {
 if (compStr(v[j],v[j+1]))
 {
 temp = v[j];v[j] = v[j+1];v[j+1] = temp;
 haTroca=1;
 }
 }
if (haTroca==0)
 return;
 }
}
 //Quick sort para inteiros
static int cmpInt(int a,int b)
{
return a < b;
}
void quicksort(int n,int * v)
{
int x = v[0];
int temp;
int a = 1;
int b = n-1;
if (n<=1)
 return;
do
 { 
 while(a < n && !cmpInt(v[a],x) )
 a++;
while( cmpInt(v[b],x) )
 b--;
if(a < b)
 {
2
 temp = v[a];
 v[a] = v[b];
 v[b] = temp;
 a++;
 b--;
 }
 }
while(a <= b);
 v[0] = v[b];
 v[b] = x;
 quicksort(b,v);
 quicksort(n-a,&v[a]);
}
 //Busca binaria para inteiros
static int compInt(int c,int b)
{
if (c < b)
return-1;
else if (c > b)
return 1;
else
return 0;
}
int buscaInt(int n,int * v,int c)
{
int ini=0;
int fim=n-1;
int meio, cmp;
while (ini <= fim)
 {
 meio=(ini+fim)/2;
 cmp = compInt(c,v[meio]);
if (cmp <0)
 fim=meio-1;
else
 if (cmp >0)
 ini=meio+1;
else
 return meio;
 }
3
return-1;
}
 //Busca binaria em strutura
struct pessoa
{
 char * nome;
 int idade;
};
typedef struct pessoa Pessoa;
static int compPessoa(char * a, Pessoa * b)
{
return strcmp(a,b->nome);
}
int buscaPes(int n, Pessoa ** v, char * nome)
{
int ini=0;
 int fim=n-1;
int meio, cmp;
while (ini <= fim)
 {
 meio=(ini+fim)/2;
 cmp=compPessoa(nome,v[meio]);
 if (cmp<0)
 fim=meio-1;
else if (cmp>0)
 ini=meio+1;
else
 return meio;
 }
 return-1;
}
4