Blog

À Maria, esposa e companheira, Patricia e Paula, nossas filhas. Dados Internacionais de Catalogação na Publicação (CIP) ( C i m a r a Brasileira do Livro, S P, Brasil) Ziwani, Nivio Projeto de algoritmos c o m implementações pascal • C / NiVi0 Zi’. nani. • (Pioneira Informática) Bibliografia. ISBN 85-221 1. Algoritmos 2. c (LI computadores) 3. Da 4. PASCAL (Linguage Titulo. II. Série 98-5286 CDD05. 1 . 4. ad. São Paulo ar 169 m : Pioneira, 1999. – o para da computação). computadores) l. índices para catálogo sistemático: 1 .

Algoritmos : Programação : Processamento de dados 005. 1 Projeto de Algoritmos Com Implementações em Pascal e C PIONEIRA INFORMATICA Coordenador: Computadores Dirceu de Lima, 313 Telefone: (OI 1) 858-3199 Fax: (011) 8584)443 — São paulo — sp e-mail: pioneira@editorapioneira. com. br Impresso no Brasil Printed in Brazil Prefácio Este livro apresenta uma introdução ao estudo de algoritmos computacionais. As principais técnicas de projeto de algoritmos são ensinadas através da explicação detalhada de algoritmos e estruturas de dados para o uso eficiente do computador.

Estas explicações são mantidas o mais simples possível, mas sem perder a profundidade e c rigor matemático. O conteúdo é dirigido principalmente para ser utilizado como livro-texto em cursos sobre algoritmos e estruturas de dados. Pelo fato de apresentar muitas implementações de algoritmos práticos o texto é igualmente útil para profissionais engajados no desenvolvimento de sistemas de computação e de programas de aplicação.

Os algoritmos são apresentados através de refinamentos sucessivos até o nível de uma implementação na linguagem Pascal, o que permite que qualquer pessoa com um mínimo de experiência em programação possa ler o código. Conteúdo O Ilvro apresenta as principais técnicas utilizadas para implementação de estruturas de dados básicas e de algoritmos para ordenação e pesquisa em memória primária e memória secundária.

Os tópicos estão agrupados em cinco capítulos, cada um com o seguinte conteúdo: (i) conceito de algoritmo, estrutura de dados e tipo abstrato de dados, técnicas de análise de desempenho de algoritmos, linguagem Pascal; (ii) estruturas de dados básicas: listas lineares, pilhas e filas; (iii) métodos de ordenação em memória primária: por inserção, por seleção, shellsort, quicksort e heapsort, e em memór shellsort, quicksort e heapsort, e em memória secundária: ntercalação balanceada; (iv) métodos de pesquisa em memória prméria: pesquisa sequencial, pesquisa binária, árvores de pesquisa e hashing; (v) métodos de pesquisa em memória secundária: sequencial indexado e árvores B. O estudo do comportamento dos algoritmos tem um papel decisivo no projeto de algoritmos eficientes.

