Arrays
Representação bastante usada
Posições consecutivas de memória
 uma confusão entre a estrutura e representação
devido à associação com posições consecutivas [NEM
SEMPRE]
Pares (índice, valor)
MAPEAMENTO
/
\
índice
valor
Para cada índice definido  um valor associado àquele
índice
Operações  armazenar e recuperar valores
CAP-223
Listas ordenadas
Lista Linear {a1, a2, ..., an}
Operações:
tamanho da lista
ler a lista da esquerda para direita e
vice-versa
recuperar o elemento i
armazenar novo valor na posição i
inserir novo elemento na posição i
i, i+1, ..., n
i+1, i+2, ..., n+1
deletar elemento na posição i
i+1, ..., n
i, i+1, ..., n-1
CAP-223
Listas ordenadas (cont.)
Array associa valor ai com índice i
Mapeamento seqüencial ai, ai+1, ... nas posições i, i+1
Recuperação e modificação leva um tempo constante
MAS inserir/deletar necessitam de esforço computacional
quando se utiliza alocação seqüencial
mover elementos para manter mapeamento seqüencial
CONSDIERAR mapeamento não seqüencial
CAP-223
Matrizes
elementos organizados por
linhas
e
colunas
A (1:m, 1:n) m linhas e n colunas
CAP-223
Matrizes Esparsas
Maioria dos elementos são nulos
Não existe uma definição precisa - é só intuição.
O objetivo é achar uma alternativa para representar
esse tipo de matriz. POR QUE?
Alternativa - armazenar somente elementos não-nulos
por exemplo armazenar linha, coluna e o valor
A ( 0:t, 1:3 ), onde t = número de elementos não-nulos
A ( 0, 1 ) = número de linhas
A ( 0, 2 ) = número de colunas
A ( 0, 3 ) = t
CAP-223
Matrizes Esparsas (cont.)
A ( 0,
1,
2,
3,
4,
5,
6,
7,
8)
1,
2,
3
-----------------------6
6
8
1
1
15
1
4
22
1
6
-15
2
2
11
2
3
3
3
4
-6
5
1
91
6
3
28
6 linhas
6 colunas
8 elementos não-nulos
Uma possível operação:
Transposição
ai,j
para aj,
CAP-223
Matrizes Esparsas (cont.)
mrows, ncols, t  a0,1, a0,2, a0,3
b0,1, b0,2, b0,3  ncols, mrows, t
q1
for col  1, ncols
for p  1, t
if ap,2 == col
{ bq,1, bq,2, bq,3  ap,2, ap,1, ap,3
q++
O (nt)
}
end
se t = nm então O(n2m)
end
Que tal O (n+t)???
CAP-223
Matrizes Esparsas (cont.)
Melhorar algoritmo utilizando mais espaço de memória
Sk = número de elementos na coluna k
Tp = a posição onde deve começar a linha p
inicializações do b0,1, b0,2 e b0,3
Si  Ti  0, para i = 1, ncols
for i  1, t Sa(i,2)  Sa(i,2)++
T1  1
for i  2, ncols Ti = Ti-1 + Si-1
for i  1, t
j  ai,2
bT(j),1, bT(j),2, bT(j),3  ai,2, ai,1, ai,3
Tj++
end
CAP-223
Representação de Arrays
A ( l1:u1, l2:u2, l3:u3, ..., ln:un ) como calcular o
número de elementos?  (u  l 1)
n
i
i
i 1
Por exemplo A (4:5, 2:4, 1:2, 3:4) tem 24 elementos e são
armazenados assim:
A(4, 2, 1, 3), A(4, 2, 1, 4), A(4, 2, 2, 3), A(4, 2, 2, 4)
A(4, 3, 1, 3), A(4, 3, 1, 4), A(4, 3, 2, 3), A(4, 3, 2, 4)
...
...
...
...
A(5, 4, 1, 3), A(5, 4, 1, 4), A(5, 4, 2, 3), A(5, 4, 2, 4)
o último índice move mais rápido (LINGUAGEM
DE PROGRAMAÇÃO)
se A(4,2,1,3) ocupar posição 100 A(4,2,1,4) ocupa 101 e
A(5,4,2,4) ocupa 123
CAP-223
Representação de Arrays (cont.)
Dado A(1:u1) e p é a posição do primeiro elemento,
então A(i) ocupa p + i-1
Dado A(1:u1, 1:u2)
u2 elementos u2 elementos ... u2 elementos
|---------------------|--------------------| ... |--------------------|
linha 1
linha 2
linha u1
se p é a posição do A(1,1), então A(i, 1) = p + (i-1)u2
A(i, j) = p + (i-1)u2 + (j-1)
EXERCÍCIO: Ache a fórmula para n índices ou seja
A(i1, i2, ..., in)
CAP-223
Representação de Arrays (cont.)
Estrutura de Dados Implícitos
Relações entre elementos utilizam
fórmulas e declarações nos programas
Não Existe necessidade de espaço
extra para estas relações
CAP-223
Tipos Abstratos de Dados
(TAD)
Analogia entre DADOS e PROGRAMAS
Abstração Procedural
•Operações ou algoritmos isolados para
serem substituídos facilmente
•Outras partes do programa não conhecem o
conteúdo. Só como chamar e o que retorna.
CAP-223
TAD (cont.)
Linguagens modernas
ABSTRAÇÃO DE DADOS
ou
ENCAPSULAMENTO DE DADOS
Organização de dado é encapsulada para
possibilitar a modificação da estrutura de
dados sem ter que mudar todo o programa
CAP-223
TAD (cont.)
1) Domínio (de onde os dados são obtidos)
2) Conjunto de operações
Especificar um T.A.D.
• Identificar o domínio
• Operações
CAP-223
TAD (cont.)
Identificação de domínio é IMEDIATO
Definição de Operações
• Sintática (Procedure heading - nome, tipos
de cada operando)
• Semântica (anexa um significado para
a operação ou seja valores
a produzir e efeito sobre o
ambiente)
CAP-223
Pilhas
Pilha - lista ordenada
inserções e remoções realizadas
somente por um lado
D
C
B
A
 Topo
