Estrutura de dados

£ £ £ £££ £ ¢ ¡¡¡ £ ¢¡ ¢ £ £ ¢¡ £¡¢¢££¢¡ £ ¢ ¡¡¡ ¢¡ ¢ ¡£¢¢¢¢¡£ £¡ ££ £ £ ¢¡¢¡¡££¡¢ ¢¡ ¢ ¢ ¢ £ ¡££ £¡ £ ¢¡ ¢¡¡¡¡¢¡ ¢¡ ¢¢¢

Estruturas de Dados e T´ cnicas de Programacao e ¸˜
˜ Versao 1.12 Agosto de 2004 Cl´ udio L. Lucchesi a Tomasz Kowaltowski

I NSTITUTO DE C OMPUTAC AO ¸˜ U NIVERSIDADE E STADUAL DE C AMPINAS

UNICAMP

ii

Nenhuma parte destas notas pode ser reproduzida, qualquer que seja a forma ou o meio, sem a permiss˜ o, por escrito, de ambos os autores. a a ı ¸˜ ¸˜ Os autores concedem a permiss˜ o expl´cita para a utilizacao e reproducao deste material no contexto do ensino de disciplinas regulares dos cursos de graduacao ¸˜ sob a responsabilidade do Instituto de Computacao da UNICAMP. Qualquer ou¸˜ ´ tra utilizacao deste material e vedada sem a permiss˜ o, por escrito, de ambos os ¸˜ a autores. c Copyright 1997–2004 Todos os direitos reservados por: Cl´ udio L. Lucchesi e Tomasz Kowaltowski a

Instituto de Computacao ¸˜ UNICAMP Caixa Postal 6176 13083-970 Campinas, SP http://www.ic.unicamp.br/˜{lucchesi,tomasz}

Pref´ cio a
´ Este texto e o resultado da tentativa de reunir o material preparado pelos autores durante os v´ rios anos em a que tˆ m ministrado as disciplinas sobre estruturas de dados, na UNICAMP e em v´ rias outras instituicoes. e a ¸˜ Os cap´tulos e secoes que comp˜ em o texto est˜ o em est´ gios distintos de elaboracao. Alguns tˆ m apenas ı ¸˜ o a a ¸˜ e seus t´tulos enunciados, outros est˜ o bastante completos. Os autores esperam que, com o tempo, o texto ı a possa evoluir para um livro completo. ´ A preocupacao principal do texto e com as estruturas de dados fundamentais e os algoritmos para a sua ¸˜ manipulacao, incluindo nocoes b´ sicas de eficiˆ ncia. Os exemplos procuram utilizar o conceito de tipos ¸˜ ¸˜ a e abstratos de dados, sempre que aplic´ vel. Entretanto, a metodologia de programacao n˜ o e um assunto a ¸˜ a ´ aprofundado neste texto, j´ que trata-se de programacao em pequena escala