AEDSII_aula_003_linguagem_C-TAD

Prévia do material em texto

The image cannot be displayed. Your computer may not have 
enough memory to open the image, or the image may have 
been corrupted. Restart your computer, and then open the file 
again. If the red x still appears, you may have to delete the 
image and then insert it again.
The image 
cannot be 
displayed. 
Your 
computer 
may not 
have 
enough 
memory to 
open the 
image, or 
the image 
may have 
Tipos Abstratos de Dados 
Luiz Chaimowicz, Raquel O. Prates e 
Gisele L. Pappa 
(versão adaptada) 
Livro “Projeto de Algoritmos” 
Capítulo 1 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
n  Algoritmo e Programa 
n  Tipo Abstrato de Dados 
q  Qual papel do programador e do usuário do TAD 
 
n  Conceitos de typedef e struct 
Algoritmos e Estrutura de Dados II 
3 Pontos Principais 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Qual a diferença entre um 
algoritmo e um programa? 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmo ou Programa? 
Algoritmos e Estrutura de Dados II 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmo ou Programa? 
Algoritmos e Estrutura de Dados II 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Algoritmos e Estruturas de Dados 
n  Algoritmo: 
q  Sequência de ações executáveis para a 
solução de um determinado tipo de problema 
q  Exemplo: “Receita de Bolo” 
q  Algoritmos trabalham sobre Estruturas de Dados 
n  Estrutura de Dados: 
q  Conjunto de dados que representa uma situação 
real (estado do mundo) 
q  Modo eficiente de armazenamento para facilitar seu 
acesso e modificação. 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Representação dos Dados 
n  Os dados podem estar representados 
(estruturados) de diferentes maneiras 
n  Normalmente, a escolha da representação 
é 
determinada pelas operações que serão 
utilizadas sobre eles 
n  Exemplo: números inteiros q  Representação por palitinhos: II + IIII = IIIIII 
 
q  Representação decimal: 1278 + 321 = 1599 
 
 
q  Boa para pequenos números (operação simples) 
 
q  Boa para números maiores (operação complexa) 
 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Programas 
n  Um programa é uma formulação concreta 
de um algoritmo abstrato, baseado em 
representações de dados específicas 
n  Os programas são feitos em alguma 
linguagem que pode ser entendida e seguida 
pelo computador 
q  Linguagem de máquina 
q  Linguagem de alto nível (uso de compilador) 
q  Aqui vamos utilizar a Linguagem C 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Linguagem C 
n  Criada em no início da década de 70 para 
a 
programação do sistema operacional Unix 
n  Uma das linguagens mais utilizadas no 
mundo, e serviu como base para outras 
como C++, C#, etc. 
 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Tipos Abstratos de Dados (TADs) 
n  Agrupa a estrutura de dados juntamente com 
as operações que podem ser feitas sobre 
esses dados 
n  O TAD encapsula a estrutura de dados. Os 
usuários do TAD só tem acesso a algumas 
operações disponibilizadas sobre esses dados 
n  Usuário do TAD x Programador do TAD 
q  Usuário só “enxerga” a interface, não a 
implementação 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Tipos Abstratos de Dados (TADs) 
n  Dessa forma, o usuário pode abstrair da 
implementação específica. 
n  Qualquer modificação nessa implementação 
fica restrita ao TAD 
n  A escolha de uma representação específica é 
fortemente influenciada pelas operações a 
serem executadas 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Tipos Abstratos de Dados (TADs) 
Algoritmos e Estrutura de Dados II 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Exemplo: Lista de números inteiros 
 n  Operações 
