Estruturas de Dados - Vetores e Ponteiros (Guilherme)

Prévia do material em texto

Estruturas de Dados
Vetores & Ponteiros
Guilherme N. Ramos
gnramos@cic.unb.br
Departamento de Cieˆncia da Computac¸a˜o
Universidade de Bras´ılia
gnramos (CIC/UnB) 116319 - Estruturas de Dados 1/28
Estruturas de Dados
Introduc¸a˜o
Exemplos de problemas:
- manipular arquivos com informac¸o˜es de alunos
- soluc¸a˜o: ordenar por nu´mero de matr´ıcula
- operac¸o˜es poss´ıveis: inserir/remover, pesquisar, etc.
- qual ED seria adequada? Lista
- corrigir provas
- soluc¸a˜o: analisar cada uma individualmente
- operac¸o˜es poss´ıveis: colocar/retirar prova
- qual ED seria adequada? Pilha
- lidar com alunos que querem revisar a prova
- soluc¸a˜o: ordernar por ordem de chegada
- operac¸o˜es poss´ıveis: entrar (ao fim)/sair (do comec¸o)
- qual ED seria adequada? Fila
gnramos (CIC/UnB) 116319 - Estruturas de Dados 2/28
Estruturas de Dados
Introduc¸a˜o
Estruturas de Dados e Algoritmos
Temas fundamentais da Cieˆncia da Computac¸a˜o, utilizados em diversas
a´reas do conhecimento e com diferentes propo´sitos de aplicac¸a˜o
- Estrutura de Dados: modo particular de armazenar/organizar dados
- Algoritmo: sequ¨eˆncia finita de instruc¸o˜es (para resolver uma tarefa)
Exemplo - problema: descobrir o telefone de um conhecido
- Algoritmo: pesquisa sequ¨encial por nome (chave de ordenac¸a˜o)
- Estrutura de dados: lista telefoˆnica - [nome] : [nu´mero de telefone]
- E se quise´ssemos pesquisar pelo peso?
Uma estrutura de dados adequada pode aumentar a eficieˆncia do
algoritmo
gnramos (CIC/UnB) 116319 - Estruturas de Dados 3/28
Estruturas de Dados
Tipos de Dados
Termos:
- Tipo de Dado: associado a um me´todo de interpretar um padra˜o de
bits (linguagem de programac¸a˜o)
- boolean (bit - 0/1)
- Tipo Abstrato de Dado (TAD): modelo de dado e operac¸o˜es
definidas sobre ele
- N e {+, -, /, *}
- Estrutura de Dados (ED): forma concreta de se implementar um
TAD → representac¸a˜o computacional do modelo matema´tico
Uma ED pode ser:
- homogeˆnea: conjuntos de dados do mesmo tipo
- heterogeˆnea: conjuntos de dados de diferentes tipos
gnramos (CIC/UnB) 116319 - Estruturas de Dados 4/28
Estruturas de Dados
Tipos de Dados - Primitivos
Dependem da linguagem de programac¸a˜o usada
Integer
Tamanho Intervalo
4 bits [-8, 7]
8 bits [-128, 127]
16 bits [-32768, 32767]
· · · · · ·
- Boolean: valor lo´gico
- b ← falso
- Integer: valor nume´rico (∈ Z)
- i ← 2010
- Float: valor nume´rico (∈ R)
- f ← 3.14
- Character: letras, d´ıgitos, s´ımbolos
- c ←’@’
- String: sequeˆncia de caracteres
- s ← “#2: Geˆnio e´ 1% inspirac¸a˜o e 99% de transpirac¸a˜o (T. Edison)”
- Ponteiro
gnramos (CIC/UnB) 116319 - Estruturas de Dados 5/28
Estruturas de Dados
Tipos de Dados - Compostos
Criados a partir dos tipos primitivos
- Registro: 2 ou mais primitivos
struct numero complexo t{
float re ;
float im;
};
- Unia˜o: diferentes tipos primitivos em um u´nico espac¸o de memo´ria
union valor u {
int iVal
float fVal
char cVal
};
- Simples: o programador precisa saber qual o tipo esta´ usando
- Variante: o computador sabe o tipo utilizado
gnramos (CIC/UnB) 116319 - Estruturas de Dados 6/28
Estruturas de Dados
Tipos de Dados - Abstratos
Modelo matema´tico para EDs similares
- Definido (indiretamente) pelas operac¸o˜es que pode realizar
Forma de organizar e relacionar dados na memo´ria do sistema, de modo
a permitir certas operac¸o˜es sobre esses dados, independentemente do
modo como essas estruturas sa˜o implementadas.
Exemplo: Pilha
- Push (inserir)
- Pop (remover)
gnramos (CIC/UnB) 116319 - Estruturas de Dados 7/28
Estruturas de Dados Lineares
Vetor
- Conjunto de dados do mesmo tipo (estrutura homogeˆnea)
- Cada elemento pode ser acessado por sua posic¸a˜o (´ındice)
- Alocac¸a˜o esta´tica e sequ¨encial
Vantagens:
- Simplicidade
- Acesso direto
Desvantagens:
- Tamanho fixo
a b c d e f
gnramos (CIC/UnB) 116319 - Estruturas de Dados 8/28
Estruturas de Dados Lineares
Vetor
Inserc¸a˜o no fim
void append(tipo item ∗vetor , int n, tipo item novo item) {
int i ; // n: numero de elementos do vetor
tipo item ∗ vetor antigo = vetor;
vetor = (tipo item ∗)malloc((n + 1) ∗ sizeof( tipo item )) ;
for ( i = 0; i < numero elementos; ++i)
vetor [ i ] = vetor antigo [ i ];
vetor [numero elementos] = novo item;
free( vetor antigo ) ;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 9/28
Estruturas de Dados Lineares
Matriz
- Conjunto de dados do mesmo tipo (estrutura homogeˆnea)
- Cada elemento pode ser acessado por sua posic¸a˜o (´ındice)
- Alocac¸a˜o esta´tica e sequ¨encial
Vantagens:
- Simplicidade
- Acesso direto
Desvantagens:
- Tamanho fixo
gnramos (CIC/UnB) 116319 - Estruturas de Dados 10/28
Estruturas de Dados Lineares
Alocac¸a˜o esta´tica x Alocac¸a˜o dinaˆmica
Varia´veis esta´ticas
Tem seu enderec¸o fixado antes do in´ıcio da execuc¸a˜o do programa. A
a´rea de memo´ria ocupada se mante´m durante toda a execuc¸a˜o.
Varia´veis dinaˆmicas
Sa˜o criadas e eliminadas durante a execuc¸a˜o do programa, ocupando
memo´ria somente quando sa˜o utilizadas
Alocac¸a˜o esta´tica
int vetor [10];
Alocac¸a˜o dinaˆmica
int ∗vetor = (int ∗)malloc(10 ∗ sizeof( int)) ;
// verificar se houve erro
gnramos (CIC/UnB) 116319 - Estruturas de Dados 11/28
Estruturas de Dados Lineares
Alocac¸a˜o esta´tica x Alocac¸a˜o dinaˆmica
E´ poss´ıvel criar vetores de tamanho varia´vel usando alocac¸a˜o dinaˆmica?
- Elementos do vetor sa˜o criados somente quando necessa´rios
- esta˜o espac¸ados na memo´ria
- Como saber onde esta´ o pro´ximo elemento do vetor?
- Ponteiros! Cada elemento do vetor guarda a posic¸a˜o do pro´ximo
- Um ponteiro indica o primeiro elemento
- Um ponteiro indica o u´ltimo elemento
- Cada elemento possui uma ligac¸a˜o para o pro´ximo elemento
Tipo data t
typedef struct {
key t key;
// etc .
} data t ;
Elemento do vetor dinaˆmico
typedef struct slist node t {
data t data;
struct slist node t ∗next;
} slist node t ;
gnramos (CIC/UnB) 116319 - Estruturas de Dados 12/28
Estruturas de Dados Lineares
Alocac¸a˜o esta´tica x Alocac¸a˜o dinaˆmica
Ana´lise de complexidade:
Considere um vetor esta´tico e um vetor com alocac¸a˜o dinaˆmica conforme
definido anteriormente:
- Qual a complexidade de inserc¸a˜o de um ı´tem novo no in´ıcio do
vetor?
Vetor esta´tico O(n)
1 criar novo vetor
2 inserir novo item
3 copiar items do velho para o
novo vetor
Vetor dinaˆmico O(1)
1 definir o primeiro item como
pro´ximo do novo item
2 definir o primeiro item como o
novo item
gnramos (CIC/UnB) 116319 - Estruturas de Dados 13/28
Estruturas de Dados Lineares
Ponteiros (apontador)
Tipo de dado de uma linguagem de programac¸a˜o. O valor armazenado se
refere diretamente a um outro valor alocado em outra a´rea da memo´ria -
e´ o enderec¸o deste.
1048736
ptr int
2010
int
2011
int
CIC
char
UnB
char
2014
int
ED
char
O Ministe´rio da Programac¸a˜o adverte
O descuido com ponteiros pode levar a se´rios bugs, perda de tempo e a
dores de cabec¸a.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 14/28
Estruturas de Dados Lineares
Ponteiros - Falha de segmentac¸a˜o
gnramos (CIC/UnB) 116319 - Estruturas de Dados 15/28
Estruturas de Dados Lineares
Ponteiros - Ponteiro selvagem
gnramos (CIC/UnB) 116319 - Estruturas de Dados 16/28
Estruturas de Dados Lineares
Ponteiros
Em C:
key t key; // estrutura qualquer
// inicializacao de key
key t ∗ptr = NULL; // ponteiro para tipo key t
ptr = &key; // ptr recebe o endereco de memoria de key
key t key2 = ∗ptr; // key2 recebe o conteudo de ptr
if ( key2 != key)
// tela azul?
gnramos (CIC/UnB) 116319 - Estruturas de Dados 17/28
Estruturas de Dados Lineares
Ponteiros
MaisC:
int array [5]; // Declaracao estatica de 5 inteiros consecutivos
int ∗ptr = array; // Um vetor pode ser usado como ponteiro
ptr [0] = 1; // Ponteiros podem ser indexados como um vetor
∗(array + 1) = 2; /∗ Vetores podem ser referenciados com a sintaxe de
ponteiro (mesmo que array[1] = 2;) ∗/
∗(1 + array) = 3; /∗ Adicao de ponteiros e comutativa (mesmo que
array [1] = 3;) ∗/
2[ array ] = 4; // Indexacao e comutativa (mesmo que array[2] = 4;)
gnramos (CIC/UnB) 116319 - Estruturas de Dados 18/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 1 () {
int x, y, ∗p1, ∗p2;
x = 5;
y = 7;
p1 = &x;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
p2 = &y;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1606416876 | *p1 = 5
p2 = 1606416872 | *p2 = 7
gnramos (CIC/UnB) 116319 - Estruturas de Dados 19/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 2 () {
int x, y, ∗p1, ∗p2;
x = 5;
y=7;
p1 = &x;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
p2 = &y;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
∗p2 = ∗p1;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1606416876 | *p1 = 5
p2 = 1606416872 | *p2 = 7
p2 = 1606416872 | *p2 = 5
gnramos (CIC/UnB) 116319 - Estruturas de Dados 20/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 3 () {
int ∗p1, ∗p2;
p1 = malloc(sizeof(int)) ;
p2 = malloc(sizeof(int)) ;
∗p1 = 10;
∗p2 = 20;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1048704 | *p1 = 10
p2 = 1048720 | *p2 = 20
gnramos (CIC/UnB) 116319 - Estruturas de Dados 21/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 4 () {
int ∗p1, ∗p2;
p1 = malloc(sizeof(int)) ;
p2 = malloc(sizeof(int)) ;
∗p1 = 10;
∗p2 = 20;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
∗p2 = ∗p1;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1048736 | *p1 = 10
p2 = 1048752 | *p2 = 20
p2 = 1048752 | *p2 = 10
gnramos (CIC/UnB) 116319 - Estruturas de Dados 22/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 5 () {
int ∗p1, ∗p2;
p1 = malloc(sizeof(int)) ;
p2 = malloc(sizeof(int)) ;
∗p1 = 10;
∗p2 = 20;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
p2 = p1;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1048768 | *p1 = 10
p2 = 1048784 | *p2 = 20
p2 = 1048768 | *p2 = 10
gnramos (CIC/UnB) 116319 - Estruturas de Dados 23/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 6 () {
int ∗p1, ∗p2;
p1 = malloc(sizeof(int)) ;
p2 = malloc(sizeof(int)) ;
∗p1 = 10;
∗p2 = 20;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
free(p2);
p2 = p1;
printf (” p2 = %d | ∗p2 = %d\n”, p2, ∗p2);
}
Resultado
p1 = 1048800 | *p1 = 10
p2 = 1048816 | *p2 = 20
p2 = 1048800 | *p2 = 10
gnramos (CIC/UnB) 116319 - Estruturas de Dados 24/28
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 7 () {
int ∗p1;
float ∗p2;
void ∗p3;
p1 = malloc(sizeof(int)) ;
∗p1 = 5;
p3 = p1;
printf (” p1 = %d | ∗p1 = %d\n”, p1, ∗p1);
printf (” p3 = %d | ∗p3 = %d\n”, p3, ∗((int ∗)p3));
p2 = malloc(sizeof(float)) ;
∗p2 = 6.2;
p3 = p2;
printf (” p2 = %d | ∗p2 = %f\n”, p2, ∗p2);
printf (” p3 = %d | ∗p3 = %f\n”, p3, ∗((float ∗)p3));
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 25/28
Resultado
p1 = 1049296 | *p1 = 5
p3 = 1049296 | *p1 = 5
p2 = 1049312 | *p2 = 6.2
p3 = 1049312 | *p1 = 6.2
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 8 () {
typedef struct {
int x;
float y;
} reg ;
reg ∗p1, ∗p2;
p1 = malloc(sizeof(reg));
p2 = malloc(sizeof(reg));
(∗p1).x = 3;
p1−>y = 5.3;
printf (” p1 = %d | (∗p1).x = %d | p1−>y = %f\n”, p1, (∗p1).x, p1−>y);
∗p2 = ∗p1;
printf (” p2 = %d | (∗p2).x = %d | p2−>y = %f\n”, p2, (∗p2).x, p2−>y);
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 26/28
Resultado
p1 = 1048848 | (*p1).x = 3 | p1->y = 5.3
p2 = 1048864 | (*p2).x = 3 | p2->y = 5.3
Estruturas de Dados Lineares
Ponteiros - Exemplos
void ptr 9 () {
slist node t ∗p1, ∗ first = NULL;
p1 = malloc(sizeof(struct slist node t )) ;
p1−>data = 0; p1−>next = first;
first = p1;
p1 = malloc(sizeof(struct slist node t )) ;
p1−>data = 2; p1−>next = first;
first = p1;
p1 = malloc(sizeof(struct slist node t )) ;
p1−>data = 4; p1−>next = first;
first = p1;
printf (” 1o elemento %d \n”, first−>data);
printf (” 2o elemento %d \n”, first−>next−>data);
printf (” 3o elemento %d \n”, first−>next−>next−>data) ;
p1 = NULL;
printf (” elemento1 %d \n”, p1−>data);
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 27/28
typedef struct slist node t{
int data;
struct slist node t ∗next;
} slist node t ;
Resultado
1o elemento 4
2o elemento 2
3o elemento 0
Segmentation fault
Estruturas de Dados Lineares
Exerc´ıcios - func¸a˜o swap
Dado um vetor e dois ı´ndices, troque os elementos das posic¸o˜es.
1 Para um vetor esta´tico (ex1, ex2)
2 Para um vetor dinaˆmico (ex3, ex4)
Assinatura da func¸a˜o:
- void swap(char *, int, int)
gnramos (CIC/UnB) 116319 - Estruturas de Dados 28/28
	Estruturas de Dados
	
	
	Estruturas de Dados Lineares