Estudante

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

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 Os autores concedem a permiss˜ o expl´cita para a utilizacao e reproducao deste a ı
¸˜
¸˜ 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 ´