Estruturas de Dados - T.332

Capítulo 3.6

Tipos Abstratos de Dados em "C"

2.3.1 Abstração
2.3.2 Tipos Abstratos de Dados: ADTs ou TADs
2.3.3 Organização Geral de um Programa Dividido em Modulos Utilizando TADs
2.3.4 Recursos de"C" para a criação de TADs
2.3.5 Exercícios

2.3.1 Abstração

Abstrato tem sido definido como:

dissociado de qualquer instância específica,
ideal,
expressando uma qualidade separadamente do objeto representado.

Abstração envolve a descoberta de qualidades essenciais de um objeto concreto ou grupo de objetos, dando a estas um nome:

descrevemos aspectos essenciais da estrutura de um objeto ou conceito,
descrevemos o comportamento de um objeto ou conceito nomeando aspectos importantes deste.

Exemplo:

2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40

30,40,22,32,36,20,34,4,18,26,6,2,38,16,12,28,8,14,10,40

É fácil memorizarmos os números da 1ª série, pois precisamos apenas memorizar a sua regra de formação.
Para a segunda série, necessitamos rememorar os números.
A abstração facilita descrever fatos: teríamos muita dificuldade de lidar com o mundo, se lembrássemos sempre de todos os detalh

O nível de abstração com que descrevemos algo é chamado de granularidade.

Abstração em Programação

A idéia de abstração é aplicada ao idealizarmos um programa de computador.
Quando queremos construir um programa de computador (sistema) estamos querendo

Descrevemos que informação é necessária,
Descrevemos, incialmente de forma sucinta, o comportamento que o programa deve possuir, para resolver este problema.
Estamos abstraindo do problema real para tratar de seus aspectos esseciais, descrevendo-os.
Em programação usamos diversos tipos de abstração:

Abstração Procedural

Um programa é um conjunto de instruções que executa uma tarefa:

Esta tarefa geralmente vai ser complexa, mas pode ser descrita sucintamente em palavras,
É lógico agrupar um conjunto de instruções que realiza uma tarefa especíca dentro do todo sob um nome:

Facilita o projeto de um sistema, pois iniciamos com um descrição muito abstrata, que vamos detalhando.
Facilita a compreensão de um sistema complexo, se organizarmos conjuntos de intruções para uma tarefa sob um nome.
Chamamos a isso de procedimentos, funções (em "C") ou métodos (em OOP).

Abstração Procedural (definição):

Nomear um conjunto de ações, instruções ou código de forma que ele possa ser manipulado ou executado simplesmente através de seu

Parametrização:

Podemos separar o que é fixo ou interno em um procedimento do que é variável, dependente do mundo "exterior", parametrizando a p

normalmente os dados que o procedimento manipula.

Através da parametrização podemos utilizar o mesmo procedimento em diferentes contextos, com diferentes dados.
Como procedimentos podem ser chamados de outros, temos assim um mecanismo para abstrações de nível mais alto.
A parametrização garante que procedimentos não terão efeitos indesejados sobre dados "externos".

2.3.2 Tipos Abstratos de Dados: ADTs ou TADs

É muito mais conveniente descrever-se algoritmos e conjuntos de dados em termos das operações efetuadas

mais intuitivo do que se descrever todos os detalhes de uma implementação,
Podemos descrever uma estrutura de dados como uma pilha ou lista nestes termos, programando-a de acordo com esta idéia,
isto é chamado tipo abstrato de dado.
Uma característica básica é que nada externo às definições de dados e algoritmos de um TAD deva referenciar a sua estrutura inteira.
Mecanismo sistemático para facilitar o desenvolvimento de grandes sistemas.

Tipos Abstratos de Dados:

Abstração de dados:

Uma abstração de dados consiste das três partes seguintes:

Um conjunto S de objetos, cuja estrutura de representação é irrelevante,
Um conjunto P de operações defindas sobre os elementos de S,
Um conjunto R de regras que definem as operações e os relacionamentos entre os elementos de S.

Tipos Abstratos de Dados X OOP

Conceitos muito semelhantes
TADs são uma técnica programação concisa e eficiente, semelhante à OOP, só que baseada em linguagens de programação de 3ª geração.
Diferenças:

em TADs, a tarefa de definir quais procedimentos são aplicáveis a quais estruturas de dados, é função do programador.
em OOP a sintaxe da linguagem e o compilador garantem que um objeto (como conjunto de dados) "saiba" quais operações são aplicáveis.

