Algoritmos e Estruturas de Dados I
Prof. Daniel M. Martin
([email protected])
Aula 3
Observações dobre o EL1
●
Sempre que usar malloc(), verificar se o
espaço foi alocado com sucesso:
int *v, n = 1000;
v = (int *) malloc(n * sizeof(int));
if (v == NULL) {
fprintf(stderr, "Memória insuficiente");
return 1;
}
●
●
Não se esquecer de liberar a memória com a
função free()
Indentação de código!
Observações sobre o EL1
●
●
Faça seus programas em C, não em C ++
(extensão do arquivo deve ser .c e não .cpp)
Uso da função scanf():
scanf("%d", &n);
●
–
Não serve para imprimir uma string
–
Precisa do endereço da variável e não do valor
Uso da função printf():
printf("O valor é: %d\n", n);
–
Não precisa de um endereço e sim de um valor
Recordação: alocação de vetores
●
Estatica:
int v[1000];
–
●
Espaço reservado na pilha (Stack)
Dinâmica:
int *v, n = 1000;
v = (int *) malloc(n * sizeof(int));
–
Espaço reservado na memória principal (Heap)
–
Liberar memória após o uso: free(v);
Observações dobre o EL1
●
Não usem a função system("...");
–
●
●
Usem getc(stdin); se precisarem manter o
terminal de execução visível
IDEs para desenvolvilemto no Windows:
–
Code::Blocks (Também disponível p/ Linux)
–
Dev C++
Code::Blocks faz um "system("pause");" no
final (i.e. pede ENTER para fechar o terminal
quando o programa termina de executar)
Code::Blocks
●
File
– New
●
Project
Dev C++
●
File
– New
●
Project
Compile & Run: F9
Estruturas de Dados
●
●
●
●
Disciplina que estuda modos de se organizar
coleções de dados na memória e sua relação
com algoritmos para processar esses dados.
Para a maior parte das applicações, a escolha
das estruturas de dados é uma decisão crucial
Para um mesmo conjunto de dados, algumas
estruturas ocupam mais espaço de memória,
e outras menos
Algumas estruturas permitem algoritmos mais
eficientes que outras
Estruturas de Dados
(Hipóteses Gerais)
●
●
●
Dados não devem ser duplicados na memória
Estrutura deve ocupar tamanho proporcional
ao volume de dados (deve expandir/encolher
conforme o necessário)
Processamento de interesse nos dados:
–
Buscar por um dado na estrutura
–
Inserir dados na estrutura
–
Remover dados da estrutura
Estruturas de Dados
Vetores
Vetores
●
Estrutura de dados fundamental
–
Diversas outras estruturas dependem de vetor
–
Organiza dados de mesma natureza em
posições sucessivas de memória
–
A própria memória pode ser vista como um
grande vetor (de bytes)
–
Cada dado é identificado por um índice
–
Queremos ser capazes de fazer as operações
de busca, inserção e remoção de elementos
em um vetor.
Vetores não-ordenados
●
Suponha que temos um vetor v:
–
N – número de posições alocadas;
–
n – número de elementos guardados em v.
Valores de interesse:
A
0
●
●
F
1
J
2
B
3
Valores lixo:
K
4
F
5
Z
6
T
7
Z
8
G
9
No exemplo: N = 10, e n = 5.
Normalmente supõe-se que os valores de
interesse são distintos.
Busca – vetores não-ordenados
●
●
●
Dado um valor x, como descobrir se x pertence ao vetor?
Objetivo: determinar a posição (o índice) do
vetor que contém o valor x ou determinar se x
não está no vetor
Solução: percorrer vetor do começo (esse
algoritmo chama-se busca seqüencial)
Busca – vetores não-ordenados
●
Pseudo-código do algortimo de busca:
(devolve o indice de x ou -1 se não houver)
BUSCA-SEQUENCIAL(v[0 … (N-1)], n, x)
i←0
enquanto i < n faça
se v[ i ] = x então devolve i
senão i ← i + 1
devolve -1
Busca – vetores não-ordenados
●
Código em C supondo um vetor de inteiros:
int busca_sequencial(int *v, int N,
int n, int x)
{
int i;
for (i = 0; i < n; i ++)
if (v[i] == x)
return i;
return -1;
}
Busca – vetores não-ordenados
●
Pode-se generalizar para um vetor de itens:
int busca_sequencial(item *v, int N,
int n, item x)
{
int i;
for (i = 0; i < n; i ++)
if (v[i] == x)
return i;
return -1;
}
Busca – vetores não-ordenados
Análise do algoritmo de busca seqüencial
(Na lousa)
Inserção – vetores não-ordenados
●
Dado um valor x, como inserir x no vetor v?
●
O algoritmo de inserção é fácil
●
●
●
Valores duplicados não são permitidos, então
devemos buscar por x antes de inserir x em v
Queremos saber a posição (o índice) do vetor
em que x foi inserido.
Se x já estiver no vetor, queremos saber a
posição (o índice em que se encontra)
Inserção – vetores não-ordenados
●
Pseudo-código do algoritmo de inserção:
(devolve o indice de x ou -1 se não couber)
INSERE(v[0...(N-1)], n, x)
se n = N então devolve -1
i ← BUSCA-SEQUENCIAL(v[0...(N-1)], n, x)
se i = -1 então
v[n] ← x
n←n+1
devolve n – 1
devolve i
Inserção – vetores não-ordenados
●
Código errado em C do algoritmo de inserção:
int insere(int *v, int N, int n, int x)
{
int i = busca_sequencial(v, N, n, x);
if (i != -1)
return i;
if (n == N)
return -1;
v[n] = x;
return n ++; /* Perderá o efeito */
}
Inserção – vetores não-ordenados
●
Código certo em C do algoritmo de inserção:
int insere(int *v, int N, int *n,
int x)
{
int i = busca_sequencial(v, N,
*n, x);
if (i != -1)
return i;
if (*n == N)
return -1;
v[*n] = x;
return *n ++;
}
Inserção – vetores não-ordenados
●
Código em C para inserção de um item geral:
int insere(item *v, int N, int *n,
item x)
{
int i = busca_sequencial(v, N,
*n, x);
if (i != -1)
return i;
if (*n == N)
return -1;
v[*n] = x;
return *n ++;
}
Remoção – vetores não-ordenados
●
Dado um valor x, como removê-lo do vetor v?
REMOVE(v[0...(N-1)], n, x)
i ← BUSCA-SEQUENCIAL(v[0...(N-1)], n, x)
se i ≠ -1 então
v[ i ] ← v[n – 1]
n←n–1
Remoção – vetores não-ordenados
●
Código em C do algoritmo de remoção:
void remove(int *v, int N, int *n,
int x)
{
int i = busca_sequencial(v, N,
*n, x);
if (i != -1)
v[i] = v[-- *n];
}
Remoção – vetores não-ordenados
●
Codigo em C para remoção do valor x:
void remove(item *v, int N, int *n,
item x)
{
int i = busca_sequencial(v, N,
*n, x);
if (i != -1)
v[i] = v[-- *n];
}
Remoção – vetores não-ordenados
●
Dado um índice i, como remover v[i]?
Remoção – vetores não-ordenados
●
Dado um índice i, como remover v[i]?
REMOVE(v[0...(N-1)], n, x)
se 0 <= i < n então
v[ i ] ← v[n – 1]
n←n–1
Remoção – vetores não-ordenados
●
Código em C de remoção por índice:
void remove(int *v, int N, int *n,
int i)
{
if (0 <= i && i < n)
v[i] = v[-- *n];
}
Vetores não-ordenados
●
●
Vetores sem elementos repetidos:
–
Busca: tempo O(n)
–
Inserção: tempo O(n)
–
Remoção por valor: tempo O(n)
–
Remoção por índice: tempo O(1) (constante)
Permitindo elementos repetidos:
–
Inserção: tempo O(1)
Simulação
Na lousa
Vetores ordenados
●
Suponha que temos um vetor v:
–
N – número de posições alocadas;
–
n – número de elementos guardados em v.
Valores de interesse:
A
0
●
●
F
1
J
2
L
3
Valores lixo:
P
4
F
5
Z
6
T
7
Z
8
G
9
No exemplo: N = 10, e n = 5.
Também é costume supor que os valores de
interesse são distintos.
Busca – vetores ordenados
●
●
●
Dado um valor x, como buscar x no vetor?
É possível fazer melhor do que a busca
seqüencial?
Como você busca uma palávra no dicionário?
Busca binária
Na lousa