Estruturas de Dados - Ponteiros, Recursão e Conhecimento na linguagem C

Prévia do material em texto

MC202 - Estruturas de Dados
Emilio Francesquini
francesquini@ic.unicamp.br
Instituto de Computação - UNICAMP
Aula 01 - 3 de março de 2017
francesquini@ic.unicamp.br
Disclaimer
• Esses slides foram preparados para um curso de Estrutura de
Dados ministrado na UNICAMP
• Este material pode ser usado livremente desde que sejam
mantidos os créditos dos autores e da instituição.
• Muitos dos exemplos apresentados aqui foram retirados de
materiais preparados pelos Profs. Tomasz Kowaltowski e
Orlando Lee da UNICAMP assim como do Prof. Paulo
Feofiloff do IME-USP
Objetivos
• O objetivo fundamental de projetar um algoritmo é resolver
um problema computacional de modo eficiente.
• Muitas vezes, a organização dos dados em um programa
(algoritmo) pode ser a diferença entre obter uma Ferrari e
obter uma carroça.
• A disciplina Estruturas de Dados tem por objetivo apresentar
métodos e ideias para organizar dados e por conseguinte
aumentar a eficiência de um programa. (educação Vs.
treino)
MC202 - Aula 1 Introdução 3 / 32
O que esperar deste curso
• Vocês aprenderão como desenvolver programas eficientes
e elegantes utilizando soluções refinadas ao longo de anos
• Vocês NÃO vão aprender a usar programas e sites (como
Office, Google, etc...)
• Vocês vão, porém, entender como estes programas
funcionam por baixo dos panos.
MC202 - Aula 1 Introdução 4 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Pré-requisitos
• Entender ponteiros
• Entender ponteiros
• Entender ponteiros
• Entender recursão
• Entender e projetar algoritmos recursivos
• Conhecimento da linguagem de programação C
MC202 - Aula 1 Introdução 5 / 32
Revisão relâmpago
• Variáveis, tipos básicos (int, float, double, char, long),
atribuições.
• Vetores e registros
• Ponteiros e alocação dinâmica de memória
• Recursão
Material adicional cobrindo estes pontos disponível em:
http://www.ic.unicamp.br/~francesquini/mc102/
MC202 - Aula 1 Revisão 6 / 32
http://www.ic.unicamp.br/~francesquini/mc102/
Variáveis
• Declaração de variáveis
Tipo a, b;
• Tipo pode ser um tipo pré-definido (int, char, double) ou
um tipo definido pelo programador (struct, union).
• Escrevendo a ou b podemos acessar ou modificar o
conteúdo da variável correspondente.
int a, b;
a = 2;
b = 3 * a + 1;
MC202 - Aula 1 Revisão 7 / 32
Ponteiros
• Declaração de variáveis ponteiros
Tipo *p;
• A variável p pode armazenar um endereço da memória
que armazena uma informação do tipo Tipo. Dizemos que p
aponta para aquele endereço da memória.
int a, b;
int *p;
a = 2;
p = &a;
MC202 - Aula 1 Revisão 8 / 32
Ponteiros
• O operador ∗ permite acessar ou modificar o conteúdo da
posição de memória apontada por p.
int a, b;
int *p;
a = 2;
p = &a;
b = *p;
*p = 7;
• Note a diferença entre o uso de ∗ na declaração e como
operador.
MC202 - Aula 1 Revisão 9 / 32
Ponteiros
• Toda variável deve ser inicializada! Ainda mais variáveis
ponteiros, pois senão podem ocorrer erros imprevisíveis!
int a, b;
int *p;
a = 2;
printf("a: %d b: %d p: %d", a, b, *p); /*surpresinha*/
b = *p; /*ruim*/
*p = 7; /*pior ainda*/
MC202 - Aula 1 Revisão 10 / 32
Ponteiros - O código abaixo funciona?
void troca(int a, int b) {
int t;
t = a; a = b; b = t;
}
...
int a, b;
a = 2;
b = 7;
troca(a,b);
MC202 - Aula 1 Revisão 11 / 32
Ponteiros - O código abaixo funciona?
void troca(int a, int b) {
int t;
t = a; a = b; b = t;
}
...
int a, b;
a = 2;
b = 7;
troca(a,b);
• Não! A função troca não troca os valores dos argumentos.
• Em C, os argumentos são sempre passados por valor (são
cópias).
MC202 - Aula 1 Revisão 11 / 32
Ponteiros - O código abaixo funciona 2?
void troca(int *pa, int *pb) {
int t;
t = *pa; *pa = *pb;
}
...
int a, b;
*pb = t;
a = 2;
b = 7;
troca(&a, &b);
MC202 - Aula 1 Revisão 12 / 32
Ponteiros - O código abaixo funciona 2?
void troca(int *pa, int *pb) {
int t;
t = *pa; *pa = *pb;
}
...
int a, b;
*pb = t;
a = 2;
b = 7;
troca(&a, &b);
• Sim!! A função troca faz o serviço
• Ao passar os endereços como argumentos é possı́vel
acessar ou modificar as variáveis originais
MC202 - Aula 1 Revisão 12 / 32
Structs
• O tipo struct permite agregar variáveis e definir um novo
tipo.
struct Fruta {
char nome[30];
float preco;
}
struct Fruta a = {"caqui", 2.0}, b, c;
• Pode-se fazer atribuição direta entre variáveis do mesmo
tipo struct, mas não comparação.
c = a;
b = {"mamao", 3.0}; /* errado! */
if (c == a) /* errado! */
printf("Mesma fruta!\n");
MC202 - Aula 1 Revisão 13 / 32
typedef
• O operador typedef permite criar sinônimos para tipos.
typedef float real;
struct Fruta{
char nome[30];
real preco;
}
typedef struct Fruta Fruta; /*nao errei*/
Fruta a = {"caqui", 2.0}, b, c;
MC202 - Aula 1 Revisão 14 / 32
Cadastro de frutas
typedef struct Fruta {
char nome[30];
float preco;
}
typedef struct Cadastro {
Fruta fruta;
int vazio;
} TipoCadastro;
TipoCadastro cadastro[MAX];
/*Funcoes de manipulacao*/
void inicializa(void);
int insere(Fruta f);
void remove(char *nome);
int procura(char *nome);
MC202 - Aula 1 Revisão 15 / 32
Cadastro de frutas
void inicializa(void) {
int i;
for (i = 0; i < MAX; i++)
cadastro[i].vazio = 1;
}
MC202 - Aula 1 Revisão 16 / 32
Cadastro de frutas
int insere(Fruta f) {
int i = 0;
while (i < MAX && !cadastro[i].vazio) i++;
if (i < MAX)
cadastro[i].fruta = f;
return (i < MAX);
}
MC202 - Aula 1 Revisão 17 / 32
Cadastro de frutas
void remove(char *nome) {
int i = 0;
while (i < MAX) {
if (!cadastro[i].vazio &&
!strcmp(cadastro[i].fruta.nome, nome)) {
cadastro[i].vazio = 1;
break;
}
MC202 - Aula 1 Revisão 18 / 32
Cadastro de frutas
int procura(char *nome) {
int i = 0;
while (i < MAX) {
if (!cadastro[i].vazio &&
!strcmp(cadastro[i].fruta.nome, nome)) {
break;
} else
i++;
if (i < MAX)
return i;
else
return -1;
}
}
MC202 - Aula 1 Revisão 19 / 32
Cadastro de frutas
• A implementação da função procura devolve um índice do
vetor cadastro.
• Entretanto, isto não é totalmente satisfatório, pois o usuário
teria acesso ao campo vazio da estrutura TipoCadastro.
• O ideal seria esconder esta informação do usuário. Ele só se
interessa pelo campo fruta e não precisa saber como o
cadastro é implementado internamente.
• Basta devolver um ponteiro para a estrutura do campo
fruta.
MC202 - Aula 1 Revisão 20 / 32
Cadastro de frutas
• A implementação da função procura devolve um índice do
vetor cadastro.
• Entretanto, isto não é totalmente satisfatório, pois o usuário
teria acesso ao campo vazio da estrutura TipoCadastro.
• O ideal seria esconder esta informação do usuário. Ele só se
interessa pelo campo fruta e não precisa saber como o
cadastro é implementado internamente.
• Basta devolver um ponteiro para a estrutura do campo
fruta.
MC202 - Aula 1 Revisão 20 / 32
Cadastro de frutas
• A implementação da função procura devolve um índice do
vetor cadastro.
• Entretanto, isto não é totalmente satisfatório, pois o usuário
teria acessoao campo vazio da estrutura TipoCadastro.
• O ideal seria esconder esta informação do usuário. Ele só se
interessa pelo campo fruta e não precisa saber como o
cadastro é implementado internamente.
• Basta devolver um ponteiro para a estrutura do campo
fruta.
MC202 - Aula 1 Revisão 20 / 32
Cadastro de frutas
• A implementação da função procura devolve um índice do
vetor cadastro.
• Entretanto, isto não é totalmente satisfatório, pois o usuário
teria acesso ao campo vazio da estrutura TipoCadastro.
• O ideal seria esconder esta informação do usuário. Ele só se
interessa pelo campo fruta e não precisa saber como o
cadastro é implementado internamente.
• Basta devolver um ponteiro para a estrutura do campo
fruta.
MC202 - Aula 1 Revisão 20 / 32
Ponteiros para structs
Fruta* procura(char *nome) {
int i = 0;
while (i < MAX) {
if (!cadastro[i].vazio &&
!strcmp(cadastro[i].fruta.nome, nome)) {
break;
} else
i++;
if (i < MAX)
return &(cadastro[i].fruta);
else
return NULL;
}
MC202 - Aula 1 Revisão 21 / 32
Ponteiros para structs
Fruta* procura(char *nome) {
int i = 0;
while (i < MAX) {
if (!cadastro[i].vazio &&
!strcmp(cadastro[i].fruta.nome, nome)) {
break;
} else
i++;
if (i < MAX)
return &(cadastro[i].fruta);
else
return NULL;
}
• É comum em C escrever p->preco em vez de (*p).preco. A
maioria dos textos e códigos usa esta notação.
MC202 - Aula 1 Revisão 22 / 32
Alocação dinâmica – malloc
• A função malloc permite alocar uma quantidade de
memória especificada pelo usuário.
TipoCadastro inicializa(int n) {
TipoCadastro *p;
int i;
p = malloc(n*sizeof(TipoCadastro);
for (i = 0; i < MAX; i++)
p[i].vazio = 1;
return p;
}
...
TipoCadastro *cadastro;
cadastro = inicializa(MAX);
• O restante do código não muda.
MC202 - Aula 1 Revisão 23 / 32
Alocação dinâmica – free
• A função free desaloca memória alocada previamente.
void finaliza(void) {
free(cadastro);
}
• Todo malloc pede um free. Lembre-se disso ao programar.
• Não existe free sem o malloc correspondente
MC202 - Aula 1 Revisão 24 / 32
Vetores vs. ponteiros
• Do ponto de programação, um vetor nada mais é do que o
endereço do primeiro elemento do vetor.
int vetor[MAX];
int *p;
for (i = 0; i < MAX; i++)
vetor[i] = 0;
p = vetor; /* p = &(vetor[0]) */
for (i = 0; i < MAX; i++)
p[i] = 0; /* *(p+i) = 0 */
MC202 - Aula 1 Revisão 25 / 32
Alocação dinâmica de matrizes
Declaração estática
float mat[MAXLIN][MAXCOL];
Alocação parcialmente dinâmica
float *mat[MAXLIN];
/* vetor de ponteiros! */
for (i = 0; i < MAXLIN; i++)
mat[i] = malloc(MAXCOL * sizeof(float));
...
mat[i][j] = 3.1416;
MC202 - Aula 1 Revisão 26 / 32
Alocação dinâmica de matrizes
Alocação dinâmica
float **mat;
/* vetor de ponteiros dinamico */
mat = malloc(MAXLIN * sizeof(float *));
for (i = 0; i < MAXLIN; i++)
mat[i] = malloc(MAXCOL * sizeof(float));
...
mat[i][j] = 3.1416;
MC202 - Aula 1 Revisão 27 / 32
Recursão
MC202 - Aula 1 Revisão 28 / 32
Recursão
MC202 - Aula 1 Revisão 29 / 32
Recursão - Fatorial
• Problema: Calcular o fatorial de um número (n!).
• Qual o caso base e o passo da indução?
• Se n é igual a 1, então o fatorial é 1.
• Qual seria o passo indutivo?
• Temos que expressar a solução para n > 1, supondo que já
sabemos a solução para algum caso mais simples.
• n! = n ∗ (n − 1)!
• Este caso é trivial pois a própria definição do fatorial é
recursiva
MC202 - Aula 1 Revisão 30 / 32
Recursão - Fatorial
• Portanto a solução do problema pode ser expressa de
forma recursiva como:
• Se n = 1 então n! = 1
• Se n > 1 então n! = n ∗ (n − 1)!
• Note como aplicamos o princípio da indução
• Sabemos a solução para o caso base n = 1
• Definimos a solução do problema geral n! em termos do
mesmo problema só que para um caso menor ((n − 1)!)
MC202 - Aula 1 Revisão 31 / 32
Recursão - Fatorial
long fatr(long n){
long x,r;
if(n == 1) //Passo Basico
return 1;
else {
x = n - 1;
r = fatr(x); //Sabendo o fatorial de (n-1)
return (n* r); //calculamos o fatorial de n
}
}
• Para solucionar o problema é feita uma chamada para a
própria função, por isso, esta função é chamada recursiva.
• Recursividade geralmente permite uma descrição mais
clara e concisa dos algoritmos, especialmente quando o
problema é recursivo por natureza.
MC202 - Aula 1 Revisão 32 / 32
	Cover Section
	Aviso
	Introdução
	Revisão