Algoritmos e Estruturas de Dados

Transcrição

�
�
�
MATEUS�CONRAD�BARCELLOS�DA�COSTA�
Algoritmos e Estruturas de
Dados
M.�B.�Costa��Algoritmos�e�Estruturas�de�Dados
[ Serra, ES ]
[ 2008 ]
2
Referências utilizadas na elaboração deste material
1. LISKOV B. Data Abstraction and Hiararchy. In OOPSLA87:
Conference on Object Oriented Programming Systems Languages and
Applications. Addendum to the proceedings on Object-oriented
programming systems, languages and applications, 1987.
2. TENENBAUM A. M. Data Structs using C. Prentice Hall Int.
Editions, 1990.
3. ZIVIANI N. Projeto de Algoritmos. Segunda Edição. Pioneira, 2003.
3
Meu nome é Mateus Barcellos Costa, sou professor e pesquisador do Ifes
desde 2005. Atuo na área de Engenharia de Software e em disciplinas de
Programação. Se você quiser mais informações sobre mim e sobre os
trabalhos que desenvolvo, pode
visitar minha página pessoal em
http://www.sr.cefetes.br/~mcosta.
Produzi o material que ora lhe apresento como instrumento básico para o
estudo da disciplina de Técnicas de Programação Avançada. Nesta disciplina
iremos aprofundar nossos conhecimentos em Programação de Computadores
usando uma linguagem imperativa. Exemplos destas linguagens são C e
Pascal. Iremos adotar a linguagem C, em nossos exemplos e
implementações. No entanto, é preciso que você saiba que os conceitos
estudados aqui vão além da linguagem e podem ser aplicados em diversos
cenários, na programação e na Engenharia de Software como um todo.
4
Sumário
1�
2�
Abstração de dados ...................................................................................... 7�
1.1�
Introdução ............................................................................................ 7�
1.2�
Conceitos de abstração de dados .......................................................... 9�
1.2.1�
Abstração em Computação........................................................... 9�
1.2.2�
Abstração de Procedimentos ...................................................... 11�
1.2.3�
Tipos Abstratos de Dados .......................................................... 13�
1.2.4�
Implementação de Tipos Abstratos de Dados ............................ 19�
1.2.5�
Avaliação de Implementações de Tipos Abstratos de Dados ..... 20�
Tipos Abstratos de Dados Fundamentais ................................................... 25�
2.1�
2.1.1�
Especificação do TAD Pilha ...................................................... 26�
2.1.2�
Implementação de Pilhas em Arranjos ....................................... 28�
2.2�
4�
Filas .................................................................................................... 31�
2.2.1�
Especificação do TAD FILA...................................................... 32�
2.2.2�
Implementação de Filas em arranjos com deslocamento ........... 35�
2.2.3�
Implementação de Filas com Arranjos circulares ...................... 37�
2.3�
3�
Pilhas .................................................................................................. 25�
Implementação de TADS com alocação dinâmica de memória ......... 40�
2.3.1�
Revisão de Alocação Dinâmica de Memória ............................. 40�
2.3.2�
Implementação do TAD Pilha .................................................... 47�
2.3.3�
Implementação do TAD Fila ...................................................... 50�
Listas e Árvores.......................................................................................... 55�
3.1�
Listas Circulares ................................................................................. 55�
3.2�
Lista Circular Duplamente encadeada ................................................ 64�
3.3�
Árvores Binárias................................................................................. 69�
3.3.1�
Árvore Binária de Pesquisa ........................................................ 70�
3.3.2�
O TAD Árvore Binária de Pesquisa ........................................... 71�
3.3.3�
Implementação do TAD árvore Binária de Pesquisa ................. 72�
Pesquisa em Memória Primária.................................................................. 83�
4.1�
Pesquisa Sequencial ........................................................................... 85�
4.1.1�
Implementação da Pesquisa Seqüencial ..................................... 86�
4.1.2�
Tempo de execução de algoritmos ............................................. 87�
4.2�
Pesquisa Binária ................................................................................. 89�
4.3�
Tabelas Hash ...................................................................................... 92�
4.3.1�
Operações de Inserção e Pesquisa em Tabelas Hash................. 94�
5
5�
4.3.2�
Tratamento de Colisões .............................................................. 96�
4.3.3�
Tratamento de Colisão usando endereçamento Aberto .............. 98�
Ordenação em Memória Primária ............................................................ 100�
5.1�
Conceitos Básicos de ordenação ...................................................... 100�
5.1.1�
5.2�
Operações Típicas de processos de Ordenação ........................ 100�
Métodos de Ordenação ..................................................................... 101�
5.2.1�
Ordenação por Seleção ............................................................. 101�
5.2.2�
Método da Inserção .................................................................. 103�
5.2.3�
Método da Bolha ...................................................................... 104�
5.2.4�
Desempenho dos métodos de Seleção, Inserção e Bolha ........ 105�
5.2.5�
Método de Shell ....................................................................... 106�
5.2.6�
O Método Quicksort ................................................................. 109�
6
1
ABSTRAÇÃO DE DADOS
Olá! Neste Capítulo iremos discutir e aprender sobre Abstração de Dados.
Abstração de Dados é uma técnica de programação que visa simplificar o
desenvolvimento de programas. Sua aplicação pode se dar no
desenvolvimento de programas menores. Mas podemos afirmar que seria
impossível o desenvolvimento de sistemas que temos hoje, com milhões de
linhas de código, sem o uso de abstração de dados.
1.1 INTRODUÇÃO
Um programa de computador desenvolvido para atender alguma finalidade
prática é, normalmente, um artefato complexo. Por esse motivo, a atividade de
desenvolvimento desses artefatos, a programação de computadores, está entre as
atividades mais complexas desempenhadas pelo homem. Se você cursou
disciplinas introdutórias de programação, pode estar se questionando: � Ora,
desenvolver um programa não é tão complexo assim! Basta compreender o problema,
suas entradas e suas saídas e construir a solução usando uma linguagem de
programação. Simples não? Não! A história da programação tem dado provas
que programar não é tão simples assim.
Figura 1.1: O Gap Semântico.
Programar é uma atividade complexa por diversos aspectos, tanto de cunho
teórico quanto prático. Dentre estes aspectos destacamos os seguintes:
1. Programar um computador significa desenvolver programas de
computadores (formais e precisos) para atender a finalidades práticas
definidas em termos de conceitos do mundo real (informais e
imprecisos). Existe um abismo entre o mundo dos problemas reais e o
mundo das soluções. Esse abismo é chamado na computação de gap
semântico. Transpor o abismo é um dos desafios centrais da
programação de computadores e da Engenharia de Software como um
7
todo. A Figura 1.1 é uma alegoria que busca mostrar a função do
desenvolvedor de software: Transpor o abismo entre o mundo informal
(dos problemas) e o mundo formal (das soluções computacionais).
Nessa transposição existem muitos desafios e perigos que podem
dificultar a trajetória do desenvolvedor.
2. Muitas vezes, em disciplinas iniciais de programação, deparamo-nos
com o desenvolvimento de programas mais simples, de cunho didático.
Por exemplo, programas para calcular médias ou somatórios. Em outros
momentos fazemos programas para aprender a usar um certo
mecanismo, por exemplo, apontadores. Aqui, estamos nos referindo a
programas de computadores para ajudar pessoas a resolverem problemas
do mundo real, problemas grandes e complexos! Exemplos desses
problemas incluem:
a. Gerenciar as operações financeiras de uma empresa;
b. Controlar uma aeronave;
c. Controlar os trens de uma malha ferroviária;
d. Produzir edições diárias de um jornal;
e. Gerenciar o processo de produção de um filme.
3. Problemas como esses não são simples de se resolver.
Conseqüentemente, programas voltados para essas finalidades são
complexos, levam muito tempo para ficar prontos, têm de ser
desenvolvidos por uma equipe de pessoas, utilizando diversas
tecnologias e seguindo um processo de desenvolvimento sistemático.
4. Para atender às funcionalidades esperadas, um programa deve
apresentar um conjunto de características que juntas vão tornar o
programa efetivamente útil e determinarão a qualidade do mesmo.
Essas características são as seguintes:
a. Um programa deve estar correto, livre de erros;
b. Um programa deve ser robusto. Um programa robusto ou
sistema robusto é aquele que consegue funcionar, mesmo que
precariamente, diante de uma adversidade. Por exemplo,
suponha que um programa precise dos dados x, y e z para
realizar uma tarefa. Se este for robusto, na falta de um dos
dados, o programa pode tentar realizar o processamento possível
com a ausência dado;
c. Um programa deve ser eficiente. A eficiência de um programa
está relacionada ao seu tempo de execução (eficiência na
execução) ou ao espaço em memória (eficiência na ocupação)
de que necessita para executar (área de dados). Para um
problema há infinitas soluções (programas). Quanto menores
esses valores mais eficiente o programa. Em computação podese verificar se uma solução é ótima (mais eficiente possível)
para um problema;
d. Um programa deve ser compatível com outros programas;
e. Um programa deve ser fácil de usar;
8
f.
Um programa deve ser portável, podendo funcionar em
diferentes plataformas ou sistemas operacionais;
g. Um programa deve ser íntegro, ou seja, deve evitar que os dados
sejam corrompidos ou violados;
h. O processamento realizado pelo programa deve ser verificável;
i.
O programa ou partes dele devem poder ser utilizados em outros
cenários diferentes daquele para o qual o programa foi
originalmente desenvolvido.
5. Por último, devemos considerar a atividade de programação como
atividade econômica. Assim como outras atividades econômicas, o
desenvolvimento de software é regido por leis de mercado que impõem
severas exigências aos desenvolvedores. De acordo com essas leis, não
basta apenas desenvolver um programa que atenda à finalidade
esperada. Esses programas devem ser desenvolvidos dentro dos prazos
e custos estabelecidos. Além disso, o programa precisa ter outras
características importantes que permitam a sua evolução. Essas
características são chamadas de fatores internos. São eles:
a. Facilidade de manutenção;
b. Facilidade de evolução;
c. Fácililade de entendimento;
d. Modularidade.
Pelos motivos discutidos acima, o desenvolvimento de programas requer a
aplicação de princípios, métodos e técnicas que diminuam a complexidade desse
desenvolvimento. A Abstração de Dados envolve uma série de conceitos e
princípios para esse fim. A seguir discutiremos esses conceitos.
Atividade 1
Nesta introdução foram levantados cinco aspectos que tornam o
desenvolvimento de software uma tarefa difícil. Para atacar esses
aspectos e tornar o desenvolvimento de software mais simples são
consideradas três dimensões: Processo de desenvolvimento, Pessoas
(partes interessadas: clientes, desenvolvedores) e Tecnologias de
desenvolvimento. Releia os cinco motivos e tente escrever um texto
resumido, estabelecendo uma relação entre esses 5 motivos e essas
três dimensões.
1.2 CONCEITOS DE ABSTRAÇÃO DE DADOS
1.2.1 Abstração em Computação
A abstração é um dos conceitos mais importantes da computação. Sem o uso
deste conceito podemos afirmar que a evolução apresentada pela computação
teria sido mais lenta.
Segundo o dicionário Michaelis, temos a seguinte definição para a palavra
Abstração:
9
1. O ato ou efeito de abstrair. Consideração das qualidades independentemente
dos objetos a que pertencem. Abstrair: Considerar um dos caracteres de um
objeto separadamente;2. Excluir, prescindir de.
A finalidade principal de uso de abstração em qualquer área do conhecimento é
colocarmos foco em um subconjunto dos aspectos de um sistema ou processo
complexo. Considere, por exemplo, o processo de pintar um quadro. A Figura
1.2 mostra, à esquerda um esquema inicial mostrando as linhas principais do
quadro que se encontra do lado direito (A Virgem, o Menino e Sant’Ana,
Leonardo Da Vinci).
Figura 1.2: Abstração na Pintura.
Observe que, no desenho, as proporções, os detalhes das posturas e feições são
já determinados. Esse processo ajuda o pintor pois, no momento da idealização
do quadro, ele não precisa se preocupar com outros aspectos complexos, como
cores, nuances de sombras e reflexos, para definir a estrutura e a sua aparência
geral. Podemos dizer então que o desenho à esquerda é uma abstração do
quadro.
Em computação, abstração também possui finalidades semelhantes. Em
programação, especificamente, esse conceito está presente quase o tempo todo,
seja nas construções existentes nas linguagens, seja nos métodos de
programação empregados.
Uma das principais abstrações das linguagens de programação é o conceito de
variável. Uma variável é um conceito abstrato que esconde diversos aspectos
técnicos que não interessam ao programador. Quando declaramos uma variável
em um programa, essa declaração implica em coisas que não irão interferir no
seu desenvolvimento. Por exemplo, por trás de uma variável do tipo inteiro em
C, (ex. int x;), estão escondidas as características físicas do armazenamento da
variável em memória, a saber:
-
A forma de representação de números inteiros usando base 2 (por
exemplo, complemento de 2);
-
O padrão usado pelo hardware (ex. little endian, big endian);
-
O número de bytes que uma variável do tipo inteiro ocupa;
-
O endereço da variável na memória principal;
-
O conjunto de bits responsável por armazenar o sinal do número inteiro.
10
Para o programador em C, geralmente, nenhuma dessas informações é
importante. O que o programador deseja é utilizar a variável realizando as
operações permitidas aos números inteiros (operações aritméticas e
comparações), atribuir, recuperar e modificar o valor contido na variável.
Assim podemos dizer que uma variável permite ao programador abstrair-se
de detalhes que não interessam e não irão influenciar no comportamento do
programa.
Atividade 2
Os itens 1,2 e 3 são todos abstrações. Para cada um deles
descreva os aspectos que estão sendo escondidos e os aspectos
que realmente importam ao programador:
1. O comando
if(){
..
}
else{
..
}
2. um arquivo
3. a função scanf
1.2.2 Abstração de Procedimentos
Podemos afirmar que a grande maioria dos elementos de linguagem utilizados
em uma linguagem de programação de alto nível são abstrações. Essas
abstrações facilitaram o desenvolvimento de programas mais complexos e
sofisticados, evitando que programadores precisassem manipular bits e
endereços de memória e interagir diretamente com o sistema operacional.
Uma outra abstração de programação importante é a Abstração de
Procedimento.
Abstração de Procedimento
A abstração de procedimento permite que o programador crie, ele mesmo, sua
forma de abstrair, utilizando os comandos disponíveis na linguagem. A
possibilidade de criar procedimentos permite ao programador criar
funcionalidades mais abstratas que escondem a seqüência de operações
necessária para a realização de uma tarefa complexa.
Por exemplo, sabemos que na linguagem C não existe um comando que seja
capaz de ordenar um vetor de inteiros em ordem crescente. Seria muito bom que
pudéssemos contar com esse comando, certo? Mas, como não temos esse
comando, iremos criar uma função (abstração de procedimento) que realize essa
tarefa para nós. A função ordena na Figura 1.3 é essa abstração.
11
void ordena(int a[], int tamanho) {
int i, j, valor;
for(i = 1; i < tamanho; ++i) {
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; --j){
a[j + 1] = a[j];
}
a[j+1] = valor;
}
}
Figura 1.3: Função ordena: Cria uma abstração do procedimento de ordenação.
Após a implementação da função ordena, quando o programador precisar
ordenar um vetor, basta que ele invoque a função, passando os parâmetros
necessários. Ou seja, ao usar o procedimento, o programador irá se preocupar
apenas com o que a função faz e não mais com os detalhes de sua
implementação.
Uma abstração de procedimento deve realizar uma tarefa (por exemplo, ordenar
um vetor de inteiros) que deve ser independente da forma como este vai ser
implementado. O programador deve antes de tudo ver o procedimento como
uma caixa preta, cuja especificação deve conter três elementos básicos (Figura
1.4):
�
Entrada: O conjunto de dados de entrada necessário;
�
Saída: O conjunto de dados produzido pelo procedimento;
�
Função: A descrição do que o procedimento faz.
ENTRADA
FUNÇÃO
SAÍDA
Figura 1.4: Os elementos considerados na definição de um procedimento.
Na especificação do procedimento, o programador não deve estar preocupado
com a implementação, mas sim com o comportamento (função) do mesmo.
Qualquer implementação que realize a função especificada irá servir como
solução . Para o caso da ordenação, veremos adiante neste curso que existem
diferentes métodos de ordenar um vetor. O método utilizado na função ordena
se chama ordenação por inserção. A implementação interna poderia ser
substituída por qualquer outro método de ordenação. A própria linguagem C
oferece em sua biblioteca padrão stdlib, uma função chamada qsort, que
pode ser usada para ordenar vetores. Essa função utiliza um outro método de
ordenação muito conhecido e também muito rápido, chamado de Quick Sort.
12
Atividade 3:
1. Suponha que você tenha disponíveis as seguintes funções
em C:
�
�
�
�
Int CalculaMedia(int *notas);
Void DeterminaMaiorEMenorNotas(int *v, int
* maior, int *menor);
Void leNotas(int *notas);
Void
MostraResultados(int
media,int
maiorNota, int menorNota);
Utilizando essas funções, desenvolva um programa em C
que leia as notas de 5 turmas e para cada uma delas,
imprima a média, a maior e a menor nota.
1.2.3 Tipos Abstratos de Dados
A abstração de dados visa aos mesmos objetivos que a abstração de
procedimentos, mas com relação às estruturas de dados utilizadas nos
programas. A abstração de dados visa criar novos tipos de dados definidos em
temos de seu comportamento. Esses novos tipos são chamados de Tipos
Abstratos de Dados - TAD.
É muito importante que você perceba que um tipo abstrato de dados não se
resume a uma nova estrutura de dados. Vamos então discutir um pouco sobre
essa diferença.
Primeiramente, uma estrutura de dados pode ser definida simplesmente como
uma variável capaz de armazenar mais de um valor simultaneamente. Assim, um
vetor, uma matriz ou um registro (struct em C) são exemplos de estruturas de
dados. A combinação desses elementos em estruturas mais complexas dá origem
a outras estruturas de dados. A Figura 1.5 apresenta as declarações de struct
ponto e struct reta, como exemplos de tipos de estruturas de dado.
struct ponto{
float x, y;
};
struct reta {
struct ponto a,b;
};
Figura 1.5: Estruturas de Dados ponto e reta.
Ao definir a struct ponto, passamos a contar com mais uma alternativa
para definição de tipos de variáveis e, conseqüentemente, para a composição de
novos tipos de estruturas. Assim a struct reta foi definida como uma
composição de duas variáveis do tipo struct ponto. Essas estruturas
podem ser usadas para declarar tanto variáveis como argumentos de funções.
Em C temos ainda a cláusula typedef, que permite definir o nome do novo
tipo. Nesse caso, não precisamos usar a palavra reservada struct na
declaração de variáveis do tipo definido. Na Figura 1.6 temos o uso de
13
typedef. Veja que na definição do tipo Reta, o nome Ponto é usado sem a
palavra reservada struct.
typedef struct {
float x, y;
}Ponto;
typedef struct {
Ponto a,b;
}Reta;
Figura 1.6: Definição dos tipo Reta e Ponto.
Estrutura de Dados versus Tipo Abstrato de Dados
A definição de uma estrutura de dados se preocupa em demonstrar como o
objeto é representado na memória de um computador (representação). Nessa
definição são considerados aspectos do tipo: quais as informações que serão
armazenadas ali e qual a quantidade destas informações. A definição de um
Tipo Abstrato de Dados segue uma abordagem diferente. Essa definição é
feita em termos das operações que podem ser realizadas sobre o tipo.
A definição de um Tipo Abstrato de Dado (TAD) é chamada de especificação
e consiste, basicamente, em definir as operações relacionadas ao tipo.
Dizemos que essas operações definem o comportamento do TAD.
Vamos aplicar o conceito de TAD considerando os objetos Reta e Ponto. Um
passo importante na definição do TAD, que já ajuda na programação de uma
maneira geral, é que não conseguimos defini-lo sem conhecermos a sua
finalidade e o contexto no qual será usado. Em nosso exemplo precisamos
saber para quê? nós queremos um ponto e uma reta. Geralmente essa
informação é conseguida a partir do enunciado do problema. Assim, vamos
supor a seguinte descrição para o nosso problema envolvendo retas e pontos:
Problema A. É necessário um programa de computador que realize operações
geométricas envolvendo pontos e retas localizadas no plano cartesiano. O
programa deve permitir: calcular a distância do ponto até a origem do plano
cartesiano; calcular a distância entre dois pontos; dada a representação da reta
por dois pontos, calcular o ângulo de inclinação da reta, fornecer os
parâmetros a e b correspondentes a equação da reta ax + b. Determinar a
distância de uma reta a um ponto. Evidentemente, o programa deve permitir a
leitura e impressão de pontos e retas conforme a necessidade das operações.
Com base na descrição acima podemos identificar a necessidade do TAD ponto
e do TAD Reta, bem como suas operações. Essas operações aparecem
sublinhadas no texto do problema e são apresentadas nas Figuras 1.7 e 1.8.
Operações TAD Ponto:
-
Calcular Distância do ponto até
a Origem do plano cartesiano
Calcular Distância
14 até outro
ponto
Ler um ponto
Imprimir um ponto
Figura 1.7: operações do TAD Ponto para o problema A.
Operações TAD Reta:
-
Calcular o ângulo de inclinação
da reta
Calcular os parâmetros a e b
Calcular a Distância da reta a
até um ponto
Ler uma reta representada por
dois pontos
Imprimir uma reta representada
por dois pontos
-
Figura 1.8: operações do TAD Reta para o problema A.
Agora, considere que estejamos desenvolvendo um programa para o problema
abaixo:
Problema B. É necessário um programa de computador para apresentar
graficamente figuras geométricas formadas por pontos e retas, usando o
monitor do computador como plano. O programa deve permitir: ler um ponto,
plotar um ponto na tela, ligar dois pontos por um segmento de reta; dada uma
reta passando por esse ponto, deslocar um outro ponto com base na equação
dessa reta; dada uma reta representada por dois pontos, plotar esta reta no
monitor; dada uma reta e um valor d, criar uma reta paralela à reta dada a uma
distancia d da reta.
As operações necessárias aos TAD Ponto e Reta neste problema são
apresentadas nas Figuras 1.9 e 1.10.
Operações TAD Ponto:
-
Ler um ponto
Plotar um ponto
Ligar dois pontos
Deslocar um ponto
Figura 1.9: operações do TAD Ponto para o problema B.
Operações TAD Reta:
-
Ler uma Reta 15
Plotar uma Reta
Criar Reta Paralela
Figura 1.10: operações do TAD Reta para o problema B.
Note que nos dois problemas foram definidos os tipos Ponto e Reta. No
entanto, a abstração necessária difere de um problema para o outro,
interferindo na definição das operações. Embora existam essas diferenças,
iremos sempre tentar criar abstrações mais genéricas o quanto for possível.
Quanto mais genérico um TAD, maior o um número de problemas em que
esse poderá ser aplicado.
Embora as operações não informem nada a respeito da representação interna
de um TAD, elas fornecem ao programador tudo o que ele precisa para
manipular o TAD. As operações de um TAD especificam a sua interface com
o restante do programa. Isso significa que Qualquer ação relacionada ao
TAD deve ser feita mediante uma de suas operações.
Temos como resultado prático que o programador, ao usar o TAD, não vai
precisar se preocupar com sua implementação interna . Iremos agora analisar
esse aspecto considerando os TAD Ponto e Reta e o problema A.
Na implementação, ponto e reta foram definidos e implementados, originando
dois módulos independentes: o módulo Ponto e o módulo Reta. Cada módulo em
C é normalmente implementado por dois arquivos: o arquivo .h e o arquivo .c.
No arquivo .c teremos a implementação das operações do TAD e no arquivo .h
teremos a especificação da interface do TAD. A Figura 1.11 e a Figura 1.12
apresentam as interfaces dos módulos Ponto e Reta, respectivamente.
// interface do Tad Ponto: ponto.h
typedef struct ponto {
int x, int y;
}Ponto;
void lerPonto(Ponto *);
void distanciaOrigem(Ponto);
void distancia2Pontos(Ponto,Ponto);
Figura 1.11: Interface do TAD Ponto.
// interface do Tad Reta: Reta.h
typedef struct reta {
struct ponto a,b;
} Reta;
void lerReta(Reta *);
void distanciaRetaPonto(Reta,Ponto);
void InclinacaoReta(Reta);
void equacaoReta(Reta);
16
Figura 1.12: Interface do TAD Reta.
Com a implementação dos TADs Ponto e Reta concluídas e devidamente
testadas, qualquer outro módulo do programa poderá utilizar esses tipos por
meio das operações definidas para os mesmos. Quando um módulo A utiliza
um módulo B em programação, dizemos que o módulo A é cliente do módulo
B. Essa relação de clientela entre os módulos (ou TADs) de um programa
pode ser representada graficamente por meio de um diagrama de estrutura
modular - DEM.
Diagrama de Estrutura Modular
Um diagrama de estrutura modular é formado por retângulos e linhas
direcionadas relacionando os retângulos. Cada retângulo representa um
módulo. As linhas direcionadas significam cliente de” e indicam o
acionamento de operações contidas no módulo apontado pelo módulo cliente.
Esses digramas também são chamados diagramas hierárquicos pois
apresentam a hierarquia dos módulos, iniciando por um módulo que inicia o
programa e aciona os demais módulos.
Como exemplo, suponha que tenhamos também, junto aos módulos Ponto e
Reta, um módulo chamado principal. Esse módulo é cliente dos módulos Ponto e
Reta. A Figura 1.13 a seguir ilustra o DEM deste programa. O módulo que
inicia o programa é o módulo principal (e deve conter uma função main() ). Ele
aciona as operações tanto do módulo ponto quanto do módulo reta. Reta, por sua
vez, também é cliente do módulo ponto.
Ponto
Reta
Principal
Figura 1.13: DEM com módulos Ponto Reta e Principal.
A Figura 1.14 ilustra a implementação de um módulo Principal. Note que a
única forma de acesso aos TADs Ponto e Reta é por meio das operações
definidas em suas respectivas interfaces.
Use diagramas de estrutura modular sempre que for iniciar um novo projeto.
Defina os TADs e estabeleça o relacionamento entre eles por meio de DEMs.
Junto às linhas, você pode especificar as operações do TAD que são
acionadas pelo cliente. Isso vai ajudar você na especificação dos TADs.
Atividade 4
Implementar as operações do TadPonto e do TadReta considerando o
17
enunciado do problema 1, da Seção 1.2.3 do texto, e desenvolver um
programa usando a função principal (do quadro a seguir) de forma a testar as
operações.
void principal() {
char opcao;
Ponto p1,p2;
Reta r1;
printf("1- Calcular Distância até a origem.\n");
printf("2- Calcular Distância entre pontos.\n");
printf("3- Calcular Distância de uma reta a um
ponto.\n");
printf("4- Determinar inclinação da reta.\n");
printf("5- Determinar equação da reta.\n");
printf("0- Sair.\n");
printf("Informe a opção Desejada: ");
do{
opocao = getchar();
switch(opcao){
case '1': lerPonto(&p1);
distanciaOrigem(p1);
break;
case '2': lerPonto(&p1);
lerPonto(&p2);
distancia2Pontos(p1,p2);
break;
case '3': lerReta(&r1);
lerPonto(&p1);
distanciaRetaPonto(r1,p1);
break;
inclinacaoReta(r1);
break;
equacaoReta(r1);
break;
default: printf("Informe uma Opção Válida.");
}
} while(opcao!='0');
}
int main(){
principal();
return 0;
}
Figura 1.14: Módulo Principal para o Problema A.
Até o momento, em nosso exemplo envolvendo Ponto e Reta, não abordamos
a questão de como as operações serão implementadas propositalmente. É
que até a parte que apresentamos do desenvolvimento não precisamos saber
mesmo. Você por acaso lembra como se calcula a distância entre dois
18
pontos? E a distância entre uma reta e um ponto? Pois bem, o importante é
que você tenha compreendido a discussão feita e o exemplo dado, mesmo
sem saber responder essas duas perguntas. Assim espero!
1.2.4 Implementação de Tipos Abstratos de Dados
Um dos principais benefícios da abstração de dados é separar o
comportamento do TAD, especificado por meio da definição de suas
operações, da sua implementação. Em nosso exemplo, o que definimos a
respeito dos TAD Ponto e Reta foi o seu comportamento, as suas operações.
Nesta seção, discutiremos melhor como separar em um projeto a definição do
comportamento e da implementação de um TAD.
O projeto completo de um TAD consiste de dois passos:
1. Especificação - Consiste na especificação do comportamento do TAD;
2. Implementação Implementação das operações e estruturas de dados.
Especificação
A especificação de um TAD descreve o que TAD faz, mas omite informações
sobre como o mesmo é implementado. Por omitir detalhes de implementação,
uma única especificação permite muitas implementações diferentes.
A especificação é feita por meio da definição das operações do TAD. Para
detalhar melhor cada uma destas operações, devemos estabelecer, para cada
operação, dois elementos:
-
Pré-condições: definem as condições necessárias para que a operação
possa ser realizada. Por exemplo, suponha que desejamos especificar o
TAD Conjunto com a operação listarConjunto. Uma pré-condição
para essa operação é que o Conjunto não esteja vazio.
-
Pós-condições: definem o estado do TAD após a execução da
operação,Por exemplo, suponha a operação inserirElemento no
TAD conjunto. Uma pós-condição para essa operação seria: elementos
no conjunto = elementos no conjunto + novo elemento. A Figura 1.15
ilustra a definição do TAD conjunto.
TAD Conjunto:
Operações:
inserirElemento
-
Pré-condições: conjunto cheio == FALSO
-
Pós Condições: elementos no conjunto
elementos do conjunto + novo elemento
listarConjunto
-
19
Pré-Condições: conjuntoVazio == FALSO
-
Pós-Condições:
não há
=
Figura 1.15: Especificação do TAD Conjunto.
Implementação
Um TAD é implementado por um módulo de um programa. Uma única
especificação permite diferentes implementações para um mesmo TAD. Uma
implementação está correta se esta provê o comportamento especificado para o
TAD. Implementações corretas podem diferir uma da outra, por exemplo, em
termos do algoritmo ou da estrutura de dados que elas usam. Essas diferenças
interferem na eficiência (desempenho em tempo de execução, ou ocupação de
espaço) apresentado pelo TAD para realização das operações.
Encapsulamento
Para uma abstração funcionar corretamente, a sua implementação deve ser
encapsulada. Se a implementação for encapsulada, nenhum outro módulo do
programa vai depender de detalhes de implementação do TAD.
Encapsulamento garante que módulos do programa podem ser implementados
e re-implementados independentemente, sem afetar os outros módulos do
programa.
O encapsulamento geralmente é conseguido por meio da separação da interface
e da implementação do módulo. Conforme já vimos anteriormente, em C a
implementação de um TAD por meio de um módulo consiste em duas partes: a
especificação da interface do módulo por meio do arquivo header ( com
extensão .h) e da implementação das operações por meio de um arquivo com
extensão .c.
1.2.5 Avaliação de Implementações de Tipos Abstratos de
Dados
É fundamental para um programador saber criticar e avaliar a qualidade de
uma implementação! Uma implementação baseada em Abstração de
Dados é um indicativo de boa qualidade. Nesta Seção, discutiremos
elementos que permitem que você verifique se uma implementação
realmente está de acordo com essa técnica.
Embora a linguagem C não ofereça um mecanismo que impeça realmente que o
programador tenha acesso à estrutura interna do TAD, esta é uma regra
fundamental e deve ser respeitada pelo programador. Esta regra ou característica
de TADs é o encapsulamento, discutido na seção anterior. Dizemos que um
TAD é encapsulado por suas operações no sentido de que a estrutura interna do
TAD fica preservada e invisível ao restante do programa. Violar essa regra
significa não usar corretamente a Abstração de Dados.
Localidade
O maior benefício do encapsulamento chama-se princípio da Localidade.
20
Esse princípio permite que um programa seja implementado, entendido e
modificado um módulo de cada vez. A localidade aumenta a qualidade do
software que está sendo desenvolvido.
Dentre os benefícios oriundos do princípio da localidade temos:
1. O programador de uma abstração sabe o que é necessário pelo que está
descrito na especificação. Dessa forma, ele não precisa interagir com
programadores de outros módulos (ou, pelo menos, essa interação vai
ser bem limitada).
2. De forma análoga, o programador de um módulo que usa a abstração
sabe o que esperar desta abstração, apenas pelo comportamento descrito
em sua especificação.
Uma ferramenta que pode contribuir para esse entendimento é a
documentação do TAD. Ou seja, a explicação sobre o seu funcionamento e
sobre como utilizá-lo. Procure sempre fazer uma boa documentação do TAD.
Essa documentação pode vir como um documento à parte que acompanha o
módulo.
3. É necessário apenas o raciocínio local (por módulo), para saber o que o
programa faz e se está fazendo a coisa certa. Para estudar e compreender
o programa, podemos dividi-lo em módulos, e analisar um módulo de
cada vez. Em cada caso, preocupamo-nos em saber se o módulo faz o
que é suposto que faça. Ou seja, se ele cumpre o que está na
especificação.
Pode-se assim limitar a atenção para um módulo, ignorando tanto os
módulos usados por este quanto os que o utilizam. Os módulos que
utilizam o módulo estudado podem ser ignorados porque dependem
apenas de sua especificação e não da sua implementação. Os módulos
utilizados são ignorados, raciocinando-se sobre o que eles fazem
utilizando apenas sua especificação em vez de sua codificação. Com
isso, tem-se uma grande economia de esforço, dado que as
especificações são muito menores que as implementações. Observandose apenas as especificações evita-se também um efeito cascata. Por
exemplo, se tivermos que olhar o código do módulo que utilizamos,
teremos que olhar também o código dos módulos que são utilizados
pelos módulos que utilizamos e assim por diante.
4. Finalmente, a modificação do programa pode ser feita módulo por
módulo. Se uma abstração particular necessita ser reimplementada para
prover um melhor desempenho, corrigir um erro ou prover uma nova
funcionalidade, o módulo implementado anteriormente pode ser trocado
por uma nova implementação sem afetar os outros módulos.
Prototipagem
Localidade também provê uma base firme para a prototipação ou
prototipagem. Um protótipo é uma implementação inicial, rudimentar e
incompleta de um programa a ser desenvolvido. Se mantivermos o
21
princípio da localidade no desenvolvimento do protótipo, essa
implementação inicial pode ir sendo completada ou substituída por
implementações melhores sem grande esforço nem re-trabalho.
Localidade também provê suporte para evolução. Abstrações podem ser
utilizadas nesse caso para encapsular modificações potenciais no
programa. Por exemplo, suponha que desejamos um programa para ser
executado em diferentes máquinas. Podemos tratar esse problema
inventando abstrações que escondam as diferenças entre as máquinas de
forma que, para mover o programa para uma máquina diferente, apenas
essas abstrações precisem ser reimplementadas. Um bom princípio de
projeto é pensar sobre modificações esperadas e organizar o
desenvolvimento utilizando abstrações que encapsulem as mudanças.
Domínio da complexidade
Os benefícios da localidade são particularmente importantes para a
abstração de dados. Estruturas de dados são muitas vezes complicadas e a
visão mais abstrata mais simples provida pela especificação torna o resto
do programa mais simples. Ainda, mudanças nas estruturas de
armazenamento são uma das principais formas de evolução de programas.
Portanto, os efeitos dessas mudanças devem ser minimizados encapsulando
essas estruturas de dados em abstrações de dados.
Se avaliarmos um programa segundo o critério da abstração de dados,
devemos observar os seguintes fatores:
1. Os TADs estão realmente encapsulados?
a. O entendimento de cada módulo do programa independe dos
demais módulos?
b. O efeito cascata é evitado na depuração?
c. É possível reimplementar um módulo sem afetar os outros?
2. Potenciais mudanças foram previstas no projeto do TAD?
3. Os TADs oferecem abstrações suficientemente simples das estruturas de
dados que encapsulam?
Atividade 5
Os códigos a seguir especificam as interfaces de dois módulos:
Aluno e Turma.
/**************** aluno.h *******************/
typedef struct aluno{
char nome[30];
int matricula;
int cdgcurso;
22
} Aluno;
void leAluno(Aluno *);
void imprimeAluno(Aluno);
void AlteraAluno(Aluno *);
/******************* turma.h *****************/
#include "aluno.h"
#define MAXTURMA 100
typedef struct turma {
int nalunos;
Aluno alunos[MAXTURMA];
}Turma;
void insereAluno(Turma *,Aluno);
/*insere o aluno passado como paramentro na
turma */
void localizaAluno(Turma *, char
*); /* localiza um aluno na turma pelo nome */
void imprimeTurma(Turma);
void atualizaAlunoDaTurma(Turma
*, char *);
Agora, suponha que tenhamos o seguinte módulo principal,
utilizando esses módulos:
/************ Modulo Principal **************/
#include "turma.h"
Turma turma1;
void principal(){
int opcao,i;
aluno a;
char nome[30];
do{
scanf("%d",&opcao);
switch(opcao){
case 1: /* cadastrar aluno */
lealuno(&a);
insereAluno(&turma1,a);
break;
}
case 2: /* imprimir os dados de um aluno
cujo nome é xxx*/
scanf("%s",nome);
a= localizaAluno(&turma1, nome);
printf("%s - %d - %d",a.nome,
a.matricula,a.cdgcurso);
break;
case 3: /* imprimir turma */
for (i=0;i<turma.nalunos;i++)
imprimeAluno(turma.alunos[i]);
}
break;
case 4: /* alterar dados de um aluno */
scanf("%s",nome);
atualizaAlunoDaTurma(&turma1,
nome);
23
break;
}
}
}
Tarefas:
a) Critique a implementação do módulo acima com base nos
critérios de avaliação de TADs discutidos acima.
b)
Faça
uma
implementação
da
operação
atualizaAlunoDaTurma, respeitando os princípios de
programação baseada em tipos abstratos de dados.
Dijkstra (1930 2002) foi, sem dúvida, um dos cientistas que mais
contribuíram para o desenvolvimento da Programação de Computadores.
Terminamos este capítulo com uma frase dele, que resume o conceito de
abstração:
O propósito da abstração não é ser vaga, mas sim, criar um novo nível
semântico no qual ela possa ser absolutamente precisa.
Edsger. W. Dijkstra, The Humble Programmer (O Programador Pobre),
Communications of the ACM, 15(10), 1972.
Reflita sobre isso!
24

Algoritmos e Estruturas de Dados

Transcrição

Documentos relacionados

Atividade TAD: Preparação para a prova. 1

Alg I - Glencoe

Números Reais ‒ Localização na reta numérica

CIPA Informa: dicas para manter uma postura correta

Números Reais – Localização na reta numérica

a origem da computação - Afiliados

luís pais antunes "não se justifica um tribunal só para o futebol"

2. Função Linear 2.1 Função linear e sua representação gráfica

y - Webnode

EXERCÍCIO PRÁTICO MODELANDO UMA CUECA CLÁSSICA 01

Derivada Implícita