Aula 3 – Alocação Dinâmica

Universidade Federal de Santa MariaColégio Agrícola de Frederico WestphalenCurso Superior de Tecnologia em Sistemas de Internet

Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno

Ponteiros ou Apontadores

• É um conceito/recurso de bastante utilidade e pré-requisito para as próximas aulas;

Vamos a um exemplo ...

int a;int* p;

a = 10;

p = &a;

*p = 5;

printf(“%d”,a);

10ap

int A, B, S;

int* ptA;

int* ptB;

int* ptS;

A = 2;

B = 3;

ptA = &A;

ptB = &B;

ptS = &S;

*ptS = *ptA + *ptB;

printf("Resultado = %d",S);

2 3 5

int* e;

e = malloc(sizeof(int));

if (e == NULL) {printf(“Memória cheia”);exit(1);

}

*e = 10;

printf(“e = %p e contém %d”,e,*e);

free(e);

E se eu acessar “e”antes de inicializá-lo?

int* p;

int* r;

int* q;

p = malloc(sizeof(int));

*p = 5;

q = malloc(sizeof(int));

q = p;

r = p;

printf("%d",*p);

5

O que acontece com o

espaço alocado para q?

int* e;

e = malloc(sizeof(int));

while (e != NULL) {e = malloc(sizeof(int));

}

printf("MEMÓRIA CHEIA");

void troca(int a, int b) {int aux;aux = a;a = b;b = aux;}

void main {

int x = 5;

int y = 10;

troca(x, y);

printf(“x = %d, y = %d”, x,y);

}

Quanto vale x ?

void troca(int* a, int* b) {int aux;aux = *a;*a = *b;*b = aux;}

void main {

int x = 5;

int y = 10;

troca(&x, &y);

printf(“x = %d, y = %d”, x,y);

}

Agora sim!

• Por valor:O valor enviado para a subrotina é copiado e todas as alterações feitas na subrotina afetam apenas a cópia do parâmetro;

As alterações da subrotina não afetam a variável original;

• Por referência:Neste caso o parâmetro não é apenas uma cópia do valor, mas sim a variável (o endereço) original.

As alterações da subrotina são feitas diretamente na variável original.

Aula 4 – Estr. Clássicas - Pilha

Universidade Federal de Santa MariaColégio Agrícola de Frederico WestphalenCurso Superior de Tecnologia em Sistemas para a Internet

Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno

LIFO - Last In First Out

• Para que um elemento entre na pilha ele será sempre colocado no topo da mesma;

• Para que um elemento seja retirado da pilha, ele sempre sairá do topo da mesma.

LIFO

• Last in, first out

• Os elementos da pilha são retirados na ordem inversa à ordem em que foram introduzidos: o último a entrar é o primeiro a sair;

• Não são permitidas operações sobre quaisquer nodos, somente sobre aqueles definidos pela organização da pilha.

• Recurso de “desfazer” dos editores (de texto ou editores gráficos)

Juquinha desenhou o chão;

Mariazinha desenhou um caixa sobre o chão;

Pedrinho completou ... Isso é uma casa;

Zezinho desenhou a neve sobre o telhado da casa;

Sandrinha fez o sol;

Joãozinho desenhou seu pai juntando o sabonete no chão do banheiro;

E a professora?

Teve que desfazer o desenho do Joãozinho!!!

• Para descontrair ... desenho do Joãozinho ...(a professora pede que cada aluno participe de um desenho colaborativo)

• Recurso de “voltar” entre os endereços mais recentemente visitados de um browser;

www.cafw.ufsm.br/~bruno/disciplinas/estrutura_dados

www.cafw.ufsm.br/~bruno

www.cafw.ufsm.br

www.ufsm.br

Voltar

Voltar

• Controle de chamadas de subrotinas (procedimentos e funções);

Sempre que o programa encontrar uma chamada a uma subrotina ele irá empilhar o contexto atual da aplicação (valores de variáveis, endereços de retorno) em uma pilha;

