estruturas de dados (lei, lm, lee) programação iii (ltsi)

ESTRUTURAS DE DADOS (LEI, LM, LEE)
PROGRAMAÇÃO III (LTSI)
Universidade da Beira Interior, Departamento de Informática
Hugo Pedro Proença, 2014/2015
Apontadores
! 
O que é um apontador?
Variável que contém um endereço de memória.
!  Exemplos: int x=5; float z=3.1415; char c;
! 
5
x, 4 bytes
! 
3.1415
z, 8 bytes
a
c, 1 byte
Apontador:
! 
Espaço ocupado depende do limite de endereçamento da
máquina, mas tipicamente tem o mesmo tamanho de um
inteiro. Exlº: int *p;
A...
p, 4 bytes
Tipos de Dados Básicos (ANSI)
! 
char " 8 bits,
1 0 0 1 0 0 1 0 0
! 
int " 16/32 bits
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
! 
float " 32 bits
! 
double " 64 bits
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
Apontadores
! 
Independentemente do espaço ocupado em memória,
os tipos de dados básicos funcionam de forma intuitiva:
! 
! 
Uma variável (x) do tipo inteiro é um “espaço com
capacidade suficiente para colocar um valor inteiro lá
256
dentro”. Exemplo:
x
Similar para os restantes tipos de dados.
! 
char y
w
! 
float z
231876.1532
! 
double h
231876.1532
Apontadores
! 
Um apontador contém informação sobre uma
determinada localização e quantidade de
memória:
! 
Exlos: int *a; double *b;
a4:b9:F:c:6
a4:b9:F:c:6
Igual tamanho!
b5:a9:4:8
b5:a9:4:8
Apontadores
! 
Qual a necessidade de usar apontadores?
! 
Resolvem 2 tipos de problemas:
! 
Permitem que diferentes secções de um programa partilhem
informação.
! 
! 
A alternativa, com desvantagens óbvias, será a cópia de
informação.
Possibilitam a construção de estruturas de dados complexas
e dinãmicas, tais como as listas ligadas e as árvores
binárias, ambas objecto de estudo nesta disciplina.
Apontadores
! 
Um apontador funciona de forma similar. É uma
variável que contém espaço suficiente para
albergar um endereço de memória.
Tipicamente 2-4 bytes.
!  int *y;
// ”y” aponta para um inteiro
! 
Representação Física
y
Representação Lógica
0x65
y
Não alocado !
0x65
25
25
Não alocado !
Apontadores: Inicialização
! 
Experimente-se executar
o seguinte programa:
! 
! 
A variável “x” é alocada para guardar espaço para um inteiro.
Qual?
! 
! 
LIXO!
De igual forma, ao declararmos um apontador ele refere-se a
um determinado espaço de memória.
! 
Qual?
! 
! 
! 
#include <stdio.h>
void main(){
int x;
printf(“%d\n”,x);
}
Não controlamos isso!
Possivelmente algum espaço afecto a outro processo ou utilizador
Resultado: “Access Violation”: tentativa de acesso a um
espaço de memória indevido.
Apontadores: Inicialização
! 
Constante NULL.
! 
! 
! 
! 
! 
Definida na biblioteca “stdlib.h”
Serve para explicitar o valor nulo.
Tenta modelar o conceito de “não estar a apontar para lado
nenhum”
Representa-se normalmente pelo síbolo de “terra” (ground),
proveniente dos sistemas digitais.
Nodo *p=NULL;
p
Memória Alocada Dinamicamente
! 
! 
! 
! 
! 
A memória alocada dinamicamente faz parte de
uma área de memória chamada heap.
Basicamente, o programa aloca e liberta porções
de memória do heap durante a execução.
Alocação: malloc, realloc, calloc.
0x01
0x02
Libertação: free.
Nodo *p=malloc(...);
...
0x0n
Símbolos * e &
! 
! 
! 
Na linguagem C, os símbolos * e & desempenham
um papel fulcral nas operações de baixo nível de
manuseamento de espaços de memória.
* " “o espaço para onde aponta a variável”
&" “o endereço da variável”
Exemplo:
! 
# 
int *p;
int x=4;
...
*p=x;
# 
p=&x;
# 
# 
# 
//”p” é um apontador para um nodo;
//”x” é um inteiro
//Cópia de inteiros. Só funcionaria se “p”
tivesse espaço válido associado!
//”p” aponta para o endereço da variável x
Símbolos * e &
! 
! 
! 
! 
! 
! 
! 
! 
! 
! 
! 
! 
! 
int x=4, y=6;
int *z;
int *z=x;
int *z=&x;
z=y;
z=&y;
&x=6;
&x=FF:AA:99:CC;
x=x+1;
z=z+1;
int * v=malloc(sizeof(int));
*z=4;
*v=5;
Parâmetros
! 
Ao executarmos uma função, é criada uma cópia de
todos os parâmetros de entrada.
!  Na
“passagem por valor”, a expressão-argumento é
avaliada e o resultado copiado para uma nova região da
memória.
#  int
porValor(int x);
#  A variàvel argumento tem alcance local (dentro da função).
!  A
“passagem por referência”, o processo é exactamente o
mesmo, tendo como única particularidade o facto da
variável-argumento ser do tipo apontador.
#  Int
porReferencia(int *x);
#  A cópia feita é relativa a apontadores, podendo ser alterado o
espaço original da variável utilizada na chamada à função.
Estruturas de Dados Dinãmicas
! 
! 
É usual definir uma estrutura de dados dinãmica em
C através da criação de um novo tipo de dados
(typedef) e da especificação da estrutura.
Sintaxe:
Nome temporário
typedef struct TIPO{
Tipo atributo1;
Atributos de Dados
...
Tipo atributon;
Atributo de ligação
struct TIPO *nseg;
Novo tipo
}Tipo;
Estruturas de Dados Dinãmicas
! 
Exemplo: Definição de um tipo de dados dinãmico
para guardar informação sobre os alunos da UBI.
Typedef struct ALUNO{
int numAluno;
long int BI;
char nome[80];
char morada[80];
struct ALUNO* nseg;
}Aluno;
Estruturas de Dados Dinãmicas
! 
! 
A partir da definição anterior, é possível passar a
criar variáveis do tipo Aluno:
numAluno
Estáticamente:
! 
BI
Nome
Aluno x;
x
! 
Morada
nseg
Dinamicamente:
! 
numAluno
Aluno *y=(Aluno*)malloc(sizeof(Aluno));
y
BI
Nome
Morada
nseg
Apontadores
Exemplos
Atribuição
Apontadores
Listas Simplesmente Ligadas
! 
! 
! 
Uma Lista ligada (simples) é um conjunto de
elementos de um determinado tipo de estrutura de
dados, em que cada elemento contém uma ligação
ao próximo elemento da lista, através da variável
apontador “nseg”.
O acesso ao primeiro elemento da lista é
efectuado através de uma variável apontador
para o respectivo tipo/estrutura de dados.
O último elemento da lista contém o atributo
apontador “nseg” a apontar para a constante
“NULL”.
Listas Ligadas
Ilustração:
! 
! 
Perspectiva Lógica de uma lista simplesmente ligada:
L
! 
E1
E2
E3
E4
Perspectiva Física de uma lista simplesmente ligada:
0x73
L 0x73
E1
0x76
E3
0x75
E4
0x00
E2
0x74
...
Alocação Dinãmica
makeNode()
Operações c/ Listas
insertFirst()
removeFirst()
Operações c/ Listas
insertLast()
removeLast()