Upload
hoangnhi
View
231
Download
0
Embed Size (px)
Citation preview
Estrutura de DadosEstrutura de DadosEstrutura de DadosEstrutura de DadosCarlos Eduardo Batista
Centro de Informática - [email protected]
� Motivação para o uso da linguagem C� Entendendo Estrutura de Dados� Revisão da Linguagem C
◦ Tipos primitivos◦ Vetores e matrizes◦ Exemplos de programas em C
� Cenas dos próximos capítulos...
Linguagem C: Revisão e MotivaçãoLinguagem C: Revisão e Motivação
� Cenas dos próximos capítulos...
2
� Estrutura de dados – uma forma particular de armazenar e organizar dados em um programa de computador de forma que possam ser utilizados eficientemente.
� Diferentes estruturas se adequam a diferentes problemas◦ Exemplo: árvores-B se são interessantes para
Estrutura de dados usando CEstrutura de dados usando C
◦ Exemplo: árvores-B se são interessantes para implementação de banco de dados, compiladores usam tabelas hash...
� Estrutura de dados: organização + operações
3
� Operações típicas associadas às estruturas de dados: inserção, deleção, primeiro item, último item, próximo item, localizar item...
� Estruturas de dados◦ Facilitam a organização de grandes volumes de informação
Estrutura de dados usando CEstrutura de dados usando C
informação◦ Facilitam o reconhecimento de dados complexos, agregando informações relacionadas
4
� Usar C para aprender estrutura de dados é bom pois C...
� É uma linguagem de grande penetração no mercado (ubíqua)◦ Mais referências para aprendizagem, melhor
aceitação no mercado� Permite controle fino do uso de memória
◦ Acesso ao ‘mundo real’ e não o mundo controlado de um sandbox
◦ Ponteiros e recursividade – usar sem medo, mas
Estrutura de dados usando CEstrutura de dados usando C
de um sandbox◦ Ponteiros e recursividade – usar sem medo, mas
com responsabilidade� Permite maior controle operacional – você
designa como o controle é feito◦ Outras linguagens oferecem muitas funcionalidades
‘embutidas’
5
� Programa de Computador ◦ Algoritmos + Estruturas de Dados◦ Implementação concreta em uma linguagem de
programação◦ Utiliza estrutura de dados para armazenamento e
manipulação das informações relacionadas com o domínio do problema atacado pelo programa
� Eficácia
Entendendo estrutura de dadosEntendendo estrutura de dados
� Eficácia◦ Atingir o objetivo proposto corretamente
� Eficiência◦ Além de atingir o objetivo, fazê-lo otimamente
(menor tempo, menor número de recursos etc.)
6
� Estrutura de dados◦ Retrata as relações lógicas existentes entre as informações utilizadas por um programa de computador
◦ Organiza informações◦ Facilitam manipulação algorítmica das informações
Entendendo estrutura de dadosEntendendo estrutura de dados7
� Na definição de estruturas de dados devem ser considerados os seguintes aspectos◦ Maneira como as estruturas serão utilizadas◦ Métodos de manipulação que as estruturas oferecem
◦ Tipo de alocação de memória utilizada
Entendendo estrutura de dadosEntendendo estrutura de dados
◦ Tipo de alocação de memória utilizada
8
� Tipos de dados◦ Conjunto de valores (domínio) que uma variável pode assumir
◦ Define também quais operações poderão ser aplicadas sobre os valores
◦ Tipos básicos: inteiro, real, caractere, booleano...
Tipos básicos são indivisiveis
Entendendo estrutura de dadosEntendendo estrutura de dados
� Tipos básicos são indivisiveis◦ Tipos estruturados: vetores, matrizes...� Agregador de valores primitivos
9
� Tipos abstratos de dados◦ Especificam conceitualmente os dados (organização física e lógica)
◦ Definem operações para manipulação da estrutura
◦ Devem ser construídos pelo desenvolvedor
Entendendo estrutura de dadosEntendendo estrutura de dados10
#include < stdio.h >
int main( int argc , char ** argv []) {printf (“Hello World!!");return 0;
Revisão da Linguagem CRevisão da Linguagem C11
return 0;}
� Um programa simples:� Define (secretamente) um número
aleatório� Solicita ao usuário que insira um número� Verifica se usuário acertou o número
aleatório definido◦ Se errou, informa se o valor tentado é maior
Revisão da Linguagem CRevisão da Linguagem C
◦ Se errou, informa se o valor tentado é maior ou menor
◦ Se acertou, exibe mensagem, informando quantas tentativas foram feitas
12
� Compilação◦ Pré-processamento◦ Verificação sintática◦ Compilação◦ Linkedição
Revisão da Linguagem CRevisão da Linguagem C13
� Variável◦ Região de memória ‘rotulada’, que armazenará dados de um tipo específico
� Tipo de dado◦ Conjunto de valores que podem ser atribuídos a uma variável
Revisão da Linguagem CRevisão da Linguagem C14
char letra = 'a';float area;int lado;lado = 5;area = lado * lado;
Endereço 3048 3049 3050 3051 3052 3053 3054
ID letra area lado
Revisão da Linguagem CRevisão da Linguagem C15
ID letra area lado
Valor a 25 5
Tipo Tamanho Valores
char 1 byte -128 a 127
unsigned char 1 byte 0 a 255
short int 2 bytes -32.768 a 32.767
long int 4 bytes -2.147.483.648 a 2.147.483.647
Revisão da Linguagem CRevisão da Linguagem C
float 4 bytes 10-38 a 1038
double 8 bytes 10-308 a 10308
16
� Constantes ◦ Macros◦ Substituídos na etapa de pré-processamento
#define PI 3.14159265
Revisão da Linguagem CRevisão da Linguagem C17
� Entrada e Saída
printf(formato, lista de constantes/variáveis/expressões);
printf(“%d %f\n”, 34234, 243.345);printf(“Inteiro = %d Real = %f\n”, 33, 5.3);
scanf(formato, lista de endereços);
scanf (“%d”,&n);
Revisão da Linguagem CRevisão da Linguagem C18
scanf (“%d”,&n);scanf(“%d:%d”,&h,&m);
� Declaração de funções◦ Com ou sem retorno (void)
� Escopo de variáveis◦ Escopo global, local...
� Vetor
Revisão da Linguagem CRevisão da Linguagem C
� Vetor◦ Variável multivalorada unidimensional
� Matriz◦ Variável multivalorada multidimensional
19
� Tipos abstratos de dados em C� Aritmética de ponteiros em C� Métodos de pesquisa e classificação de
dados
Próximas aulasPróximas aulas20
� https://code.google.com/p/learnc/� Notas de Aula do Prof. Bruno B. Boniati
ReferênciasReferências21
Estrutura de DadosEstrutura de DadosEstrutura de DadosEstrutura de DadosCarlos Eduardo Batista
Centro de Informática - [email protected]