Procedimento organizacional em TADs

Concepção:

Semelhante à OOP
Concebemos um Objeto (TAD) atraves da descrição do comportamento que queremos que tenha de de quais dados deve "conter" (Top-Dow

Ex.: Uma lista deve poder receber e devolver elementos, deve conter os elementos em um ordem, etc.
Através de refinamentos sucessivos detalhamos esta descrição.

Programação:

Organizamos um programa em Módulos, cada qual contendo um ou mais TADs relacionados
Um módulo contem a declaração de tipo de dados e as funções relativas a um TAD.

2.3.3 Organização Geral de um Programa Dividido em Modulos Utilizando TADs

Módulo Definição de Dados da Lista: lista.h

/*------------------------------------------

Modulo: lista.h

Funcao: Definir os tipos e a estrutura

dos dados para o

TAD lista

Programador: Aldo

Data: 01.03.1997

Versao: 1.0

------------------------------------------*/

#ifndef EstruturaDaLista
#define EstruturaDaLista

/* Definir uma estrutura para a lista */
struct estruturaDaLista

{

int elemento;

lista *proximo;

};

/* Definir um tipo que tem a estrutura da lista. */

typedef struct estruturaDaLista lista;

#endif

/* Observacao importante:
   A diretiva de compilacao #ifndef (if not defined)
   diz que aquela area de codigo fonte entre o #ifndef
   e o #endif somente sera levada em conta pelo compilador
   se o argumento de #ifndef ainda nao houver sido definido
   na mesma sessao de compilacao no escopo de um modulo.

   Isso garante que codigo que a gente "por via das duvidas"
   inclui mais de uma vez em um modulo nao seja considerado
   duas vezes.

   Um exemplo de como isto e util esta na diretiva
   #include <stdio.h> que esta presente tanto em lista.h
   como em lista.c como em aplic.c.
   Como aplic.c carrega lista.h "para dentro" de si mesmo,
   carregara tambem stdio.h. Como estah explicitamente tambem
   carregando stdio.h, se nao houver uma diretiva #ifndef
   em stdio.h, ele tera o mesmo codigo existente em
   stdio.h duas vezes. */

Módulo Lista: lista.c

/*------------------------------------------

Modulo: lista.c

Funcao: Definir as operacoes (funcoes)

sobre a estrutura de dados do

TAD lista.

Programador: Aldo

Data: 01.03.1997

Versao: 1.0

------------------------------------------*/

#include <stdlib.h>
#include <stdio.h>
#include "lista.h"

lista *criaLista(int tam)

{

- - -

}

lista *retiraDaLista()

{

.....;

}

Programa principal: aplica.c

/*------------------------------------------
    Modulo: aplica.c
    Funcao: Programa que utiliza listas.
    Programador: Aldo
    Data: 01.03.1997
    Versao: 1.0
------------------------------------------*/

#include <stdio.h>
/* Inclua a definicao de tipo de dados.
NUNCA inclua codigo executavel .c */
#include "lista.h"

main ()

{

char *a, *b;

lista *minhaLista, *outraLista;

minhaLista = criaLista(20);

..... .....

}

Vantagens

Reutilizabilidade

Um TAD bem programado eu posso utilizar em muitos programas.

Abstração

Se eu uso um TAD simplesmente prestando atenção às qualidades e ao comportamento que ele exporta, a minha vida fica mais fácil.

Manutenibilidade

Se eu quiser que as Listas que eu uso no meu programa se comportem diferente, eu só preciso fazer alterações no TAD

2.3.4 Recursos de"C" para a criação de TADs

Aspectos procedurais (comportamentais):

Funções ou Procedimentos (funções tipo void).

Aspectos de estruturas de dados: Declaração de tipos derivados estruturados:

estruturas ou tipo derivado estruturado são tipos de dados definidos pelo programador que têm um nome e representam um conjunto de um ou mais tipos de dados, chamados de campos.

Para definir um tipo estruturado em "C" voce tem que realizar um procedimento um pouco mais complicado do que em outras linguagens:

Defina a estrutura de informação que os dados terão declarando uma struct com o nome dessa struct logo após a palavra reservada struct (caso contrario voce estara declarando uma variavel).
Em seguida defina um tipo utilizando typedef com base nessa struct na seguinte ordem:

typedef struct NomeDaEstrura NomeDoTipo

Depois disso você pode declarar variáveis desse tipo nromalmente como qualquer outro tipo.
Exemplo:

struct EstruturaDoEmpregado

{

char nome[40];

char endereço[100];

char função[20];

int salário;

- - -

};

typedef struct EstruturaDoEmpregado Empregado;

Empregado emp1, emp2, empX;

Usando Estruturas

Estruturas podem ser declaradas e utilizadas diretamente, como se fossem variáveis:

struct {

char nome[50];

char rua[50];

char cidade[30];

long cep;

} endereço;

endereço.cep = 88049;

nesse caso não estamos definindo um novo tipo, apenas declarando uma variável com uma estrutura complexa.
para a referência e utilização dos campos usa-se o ponto "." imediatamente após o nome da variável.

Estruturas são mais úteis quando utilizadas para a definição de tipos derivados estruturados

struct estruturaDeEndereço {

/* Decl. Tipo Deriv. */

char nome[50];

char rua[50];

char cidade[30];

long cep;

};

typedef struct estruturaDeEndereço endereco;

/* Decl. de duas variáveis tipo endereco */
endereço meuEndereço, outroEndereço;

strcpy(meuEndereço.nome,"Aldo");
strcpy(meuEndereço.rua,"Rua Lauro linhares");
meuEndereco.cep = 88036;

Usando Ponteiros para Estruturas

Uma estrutura, sendo uma variável pode ser referenciada normalmente através de um ponteiro:

truct estruturaDeEndereço {

/* Decl. Tipo Deriv. */

char nome[50];

char rua[50];

char cidade[30];

long cep;

};

typedef struct estruturaDeEndereço endereco;

/* Decl. de duas variáveis tipo endereco */
endereco end1, end2;

/* Decl. de ponteiro p/variavel tipo endereço */
endereço *enderPointer;

/* Usando ponteiros para e enderecos de variaveis estruturadas */
enderPointer = &end1;
end2 = *enderPointer;

Para acessar os campos de uma estrutura usando um ponteiro para a estrutura usamos o operador ->
Este operador é chamado de operador de derreferência de campo.

enderPointer->cep = 88036;
strcpy(enderPointer->nome, "Aldo");

end2.cep = enderPointer->cep;

Note que a derreferência "*" aqui não é mais necessária.
Acessar um campo de uma estrutura apontada por um ponteiro atraves do operador de derreferencia de campo significa acessar aquele campo como se fosse uma variável comum.

2.3.5 Exercícios-Exemplo

2.3.5.1 Obrigatório: Lista de Strings de Tamanho Variável com Tamanho Fixo:
Reimplemente a lista ordenada utilizando um vetor de ponteiros para Strings.

A Lista passa a ser um TAD que possui uma representação interna:

do nº máximo de elementos e
de qual é o último elemento e
da lista como sob a forma de um vetor de ponteiros para char.

Além das funções existentes:

As únicas variáveis globais que um programa principal usando a lista possui, sao variaveis do tipo lista.
O progr.principal só pode manipular a lista através das funções de acesso.
Passe sempre a lista como parametro por referência atraves de um ponteiro para ela.

Crie uma aplicação que gerencie duas listas: credores e devedores.

Em um menu no programa principal o usuario escolhe se vai trabalhar com a lista de credores ou com a de devedores.
Depois disso, o usuario pode incluir, excluir ou listar nomes de pessoas da lista que ele escolheu para manipular.

2.3.5.2 Para você treinar mais: Lista de Strings de Tamanho Variável com Comprimento Variável:

Reimplemente o TAD lista ordenada de strings utilizando um vetor de ponteiros definido acima como uma lista cujo tamanho máximo pode ser definido pelo usuário do programa em tempo de execução do programa.

A Lista passa a ser um TAD que possui uma representação interna:

O nº máximo de elementos (inteiro)
Qual é o último elemento (inteiro)
Um ponteiro para a lista sob a forma de um vetor de ponteiros para char. Isto você faz através de um ponteiro para um vetor de tamanho indefinido.

Uma função que cria uma lista, alocando memória para duas coisas:

uma estrutura com os tres campos acima e
para o vetor de ponteiros de strings, cujo tamanho é um parâmetro a ser passado para a função.

A única variável global que um programa principal usando a lista possui, é um ponteiro apontando para este TAD.