Figura 1
Figura 1
Figura 2
Autor: Fabrício Olivetti de França
Data de criação: 23/08/1999
Data de última modificação: 28/12/1999
Assunto: Esse texto visa dar aos alunos de Engenharia e Ciências da Computação um suporte ao estudo de Estrutura de Dados. Este texto foi baseado no livro Estrutura de Dados em C++ e nas aulas de Estrutura de Dados. Não reproduza ou modifique este documento sem antes me contatar via e-mail (fabricioolivetti@yahoo.com.br).
Um Tipo de Dado Abstrato é um dado não reconhecido pelo processador, e por isso, tendo que ser implementado pelo programador.
Ao definir um tipo de dado abstrato não deve-se tomar em consideração a eficiência , pois isso é uma questão de implementação, e o TDA não se relaciona em nada com a implementação. Pode até acontecer de não se conseguir implementar um tipo de dado em um sistema de computador. Apesar disso, o TDA é uma técnica muito útil para os programadores que queiram usar certas propriedades matemáticas que não existam na linguagem que eles usam e/ou usar um tipo de dado de maneira correta.
Um TDA é definido em duas partes: a definição de valores e de operadores. Por sua vez a definição de valores é sub dividido em duas partes: cláusula de definição e cláusula de condição.
A cláusula de definição é a parte que define a estrutura do TDA, como ele é formado.
A cláusula de condição define as condições para que o TDA exista.
Na definição dos operadores é especificado quais são e como são feitas as operações entre esses tipos, é subdividido em duas partes: precondition: as condições iniciais e postcondition: a operação em si.
Consideremos os números racionais como nosso primeiro exemplo.
Os números racionais são formados por dois números inteiros que formam uma fração. O inteiro de cima é chamado numerador e o de baixo denominador e se encontra na forma a/b.
A cláusula de definição dos racionais é dado por:
abstract typedef <int, int> RACIONAL;
Ou seja, uma matriz de dois elementos, onde cada elemento é um inteiro. A cláusula de condição é que o segundo elemento (denominador) seja diferente de zero (senão diverge):
condition RACIONAL[1] <> 0;
Obs1.: Lembre-se que em C as matrizes e listas começam a contar do "0", assim o segundo elemento é o "1".
Obs2.: "<>" é o sinal de "diferente de".
Na definição de operação nós teremos a criação do tipo de dado (racional), soma de dois números racionais, multiplicação, e teste de igualdade:
abstract RACIONAL cria_racional (int a, int b);
precondition b <> 0;
postcondition criaracional[0] = a; criaracional[1] = b;
abstract RACIONAL soma (RACIONAL a, RACIONAL b);
postcondition soma[1] = a[1] * b[1];
soma[0] = a[0]*b[1] + b[0]*a[1];
abstract RACIONAL mult (RACIONAL a, RACIONAL b);
postcondition mult[0] = a[0] * b[0];
mult[1] = a[1] * b[1];
abstract RACIONAL equal(RACIONAL a, RACIONAL b);
postcondition equal = (a[0]*b[1] == b[0]*a[1]);
Lembre-se: dois números racionais são iguais não só quando os numeradores e denominadores são iguais (Figura 1).
Lembre-se também: na soma devemos fazer exatamente como soma de racionais (Figura 2).
A estrutura dos números complexos é a seguinte: um número real formando a parte real e um número real como coeficiente da parte imaginária. A implementação é parecida com os números racionais, afinal será uma lista de dois números reais sem restrições.
abstract typedef <float, float> COMPLEXOS;
declarou-se dois números reais como complexos, nos casos dos complexos não há nenhuma restrição, portanto pularemos a diretiva condition.
abstract COMPLEXO cria_imaginario (float a, float b);
postcondition criaimaginariol[0] = a; criaimaginario[1] = b;
abstract COMPLEXO soma (COMPLEXO a, COMPLEXO b);
postcondition soma[0] = a[0] + b[0];
soma[1] = a[1] + b[1];
abstract COMPLEXO mult (COMPLEXO a, COMPLEXO b);
postcondition mult[0] = (a[0] * b[0]) – (a[1] * b[1]);
mult[1] = (a[0] * b[1]) + (a[1] * b[0]);
abstract COMPLEXO equal(COMPLEXO a, COMPLEXO b);
postcondition equal = (a[0] == b[0] && a[1] == b[1]);
Lembre-se: a multiplicação de números complexos é feito de forma distributiva.
Ex.: 
No apêndice desse tutorial eu farei um estudo maior dos números complexos, como divisão, módulo, complemento, conversão de/para forma polar, trigonométrica.
Recursividade é um método de programação quando um programa, função ou procedimento chama a si mesmo, isso é útil para resolver vários métodos e funções matemáticas que depende do resultado anterior para obter o resultado. Exemplos do uso desses métodos são: fatorial, número de Fibonacci, Torre de Hanói, e muitos outros.
Muitas linguagens permitem a implementação de recursividade, mas outras não permitem, exigindo uma simulação através do loop while (não discutiremos isso, pois não acho necessário, ficando como exercício).
O Fatorial é uma função matemática definida por:
0! = 1
1! = 1
2! = 1.2 = 1! . 2
3! = 1.2.3 = 2! . 3
4! = 1.2.3.4 = 3! . 4
5! = 1.2.3.4.5 = 4! . 5
...
n! = 1.2.3.4.5. ... .(n-1).(n) = (n-1)! . n
É facilmente verificado que esta é uma função recursiva, pois repare que 3! = 2! . 3, 4! = 3! . 4 etc.. Ou seja, você tem que chamar a função fatorial novamente para o número anterior e assim sucessivamente até chegar no resultado final, até que chegue no zero quando o fatorial é 1 (hum).
Implementando isso em C teremos:
int Fatorial(int n)
{
int fatorial;
If (n == 0) return (1);
else {
fatorial = Fatorial(n-1);
return (fatorial*n);
}
}
A Torre de Hanói consiste originalmente de três pinos (A, B, C) e cinco argolas que devemos passar para o pino C na mesma ordem usando o pino B como pino de trabalho e seguindo a única regra de que não se pode ter um pino em cima de um menor.
Suponha que você possa resolver a Torre de Hanói para 4 argolas, só que usando o pino B como destino e o C como trabalho, desta forma basta colocar a última argola no pino C e realizar a solução novamente para quatro argolas só que usando o pino C como destino e A como trabalho.
Aí que está a recursividade, pois para solucionarmos a solução de 4 argolas, basta saber a de três, para a de três basta a de duas, e para a de duas basta a de uma, que é apenas levar a argola para o destino.
Abaixo uma pequena ilustração do que dissemos:
O algoritmo é construído facilmente, como segue:
#include <stdio.h>
void main ( )
{
int n;
scanf ("%d", &n);
torre(n, ‘A’, ‘C’, ‘B’);
}
/* A funcao em si */
void torre(int n, char origem, char destino, char trabalho)
{
if (n == 1) {
/* se tiver um so pino e facil */
printf("\nmover disco 1 da estaca %c "para a estaca %c", origem, destino);
return;
}
torre(n-1, origem, trabalho, destino);
/* realiza a torre de hanoi para n-1 usando B como destino */
printf("\nmover disco %d da estaca %c para a estaca %c", n, origem, destino);
torre(n-1, trabalho, destino, origem)
/* realiza de novo n-1 mas usando C como destino e A como trabalho */
}
Listas sequenciais são listas comuns, onde o próximo campo está logo após do campo atual, na memória, assim o acesso aos campos desta lista é feito direto, ou seja: Lista[número do campo].campo.Ex.: Lista[3].nome, acessa o campo nome na posição 3, quarto nome da lista (começa a contar do 0). Na linguagem C as listas começam a serem contadas do 0. As listas também tem que ter um tamanho pré-definido, essa é sua limitação.
As operações básicas em uma lista são: Busca, Inserção, Remoção.
Uma lista pode ser Lineares ou Circulares, Ordenada ou Não-ordenada.
Abaixo está uma figura esquematizando uma lista sequencial:
Busca: é feita comparando um a um os elementos até que se ache ou termine a lista. Retorna a posição em que se encontra o elemento procurado.
Inserção: é verificado se a lista está cheia para não causar overflow, depois se o elemento não existe através da busca, e então é feita a inserção no final da lista.
Remoção: é verificado se alista não está vazia para não causar underflow, depois se o elemento já existe e então é feita a remoção.
int Busca (int x, int N, int n, int Lista[ ])
{
/* x = elemento procurado (deve-se mudar o tipo para outros tipos de elementos) N = tamanho da lista n = ultimo elemento da lista*/
int i = 0;
while (Lista[i] <> x) i++;
if (Lista[i] <> x) i = -1;
return (i);
}
void Insere(int x, int N, int n, int Lista[ ])
{
if (n < N) {
int busca = Busca(x, N, n, Lista[ ]);
if (busca == -1) Lista[n+1] = x;
else printf("\nelemento já existe");
}
else printf("\nOverflow");
return;
}
int Remove(int x, int N, int n, int Lista[ ])
{
int valor_recuperado = 0
if (n >= 0) {
int busca = Busca(x, N, n, Lista[ ]), valor_recuperado, i;
if (busca <> -1) {
valor_recuperado = Lista[busca];
for (i = busca, i<n, i++) Lista[i] = Lista[i+1];
}
else printf("\nelemento não existe");
}
else printf("\nUnderflow");
return (valor_recuperado);
}
A diferença nessa lista é que na busca usaremos um algoritmo para tornar mais rápido a busca: a busca binária; e na inserção e teremos de colocar o elemento na ordem.
A busca binária é feita através da lista dividida em duas, verifica-se o elemento do meio, como ela é ordenada, se o elemento for maior ele estará à direita senão estará à esquerda, então limitamos a lista no intervalo do meio até o extremo direito ou esquerda, dependendo do resultado da comparação.
int inicio = 0
*/ inicio e declarado aqui para se tornar global e podermos usa-lo na insercao */
int Busca-bin (int x, int N, int n, int Lista[ ])
{
int fim = n, meio, busca = -1;
while (inicio <= fim) {
meio = floor((inicio+fim)/2);
if (Lista[meio] == x) {
busca = meio;
inicio = fim + 1;
}
else if (Lista[meio] < x) meio = floor ( (meio+1 + fim)/2);
else meio = floor((meio-1+inicio)/2);
}
return (busca);
}
void Insere(int x, int N, int n, int Lista[ ])
{
if (n < N) {
int busca = Busca-Bin(x, N, n, Lista[ ]);
if (busca == -1) {
temp = Lista[inicio];
Lista[inicio] = x;
for (i=inicio+1, i<n, i++){
temp1 = Lista[i];
Lista[i] = temp;
Temp = temp1;
}
}
else printf("\nelemento já existe");
}
else printf("\nOverflow");
return;
}
A remoção é idêntica ao anterior.
Nesta lista devemos considerar dois ponteiros, um que aponta para o começo e outro para o fim, a subtração entre os dois ponteiros nos dá o tamanho da lista. A busca é aprecida com a binária, à não ser que ela é feita através dos ponteiros de começo e fim. Na inserção e remoção devemos tomar cuidado para ajustar os ponteiros ao final da operação.