Por isso, são apresentadas informações sobre as caracter[sticas de desempenho de cada algoritmo apresentado. Entretanto, a parte matemática utilizada para apresentar os resultados analíticos é autocontida e exige muito pouco conhecimento matemátlco prévio para ser entendida. A linguagem de programação utilizada para apresentação do refinamento final dos algoritmos apresentados é a linguagem Pascal. A vantagem de se usar a linguagem Pascal é que os programas se tornam fáceis de ser lidos e de ser traduzidos para outras linguagens. Além disso, todos os algoritmos implementados na linguagem Pascal são também implementados na linguagem C. Todo programa Pascal de um capítulo tem um programa C correspondente no apêndice.

Ao Leitor O material apresentado é adequado para ser utilizado como livro texto em cursos de graduação em Ciência da Computação e em cursos de extensão para formação de Programadores na área de Algoritmos e Estruturas de Dados. E recomendável que o estudante já tenha tido um curso de programação (ou experiência equivalente) em uma linguagem de alto nível, tal como Pascal ou C, assim como conhecimentos de utilização de sistemas de computação. Versões anteriores deste livro foram utilizadas na de utilização de sistemas de computação. Versões anteriores deste livro foram utilizadas na Universidade Federal de Minas Gerais.

A disciplina Algoritmos e Estruturas de Dados II do Curso de Bacharelado em Ciência da Computação, com carga horária de 0 horas e um semestre de duração, possui a seguinte ementa: tipos abstratos de dados; introdução a análise de algoritmos; listas lineares, pilhas e filas; ordenação: seleção direta, inserção direta, shellsort, quicksort, heapsort, mergesort e radixsort; pesquisa em tabelas: sequencial, binária e transformação de chave ( hashing); árvores de pesquisa: sem balanceamento, com balanceadamento, tries e patricia. Os tópicos ordenação externa, pesquisa em memória secundária e um estudo mais elaborado de análise de algoritmos fazem parte da disciplina Algoritmos e Estruturas de Dados III, do mesmo Curso. Ao final de cada apítulo são incluídos exercícios. Alguns exercícios são do tipo questões curtas, para testar os conhecimentos básicos sobre o material apresentado.

Outros exercícios são do tipo questões mais elaboradas, podendo exigir do leitor um trabalho de vários dias, devendo ser realizado em casa ou em laboratorio. Assim, os exercícios propostos devem ser utilizados em testes e trabalhos práticos para avaliação da aprendizagem. Este texto pode também ser utilizado como manual para programadores que já tenham familiaridade com o assunto, pois são apresentadas implementações de algoritmos de utilidade geral. Os algoritmos ropostos são completamente implementados nas linguagens Pascal e C e as operações envolvidas são descritas através da apresentação de exemplos de execução. Agradecimentos operações envolvidas são descritas através da apresentação de exemplos de execução.

Agradecimentos Uma versão inicial deste texto foi escrita para ser usada no Curso Estruturas de Dados e Algoritmos da I Escola Brasileiro-Argentina de Informática em fevereiro de 1986, publicada pela Editora da Unicamp sob o título Projeto de Algoritmos e Estruturas de Dados. Gostaria de agradecer a Carlos José Pereira de Lucena e Routo Terada por lembrarem o meu nome para participar da Escola Brasileiro-Argentina de Informática, o que motivou o desenvolvimento da semente deste texto. Gostaria de agradecer a Cilio Rosa Ziviani, Cleber Hostalácio de Melo, José Monteiro da Mata, Lilla Tavares Mascarenhas, Luiz Carlos de Abreu Albuquerque, Regina Helena Bastos Cabral e Rosângela Fernandes pelas contribuições para a primeira versão do texto. Muitos amigos e colegas me auxiliaram na. elaboração deste livro. Agradeço a todos pela ajuda e pelas críticas construtivas.

O Departamento de Ciência da Computação da Universidade Federal de Minas Gerais tem proporcionado um xcelente ambiente de trabalho. Os meus alunos de extensão, graduação, especialização e pós-graduação, especialmente os alunos das disciplinas Técnicas de programação, Algoritmos e Estruturas de Dados e Projeto e Análise de Algoritmos contribuíram significativamente. Vários erros foram corrigidos como conseqüência da leitura cuidadosa de várias pessoas, em especial Alberto Henrique Frade Laender, Eduardo Fernandes Barbosa, José Nagib Cotrim Arabe, Márcio Luiz Bunte de Carvalho, Osvaldo Sérgio Farhat de Carvalho, Roberto Márcio Ferreira de Souza e Virg(lio Augusto Fernandes Almeida, aos qu

Carvalho, Roberto Márcio Ferreira de Souza e Virgílio Augusto Fernandes Almeida, aos quais gostaria de registrar meus agradecimentos. Gostaria de agradecer a Cristina Duarte Murta pela leitura critica de todo o texto, pelos testes dos programas Pascal e pela execução dos programas que permitiu o estudo comparativo dos algoritmos de ordenação. A versão C dos algoritmos existe graças ao trabalho paciente de tradução dos programas Pascal conduzido -por Maurício Antônio de Castro Lima e Wagner Toledo Corrêa, realizado com o aux(lio do programa p2c para tradução automática de programas em Pascal para programas em C, desenvolvido por Dave Gillespie, do California Institute of Technology, EUA. O livro foi formatado com LATEX, um conjunto de macros para o TEX.

Um agradecimento todo especial para Márcio uiz Bunte de Camalho pela imensa ajuda durante todo o trabalho de formatação, incluindo a criação de ambientes especiais em LATEX para este texto, sendo que esta etapa contou também com a ajuda de Murilo Silva Monteiro. Nivio Zivianl gelo Horizonte Dezembro de 1992 Endereço Internet: nivio@dcc. ufmg. br Sumário Prefácio Lista de Figuras Lista de Tabelas Lista de Programas v xiii XV XVII 1 Introdução 1 1. Algoritmos, Estruturas de Dados e Programas „ — Abstratos de Dados . 1 1. 2 Tipos de Dados e Tipos . 2 1. 3 Medida do Tempo de Execução de um Programa — . Comportamento Assintótico de Funções . 1. 3. 2 Classes de Comportamento Assintótico . 14 1. Técnicas de Anál 3 1. 3. 1 11 1. 3. 2 Classes de Comportamento Assintótico — ……… 141. 4 Técnicas de Análise de Algoritmos 18 1. 5 Pascal 25 Notas Bibliográficas 30 Exercícios . 30 2 Estruturas de Dados Básicas 35 2. 1 Listas Lineares — 35 2. 1. 1 Implementação de Listas Através de Arranjos . 37 2. 1. 2 Implementação de Listas Através de Apontadores 38 2. 2 Pilhas „ … ,47 2. 2. 1 Implementação de Pilhas Através de Arranjos — 2. 2. 2 Implementação de Pilhas Através de Apontadores 49 2. 3 Filas .. 55 2. 3. 1 Implementação de Filas Através de Arranjos . 56 2. 3. 2 Implementação de Filas Através de Apontadores Bibliográficas . 8 Exercícios . 58 SUMÁRIO 3 Ordenação 69 3. 1 Ordenação Interna . 58 Notas Sequencial . Pesquisa Binária . 1 IO 4. 3 Arvores de Arvores Binár 71 3. 1. 1 Ordenação por Seleção . 72 3. 1-2 Ordenação por Inserção 73 3. 1. 3 Shellsort . 76 3. 1 . 4 QIliCksort • • • • 78 3. 1. Heapsort . 81 3. 1. 6 Comparação Entre os Métodos 87 3. 2 Ordenação Externa 91 3. 2. 1 Intercalação Balanceada de Vários Caminhos — 92 3. 2. 2 Implementação Através de Seleção por Substituição . 94 3. 2. 3 Considerações Práticas — 97 Notas 99 Exercícios 99 4 Pesquisa em Memória Primária 107 4. 1 Pesquisa Pesquisa 108 4. 2 . 111 4. 3. pesquisa Com Balanceamento . Digital „ 127 4. 5 Transformação de Chave (Hashing) . de Transformação Listas Encadeadas . 137 4. 5. 3 open Addressing . 143 Exercícios Secundária 155 5. 1 Secundária Indexado . Arvores g 5. 3. 2 Árvores B* 111 4. . 1 Arvores Binárias de Pesquisa Sem Balanceamento 112 4. 3. 2 Arvores Binárias de Práticas _ 117 4. 4 pesquisa . 135 4. 5. 1 punçoes 136 4. 5. 2 . 140 Notas Bibliográficas — 1445 Pesquisa em Memória Modelo de Computação para Memória 157 5. 2 Acesso Sequencial 163 5. 3 Arvores de Pesquisa — — 169 5. 3. 1 170 182 5. 3. 3 Acesso Concorrente em Arvores 184 5. 3. 4 Considerações 189 Notas P-aGFg . 92 Exercícios 193 A programas C do Captulo 1 B programas C do Capítulo 2 197 203 SUMÁRIO C D E F G programas C do capítulo 3 programas C do Capítulo 4 Programas C do Capitulo 5 Caracteres ASCII Referências Bibliográficas 217 223 243 253 255 261 índice Lista de Figuras 1. 1 Partição de A em dois subconjuntos 9 1. 2 Dominação assintótica de f(An) sobre 12 1. 3 Operações com a notação 0.. do caixeiro viajante . 18 1. 5 Estrutura de um programa Pascal 25 1. 6 Registro do tipo pessoa encadeada . 30 2. 1 Implementação de uma lista através de arranjo ……….. 37 2. 2 Implementação de uma lista 40 2. 3 Classificação dos 43 2. 4 Lista de aprovados por Curso — — . 442. 5 . 13 1. 4 problema 28 1. 7 Lista através de apontadores alunos por NotaFinal „ . Implementação de uma pilha através de a PAGF 10