Upload
internet
View
105
Download
1
Embed Size (px)
Citation preview
1
Tipos definidos O programador pode definir seus próprios
tipos de dados tipos complexos usados da mesma
forma que os simples declaram-se variáveis utilizando-se
esses novos tipos
2
Tipos definidos pelo usuário
Definição de tipo não incorpora novas operações de
acesso ao tipo operações: as mesmas dos elementos
básicos usados na construção do tipo
3
Agregados de Dados de objetos elementares ou de outros
agregados de elementos homogêneos: array de elementos heterogêneos: struct
objeto agregado tem um único nome a manipulação pode ser feita sobre um
único componente elementar de cada vez algumas linguagens permitem atribuir
valores ou comparar agregados inteiros
4
Agregados Heterogêneos struct
struct { int registro; char nome[50]; int idade; float salario;} funcionario;
Seu emprego
funcionario funcionario;
funcionario.idade = 35;end_func = &funcionario;
5
Agregados Heterogêneos Struct: arranjo seqüencial de
componentes cada componente ocupa um número inteiro
de unidades endereçáveis de memória, podendo ser referenciado pelo nome de seu campo
variáveis não podem conter nomes de campos
6
Agregados Heterogêneos e Homogêneos
Struct { int a; float b; int c[5];} tipo_T
tipo_T a[N];
índices: inteiros de 0 a N-1 tipo_T – tipo de cada
elemento
7
Agregados Homogêneos float a [5];
mapeamento dos inteiros de 0 a 4 no conjuntos dos reais
um objeto/elemento pode ser selecionado por indexação: índice do domínio
a[k]: aplicação da função ao argumento k k fora do domínio implica em erro,
detectado em tempo de execução
8
Agregados Homogêneos Array
aloca um número inteiro de unidades endereçáveis de memória contígua
o nome do array indica a posição de memória onde se encontra o 1o. elemento
uma referência a primeira posição da área onde o objeto de informação está armazenado
é um ponteiro
9
Seqüências Exemplo: cadeias de caracteres (strings) operações sobre cadeias:
concatenação seleção do primeiro ou último componente uma subcadeia pode ser extraída
especificando-se as posições do primeiro e do último caracteres desejados
10
Ponteiros Endereço de memória
variável ponteiro guarda o endereço do valor correspondente ao seu tipo
Operadores de Ponteiro: & e * &a = endereço da variável a *a = conteúdo do endereço a
11
Ponteiros utilização de ponteiros em C
retorno de valores em argumentos de função
tipos retornados por função tipos de dados recursivos: estruturas
de dados dinâmicas - listas encadeadas ...
12
Ponteiros variáveis que guardam ponteiros devem
ser declaradas como tal declaração: tipo * nome_ponteiro
tipo: tipo base do ponteiro aloca memória para um endereço e
não, para a variável cuidado - espaços devem ser
alocados pode levar a sérias violações de tipos
13
Ponteiros exemplo
14
Ponteiros Alocação Dinâmica
int * x;x = malloc(sizeof(int));
um ponteiro pode ficar pendurado - pode se referir a uma posição que não alocadafree(x);
uma posição de memória alocada pode ficar inacessível (x local a uma função)
15
Ponteiros Alocação pode causar estouro da pilha:
deve-se sempre utilizar o free para limpeza
Ponteiros não inicializados podem provocar acesso não controlado à memória (violação)
NULL: não aponta para nada (inicializações)
16
Controle a Nível de Instrução
Seqüência Seleção
if (condição) comando1 else comando2switch ... case....
Repetiçãowhile (condição)...do ... while(condição)for (i=0; i<N; i++) .....
17
Subprogramas e Blocos Blocos: unidade de programa
iniciado em seqüência a partir da primeira instrução
define um ambiente local
Subprogramas: um novo “comando” também definem um ambiente local dá nome a uma unidade de programa
sua chamada faz com que o controle seja transferido para a unidade chamada (primeira instrução) e executa até encontrar o fim da unidade (última instrução)
18
Subprogramas e Blocos
Main(){.......
A = Calculo()A= A+1;.......
}
Calculo(){1a. instrução2a. instrução.......última instrução}
1
última
19
Subprogramas e Blocos Ao terminar, o controle volta para instrução
seguinte a chamada Parâmetros Formais
convenções para passagem de parâmetros permitem troca de informação explícita entre unidades
variáveis podem ser declaradas dentro das funções – locais a função fora das funções – variáveis globais na lista de parâmetros – passagem de
parâmetros
20
Complexidade de Algoritmos
Uma característica importante de qualquer algoritmo é seu tempo de execução é possível determiná-lo através de
métodos empíricos, considerando-se entradas diversas
é também possível obter este tempo a partir de métodos analíticos
21
Complexidade de Algoritmos Métodos analíticos
objetivo: determinar uma expressão matemática que traduza o comportamento de tempo de um algoritmo.
o tempo de execução independente: do método utilizado da linguagem e compiladores empregados e das condições locais de processamento
22
Complexidade de Algoritmos obter uma expressão matemática não é
simples, mesmo considerando uma expressão aproximada
Várias simplificações são introduzidas quantidade de dados a serem
manipulados pelo algoritmo é suficientemente grande
quantidade de dados de entrada reduzida não serão considerados
23
Complexidade de Algoritmos somente o comportamento assintótico é
avaliado
não serão consideradas constantes aditivas ou multiplicativas na expressão considerada
24
Complexidade de Algoritmos
Qual a variável em relação à qual a expressão matemática avaliará o tempo de execução?
Um algoritmo funciona a partir de uma entrada para produzir uma saída dentro de um tempo
fornecer o tempo de execução em função da entrada
25
Complexidade de Algoritmos
O processo de execução de um algoritmo pode ser dividido em etapas elementares - passos um número fixo de operações básicas
cujo tempo de execução é considerado constante
a operação básica de maior freqüência de execução do algoritmo é denominada operação dominante
26
Complexidade de Algoritmos
expressão de tempo de execução - obtida a menos de constantes aditivas e multiplicativas: número de passos número de execuções da
operação dominante A expressão matemática de avaliação do
tempo de execução de um algoritmo é a função que fornece o número de passos efetuados no algoritmo a partir de uma certa entrada
27
Complexidade de Algoritmos
Por exemplo: algoritmos para ordenar os elementos de uma seqüência dada cada passo corresponde a comparação entre
dois elementos da seqüência
O número de passos de um algoritmo constitui a informação de que se necessita para avaliar seu comportamento no tempo
28
Complexidade de Algoritmos
Inversão de uma seqüência
fim = n/2for (i=0; i<fim; i++){ temp = S[i];
S[i] = S[n-1-i];S[n-1-i] = temp;
}
29
Complexidade de Algoritmos n = 5 troca S[i] por S[n-1-i]
fim = 2 i = 0 troca S[0] por S[5-1-0] (S[4]) i = 1 troca S[1] por S[5-1-1] (S[3])
inicial final
M AA R I
0 41 2 3
A MI R A
0 41 2 3
30
Complexidade de Algoritmos n = 6 troca S[i] por S[n-1-i]
fim = 3 i = 0 troca S[0] por S[6-1-0] (S[5]) i = 1 troca S[1] por S[6-1-1] (S[4]) i = 2 troca S[2] por S[6-1-2] (S[3])
inicial final
E DS T A
0 41 2 3
O SD A T
0 41 2 3
O
5
E
5
31
Complexidade de Algoritmos n = 50 troca S[i] por S[n-1-i]
fim = 25 i = 0 troca S[0] por S[50-1-0] (S[49]) i = 1 troca S[1] por S[50-1-1] (S[48]) i = 2 troca S[2] por S[50-1-2] (S[47])......... i = 23 troca S[23] por S[50-1-23] (S[26]) i = 24 troca S[24] por S[50-1-24] (S[25])
32
Complexidade de Algoritmos
o algoritmo executa extamente as mesmas operações para seqüências de tamanho n
cada passo corresponde à troca de posição entre dois elementos da seqüência a execução das três atribuições
o número de passos é igual ao número de vezes que executa o bloco for n/2, n>1
33
Complexidade de Algoritmos Problema: determinar a soma C e o
produto D de duas matrizes dadas A e B. A = (aij) e B = (bij) ambas n x n C e D também serão matrizes n x n seus elementos podem ser calculados como: cij = aij + bij
dij = aik * bkj 1k n
34
Complexidade de Algoritmos
Somafor(i=0; i<n; i++)
for(j=0; j<n; j++)cij = aij + bij ;
Produtofor(i=0; i<n; i++)
for(j=0; j<n; j++){ dij = 0;
for(k=0; k<n; k++) dij = dij + aik* bkj;
}
35
Complexidade de Algoritmos
Seja A um algoritmo {E1, ....Em} o conjunto de todas as
entradas possíveis de A seja ti o número de passos efetuados por
A quando a entrada for Ei
Complexidade do pior caso: max Ei E {ti } Complexidade do melhor caso: min Ei E
{ti }
36
Complexidade de Algoritmos
Complexidade do caso médio: 1i m piti
pi é a probabilidade de ocorrência da
entrada Ei
De forma análoga podem ser definidas complexidades de espaço de um algoritmo complexidade tem por objetivo avaliar a
eficiência de tempo ou espaço
37
Complexidade de Algoritmos
Complexidade de tempo do pior caso para a entrada mais desfavorável é a mais importante das três
mencionadas fornece um limite superior para o
número de passos