INICIAIS_ALGORITMOS E EST DE DADOS.indd 1 1/14/09 6:38:34 PM INICIAIS_ALGORITMOS E EST DE DADOS.indd 2 1/14/09 6:38:34 PM Paulo Roberto Martins (Org.) INICIAIS_ALGORITMOS E EST DE DADOS.indd 3 1/14/09 6:38:35 PM © 2009 by Pearson Education do Brasil Todos os direitos reservados. Nenhuma parte desta publicação poderá ser reproduzida ou transmitida de qualquer modo ou por qualquer outro meio, eletrônico ou mecânico, incluindo fotocópia, gravação ou qualquer outro tipo de sistema de armazenamento e transmissão de informação, sem prévia autorização, por escrito, da Pearson Education do Brasil. Diretor editorial: Roger Trimer Gerente editorial: Sabrina Cairo Supervisora de produção editorial: Marcelo Françozo Editora: Josie Rogero Revisão: Juliana Campoi Capa: Rafael Mazzo Diagramação: Globaltec Artes Gráficas Ltda. Dados Internacionais de catalogação na Publicação (CIP) (Câmara Brasileira do Livro, SP, Brasil) Martins, Paulo Roberto (org.) Algoritmos e estrutura de dados : análise e desenvolvimento de sistemas / Paulo Roberto Martins. -- São Paulo : Pearson Prentice Hall, 2009. ISBN 978-85-7605-244-9 1. Algoritmos 2. Estrutura de dados (Ciência da computação) - Estudo e ensino 3. Programação (Computadores eletrônicos) I. Título. 09-00070 CDD-005.107 Índice para catálogo sistemático: 1. Computadores : Programas : Processamento de dados : Estudo e ensino 005.107 2. Programação de computadores : Processamento de dados : Estudo e ensino 005.107 2009 Direitos exclusivos para língua portuguesa cedidos à Pearson Education do Brasil, uma empresa do grupo Pearson Education Av. Ermano Marchetti, 1435 CEP: 05038-001 - São Paulo - SP Tel.: (11) 2178-8686, Fax: (11) 2178-8688 e-mail: [email protected] INICIAIS_ALGORITMOS E EST DE DADOS.indd 4 1/14/09 6:38:35 PM Sumário Unidade 1 – Algoritmos de ordenação em vetores .............1 Algoritmo de ordenação por troca ..........................................................................1 Algoritmo de ordenação por inserção ...................................................................16 Algoritmo de ordenação por seleção ....................................................................26 Algoritmo de ordenação por intercalação .............................................................34 Unidade 2 – Algoritmos de busca em vetores .....................46 Algoritmo de busca seqüencial .............................................................................46 Algoritmo de busca binária ...................................................................................59 Unidade 3 – Estruturas de dados dos tipos pilha e fila ..................................................................................................67 Pilha ......................................................................................................................67 Implementação estática de uma pilha ...................................................................68 Implementação dinâmica de uma pilha ................................................................71 Aplicação de controle de estoque usando pilha dinâmica ....................................75 Fila .......................................................................................................................86 Implementação estática de uma fila ......................................................................87 Implementação dinâmica de uma fila ...................................................................90 Aplicação de controle de senhas usando fila dinâmica .........................................94 INICIAIS_ALGORITMOS E EST DE DADOS.indd 5 1/14/09 6:38:35 PM vi Algoritmos e estrutura de dados Unidade 4 – Listas estática e dinâmica simplesmente encadeadas .............................................................................................101 Implementacão de uma lista estática simplesmente encadeada e não ordenada ............................................................................................104 Implementação de uma lista estática simplesmente encadeada e ordenada ..................................................................................................108 Implementação de uma lista dinâmica simplesmente encadeada e não ordenada ............................................................................................112 Implementação de uma lista dinâmica simplesmente encadeada e ordenada ..................................................................................................119 Aplicacão de controle de alunos usando lista dinâmica simplesmente encadeada e não ordenada ..........................................................................124 Unidade 5 – Lista dinâmica duplamente encadeada ...............................................................................................136 Implementação de uma lista dinâmica duplamente encadeada e não ordenada ............................................................................................140 Implementação de uma lista dinâmica duplamente encadeada e ordenada ........147 Aplicação de controle de vôos usando lista dinâmica duplamente encadeada e não ordenada ...........................................................................153 Unidade 6 – Árvore binária ..........................................................155 Implementação de uma árvore binária dinâmica ................................................158 Aplicação de fluxo de caixa usando árvore binária .............................................169 INICIAIS_ALGORITMOS E EST DE DADOS.indd 6 1/14/09 6:38:35 PM Carta ao aluno O crescimento e a convergência do potencial das tecnologias da informação e da co- municação fazem com que a Educação a Distância, sem dúvida, contribua para a expansão do ensino superior no Brasil, além de favorecer a transformação dos métodos tradicionais de ensino em uma nova e inovadora proposta pedagógica. Foram exatamente essas características que possibilitaram à Unopar ser o que é hoje: uma referência nacional em ensino superior. Além de oferecer cursos nas áreas de humanas, exatas e da saúde em três campi localizados no Paraná, é uma das maiores universidades de educação a distância do país, com mais de 350 pólos e um sistema de ensino diferen- ciado que engloba aulas ao vivo via satélite, Internet, ambiente Web e, agora, livros-texto como este. Elaborados com base na idéia de que — embora a educação a distância tenha entre seus pilares o autodesenvolvimento — os alunos precisam de instrumentos didáticos que os apóiem, os livros-texto da Unopar têm como objetivo permitir que os estudantes ampliem seu conhecimento teórico ao mesmo tempo em que aprendem a partir de suas experiências, desenvolvendo a capacidade de analisar o mundo a seu redor. Para tanto, além de possuírem um alto grau de dialogicidade — caracterizado por um texto claro e apoiado por elementos como “Saiba mais”, “Links” e “Para saber mais” —, esses livros contam com a seção “Aprofundando o conhecimento”, que proporciona acesso a materiais de jornais e revistas, artigos e textos extraídos de livros de autores consagrados, como Philip Kotler, Lawrence Gitman e Stephen Robbins. E, como não deve haver limites para o aprendizado, os alunos que quiserem ampliar seus estudos poderão encontrar na íntegra na Biblioteca Digital, acessando a Biblioteca Virtual Universitária disponibilizada pela instituição, a grande maioria dos livros indicada na seção “Aprofundando o conhecimento”. Essa biblioteca, que funciona 24 horas por dia durante os 7 dias da semana, conta com mais de 700 títulos em português das mais diversas áreas do conhecimento e pode ser acessada de qualquer computador conectado à Internet. Somados à experiência dos professores e coordenadores pedagógicos da Unopar, esses recursos são uma parte do esforço da instituição para realmente fazer diferença na vida e na carreira de seus estudantes e também — por que não — para contribuir com o futuro de nosso país. Bom estudo! Pró-reitoria INICIAIS_ALGORITMOS E EST DE DADOS.indd 7 1/14/09 6:38:35 PM INICIAIS_ALGORITMOS E EST DE DADOS.indd 8 1/14/09 6:38:35 PM Algoritmos de Unidade ordenação em 1 vetores* Existem situações em que se tem um vetor de dados desordenados e se deseja ordená-los; para realizar o procedimento de ordenação, alguns algo- ritmos podem ser usados. Veja a seg uir alguns algoritmos de ordenação. Algoritmo de ordenação por troca Neste algoritmo de ordenação serão efetuadas comparações entre os dados armazenados no vetor. Quando a situação procurada (crescente ou decres- cente) é encontrada, uma troca de posições entre os dados é realizada. Assim, um laço com as comparações e as trocas será efet uado na quantidade de vezes igual ao número de dados do vetor menos 1, ou seja, na maior quantidade possível de trocas. Abaixo, o algoritmo de ordenação por troca será ilustrado com um vetor que possui dez posições, logo o laço será executado nove vezes e tendo como objetivo ordenar os dados do vetor de forma crescente. Execução número 1 do laço: Vet 5 4 2 1 8 2 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Compara-se se o número da posição 1 (número 5) é maior que o número da posição 2 (número 4). Se for, então ocorre a troca e avança-se. Do contrário, avança-se com a pesqui sa. Neste caso ocorreram a troca e o avanço, como mostra o vetor a seguir. * Esta unidade corresponde ao Capítulo 2 de ASCENCIO, Ana Fernanda Gomes. Aplicações das estruturas de dados. São Paulo: Pearson/Prentice Hall, 2005. Algor_Est_Dados_UN1.indd 1 1/16/09 3:15:41 PM 2 Algoritmos e estrutura de dados Vet 4 5 2 1 8 2 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Compara-se se o número da posição 2 (número 5) é maior que o número da posição 3 (número 2). Se for, então ocorre a troca e avança-se. Do contrário, avança-se com a pesqui sa. Neste caso ocorreram a troca e o avanço, como mostra o vetor a seguir. Vet 4 2 5 1 8 2 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Compara-se se o número da posição 3 (número 5) é maior que o número da posição 4 (número 1). Se for, então ocorre a troca e avança-se. Do contrário, avança-se com a pesqui sa. Neste caso ocorreram a troca e o avanço, como mostra o vetor a seguir. Vet 4 2 1 5 8 2 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Compara-se se o número da posição 4 (número 5) é maior que o número da posição 5 (número 8). Se for, então ocorre a troca e avança-se. Do contrá- rio, avança-se com a pesquis a. Neste caso ocorreu apenas o avanço, como mostra o vetor a seguir. Vet 4 2 1 5 8 2 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Compara-se se o número da posição 5 (número 8) é maior que o número da posição 6 (número 2). Se for, então ocorre a troca e avança-se. Do contrário, avança-se com a pesqui sa. Neste caso ocorreram a troca e o avanço, como mostra o vetor a seguir. Vet 4 2 1 5 2 8 4 5 9 7 1 2 3 4 5 6 7 8 9 10 Algor_Est_Dados_UN1.indd 2 1/14/09 4:43:46 PM