LIFO
CAP-223
Pilhas (cont.)
Utilização comum da estrutura da Pilha é nos
programas na chamada de subrotinas
Principal
...
Call Func1
e1: ...
End
e2
e1
q
Func1
...
Call Func2
e2: ...
Return
Func2
...
...
Return
Posições consecutivas?
CAP-223
Pilhas (cont.)
Operações associadas à Pilha
criar
incluir
remover
topo
isEmpty
- Cria uma Pilha P de n elementos
- Adicionar um novo elemento no Topo
- Deletar o elemento do Topo
- retorna o elemento do Topo
- função booleana
TRUE se Pilha vazia
FALSE caso contrário
CAP-223
Pilhas (cont.)
criar ( )
{
Pilha ( 1 : n )
Topo  0
}
incluir ( valor, Pilha P, n, Topo )
{
// valor a ser inserido no Topo da
// Pilha P que tem n é o tamanho
// da Pilha
if ( Topo  n ) pilha cheia
Topo++
P ( Topo )  valor
}
EXERCÍCIO: Implementar outras operações. Escolha o
tipo do valor
Utilize o ARRAY e não a alocação dinâmica
CAP-223
FILAS
Fila - lista ordenada
inserções numa ponta e remoções
na outra ponta
A
B

front
C
D
E

rear
FIFO
Exemplo: Jobs num computador
CAP-223
FILAS (cont.)
Operações associadas à Fila
criar
inserir
remover
isEmpty
first
- criar Fila Q de n elementos
- adicionar um elemento novo no
final da Fila
- retirar um elemento do início da Fila
- função booleana TRUE se
Fila é vazia
FALSE caso contrário
- retorna o elemento do início da Fila
CAP-223
FILAS (cont.)
Inserção é através do ponteiro rear
Remoção é através do ponteiro front
front aponta para uma posição a menos do elemento
do início da Fila (Para remover, tem que mover antes)
rear sempre aponta para o último elemento da
Fila - INSERÇÃO
front = rear = 0  Condição inicial
front = rear  Fila vazia
rear = n  Fila Cheia (??? - Correto?)
EXERCÍCIO: Implementar as operações da Fila e testar em exemplosCAP-223
FILAS (cont.)
A
Insere A
front = rear = 0
front = 0 rear = 1
A
B
Insere B
front = 0
rear = 2
B
Remove A
front = 1
rear = 2
CAP-223
FILAS (cont.)
Re-arranjar os elementos para que Q(1)
tenha o primeiro elemento e o ponteiro
front = 0 (senão sempre que rear é igual a
n será considerada FILA como cheia)
Uma alternativa é considerar uma Fila Circular
Para isso é mais conveniente declarar a Fila
como Q (0:n-1)
CAP-223
FILAS (cont.)
Fila Circular
Produtor / Consumidor
exemplo: Teclado / Editor
velocidades semelhantes
Por que?
Não há necessidade de um Buffer
ou
Overflow do Buffer
CAP-223
FILAS (cont.)
primeira célula é sucessor da última
front continuaria apontando para posição 0
a inserção começa na posição 1 movendo rear
a remoção começa movendo front antes de fazer
a operação
CAP-223
FILAS (cont.)
Utilização de um contador resolve
Programas concorrentes
sincronização de variáveis compartilhadas
front = rear  FILA VAZIA
(rear + 1) mod m = front  FILA CHEIA
CAP-223
FILAS (cont.)
0
1
2
f
r
0
1
A
f
r
2
0
1
A
2
B
r
f
Para inserir um outro elemento, r = (r + 1) mod 3 que é igual
a f. ENTÃO OVERFLOW
0
1
2
B
0
C
1
f
r
r
f
2
B
CAP-223
FILAS (cont.)
Priority Queue
remoção no início da Fila
inserção na posição certa
Dictionary (Table)
processa elementos de acordo com o valor
CAP-223
AVALIAÇÃO DE EXPRESSÕES
X  A / B ** C + D * E - A * C
operadores no meio de operandos
Notação INFIXA (Infix)
prioridade dos operadores: 6**, -unário, +unário, ¬
5 *, /
4 +, 3 , , =, , , 
2 AND
1 OR
CAP-223
AVALIAÇÃO DE EXPRESSÕES (cont.)
Operadores adjacentes da mesma prioridade
Como resolver?
A ** B ** C prioridade 6
A*B/C
-
outras prioridades -
da direita para
esquerda
da esquerda para
direita
Dada uma expressão (A / (B ** C)) + (D * E) - (A * C)
como é que é tratada por um compilador?
Notação POLONESA PÓS-FIXA (Postfix)
CAP-223
AVALIAÇÃO DE EXPRESSÕES (cont.)
Por exemplo uma expressão utilizando a notação
Infixa 3 * (4 + 5)
é escrita em notação polonesa
Pós-fixa como 3 4 5 + *
9
27
CAP-223