§1  EX12  UM EXEMPLO SIMPLES DE  1

1. Um exemplo simples de . Este programa recebe um arquivo texto e ordena as linhas em ordem alfabética (para ser mais preciso, na ordem lexicográfica induzida pela tabela ASCII). Por simplicidade,

assumimos que as linhas têm no máximo  caracteres e que o arquivo tem no máximo  linhas.

Observação. A versão do que estamos usando neste programa não mescla muito bem com o português: um projeto interessante seria encontrar uma solução simples para este problema.

#define  256
#define  8192

2. Usaremos a variável status para passar ao sistema operacional informação sobre o sucesso, ou não, da execução deste programa. A variável nome do prog é usada para guardar o nome do programa. #define 0 /∗ valor de status quando tudo correu bem ∗/

#define erro na alocacao de memoria 1

/∗ valor de status para quando ocorre erro na alocação de memória ∗/

⟨ Variáveis globais 2 ⟩ ≡ char ∗nome do prog ; int status = ;

This code is used in section 3.

3. Aqui está a estrutura geral do nosso programa .

⟨ Inclusão de arquivos sobre as bibliotecas 4 ⟩ ⟨ Variáveis globais 2 ⟩ ⟨ Função de ordenação 11 ⟩ ⟨ O programa principal 5 ⟩

4. Precisamos incluir os arquivos para as funções de entrada e saída e para as funções de alocação de memória. ⟨ Inclusão de arquivos sobre as bibliotecas 4 ⟩ ≡ #include /∗ para as funções de entrada e saída ∗/ #include /∗ para calloc( ), malloc( ), e free( ) ∗/ #include /∗ para as funções sobre cadeias de caracteres ∗/

This code is used in section 3.

5. Vamos começar com a função main. ⟨ O programa principal 5 ⟩ ≡

main(argc, argv )

int argc; /∗ o número argumentos na linha de comando ∗/ char ∗∗argv ; /∗ um vetor de strings, contendo os argumentos ∗/

{ ⟨ Variáveis locais a main 7 ⟩ nome do prog = argv [0]; ⟨ Leia a entrada 6 ⟩; ⟨ Ordene 10 ⟩; ⟨ Imprima o resultado 9 ⟩; exit (status );

}

This code is used in section 3.

2  UM EXEMPLO SIMPLES DE  EX12 §6

6. Façamos agora a leitura. Assumimos que a entrada vem em stdin, por simplicidade. Usamos a função gets ( ) de stdio.h para ler as linhas da entrada. Esta função lê toda a linha, substitui o símbolo de fim de linha por , que, na convenção de , marca o fim de cadeias. As funções strlen( ) e strcpy ( ) são de string .h. ⟨ Leia a entrada 6 ⟩ ≡

⟨ Inicialize o vetor texto 8 ⟩; i = 0; while (gets (linha)) {

tmp = strlen(linha);

s = (char ∗) malloc(tmp + 2); /∗ +2 para o e a serem acrescentado depois ∗/ if (s ≡ Λ) { /∗ estourou a memória... ∗/

status = erro na alocacao de memoria;

fprintf (stderr , ␣ ␣ , nome do prog );

exit (status ); } strcpy (s, linha); s[tmp] = ;

/∗ acrescentamos um  explicitamente porque gets ( ) substitui este caracter por  ∗/
s[^{++}tmp] =  ;  /∗ marcação de fim de cadeia ∗/

texto[i^{++}] = s; } n linhas = i;

This code is used in section 5.

7. ⟨ Variáveis locais a main 7 ⟩ ≡ char linha[ ]; /∗ para a leitura de uma linha ∗/ char ∗s; /∗ um ponteiro para uma cópia da linha lida ∗/ int i; /∗ índice da linha sendo lida ∗/ int n linhas ; /∗ número de linhas lidas ∗/ int tmp;

char ∗texto[  ];  /∗ vetor de apontadores para strings, cada string contendo uma linha do texto ∗/

This code is used in section 5.

8. ⟨ Inicialize o vetor texto 8 ⟩ ≡ for (i = 0; i < ; i^{++}) texto[i] = Λ;

This code is used in section 6.

9. ⟨ Imprima o resultado 9 ⟩ ≡ for (i = 0; texto[i]; i^{++}) printf ( , texto[i]);

This code is used in section 5.

§10  EX12  A ROTINA DE ORDENACAO 3

10. A rotina de ordenacao. Usamos o algoritmo QuickSort, devido a Hoare [veja, por exemplo, o Volume 3 de Knuth, D. E., Sorting and Searching, Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv + 780pp. + foldout. ISBN 0-201-89685-0]. Esté é um algoritmo genérico de ordenação que é muito popular pela sua eficiência. Ele é bastante sutil, e no momento não vamos nos preocupar muito com o funcionamento dele. ⟨ Ordene 10 ⟩ ≡

quicksort (texto, 0, n linhas − 1);

This code is used in section 5.

11. ⟨ Função de ordenação 11 ⟩ ≡ void quicksort (char ∗∗tab, int l, int r) { int j;

if (l < r) { ⟨ Determine o índice j para a partição 12 ⟩; quicksort (tab, l, j); quicksort (tab, j + 1, r);

} }

This code is used in section 3.

12. ⟨ Determine o índice j para a partição 12 ⟩ ≡

{ char ∗pivot ; char ∗ptr aux ; int i; pivot = tab[l]; i = l − 1; j = r + 1; while (1) {

while (strcmp(tab[^{−}j], pivot ) > 0) ;

while (strcmp(tab[^{++}i], pivot ) < 0) ;

if (i ≥ j) break;

ptr aux = tab[i], tab[i] = tab[j], tab[j] = ptr aux ; }

}

This code is used in section 11.

4  INDICE  EX12 §13

13. Indice. Aqui está uma lista de identificadores que são usados, com indicação de onde eles aparecem. As entradas sublinhadas indicam onde eles aparecem.

argc: \underline{5}. argv : \underline{5}. calloc: 4. : \underline{1}, 7. erro na alocacao de memoria: \underline{2}, 6. exit : 5, 6. fprintf : 6. free: 4. gets : 6. i: \underline{7}, \underline{12}. j: \underline{11}. l: \underline{11}. : \underline{1}, 7, 8. linha: 6, \underline{7}. main: \underline{5}. malloc: 4, 6. n linhas : 6, \underline{7}, 10. nome do prog : \underline{2}, 5, 6. : \underline{2}. pivot : \underline{12}. printf : 9. ptr aux : \underline{12}. quicksort : 10, \underline{11}. r: \underline{11}. s: \underline{7}. status : \underline{2}, 5, 6. stderr : 6. stdin: 6. stdio: 6. strcmp: 12. strcpy : 6. string : 6. strlen: 6. tab: \underline{11}, 12. texto: 6, \underline{7}, 8, 9, 10. tmp: 6, \underline{7}.

EX12 NAMES OF THE SECTIONS 5

⟨ Determine o índice j para a partição 12 ⟩ Used in section 11. ⟨ Função de ordenação 11 ⟩ Used in section 3. ⟨ Imprima o resultado 9 ⟩ Used in section 5. ⟨ Inclusão de arquivos sobre as bibliotecas 4 ⟩ Used in section 3. ⟨ Inicialize o vetor texto 8 ⟩ Used in section 6.

⟨ Leia a entrada 6 ⟩ Used in section 5.

⟨ O programa principal 5 ⟩ Used in section 3.

⟨ Ordene 10 ⟩ Used in section 5.

⟨ Variáveis globais 2 ⟩ Used in section 3. ⟨ Variáveis locais a main 7 ⟩ Used in section 5.