Estrutura de Dados Jo˜ao Dovicchi 2 Conteu´do 1 Dados 9 1.1 Tipos de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Tipo de dado abstrato . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Tipos de dados em C . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Operac¸˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Referˆencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6 Dados em C: Tipos e modificadores . . . . . . . . . . . . . . . . 15 1.6.1 O tipo int . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.2 O tipo float . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.3 O tipo double . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.4 O tipo char . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6.5 O tipo enum . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.7 Modificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.8 Qualificadores de dados . . . . . . . . . . . . . . . . . . . . . . . 19 2 Representa¸c˜ao de dados 21 2.1 Representac¸˜ao em array . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Usando vetores como parˆametros de func¸˜oes . . . . . . . . . . . 25 2.3 Operac¸˜oes com arrays . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Linguagens funcionais e array . . . . . . . . . . . . . . . . . . . 30 2.5 Representac¸˜ao de dados e matrizes . . . . . . . . . . . . . . . . 31 2.5.1 Matrizes: conceitos gerais . . . . . . . . . . . . . . . . . 31 2.5.2 Operac¸˜oes com matrizes . . . . . . . . . . . . . . . . . . 33 2.5.3 Matrizes booleanas . . . . . . . . . . . . . . . . . . . . . 35 2.5.4 Matrizes esparsas . . . . . . . . . . . . . . . . . . . . . . 37 2.6 Tipos de dados definidos pelo usu´ario . . . . . . . . . . . . . . . 39 2.6.1 Estruturas . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.6.2 Uni˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.6.3 Campos de bits . . . . . . . . . . . . . . . . . . . . . . . 45 3 ´ 4 CONTEUDO 2.7 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 Listas 49 3.1 Definic¸˜oes e declarac¸˜oes . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Operac¸˜oes com listas . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Pilhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3.1 Operac¸˜oes e TDA . . . . . . . . . . . . . . . . . . . . . . 55 3.3.2 Implementac¸˜ao e Exemplos em C . . . . . . . . . . . . . 57 3.4 Filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4.1 Filas: operac¸˜oes e TDA . . . . . . . . . . . . . . . . . . . 61 3.4.2 Implementac¸˜ao em C . . . . . . . . . . . . . . . . . . . . 61 3.4.3 Filas circulares . . . . . . . . . . . . . . . . . . . . . . . 63 3.4.4 Listas ligadas . . . . . . . . . . . . . . . . . . . . . . . . 64 3.4.5 Operac¸˜oes com listas ligadas . . . . . . . . . . . . . . . . 67 3.5 Pilhas e Func¸˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4 Grafos e ´arvores 75 4.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.1.1 Definic¸˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.1.2 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2 Grafos e Estrutura de dados . . . . . . . . . . . . . . . . . . . . 80 4.2.1 Grafos direcionados e matriz adjacˆencia . . . . . . . . . . 81 4.2.2 Acessibilidade dos n´os de um grafo . . . . . . . . . . . . 82 4.3 Caminho m´ınimo . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.1 Um exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4 Algoritmos para grafos . . . . . . . . . . . . . . . . . . . . . . . 85 4.4.1 Algoritmo de Warshall . . . . . . . . . . . . . . . . . . . 85 4.4.2 Caminho de Euler . . . . . . . . . . . . . . . . . . . . . . 86 4.4.3 Algoritmo do Caminho M´ınimo . . . . . . . . . . . . . . 88 4.4.4 Problema do Caixeiro Viajante . . . . . . . . . . . . . . 90 4.5 Listas adjacˆencia . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.5.1 Matriz Adjacˆencia . . . . . . . . . . . . . . . . . . . . . 91 4.5.2 Lista de Adjacˆencias . . . . . . . . . . . . . . . . . . . . 91 4.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.7 A´rvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.7.1 Percurso . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.7.2 Um exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.8 A´rvore Geradora M´ınima . . . . . . . . . . . . . . . . . . . . . . 96 ´ CONTEUDO 5 4.8.1 Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . 97 4.8.2 Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . 97 4.9 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5 M´aquinas de Estado 99 5.1 M´aquinas de estado finito . . . . . . . . . . . . . . . . . . . . . 100 5.1.1 Um exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.3 M´aquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6 Algoritmos 109 6.1 Algoritmos determin´ısticos e n˜ao-determin´ısticos . . . . . . . . . 110 6.2 Otimizac¸˜ao de algoritmos. . . . . . . . . . . . . . . . . . . . . . 112 6.3 Precis˜ao de algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 112 6.4 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.5 Algoritmos de Ordenac¸˜ao e Busca . . . . . . . . . . . . . . . . . 116 6.5.1 M´etodo “bolha” (bubble sort) . . . . . . . . . . . . . . . 116 6.5.2 M´etodo Troca de partic¸˜ao (Quick Sort) . . . . . . . . . . 118 A Introduc¸˜ao `a programa¸c˜ao funcional 121 A.0.3 Linguagem Funcional - O que ´e e porque usar? . . . . . . 122 A.0.4 Func¸˜oes hier´arquicas . . . . . . . . . . . . . . . . . . . . 124 A.0.5 Lazy Evaluation . . . . . . . . . . . . . . . . . . . . . . . 125 A.0.6 Um exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 126 A.1 Programac¸˜ao Funcional e listas . . . . . . . . . . . . . . . . . . 131 A.1.1 Mais sobre listas . . . . . . . . . . . . . . . . . . . . . . 131 A.1.2 Programac¸˜ao Funcional e E/S (IO) . . . . . . . . . . . . 135 A.1.3 M´odulos . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 B C´alculo λ: Uma introdu¸c˜ao 143 B.1 O C´alculo-λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 B.1.1 Computabilidade de func¸˜oes . . . . . . . . . . . . . . . . 145 B.1.2 C´opia e reescrita . . . . . . . . . . . . . . . . . . . . . . 147 B.1.3 Reduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 B.1.4 Forma normal . . . . . . . . . . . . . . . . . . . . . . . . 150 B.2 Aplicac¸˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 B.2.1 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . 151 ´ 6 CONTEUDO C Exerc´ıcios complementares 153 C.1 Lista de Exerc´ıcios - ARRAY . . . . . . . . . . . . . . . . . . . 153 C.2 Lista de Exerc´ıcios - Listas . . . . . . . . . . . . . . . . . . . . . 155 C.3 Lista de Exerc´ıcios - Listas, Pilhas e Filas . . . . . . . . . . . . 156 C.4 Lista de Exerc´ıcios - Grafos . . . . . . . . . . . . . . . . . . . . 158 C.5 Lista de Exerc´ıcios - A´rvores . . . . . . . . . . . . . . . . . . . . 159 C.6 Lista de Exerc´ıcios - M´aquinas de estado finito . . . . . . . . . . 160 C.7 Lista de Exerc´ıcios - M´aquinas de Turing . . . . . . . . . . . . . 162 C.8 Lista de Exerc´ıcios - Ordenac¸˜ao e Busca . . . . . . . . . . . . . 162 Pref´acio Este livro aborda alguns dos principais conceitos da ´area de programac¸˜ao e estrutura de dados. Podemos considerar os dados como conjuntos de elemen- tos de determinados tipos que podem ser tratados como unidades informacio- nais. A informac¸˜ao, entretanto, depende da contextualizac¸˜ao dos dados, isto´e, como s˜ao selecionados, relacionados e organizados. Uma vez que a ciˆencia da computac¸˜ao est´a fundamentada no processamento da informac¸˜ao, o estudo do conteu´do desta informac¸˜ao depende dos tipos de dados que s˜ao manipulados e sua organizac¸˜ao. Assim, adisciplinaEstrutura de Dadostratada manipulac¸˜ao, organizac¸˜ao e utilizac¸˜ao destes dados. Como manipular Estrutura de Dados Como organizar   Como utilizar  Com a finalidade de compreender os dados e a maneira como eles s˜ao tipa- dos, armazenados, ordenados etc., vamos utilizar, neste livro, alguns conceitos de programac¸˜ao procedural e funcional1. Para isso, escolhemos a linguagem C ANSI para apresentar os algoritmos conceituais no modelo procedural e a lin- guagem Haskell no modelo funcional. A forma procedural (em C) apresenta umavis˜aoimperativadosdadosealgoritmos, enquanto aformafuncionalapre- sentaumavis˜aodeclarativa. AslinguagensCeHaskellforamescolhidaspela simplicidade, pela facilidade de compreens˜ao e pelo poder de processamento de dados. Comoaslinguagensdeprogramac¸˜ao,emgeral,s˜aoapenasformassemˆanticas derepresentac¸˜ao, elasfacilitamaimplementac¸˜aodosalgoritmos. Assim, quando necess´ario faremos algumas incurs˜oes na sintaxe de C e Haskell , apenas o suficiente para compreender o processo de um algoritmo. 1Ver apˆendice A 7 8 O conteu´do deste curso se encontra dividido em 4 partes. Na primeira parte ser˜ao estudados os conceitos fundamentais e introdut´orios das entidades e abstrac¸˜oes que comp˜oem a representac¸˜ao dos dados, al´em das express˜oes que formam os termos e sintaxe desta representac¸˜ao (cap´ıtulo 1). Na segunda parte,abordaremosasrepresentac¸˜oespropriamenteditas, asoperac¸˜oescomda- dose a construc¸˜ao de func¸˜oes que nos permitam fazer estas operac¸˜oes (cap´ıtulo 2). Na terceira parte nos dedicaremos ao estudo da manipulac¸˜ao de dados em listas, filas, pilhas e outras possibilidades de representac¸˜ao, tais como grafos e ´arvores(cap´ıtulos3e4). Finalmente, naquartapartevamosvercomoasestru- turasdedadosserelacionamcomaatividadedeprogramac¸˜aoeimplementac¸˜ao de algoritmos, ressaltando os conceitos de m´aquinas abstratas, recursividade, classificac¸˜ao, busca, ordenac¸˜ao e hashing (cap´ıtulos 5 e 6). No apˆendice A, encontra-se alguns conceitos b´asicos de programac¸˜ao fun- cional, particularmente da linguagem Haskell . O apˆendice B traz uma introduc¸˜ao ao c´alculo-λ que ´e a fundamentac¸˜ao te´orica das estruturas em Lin- guagem Funcional . Finalmente, o apˆendice C traz alguns exerc´ıcios relacio- nados aos conceitos dos cap´ıtulos do livro. Prof. Dr. Jo˜ao Dovicchi Florian´opolis, agosto de 2007. Cap´ıtulo 1 Dados Se partirmos do pressuposto de que a informac¸˜ao tem por objetivo a reduc¸˜ao da incerteza sobre determinado fato, podemos afirmar que informac¸˜ao ´e uma mensagem resultante do processamento, manipulac¸˜ao e organizac¸˜ao dos dados, com a finalidade de proporcionar o conhecimento de um fato a quem tiver acesso a ela. Assim, podemos definir dados como as unidades b´asicas de um conjunto de informac¸˜oes. Em computac¸˜ao, dados s˜ao conjuntos de valores ou caracteres representa- dos por d´ıgitos bin´arios (bits) e que se localizam em enderec¸os de mem´oria, arquivos ou qualquer outro meio digital. Eles podem ser representados por conjuntos de bits de tamanho vari´avel, dependendo do seu tipo e tamanho, e podem sofrer v´arios tipos de operac¸˜oes. Neste cap´ıtulo, vamos entender como os dados s˜ao definidos (tipados) e de que maneira podem ser manipulados. 1.1 Tipos de Dados Os dados podem ser tipados dependendo de v´arios fatores que possibilitam a sua caracterizac¸˜ao. Eles devem ser definidos com relac¸˜ao a trˆes propriedades principais: 1. Conjunto de valores, ou seja, que conjunto de valores uma vari´avel ou campo de dados pode receber ou armazenar; 2. Conjunto de operadores, ou seja, que conjunto de operadores podem agir sobre os dados ou campo de dados; e 3. Referˆencia, ou seja, de que maneira os dados podem ser localizados ou referenciados. 9 ´ 10 CAPITULO 1. DADOS Nos sistemas digitais de informac¸˜ao (inform´atica), os dados podem ser de 3 tipos: num´ericos, literais e l´ogicos. Os dados num´ericos representam entidades aritm´eticas, podendo ser nu´meros inteiros, decimais ou racionais. Os dados literais representam caracteres, d´ıgitos e s´ımbolos de uma determinada tabela ou conjunto ou uma cadeia deles. Os dados l´ogicos representam os valores l´ogicos de verdadeiro ou falso. Algumas caracter´ısticas s˜ao implicitamente declaradas como, por exemplo, int, char, float etc.. Outras podem ser declaradas explicitamente, de forma abstrata. Este u´ltimo tipo ´e denominado Tipo de Dado Abstrato (TDA). Um TDA consiste em duas partes: a definic¸˜ao de valores e a definic¸˜ao de operadores. Os valores dos dados podem ser armazenados em vari´aveis ou constantes para ser referenciados posteriormente. No caso das vari´aveis, seus conteu´dos podem ser alterados no decorrer do algoritmo, enquanto as constantes n˜ao. As vari´aveis, ao ser declaradas, fazem com que o compilador reserve o espac¸o adequado de mem´oria para o seu tipo. 1.2 Tipo de dado abstrato A programac¸˜ao orientada a objetos — Object Oriented Programming (OOP) — pode ser descrita como a programac¸˜ao de tipos abstratos de dados e suas relac¸˜oes. Independentemente dalinguagemutilizada, umtipoabstratodedado podeser especificado poruma estrutura abstrata(abstract structure), definic¸˜ao de valores e de operadores. A definic¸˜ao tem 2 propriedades: 1. Exporta um tipo, definindo suas condic¸˜oes e seu dom´ınio; e 2. Exportaasopera¸c˜oes, quedefineoacesso aotipodeestrutura dedados. Para compreender como se define um tipo de dado, vamos tomar como exemplo a definic¸˜ao de um tipo de dado racional em C++ (RATIONAL). Um nu´mero racional ´e aquele que pode ser expresso como um quociente de dois inteiros. Podemos, por exemplo, definir as operac¸˜oes adic¸˜ao, multiplicac¸˜ao e igualdade sobre os nu´meros racionais a partir de dois inteiros, como na espe- cificac¸˜ao deste tipo de dado abstrato (TDA) na listagem 1.1. Observe que a definic¸˜ao do tipo RATIONAL, em C, n˜ao deixa claro como as operac¸˜oes funcionam, mas observe a mesma definic¸˜ao em uma linguagem funcional (veja listagem 1.2)