q  Faz Lista Vazia 
q  Insere número no começo da lista 
q  Remove de uma posição i 
20 13 02 30 Implementação por Vetores: 
void Insere(int x, Lista L) { 
 for(i=0;...) {...} 
 L[0] = x; 
} 
20 13 02 30 
Implementação por Listas Encadeadas 
void Insere(int x, Lista L) { 
 p = CriaNovaCelula(x); 
 L.primeiro = p; 
 ... 
} 
Programa usuário do TAD: 
int main() { 
 Lista L; 
 int x; 
 
 x = 20; 
 FazListaVazia(L); 
 Insere(x,L); 
 ... 
} 
© R. O. Prates, L.Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Implementação de TADs 
n  Em linguagens orientadas por objeto (C++, Java) a 
implementação é feita através de classes 
n  Em linguagens estruturadas (C, pascal) a 
implementação é feita pela definição de tipos 
juntamente com a implementação de funções 
n  Vamos utilizar os conceitos em C (typedef e struct) 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Estruturas (Structs) em C 
n  Uma estrutura é uma coleção de uma ou mais 
variáveis, possivelmente de tipos diferentes, 
colocadas juntas sob um único nome para 
manipulação conveniente 
n  Exemplo: 
q  para representar um aluno são necessárias as informações 
nome, matrícula, conceito 
q  Ao invés de criar três variáveis, é possível criar uma única 
variável contendo três campos. 
n  Em C, usa-se a construção struct para representar 
esse tipo de dado 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Estruturas (Structs) em C 
n  Sintaxe: 
struct nome { 
 [tipo nome_da_variável] ; 
 ... 
} [variável] ; 
 
 
struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
 
 
 
 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Estruturas (Structs) em C 
#include<iostream> 
#include<string> 
 
 
struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
 
main() { 
 struct Aluno al, aux; 
 
 al.nome = “Pedro” 
 al.matricula = 200712; 
 al.conceito = ‘A’; 
 aux = al; 
} 
 
 
Pedro 
200712 A 
al: 
Pedro 
200712 A aux: 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Estruturas (Structs) em C 
struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
 
struct Professor{ 
 string nome; 
 int matricula; 
 string classes[3]; 
}; 
 
main() { 
 struct Aluno al; 
 struct Professor pr; 
 
 al.nome = “Pedro”; 
 pr.nome = “José”; 
} 
 
 
 
 
main() { 
string alunoNome; 
int alunoMatricula; 
Char alunoConceito; 
string alunoNome2; 
int alunoMatricula2; 
Char alunoConceito2; 
string professorNome; 
int professorMatricula; 
string professoClasses[3]; 
 
 
 alunoNome = “Pedro” 
 alunoMatricula = 200712; 
 alunoConceito = ‘A’; 
 alunoNome2 = alunoNome; 
 alunoMatricula2 = alunoMatricula; 
 alunoConceito2 = alunoConceito; 
} 
 
 
 
 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Declaração de Tipos 
n  Para simplificar, uma estrutura ou mesmo 
outros tipos de dados podem ser definidos 
como um novo tipo 
n  Uso da construção typedef 
n  Sintaxe: typedef tipo identificador; 
typedef struct { 
 string nome; 
 int matricula; 
 char conceito; 
} TipoAluno; 
 
typedef int Vetor[10]; 
int main() { 
 TipoAluno al; 
 Vetor v; 
 
 ... 
} 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
TADs em C 
n  Para implementar um Tipo Abstrato de 
Dados em C, usa-se a definição de tipos 
juntamente com a implementação de funções 
que agem sobre aquele tipo 
n  Como boa regra de programação, evita-se 
acessar o dado diretamente, fazendo o 
acesso só através das funções 
q  Mas, diferentemente de C++ e Java, não há uma 
forma de proibir o acesso. 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
n  Uma boa técnica de programação é 
implementar os TADs em arquivos separados 
do programa principal 
n  Para isso geralmente separa-se a declaração 
e a implementação do TAD em dois arquivos: 
q  NomeDoTAD.h : com a declaração 
q  NomeDoTAD.c : com a implementação 
n  O programa ou outros TADs que utilizam o 
seu TAD devem dar um #include no arquivo .h 
TADs em C 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
TADs em C 
Algoritmos e Estrutura de Dados II 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
arquivo .c 
arquivo .h 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Exemplo 
n  Implemente um TAD ContaBancaria, com os 
campos número e saldo onde os clientes 
podem fazer as seguintes operações: 
q  Iniciar uma conta com um número e saldo inicial 
q  Depositar um valor 
q  Sacar um valor 
q  Imprimir o saldo 
n  Faça um pequeno programa para testar o 
seu TAD 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
ContaBancaria.h 
// definição do tipo 
typedef struct { 
 int numero; 
 double saldo; 
} ContaBancaria; 
 
// cabeçalho das funções 
ContaBancaria Inicializa (int, double); 
void Deposito (ContaBancaria *, double); 
void Saque (ContaBancaria *, double); 
void Imprime (ContaBancaria); 
 
 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. PappaThe image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
ContaBancaria.c 
#include<stdio.h> 
#include"Contabancaria.h" 
 
