§1  EX12 HEAP  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.

Faremos uma contagem do número de chamadas a strcmp( ) que fazemos no processo de ordenação ao executarmos este programa. Poderemos assim usar este programa para fazer alguns testes sobre o desempenho do “heapsort”, que é o algoritmos que usamos para o processo de ordenação. Usaremos a variável global n comp para esta contagem.

#define  256
#define  200000
#define o n comp^{++}

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 = ; unsigned long n comp;

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 12 ⟩

⟨ 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 11 ⟩; ⟨ Imprima o resultado 9 ⟩; ⟨ Imprima o número de comparações feitas 10 ⟩; exit (status );

}

This code is used in section 3.

2  UM EXEMPLO SIMPLES DE  EX12 HEAP §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. ⟨ Imprima o número de comparações feitas 10 ⟩ ≡

printf (  ␣   ␣  , n comp);

This code is used in section 5.

§11  EX12 HEAP  A ORDENAÇÃO 3

11. A ordenação. Usaremos o “heapsort” neste programa. A chamada da função de ordenação é simples. ⟨ Ordene 11 ⟩ ≡

heapsort (texto, n linhas );

This code is used in section 5.

12. Implementamos nesta e na seção seguinte o algoritmo heapsort de ordenação. Vale a pena lembrarmos que texto começa indexado com 0. Desta forma, por exemplo, os filhos de um nó de índice k tem filhos de índices 2k + 1 e 2k + 2. A função que escrevemos nesta seção recebe um heap cuja raiz é tab[k], exceto que pode acontecer da propriedade de heap ser violada entre tab[k] e seus filhos. A propriedade de heap deve valer para todos os outros pares pai–filho. A função que escrevemos aqui também recebe como parâmetro um inteiro n que especifica o número de elementos do heap inteiro. ⟨ Função de ordenação 12 ⟩ ≡

void transforme em heap(char ∗∗tab, int n, int k)

{ int j; char ∗aux ; aux = tab[k]; while (k < n/2) {

j = (k ≪ 1) + 1; /∗ índice do filho esquerdo ∗/ if ((j < n − 1) ∧ (o, strcmp(tab[j], tab[j + 1]) < 0)) j^{++};

/∗ precisamos saber qual dos filhos é maior (se existe mais de um) ∗/ if (o, strcmp(aux , tab[j]) ≥ 0) break; tab[k] = tab[j]; k = j;

}

tab[k] = aux ; }

See also section 13. This code is used in section 3.

13. Aqui temos a função de ordenação propriamente dita. Precisamos primeiro montar o heap e então ordenar os elementos “extraindo” os maiores elementos um por um (pondo-os no fim do vetor).

Note que, pelo fato de termos o nosso vetor começando com o índice 0, o elemento do heap de índice mais alto que tem um filho é aquele de índice ⌊n/2⌋ − 1, onde n é o número de elementos no heap. ⟨ Função de ordenação 12 ⟩ +≡

void heapsort (char ∗∗tab, int n)

{ int k; char ∗tmp; for (k = n/2 − 1; k ≥ 0; k^{−}) transforme em heap(tab, n, k); while (n > 1) { tmp = tab[0]; tab[0] = tab[n − 1]; tab[n − 1] = tmp; transforme em heap(tab,^{−}n, 0);

} }

4  ÍNDICE  EX12 HEAP §14

14. Índice. 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}. aux : \underline{12}. calloc: 4. : \underline{1}, 7. erro na alocacao de memoria: \underline{2}, 6. exit : 5, 6. fprintf : 6. free: 4. gets : 6. heapsort : 11, \underline{13}. i: \underline{7}. j: \underline{12}. k: \underline{12}, \underline{13}. : \underline{1}, 7, 8. linha: 6, \underline{7}. main: \underline{5}. malloc: 4, 6. n: \underline{12}, \underline{13}. n comp: 1, \underline{2}, 10. n linhas : 6, \underline{7}, 11. nome do prog : \underline{2}, 5, 6. o: \underline{1}. : \underline{2}. printf : 9, 10. s: \underline{7}. status : \underline{2}, 5, 6. stderr : 6. stdin: 6. stdio: 6. strcmp: 1, 12. strcpy : 6. string : 6. strlen: 6. tab: \underline{12}, \underline{13}. texto: 6, \underline{7}, 8, 9, 11, 12. tmp: 6, \underline{7}, \underline{13}. transforme em heap: \underline{12}, 13.

EX12 HEAP NAMES OF THE SECTIONS 5

⟨ Função de ordenação 12, 13 ⟩ Used in section 3. ⟨ Imprima o número de comparações feitas 10 ⟩ Used in section 5. ⟨ 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 11 ⟩ Used in section 5.

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