Estruturas V. I

Estruturas de Dados para Construção de Software

Volume I – Nível Básico

(440 páginas e mais de 340 programas em C, C++, Pascal e Ada)

Clique aqui para acessar dados sobre o Volume II - Nível Intermediário

Arthur Vargas Lopes, PhD

Para adquirir contate a Editora da ULBRA

(Preço promocional de R$ 39.50 incluindo despesas postais dentro do território brasileiro)

Também a venda nas Livrarias SULINA

Download Compiladores para Ada e Pascal

Prefácio

Este livro é o primeiro volume sobre estruturas de dados fundamentais para construção de software. Este volume apresenta as estruturas e os algoritmos básicos que servem de alicerce para o estudo e construção de software. O segundo volume apresenta as estruturas e os algoritmos intermediários. 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 por conseguinte 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 o 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 de cursos de graduação e para programadores em geral.

O capítulo 1 apresenta uma introdução onde são discutidos a programação estruturada, os princípios da engenharia de software, a programação orientada a objetos, o reuso de software, a programação concorrente as linguagens utilizadas, Pascal, Ada 95, C e C++ para a implementação dos algorimos estudados, revisando alguns conceitos sobre memória e o significado de um objeto na memória terminando com uma apresentação da técnica de estimação de performance de algoritmos.

O capítulo 2 discute os arrays, suas disposições na memória e funções de mapeamento, os arrays especiais, tipos de dados abstratos e a recursividade.

O capítulo 3 discute as pilhas e a notação polonesa.

O capítulo 4 discute as filas simples e circulares e os deques.

O capítulo 5 discute as listas encadeadas simples, duplas e circulares.

No capítulo 6 apresenta os conceitos e definições sobre os grafos dirigidos e valorados discutindo suas representações pela matrix de adjacência, lista de adjacência encadeada e seqüencial. São também discutidos os algoritmos e suas implementações para os caminhamentos em profundidade e amplitude, para encontrar menores caminhos, gerar caminhos de menor custo, encontrar o menor caminho, definir a conectividade de vértices, encontrar o centro de um grafo e para a ordenação topológica.

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 este livro, 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 livros.

1. Introdução

Programação Estruturada

Estruturas de Controle

Composição Modular

Formato do Programa

Comentários

Entendimento X Eficiência

Refinamentos Sucessivos

Verificação de Programa

Engenharia de Software

Ciclo de Vida

Programação Orientada a Objetos

Reuso de Software

Programação Concorrente

As Linguagens Utilizadas

Pascal

Ada 95

Ada na Internet

Association of Computer Machinery Ada Special Interest Group (SIGAda)

Public Ada Library (PAL)

C

C++

Relembrando Alguns Conceitos

Memória

Endereço

Declaração de Objetos

Estimação de Performance

Big O

O Método:

Resumo

Exercícios

2. Arrays

Vetores

Matrizes

Armazenamento de Matrizes

Por Linha

Por Coluna

Função Mapeamento

Vetores

Matrizes

Arrays Tri-Dimensionais

Arrays Especiais

Vetores de Bits

Matrizes de Bits

Matrizes de Quatro Linhas

Matrizes Triangulares

Tipos de Dados Abstratos

A Implementação de um TDA em Ada

A Implementação de um TDA em C++

Recursividade

Implementações

ETF Em Pascal

ETF Em Ada

ETF Em C

ETF Em C++

Resumo

Exercícios

3. Pilhas

Algoritmo 3.1: Inicializa(P)

Algoritmo 3.2: Push(P,D)

Algoritmo 3.3: Pop(P,R)

Implementações

Pilha em Pascal

Pilha em Ada

Pilha em C

Pilha em C++

Notação Polonesa

Avaliação de Expressões na Forma Pós-fixada

Algoritmo 3.4: Avalia_Posfix(E,R)

Implementações

Avaliação de Expressão Pós-fixada em Pascal

Avaliação de Expressão Pós-fixada em Ada

Avaliação de Expressão Pós-fixada em C

Avaliação de Expressão Pós-fixada em C++

Resumo

Exercícios

4. Filas e Deques

Algoritmo 4.1: Inicializa(F)

Algoritmo 4.2: Queue(F,D)

Algoritmo 4.3: DeQueue(F,R)

Implementações

Fila em Pascal

Fila em Ada

Fila em C

Fila em C++

Filas Circulares

Algoritmo 4.4: Inicializa(F)

Algoritmo 4.5: Queue(F,D)

Algoritmo 4.6: DeQueue(F,R)

Implementações

Fila Circular em Pascal

Fila Circular em Ada

Fila Circular em C

Fila Circular em C++

Deques

Algoritmo 4.7-: Inicializa(D)

Algoritmo 4.8: Insere_Esq(D,d)

Algoritmo 4.9: Insere_Dir(D,d)

Algoritmo 4.10: Retira_Esq(D,R)

Algoritmo 4.11: Retira_Dir(D,R)

Resumo

Exercícios

5. Listas Encadeadas

Listas Encadeadas Simples

Algoritmo 5.1: Inicializa(Ls)

Algoritmo 5.2: Insere_Esq(Ls,D)

Algoritmo 5.3: Insere_Dir(Ls,D)

Algoritmo 5.4: Insere_Dir_No(Ls,Q,D)

Algoritmo 5.5: Retira_Esq(Ls,R)

