/* ////////////////////////////////////////////////////////
// Seção 1: Comunicação com o sistema operacional
//////////////////////////////////////////////////////// */
/* O programa terminou de maneira anormal. */
#define EXIT_FAILURE 1
/* O programa terminou normalmente. */
#define EXIT_SUCCESS 0
/* A função exit interrompe a execução do programa e fecha
// os arquivos que o programa tenha porventura aberto. Se
// status = 0, o sistema operacional é informado de que o
// programa terminou com sucesso; caso contrário, o sistema
// operacional é informado de que o programa terminou de
// maneira excepcional. Uso típico: exit( EXIT_FAILURE). */
void exit( int status);
/* ////////////////////////////////////////////////////////
// Seção 2: Números pseudoaleatórios
//////////////////////////////////////////////////////// */
#define RAND_MAX 32767
/* A função devolve um número inteiro aleatório entre
// 0 e RAND_MAX inclusive, ou seja, um número inteiro
// no intervalo fechado 0..RAND_MAX.
// Uso típico: i = rand( ). */
int rand( void);
/* A função srand define uma "semente" para a função rand.
// Ela deve ser chamada antes do primeiro uso de rand para
// que a sequência de números devolvidos por rand não seja
// sempre a mesma.
// Uso típico: srand( time( NULL)). */
void srand( unsigned int);
/* ////////////////////////////////////////////////////////
// Seção 3: Conversão de strings em números
//////////////////////////////////////////////////////// */
/* A função atoi recebe uma cadeia de caracteres que
// representa um número inteiro em notação decimal e
// converte essa cadeia no número inteiro correspondente.
// Uso típico: i = atoi( s). Exemplo:
// atoi( "-1234") vale -1234,
// atoi( "1234") vale 1234.
// É responsabilidade do usuário garantir que o número
// representado pela cadeia pertence ao intervalo fechado
// INT_MIN..INT_MAX. */
int atoi( char *);
/* A função atof recebe uma cadeia de caracteres que
// representa um número real em notação decimal e
// converte essa cadeia no número real correspondente.
// Exemplo: o valor de atof( "1234.99") é 1234,99.
// Uso típico: f = atof( str). */
double atof( char *);
/* ////////////////////////////////////////////////////////
// Seção 4: Alocação de memória
//////////////////////////////////////////////////////// */
#define NULL 0
typedef unsigned int size_t;
/* A função recebe um número inteiro, digamos N, e aloca
// N bytes consecutivos na memória. Devolve o endereço do
// primeiro byte alocado. Se não puder alocar os N bytes,
// malloc devolve NULL. Uso típico: pntr = malloc( N). */
void *malloc( size_t);
/* A função recebe o endereço de um bloco de bytes
// previamente alocado por malloc. A função desaloca
// (= libera) o bloco de bytes.
// Uso típico: free( pntr). */
void free( void *);
/* ////////////////////////////////////////////////////////
// Seção 5: Busca binária
//////////////////////////////////////////////////////// */
/* A função bsearch recebe o endereço key de um objeto e um
// vetor base[0..nmemb-1] de objetos. Cada objeto ocupa
// size bytes. O vetor está em ordem crescente, sendo a
// comparação entre elementos do vetor dada pela função
// compar (veja detalhes abaixo). A função devolve o
// endereço de um elemento do vetor que tenha valor igual
// a *key ou devolve NULL se tal elemento não existe. */
void *bsearch( const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)( const void *, const void *));
/* ////////////////////////////////////////////////////////
// Seção 6: Ordenação
//////////////////////////////////////////////////////// */
/* A função qsort rearranja o vetor base[0..nmemb-1]
// em ordem crescente. Cada elemento ocupa size bytes.
// A comparação entre elementos do vetor é dada pela
// função compar. (Detalhes abaixo.) */
void qsort( void *base, size_t nmemb, size_t size,
int (*compar)( const void *, const void *));
|
A função qsort rearranja o vetor base[0..nmemb-1] em ordem crescente. (O endereço do primeiro elemento do vetor é base e o vetor tem nmemb elementos.) A natureza dos elementos do vetor não importa, mas qsort precisa saber que cada elemento ocupa size bytes. Eis o protótipo da função:
void qsort( void *base, size_t nmemb, size_t size,
int (*compar)( const void *, const void *));
O último argumento de qsort é uma função compar, que recebe os endereços (moldados por void *) de dois elementos do vetor e devolve um inteiro
A função qsort é, essencialmente, uma implementação do algoritmo Quicksort.
int cmp( const void *x, const void *y) {
return (*(int *)x - *(int *)y);
}
então o comando
qsort( a, n+1, sizeof (int), cmp);
rearranja o vetor a[0..n] em ordem crescente.
int cmp( const void *x, const void *y) {
return strcmp( *(char **)x, *(char **)y);
}
então o comando
qsort( str, n+1, sizeof (char*), cmp);
rearranja o vetor str[0..n] em ordem lexicográfica.
struct al {
char nome[81];
int nota;
};
typedef struct al aluno;
aluno a[1000];
A seguinte função compara os alunos apontados por x e y com base nas suas notas:
int cmp( const void *x, const void *y) {
int notax, notay;
notax = ((aluno *)x)->nota;
notay = ((aluno *)y)->nota;
return notax - notay;
}
Para rearranjar o vetor a[0..n-1] em ordem crescente de notas, basta dizer
qsort( a, n, sizeof (aluno), cmp);