Estruturas de Dados - T.332

Capítulo 5

Tipos Abstratos de Dados
Abstração
n	Abstrato tem sido definido como:
u	dissociado de qualquer instância específica,
u	ideal,
u	expressando uma qualidade separadamente do objeto representado.
n	Abstração envolve a descoberta de qualidades essenciais de um objeto concreto ou grupo de objetos, dando a estas um nome:
u	descrevemos aspectos essenciais da estrutura de um objeto ou conceito,
u	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
u	É fácil memorizarmos os números da 1ª série, pois precisamos apenas memorizar a sua regra de formação.
u	Para a segunda série, necessitamos rememorar os números.
u	A abstração facilita descrever fatos: teríamos muita dificuldade de lidar com o mundo, se lembrássemos sempre de todos os detalhes de coisas, ao invés de abstrair e generalizar.
n	O nível de abstração com que descrevemos algo é chamado de granularidade.
Abstração em Programação 
n	A idéia de abstração é aplicada ao idealizarmos um programa de computador.
n	Quando queremos construir um programa de computador (sistema) estamos querendo 
resolver um problema real:
u	Descrevemos que informação é necessária,
u	Descrevemos, incialmente de forma sucinta,  o comportamento que o programa deve possuir, para resolver este problema.
u	Estamos abstraindo do problema real para tratar de seus aspectos esseciais, descrevendo-os.
u	Em programação usamos diversos tipos de abstração:
Procedimento geral para a solução de um problema:
Abstração Procedural
n	Um programa é um conjunto de instruções que executa uma tarefa:
u	Esta tarefa geralmente vai ser complexa, mas pode ser descrita sucintamente em palavras,
u	É lógico agrupar um conjunto de instruções que realiza uma tarefa especíca dentro do todo sob um nome:
F	Facilita o projeto de um sistema, pois iniciamos com um descrição muito abstrata, que vamos detalhando.
F	Facilita a compreensão de um sistema complexo,  se organizarmos conjuntos de intruções para uma tarefa sob um nome.
F	Chamamos a isso de procedimentos, funções (em "C") ou métodos (em OOP). 
Abstração Procedural (definição):
n	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 nome.
u	Parametrização:
F	Podemos separar o que é fixo ou interno em um procedimento do que é variável, dependente do mundo "exterior", parametrizando a parte variável:
•	normalmente os dados que o procedimento manipula.
F	Através da parametrização podemos utilizar o mesmo procedimento em diferentes contextos, com diferentes dados.
F	Como procedimentos podem ser chamados de outros, temos assim um mecanismo para abstrações de nível mais alto.
F	A parametrização garante que procedimentos não terão efeitos indesejados sobre dados "externos".
Tipos Abstratos de Dados:  ADTs ou TADs
n	É muito mais conveniente descrever-se algoritmos e conjuntos de dados em termos das operações efetuadas
u	mais intuitivo do que se descrever todos os detalhes de uma implementação,
u	Podemos descrever uma estrutura de dados como uma pilha ou lista nestes termos, programando-a de acordo com esta idéia,
u	isto é chamado tipo abstrato de dado.
u	Uma característica básica é que nada externo às definições de dados e algoritmos de um TAD deva referenciar a sua estrutura interna e vice-versa.
u	Mecanismo sistemático para facilitar o desenvolvimento de grandes sistemas.
Tipos Abstratos de Dados:
n	Abstração de dados:
Uma abstração de dados consiste das três partes seguintes:
u	Um conjunto S de objetos, cuja estrutura de representação é irrelevante,
u	Um conjunto P de operações defindas sobre os elementos de S,
u	Um conjunto R de regras que definem as operações e os relacionamentos entre os elementos de S.
Tipos Abstratos de Dados   X   OOP
n	Conceitos muito semelhantes
n	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 (estruturadas).
n	Diferenças:
u	em TADs, a tarefa de definir quais procedimentos são aplicáveis a quais estruturas de dados, é função do programador.
u	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 a ele. 
Procedimento organizacional em TADs
n	Concepção:
u	Semelhante à OOP
u	Concebemos um Objeto (TAD) atraves da descrição do comportamento que queremos que tenha de de quais dados deve "conter" (Top-Down)
F	Ex.: Uma lista deve poder receber e devolver elementos, deve conter os elementos em um ordem, etc.
F	Através de refinamentos sucessivos detalhamos esta descrição.
n	Programação:
u	Organizamos um programa em Módulos, cada qual contendo um ou mais TADs relacionados
u	Um módulo contem a declaração de tipo de dados e as funções relativas a um TAD.
Organização Geral
Vantagens
n	Reutilizabilidade
u	Um TAD bem programado eu posso utilizar em muitos programas.

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

n	Manutenibilidade
u	Se eu quiser que as Listas que eu uso no meu programa se comportem diferente, eu só preciso fazer alterações no TAD
Recursos de"C" para a criação de TADs
n	Aspectos procedurais (comportamentais):
u	Funções ou Procedimentos (funções tipo void).
n	Aspectos de estruturas de dados:
u	Declaração de tipos derivados estruturados:
F	estruturas são tipos de dados definidos pelo programador que têm um nome e representam um conjunto de um ou mais tipos de dados.

typedef struct Empregado
	{
   	char 	nome[40];
		char 	endereço[100];
		char	função[20];
		int 	salário;
		- - - 
	}
struct Empregado emp1, emp2, empX;
Usando Estruturas
n	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.nome = "José Arantes";
endereço.rua = "Estrada Geral Canasvieiras";

u	nesse caso não estamos definindo um novo tipo, apenas declarando uma variável com uma estrutura complexa.
u	para a referência e utilização dos campos usa-se o ponto "." imediatamente após o nome da variável.
Usando Estruturas II
n	Estruturas são mais úteis quando utilizadas para a definição de tipos derivados estruturados 

typedef struct endereço {			  / Decl. Tipo Deriv.
char	nome[50];
	char	rua[50];
	char	cidade[30];
	long	cep; };

struct endereço meuEndereço, outroEndereço; / Decl. variáveis
euEndereço.nome = "Aldo";
meuEndereço.rua = "Rua Lauro linhares";

Usando Ponteiros para Estruturas
n	Uma estrutura, sendo uma variável pode ser referenciada normalmente através de um ponteiro:
typedef struct endereço {	        / Decl. Tipo Deriv.
char	nome[50];
	char	rua[50]; };

struct endereço end1, end2;       / Decl. variáveis
truct endereço *enderPointer;    / Decl. ponteiro p/endereço
nderPointer = &end1;
end2 = *enderPointer;
n	Para acessar os campos de uma estrutura usando um ponteiro para a estrutura usamos o operador ->
enderPointer->nome = "Aldo";
end2.cep = enderPointer->cep;

u	Note que a derreferência "*" aqui não é mais necessária.
Exercício-Exemplo
Reimplemente a lista ordenada utilizando um vetor de ponteiros para Strings como um TAD:
u	A Lista passa a ser um TAD que possui uma representação interna do nº máximo de elementos e de qual é o último, sob a forma de um struct.
u	 Além das funções existentes, crie: 
a) uma que cria uma lista, alocando memória para uma estrutura com o vetor de ponteiros de tamanho max, último e max, devolvendo um ponteiro para esta e
b) uma que destrói uma lista, dada por um ponteiro para ela, liberando a memória.
u	A única variável global que um programa principal usando a lista possui, é um ponteiro apontando para esta.
u	O progr.princ. só pode manipular a lista através das funções de acesso.