Algoritmo 5.6: Retira_Dir(Ls,R)

Algoritmo 5.7: Retira_No(Ls,Q,R)

Algoritmo 5.8: Consulta(Ls,D,R)

Algoritmo 5.9: Libera_Memoria(Ls)

Implementações

Lista Encadeada Simples em Pascal

Lista Encadeada Simples em Ada

Lista Encadeada Simples em C

Lista Encadeada Simples em C++

Listas Encadeadas Duplas

Algoritmo 5.10: Inicializa(Ld)

Algoritmo 5.11: Insere_Esq(Ld,D)

Algoritmo 5.12: Insere_Dir(Ld,D)

Algoritmo 5.13: Insere_Dir_No(Ld,Q,D)

Algoritmo 5.14: Retira_Esq(Ld,R)

Algoritmo 5.15: Retira_Dir(Ld,R)

Algoritmo 5.16: Retira_No(Ld,Q,R)

Algoritmo 5.17: Consulta(Ld,D,R)

Algoritmo 5.18: Libera_Memoria(Ld)

Implementações

Lista Encadeada Dupla em Pascal

Lista Encadeada Dupla em Ada

Lista Encadeada Dupla em C

Lista Encadeada Dupla em C++

Listas Encadeadas Duplas Circulares

Algoritmo 5.19: Inicializa(Ld)

Algoritmo 5.20: Insere_Esq(Ld,D)

Algoritmo 5.21: Insere_Dir(Ld,D)

Algoritmo 5.22: Insere_Dir_No(Ld,Q,D)

Algoritmo 5.24: Retira_Dir(Ld,R)

Algoritmo 5.25: Retira_No(Ld,Q,R)

Algoritmo 5.26: Consulta(Ld,D,R)

Algoritmo 5.27: Libera_Memoria(Ld)

Implementações

Lista Encadeada Dupla Circular em Pascal

Lista Encadeada Dupla Circular em Ada

Lista Encadeada Dupla Circular em C

Lista Encadeada Dupla em C++

Fragmentação de Memória

Resumo

Exercícios

6. Grafos Dirigidos

Definições

Adjacência

Grau de Entrada

Grau de Saída

Caminho

Caminho Simples

Comprimento de um Caminho

Ciclo

Laço

Sub-Grafo

Grafo Conexo

Grafo Fortemente Conexo

Grafo Parcial

Grafo Acíclico

Rede

Componentes Fortes

Representações

Matriz de Adjacência

Algoritmo 6.1: Inicializa(G)

Algoritmo 6.2: Conecta(G,I,J)

Algoritmo 6.3: Desconecta(G,I,J)

Algoritmo 6.4: X <= Adjacente(G,I,J)

Algoritmo 6.5: Imprime(G)

Implementações

Matriz de Adjacência em Pascal

Matriz de Adjacência em Ada

Matriz de Adjacência em C

Matriz de Adjacência em C++

Lista de Adjacência

Algoritmo 6.6: Inicializa(G)

Algoritmo 6.7: Conecta(G,I,J)

Algoritmo 6.8: Desconecta(G,I,J)

Algoritmo 6.9: X <= Adjacente(G,I,J)

Algoritmo 6.10: Libera_Memoria(G)

Algoritmo 6.11: Imprime(G)

Implementações

Lista de Adjacência em Pascal

Lista de Adjacência em Ada

Lista de Adjacência em C

Lista de Adjacência em C++

Lista de Adjacência Estática

Caminhamentos

Caminhamento em Profundidade

Algoritmo 6.12: DFS(G,I,V)

Caminhamento em Amplitude

Algoritmo 6.13: BFS(G,I)

Implementações

Caminhamento em Pascal

Caminhamento em Ada

Caminhamento em C

Caminhamento em C++

Grafos Valorados

Algoritmo 6.14: Inicializa(G)

Algoritmo 6.15: Conecta(G,I,J,V)

Algoritmo 6.16: Desconecta(G,I,J)

Algoritmo 6.17: X <= Adjacente(G,I,J)

Algoritmo 6.18: Imprime(G)

Encontrando os Menores Caminhos

Algoritmo 6.19: Menores_Custos(G,C)

Gerando Caminhos de Menor Custo

Algoritmo 6.20: Gera_Caminhos(G,P)

Algoritmo 6.21: Exibe_Caminho(P,I,J)

Encontrando o Melhor Caminho

Algoritmo 6.22: Menor_Caminho(G,I,J)

Definindo a Conectividade dos Vértices de um Grafo

Algoritmo 6.23: Gera_Conectividade(G,Cd)

Encontrando o Centro de um Grafo

Algoritmo 6.24: X <= Centro(G)

Implementações

Grafos Valorados em Pascal

Grafos Valorados em Ada

Grafos Valorados em C

Grafos Valorados em C++

Ordenação Topológica

Algoritmo 6.25: Sort_Topologico(D)

Sub-algoritmo 6.25.1: Sort(D,I,V)

Implementações

Ordenação Topológica em Pascal

Ordenação Topológica em Ada

Ordenação Topológica em C

Ordenação Topológica em C++

Resumo

Exercícios

Bibliografia

Errata para a primeira edição de livro Estruturas de Dados para Construção de Software – Nível Básico – Volume I:

1. Página 34, segundo parágrafo:

... de N maiores que 10.

2. Página 62, terceira linha: