|
|
|
Estruturas de Dados para a Construção de Software Volume II – Nível Intermediário ( 615 páginas e mais de 340 programas em C, C++, Pascal e Ada) Clique aqui para acessar dados sobre o Volume I - Nível BásicoArthur Vargas Lopes, PhD Para adquirir contate a Editora da ULBRA (Preço promocional de R$ 25,00 incluindo despesas postais dentro do território brasileiro)Também a venda nas Livrarias SULINA Download Compiladores para Ada e Pascal
Aos meus pais Danilo e Carmen
Este livro é o segundo volume sobre as estruturas de dados fundamentais para construção de software. Este volume apresenta as estruturas e os algoritmos intermediários que servem de alicerce para o estudo e construção de software. O primeiro volume apresenta as estruturas e os algoritmos básicos. Ambos hardware e software de um computador são o resultado de um conjunto de tecnologias. As estruturas de dados e os algoritmos representam a base a partir do qual a tecnologia de software é desenvolvida. O uso de algoritmos eficientes depende muito do emprego de estruturas de dados adequadas. Quando estes dois elementos são combinados de forma adequada temos uma "peça" de software de valor. O objetivo principal deste livro é o de auxiliar o leitor a desenvolver software através da disponibilização de um conjunto de algoritmos implementados em diversas linguagens de programação. O enfoque adotado na apresentação das estruturas e algoritmos visa explorar a idéia dos tipos de dados abstratos e conseqüentemente da programação orientada a objetos. Para demonstrar o uso e aplicações das estruturas de dados junto com o funcionamento dos algoritmos apresentados são utilizadas quatro das linguagens de programação mais populares junto ao ensino formal da Ciência da Computação. Estas linguagens são o Pascal, Ada 95, C e C++. A escolha destas linguagens se deve à sua importância junto aos profissionais que se dedicam ao ensino da programação e também aqueles que trabalham como programadores. O Pascal é utilizado porque ainda é uma linguagem muito popular. Ada 95 é utilizada porque sua filosofia e implementação induz à construção de programas menos sujeitos a erros e mais adequados aos princípios que norteiam a Engenharia de Software entre os quais de destacam o grau de qualidade, a manutembilidade, o reuso e a portabilidade. C e C++ são apresentados, juntamente com os programas em Pascal e Ada, em decorrência de sua atual popularidade. Este livro é recomendado para as diciplinas de Algoritmos, Estruturas de Dados e Programação Concorrente de cursos de graduação e pós-graduação e para programadores em geral. O capítulo 7 apresenta os conceitos básicos sobre árvores discutindo suas representações estática, estática com vetor, estática com tabelas e cursores e dinâmica. São também discutidos os algoritmos e suas implementações para os caminhamentos pré-fixado, central e pós-fixado, árvores de expressão e heaps. No capítulo 8 são estudados os algoritmos e suas implementações para ordenação interna para os métodos da seleção linear, seleção linear otimizado, inserção, bolha, Shell, heap sort, merge sort, quick sort, contagem e radix sort. No capítulo 9 são estudados os algoritmos com suas implementações para ordenação externa pelos métodos de merge em duas e mais vias. O capítulo 10 discute os algoritmos e implementações para os métodos de pesquisa seqüencial, binária, por árvore binária de busca, em RAM e disco, e árvore B, trie e hash. O capítulo 11 introduz a programação concorrente e apresenta algoritmos concorrentes para ordenação e pesquisa juntamente com suas implementações em Ada. O Anexo 1 apresenta a notação BNF. Esta notação é utilizada no capítulo 11 para apresentar algumas das construções da linguagem Ada 95.Os fontes dos programas, nas linguagens Pascal, Ada 95, C e C++, podem ser obtidos junto com os discos distribuídos com a edição especial do livro Introdução à Linguagem Ada 95, editado pela Editora da ULBRA. Estes fontes encontram-se armazenados no diretório <dir>\Examples\Livro-DS sendo que <dir> representa o nome do caminho ("path") onde o sistema Ada+SQL, que acompanha o livro citado, foi instalado. Gostaria de agradecer a aos professores Aldoir Rigoni, diretor do Centro de Ciências Naturais e Exatas, e Miguel Rodrigues Fornari, chefe do Departamento de Informática, ambos da Universidade Luterana do Brasil, pelo apoio e estímulo recebedidos para a elaboração destes dois volumes.
7. Árvores
Alocação Estática Alocação Estática com Vetor Alocação Estática com Tabela e Cursores Alocação Dinâmica Caminhamentos Algoritmo 7.1: Pré-Fixado(X) Algoritmo 7.2: Central(X) Algoritmo 7.3: Pós-Fixado(X) Árvore de Expressão Algoritmo 7.4: Gera_Arvore_De_Expressao(Exp, Raiz) Sub-Algoritmo 7.4.1: X <- Novo_No(K) Sub-Algoritmo 7.4.2: TExp_Insere(Temp) Implementações Árvore de Expressão em Pascal Árvore de Expressão em Ada Desenho de Árvore de Expressão em Ada Árvore de Expressão em C Árvore de Expressão em C++ Heaps Algoritmo 7.5: Inicializa(Heap) Algoritmo 7.6: Insere(Heap,Va) Algoritmo 7.7: X <= Remove(Heap) Algoritmo 7.8: Imprime(Heap) Implementações Heap em Pascal Heap em Ada Heap em C Heap em C++ Resumo Exercícios
8. Métodos de Ordenação Interna
Ordenação por Seleção Linear em Pascal Ordenação por Seleção Linear em Ada Ordenação por Seleção Linear em C Ordenação por Seleção Linear em C++ Seleção Linear Otimizado Algortimo 8.2. - Sort_Selecao_Linear_Otimizado(V) Implementações Ordenação por Seleção Linear Otimizado em Pascal Ordenação por Seleção Linear Otimizado em Ada Ordenação por Seleção Linear Otimizado em C Ordenação por Seleção Linear Otimizado em C++ Inserção Algortimo 8.3. - Sort_Insercao(V) Implementações Ordenação por Inserção em Pascal Ordenação por Inserção em Ada Ordenação por Inserção em C Ordenação por Inserção em C++ Bolha Algortimo 8.4 - Sort_Bolha(V) Implementações Ordenação por Bolha em Pascal Ordenação por Bolha em Ada Ordenação por Bolha em C Ordenação por Bolha em C++ Shell Algortimo 8.5 - Shell_Sort(V) Implementações Ordenação por Shell em Pascal Ordenação por Shell em Ada Ordenação por Shell em C Ordenação por Shell em C++ Heap Sort Algortimo 8.6 - Heap_Sort(V) Implementações Ordenação por Heap em Pascal Ordenação por Heap em Ada Ordenação por Heap em C Ordenação por Heap em C++ Merge Sort Algortimo 8.7 - Merge_Sort(V,Esq,Dir) Implementações Ordenação por Merge em Pascal Ordenação por Merge em Ada Ordenação por Merge em C Ordenação por Merge em C++ Quick Sort Algortimo 8.8 - Quick_Sort(V,Esq,Dir) Implementações Ordenação por QuickSort em Pascal Ordenação por QuickSort em Ada Ordenação por QuickSort em C Ordenação por QuickSort em C++ Contagem Algortimo 8.9 - Contagem(V) Implementações Ordenação por Contagem em Pascal Ordenação por Contagem em Ada Ordenação por Contagem em C Ordenação por Contagem em C++ Radix Sort Algortimo 8.10 - Radix_Sort(V) Implementações Ordenação por Radix em Pascal Ordenação por Radix em Ada Ordenação por Radix em C Ordenação por Radix em C++ Resumo Exercícios
9. Métodos de Ordenação Externa
Ordenação por Merge em Duas Vias em Pascal Ordenação por Merge em Duas Vias em Ada Ordenação por Merge em Duas Vias em C Ordenação por Merge em Duas Vias em C++ Merge em P Vias Algoritmo 9.2: Merge_P_Vias(A,A’) Sub-algoritmo 9.2.1: Distribui_F(P) Sub-algoritmo 9.2.2: Fase Implementações Ordenação por Merge em P Vias em Pascal Ordenação por Merge em P Vias em Ada Ordenação por Merge em P Vias em C Ordenação por Merge em P Vias em C++ Outros Métodos Resumo Exercícios
10. Métodos de Pesquisa
Pesquisa Seqüêncial em Pascal Pesquisa Seqüêncial em Ada Pesquisa Seqüêncial em C Pesquisa Seqüêncial em C++ Pesquisa Binária Algoritmo 10.6: Insere(T,K) Algoritmo 10.7: X <= Consulta(T,K) Algoritmo 10.8: Remove(T,P) Implementações Pesquisa Binária em Pascal Pesquisa Binária em Ada Pesquisa Binária em C Pesquisa Binária em C++ Árvores de Busca Algoritmo 10.9 Inicializa(R) Algoritmo 10.10: Insere( (R,K) Algoritmo 10.11: X <== Consulta( (R,K) Algoritmo 10.12: Mínimo( (R,M) Algoritmo 10.13: Sucessor( (R,X,S) Algoritmo 10.14: Remove( (R,X) Implemetações Árvore de Busca por Alocação Dinâmica em Pascal Árvore de Busca por Alocação Dinâmica em Ada Árvore de Busca por Alocação Dinâmica em C Árvore de Busca por Alocação Dinâmica em C++ Árvore de Busca em Disco Algoritmo 10.15: F <= Inicializa(Fn) Algoritmo 10.16: F <= Abre (Fn) Algoritmo 10.17: E <= Fecha (Floresta) Algoritmo 10.18: X <= Hash (S) Algoritmo 10.19: X <= Seek (Floresta,O,M) Algoritmo 10.20: E <= Le (Floresta,Nodo,W) Algoritmo 10.21: E <= Grava (Floresta,Nodo,W) Algoritmo 10.22: X <= Prepara (Floresta,K,Tag) Algoritmo 10.23: X <= Insere (Floresta,K,Tag) Algoritmo 10.24: X <= Consulta (Floresta,K) Algoritmo 10.25: X <= Remove (Floresta,K) Algoritmo 10.26: X <= Tempo_De_Compactar (Floresta) Algoritmo 10.27: X <= Squash (Fn) Algoritmo 10.28: Imprime (Floresta) Implementações Árvore de Busca em Disco em Pascal Árvore de Busca em Disco em Ada Árvore de Busca em Disco em C Árvore de Busca em Disco em C++ Árvore B Propriedades Algoritmo 10.29: Init_C(X) Algoritmo 10.30: Inicializa (R) Algoritmo 10.31: Divide_Filho (X,I,FI) Algoritmo 10.32: Insere_Nao_Cheio (X,K,Tag) Algoritmo 10.33: Insere (Ra,K,Tag) Algoritmo 10.34: X <= Consulta (R,K) Algoritmo 10.35: X <= Remove (R,K) Algoritmo 10.36: Squash (Ra) Algoritmo 10.36.1: Squash_2 (Ra,Nova) Algoritmo 10.37: Conta (R,Deletados,Ativos) Algoritmo 10.38: Imprime (Ra) Implementações Árvore B em Pascal Árvore B em Ada Árvore B em C Árvore B em C++ Trie Algoritmo 10.39: Inicializa(R) Algoritmo 10.40: Insere (R,K,Tag) Algoritmo 10.41: X <= Consulta (R,K) Algoritmo 10.42: X <= Remove (R,K) Algoritmo 10.43: Imprime (P,K) Implementações Pesquisa por Trie em Pascal Pesquisa por Trie em Ada Pesquisa por Trie em C Pesquisa por Trie em C++ Hash Aberto Algoritmo 10.44: Inicializa(T) Algoritmo 10.45: X <= Hash (K) Algoritmo 10.46: Insere_Tab (T,K,Tag,Colide,B) Algoritmo 10.47: X <= Consulta (T,K) Algoritmo 10.48: Remove (T,K,R) Algoritmo 10.49: Insere (T,K,Tag) Algoritmo 10.50: X <= Quantidade (T) Algoritmo 10.51: Imprime (T) Implementações Pesquisa por Hash Aberto em Pascal Pesquisa por Hash Aberto em Ada Pesquisa por Hash Aberto em C Pesquisa por Hash Aberto em C++ Resumo Exercícios
11. Algoritmos Concorrentes
Fim da Listagem 11.1 - Duas Tasks Asíncronas Testando o Programa Tasks_Asincronas Fim da Listagem 11.2 – Tasks_Asíncronas_2 Declaração de Tasks Como um Tipo de Dado Fim da Listagem 11.3 – Tasks_Asincronas_3 Tasks Síncronas Mensagens Entry Fim da Listagem 11.4 - Tasks Síncronas_1 Testando o Programa Tasks_Sincronas_1 Accept Entry Call Fila de Entry Fim da Listagem 11.5 - Tasks Síncronas2 Comando delay Delay Relativo Fim da Listagem 11.6 – Delay_1 Testando o Programa Delay_1 Delay Until Fim da Listagem 11.7 – Delay_2 Testando o Programa Delay_2 Comando abort Comando select Quick Sort Concorrente Unidades Protegidas Resumo Exercícios
Bibliografia Anexo 1 - A Notação BNF
|
(C) 2002-2007 Arthur V. Lopes