Na medida em que as chamadas vão sendo finalizadas a pilha vai sendo desfeita;

• Uma pilha permite basicamente duas operações:

Empilhar (push)Desempilhar (pop)

• Antes de pensar os algoritmos, precisamos:Pensar em uma estratégia de armazenamento da estrutura;Pensar na interface das operações que irão manipular os dados da estrutura;

• Para representar fisicamente uma pilha podemos usar diferentes estratégias:

Contigüidade física – com o uso de vetores;Alocação dinâmica ou encadeamento – com a utilização de ponteiros;

• Vamos adotar a opção 1 (utilização de vetores) em função da simplicidade dos algoritmos;

• A organização lógica da pilha independe da estratégia de armazenamento.

#define MAX 100

typedef struct pilha {int topo;int vetor[MAX];

} Pilha;

De que forma posso representar

uma pilha?

Qual é a interface do TAD Pilha?

• Inicialmente precisamos:• Criar uma pilha;• Empilhar um elemento;• Desempilhar um elemento;• Destruir uma pilha (liberar a memória

ocupada pela mesma);• Saber se a pilha está vazia;• Saber se a pilha está cheia;• etc...

Pilha* criaPilha();

void liberaPilha(Pilha* p);

int empilha(Pilha* p, int v);

int desempilha(Pilha* p, int* v);

int estahVazia(Pilha* p);

int estahCheia(Pilha* p);

• Vetor[6]:

topo = 0

• Empilha 10• Empilha 20• Empilha 30• Desempilha• Empilha 50• Empilha 40• Empilha 12• Empilha 7• Empilha 9

10

topo = 1

topo = 2

topo = 3

topo = 4

topo = 5

20

30

40

12

7

50

topo = 6

• Erro! Pilha cheia

Pilha* criaPilha();• Aloca memória para a estrutura física;• Inicializa o topo do vetor;• Retorna um ponteiro para a estrutura criada;

void liberaPilha(Pilha* p);• Recebe um ponteiro para uma estrutura do tipo

Pilha e libera a memória ocupada por ela;

int estahVazia(Pilha* p);•

O topo está na posição zero!

int estahCheia(Pilha* p);

•O topo está na última posição!

int empilha(Pilha* p, int v);

• Recebe um ponteiro para uma estrutura do tipo Pilha e um valor a ser empilhado;

• Verifica se a pilha já não está cheia;• Se não está, então ...

Coloca o elemento na posição indicada pelo topoIncrementa o valor de topo;

• A função empilha() retorna 1 (um) se o valor foi empilhado ou então retorna 0 (zero) se não foi possível empilhar;

int desempilha(Pilha* p, int* v);

• Recebe um ponteiro para uma estrutura do tipo Pilha e um ponteiro para uma variável inteira;

• Verifica se a pilha já não está vazia;• Se não está, então ...

Retira o elemento da posição logo abaixo do topo;Decrementa o valor de topo;

• A função desempilha() retorna 1 (um) se o valor foi desempilhado ou então retorna 0 (zero) se não foi possível desempilhar;

a = criaPilha();

empilha(a,10);empilha(a,20);empilha(a,30);

int x;desempilha(a, &x);printf("Elemento '%d' retirado",x);

liberaPilha(a);

Exercícios para fixação

Dado o seguinte programa escrito em C:#include <stdio.h>

int main(void)

{

int n[] = {7, 8, 9};

int *p;

p = &n[0];

p++;

printf("Valor: %d ", *p);

(*p)++;

printf("Valor: %d\n", *p);

}

Qual é a resposta que será impressa na tela?

(a) Valor: 7 Valor: 8(b) Valor: 7 Valor: 7(c) Valor: 8 Valor: 9(d) Valor: 7 Valor: 9(e) Valor: 9 Valor: 9

2007

• Escreva um programa para simular o funcionamento de uma Torre de Hanói.

• Você deve mover todos os discos de uma torre para outra sem jamais colocar um disco maior encima de um disco menor.

• Para simplificar utilize uma torre com três discos;