ContaBancaria Inicializa(int numero, double saldo) { 
ContaBancaria conta; 
 conta.numero = numero; 
 conta.saldo = saldo; 
 return conta; 
} 
 
void Deposito (ContaBancaria *conta, double valor) { 
 conta->saldo += valor; 
} 
 
void Saque (ContaBancaria *conta, double valor) { 
 conta->saldo -= valor; 
} 
 
void Imprime (ContaBancaria conta) { 
 printf("Numero: %d – saldo: %f\n", conta.numero, conta.saldo); 
} 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Main.c 
 #include<stdio.h> #include<stdlib.h> 
#include "ContaBancaria.h" 
 
int main (void) { 
ContaBancaria conta1; 
 
 conta1 = Inicializa(918556, 300.00); 
 printf("\nAntes da movimentacao:\n "); 
 Imprime(conta1); 
 
 Deposito(&conta1, 50.00); 
 Saque(&conta1, 70.00); 
 printf("\nDepois da movimentacao:\n "); 
 Imprime(conta1); 
 
 return(0); 
} 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
TADs em C 
Algoritmos e Estrutura de Dados II 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
ContaBancaria.c 
ContaBancaria.h 
main.c 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
TADs em C 
n  Acesso direto dos dados (errado!) 
Algoritmos e Estrutura de Dados II 
20 13 02 30 Implementação por Vetores: 
typedef struct { 
 int dado[100]; 
} Lista; 
20 13 02 30 
Implementação por Listas Encadeadas 
typedef struct item { 
 int dado; 
 struct item *prox; 
} Item; 
 
typedef struct { 
 Item *inicio; 
} Lista; 
Programa usuário do TAD: 
int main() { 
 Lista L; 
 
 L.dado[0] = 20; 
} 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
Exercício 
n  Implemente um TAD Número Complexo 
q  cada número possui os campos real e imaginário 
q  Implemente as operações: 
q  Inicializa: atribui valores para os campos 
q  Imprime: imprime o número da forma “R + Ci” 
q  Copia: Copia o valor de um número para outro 
q  Soma: Soma dois números complexos 
q  EhReal: testa se um número é real 
n  Faça um pequeno programa para testar o 
seu TAD 
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
NumeroComplexo.h 
typedef struct { 
 int real; 
 int img; 
} NumeroComplexo ; 
 
NumeroComplexo Inicializa(int, int); 
void Imprime(NumeroComplexo); 
void Copia(NumeroComplexo*, NumeroComplexo); 
NumeroComplexo Soma(NumeroComplexo, NumeroComplexo); 
int EhReal(NumeroComplexo); 
!
!
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
NumeroComplexo.c 
#include <stdio.h> 
#include "NumeroComplexo.h" 
 
NumeroComplexo Inicializa(int real, int img) { 
NumeroComplexo num; 
 num.real = real; 
 num.img = img; 
 return num; 
} 
 
void Imprime(NumeroComplexo num) { 
 printf("%d + %di\n", num.real, num.img); 
} 
 
!
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
NumeroComplexo.cpp 
NumeroComplexo Soma(NumeroComplexo a, NumeroComplexo b) { 
NumeroComplexo temp; 
 temp.real = a.real + b.real; 
 temp.img = a.img + b.img; 
 return temp; 
} 
 
int EhReal(NumeroComplexo num) { 
 return num.img == 0; 
} 
 
void Copia(NumeroComplexo *dest, NumeroComplexo src) 
{ 
 dest->real = src.real; 
 dest->img = src.img; 
} 
!
© R. O. Prates, L. Chaimowicz e 
 Gisele L. Pappa 
The image cannot be displayed. 
Your computer may not have 
enough memory to open the image, 
or the image may have been 
corrupted. Restart your computer, 
and then open the file again. If the 
The 
ima
ge 
can
not 
be 
disp
laye
d. 
Algoritmos e Estrutura de Dados II 
#include <stdio.h> 
#include <stdlib.h> 
#include "NumeroComplexo.h" 
 
int main() { 
NumeroComplexo a,b,c,d; 
 
 a = Inicializa(2,5); 
 Imprime(a); 
 b = Inicializa(1,2); 
 Imprime(b); 
 c = Soma(a,b); 
 Imprime(c); 
 d = Inicializa(5,0); 
 Imprime(d); 
 if (EhReal(d)) 
 Copia(&d,a); 
 
 Imprime(d); 
 return 0; 
}!