-
Estrutura de Dados
Prof Ms. Elizabeth Brito Llamosas Gomes
1
Tipos de Dados Aula 01
-
2
Referncias Bibliogrficas
DROZDEK, Adam. Estrutura de dados e algoritmos em C++. So Paulo:
Cengage learning, 2009.
MORAES, Celso R. Estruturas de dados e algoritmos. Uma abordagem
didtica. 2. ed. So Paulo: Futura, 2003.
Preiss, Bruno R. Estrutura de dados e algoritmos: Padres de
projetos orientado a objetos com Java. Rio de Janeiro: Elsevier,
2000.
-
3
Referncias Bibliogrficas
CELES, Waldemar; CERQUEIRA, Renato; RANGEL, Jos Lucas. Introduo
a Estruturas de Dados. Rio de Janeiro: Editora Campus, 2004.
TENENBAUM, A. M; LANGSAM, Y; AUGENSTEIN, A. J. Estrutura de
dados usando C. So Paulo: Makron Books, 1995.
-
4
Algoritmos e Estrutura de dados
A resoluo de problemas atravs de algoritmos requer a representao
de entidades e objetos reais em itens de dados.
-
5
Algoritmos e Estrutura de dados
As diferentes formas nas quais os itens de dados so logicamente
relacionados definem diferentes estruturas de dados.
-
6
Algoritmos e Estrutura de dados
Pode-se classificar as estruturas de dados como:
Primitivas diretamente manipuladas em linguagem de mquina;
No primitivas ou complexas estruturas de informao em conjuntos
(formada por estruturas de dados primitivas) logicamente
relacionados.
-
7
ESTRUTURA de DADOS
Vetor Matriz
Pilha
Fila
Lista
Grafo rvore
Lgico
Numrico
Caracter
Ponteiro
Inteiro
Real
-
8
Vetor
Matriz
Pilha
Fila
Lista
rvore
Grafo
-
9
Pode representar apenas dois valores: verdadeiro e falso;
Pode ser representado na codificao binria:
1 verdadeiro;
0 falso.
Tambm chamado de booleano.
DADO LGICO
-
10
Tipo Inteiro: nos positivos e negativos.
ex.: 35 0 -12
DADO NUMRICO
Tipo Real: nos positivos, negativos e fracionrios.
ex.: 9 -12 4.6 -89.726
-
11
Sequncia contendo letras, nmeros e smbolos especiais;
Deve ser indicado entre aspas ( ou );
Tambm chamado de alfanumrico, literal, string ou cadeia.
Ex.: Rua Alfa, 52
Fone: 211-3456
F
DADO CARACTER
-
12
uma varivel cujo contedo a localizao de outra varivel;
Permite acessar indiretamente os valores de outras variveis.
Um ponteiro anlogo a uma sinalizao de estrada que leva a um
certo local, ou a uma tira de papel na qual um endereo tenha sido
anotado.
PONTEIRO
-
13
PONTEIRO
Por exemplo, na declarao:
int i = 15, j, *p, *q;
i e j so variveis numricas do tipo inteiro e p e q so ponteiros
para variveis do tipo inteiro, onde o asterisco frente de p e q
indica sua funo.
-
p i 15
14
Sendo p = i ; // ou p = (int*) i ;
Assumindo que os endereos das variveis i, j, p e q sejam 1080,
1082, 1084 e 1086, depois de se atribuir 15 para i na declarao, as
posies e os valores nas variveis de memria do computador so:
1080 15 i 1082 ? j 1084 1080 p 1086 ? q
PONTEIRO
-
15
Vetor
Matriz
Pilha
Fila
Lista
rvore
Grafo
-
16
Conjunto finito e ordenado de elementos homogneos.
Um vetor contm:
Um nome ao qual est associado um tipo de dados;
Um ndice do tipo inteiro;
Dimenso do tipo inteiro.
representado atravs de um nome e de um ndice entre
colchetes.
Exemplo: int VNUM[8], I;
VETOR
-
17
VNUM[1] = 121 VNUM[6] = 3
I=4 VNUM[I] = 0 I=0 VNUM[I] = 34
O vetor VNUM[I] do tipo numrico (inteiro) com dimenso de 8
elementos.
O acesso aos elementos so efetuados atravs de um ndice, I.
0 1 2 3 4 5 6 7
34 121 7 78 0 90 3 15
I = 0..7 N = 8
VETOR
-
18
Vetor multidimensional, pode ser:
bidimensional, tridimensional ou n-dimensional.
Exemplo: int MAT [7] [6];
0 1 2 3 4 5
0 55 12 72 8 15 99
1 121 67 17 78 12 123
2 34 4 71 7 54 212
3 56 12 12 7 56 33
4 34 21 15 8 0 79
5 76 32 78 78 56 7
6 43 221 321 77 45 7
ndice das colunas J M = 6
ndice das linhas I
N = 7
MAT[1][2] = 17
MAT[6][0] = 43
I = 2 e J = 4
MAT[I][J] = 54
MATRIZ
-
Quando um elemento novo introduzido na pilha, passa a ser o
elemento do topo e o nico que pode ser removido da pilha.
Os elementos so retirados na ordem inversa ordem em que foram
introduzidos: ltimo que entra o primeiro que sai (LIFO Last In,
First Out). 19
Lista linear na qual todos os acessos so realizados em uma s
extremidade, denominada TOPO.
topo c
b
a
entra sai
PILHA
-
20
Suporta trs operaes bsicas:
push(P,X): insere o elemento X na pilha P;
pop(P): remove e retorna o elemento do topo;
top(P): retorna uma cpia do elemento do topo, sem remov-lo.
PILHA
uma estrutura dinmica: o nmero de elementos aumenta ou diminui
medida que elementos so empilhados e desempilhados.
-
21
A quantidade de memria alocada para representar seus elementos,
um fator limitante:
Overflow: resultado de uma tentativa invlida de empilhar;
Underflow: resultado de uma tentativa invlida de desempilhar ou
acessar.
Assim, precisa-se de mais trs operaes para manipular pilhas:
init(P): inicializa a pilha P no estado vazia;
empty(P): verifica se a pilha P est vazia;
full(P): verifica se a pilha P est cheia.
PILHA
-
22
O esquema de alocao sequencial de memria apropriado na
implementao de pilhas.
PILHA
Forma de representar uma pilha na memria:
Um vetor, armazena os elementos da pilha;
Um ndice, indica a posio corrente de topo da pilha.
2 a b c ...
0 1 2 3 4 ... 49
PILHA.TOPO indica a posio do ltimo elemento inserido
PILHA:
PILHA. ITEM armazena os elementos da pilha
-
23
Declarao:
#define STACKSIZE 50 // tamanho mximo da pilha struct STACK {
int TOPO; char ITEM[STACKSIZE]; // pode ser int, float, }; struct
STACK PILHA;
PILHA.ITEM armazena os elementos da pilha 2 a b c ...
0 1 2 3 4 ... 49
PILHA.TOPO indica a posio do ltimo elemento inserido
PILHA:
PILHA
-
sai entra
comeo final
24
Lista linear onde as inseres so realizadas em um extremo e as
remoes restritas ao outro.
A ordem de sada corresponde ordem de entrada dos elementos:
Primeiro que entra o primeiro que sai (FIFO - First In / First
Out).
Exemplo: Fila em um banco, onde as pessoas formam uma fila para
aguardar at serem atendidas.
Esse tipo de estrutura no suporta inseres, nem remoes no meio da
fila.
FILA
-
25
Uma fila (queue) suporta duas operaes bsicas:
enqueue (F,X) insere o elemento X no final da fila;
dequeue (F) remove e retorna o elemento existente no comeo da
fila F.
FILA
Para insero de um elemento na fila:
Verificar se h espao, com a funo qfull();
Para remover um elemento da fila:
Verificar se no est vazia, com a funo qempty().
-
26
Recursos bsicos para implementao sequencial de uma fila:
Espao de memria sequencial para armazenar os elementos, no caso,
um vetor;
Uma referncia ao primeiro elemento da fila;
Uma referncia primeira posio livre, aps o ltimo elemento da
fila.
FILA
FILA:
-
27
Declarao:
#define MAX 50 // tamanho mximo da fila struct QUEUE { int COM,
FIM; char ITEM[MAX]; // pode ser int, float, ... }; struct QUEUE
FILA;
FILA:
FILA
-
28
A implementao sequencial apresenta problemas de lgica e
desperdcio de memria:
medida que novos elementos vo sendo inseridos ou removidos os
ndices COMEO e FIM vo sendo incrementados;
Quando na fila no existir mais nenhum elemento, os ndices sero
iguais, ento:
Nenhum elemento poder ser inserido. A funo qfull() indicar que
no existe mais espao disponvel;
e remover tambm no possvel, a funo qempty() indicar fila
vazia.
FILA
-
29
Para eliminar o erro de lgica:
Acrescenta-se uma varivel contadora para indicar quantos
elementos esto armazenados na fila;
Quando um elemento for inserido ela ser incrementada, e quando
for removido ser decrementada.
FILA
FILA:
-
30
Para eliminar o desperdcio de espao:
Sempre que um elemento for removido, sua posio liberada para ser
ocupada por um novo elemento posteriormente.
Assim, quando COMEO ou FIM for igual ou maior que o tamanho
mximo declarado da fila, restabelece-se seu valor a 0, simulando
uma circularidade.
FILA
-
31
declarao:
#define MAX 50 // tamanho mximo da fila struct QUEUE { int TOT,
COM, FIM; char ITEM[MAX]; // pode ser int, float, ... }; struct
QUEUE FILA;
FILA:
FILA CIRCULAR
-
32
Possui um mecanismo de atualizao por ambas as extremidades.
Adota o conceito de fura fila: um elemento pode ser inserido no
incio de uma fila pr-existente e passa a ser o primeiro dela.
Ex.: inserir e retirar vages de um trem.
FILA DUPLA
-
33
Operaes Bsicas:
enqueueR(F,X): acrescenta o elemento X pela direita (final);
enqueueL(F,X): acrescenta o elemento X pela esquerda
(incio);
dequeueR(F): remove o elemento pela direita (posicionado no
final da fila);
dequeueL(F): remove o elemento pela esquerda (posicionado no
incio da fila).
FILA DUPLA
-
34
Coleo L: [a1, a2, ..., an], onde n>=0, cuja propriedade
estrutural baseia-se apenas na posio relativa dos elementos,
dispostos linearmente;
Sendo n=0, a lista vazia, seno so vlidas as propriedades:
a1, o primeiro elemento do L;
an o ltimo elemento de L;
ak, 1< k < n, precedido pelo elemento ak-1, e seguido por
ak+1 em L.
LISTA LINEAR
-
35
Exemplos:
Lista de compras de supermercado,
Lista de convidados para uma festa de aniversrio ou
casamento,
Lista de alunos matriculados em um curso,
Lista de telefones,
etc.
LISTA LINEAR
-
36
Propriedades que podem ser realizadas sobre as listas:
Acessar um elemento qualquer; Inserir um elemento numa posio
especfica; Remover um elemento de uma posio
especfica; Procurar um determinado elemento; Determinar o total
de elementos; Ordenar os elementos; Combinar duas listas em uma
nica; Particionar uma lista em duas; Obter cpias de uma lista;
Apagar uma lista, etc.
LISTA LINEAR
-
37
Formas utilizadas para agrupar e acessar uma lista linear:
Sequencial e Encadeada (Dinmica)
Sequencial:
Os elementos so colocados em clulas de memria consecutivas, uma
aps a outra.
Assim, se o elemento a1 encontra-se na
clula de endereo e utiliza k bytes, temos:
LISTA LINEAR
-
38
Sequencial:
Vantagem: facilidade para calcular o endereo de memria de um
elemento de um ndice qualquer:
Endereo(ai) = +(i1)k;
Desvantagem: insero ou remoo de elementos no meio da lista, j
que ser preciso movimentar os elementos para liberar ou diminuir o
espao entre eles.
LISTA LINEAR
-
39
Encadeada (Dinmica):
Elementos podem ocupar quaisquer clulas;
Junto a cada elemento armazenado o endereo do prximo elemento da
lista;
Os elementos so armazenados em blocos de memria denominados ns.
Cada n possui dois campos: um para armazenar os dados e outro para
o prximo endereo;
So importantes dois endereos: o do primeiro elemento e o do
endereo fictcio para o qual aponta o ltimo elemento da lista;
LISTA LINEAR
-
Lista Linear Encadeada
40
Contedo Endereo
L=3FFA a1 1C34 Primeiro elemento, acessvel a partir de L
1C34 a2 BD2F O segundo elemento no ocupa um endereo consecutivo
quele ocupado por a1
BD2F a3 AC12 ...
1000 ai 3A7B Cada nodo armazena um elemento e o endereo do
prximo elemento da lista
...
5670 an2 14F6
14F6 an1 5D4A
5D4A an ltimo elemento da lista, o endereo nulo indica que o
elemento an no tem um sucessor
-
41
Encadeada (Dinmica):
Vantagem: facilidade para inserir ou remover um elemento de
qualquer ponto da lista linear. Por exemplo, para remover o
elemento a2 da lista, basta mudar o nodo no endereo 3FFA de
(a1,1C34) para de (a1, BD2F).
Desvantagem: Como apenas o primeiro elemento acessvel
diretamente atravs do endereo L, para acessar um elemento qualquer
dentro da lista, deve-se acessar o primeiro elemento e ir seguindo
os campos de ligao, um a um, at atingir a posio desejada.
LISTA LINEAR
-
42
uma estrutura de dados dinmica, isto , fisicamente seus
elementos esto armazenados em endereos aleatrios.
Cada elemento composto por nodos e cada nodo contm dois
campos:
o primeiro contm a informao em si;
o segundo que contm o endereo do nodo seguinte, portanto, um
ponteiro.
LISTA ENCADEADA
-
43
declarao:
#define NULL 0
struct NODE { int INFO; // pode ser char, float, etc. struct
NODE *NEXT; };
typedef struct NODE *NODEPTR;
NODEPTR P, BEGIN;
BEGIN = NULL; // Inicializando uma lista encadeada
P = (NODEPTR) malloc(sizeof(struct NODE)); /* Aloca espao de
memria para armazenar um nodo da lista encadeada */
LISTA ENCADEADA
-
44
composta por nodos e cada nodo contm trs campos:
Um para a informao em si (info); Dois ponteiros:
Um contm o endereo do nodo que o precede (left); O outro contm o
endereo do nodo que o sucede (right).
Left Info right Left Info right Left Info right
Begin 3 6 10
null null
Lista Duplamente Encadeada
-
45
Consiste de ns e de arcos.
representada de cima para baixo (raiz no topo e folhas na base).
A raiz no tem ancestrais, ela s pode ter ns filhos.
As folhas no tm filhos, ou seja, seus filhos so estruturas
vazias.
Cada n atingvel a partir da raiz atravs de uma sequncia de
arcos, chamado caminho.
RVORE
-
46
Uma rvore pode ser definida recursivamente como:
Uma estrutura vazia uma rvore vazia;
Se t1,...,tk, so rvores disjuntas, ento a estrutura cuja raiz
tem como suas filhas as razes de t1,...,tk tambm uma rvore;
Somente estruturas geradas pelas regras 1 e 2 so rvores.
RVORE
-
47
Uma rvore binria um caso especial de rvore cujos ns no tem grau
superior a 2, ou seja, nenhum n tem mais do que dois filhos.
Cada filho designado como filho esquerda ou filho direita.
Cada rvore caracteriza uma definio recursiva.
RVORE BINRIA
-
48
/* Declarando uma rvore Binria */
#define NULL 0
struct TREE
{
struct TREE *LEFT;
int INFO; // pode ser char, float, etc.
struct TREE *RIGHT;
};
typedef struct TREE *TREEPTR;
TREEPTR P;
RVORE BINRIA
-
49
So modelos naturais usados para representar relacionamentos
arbitrrios entre dados e objetos.
Muito utilizado para a soluo de problemas relacionados rea de
computao.
Ex.: Determinao da rota de uma mensagem em uma rede de
computadores.
Ex.: Soluo de problemas no planejamento de rotas de um companhia
de aviao entre vrios aeroportos.
GRAFOS
-
50
So aplicados:
Modelagem de circuitos digitais;
Representao de lista ligada;
rvore de deciso;
Diagrama Entidade Relacionamento;
Diagrama de Fluxo;
Representao de processos em sistema paralelo;
Mquina de estado finito;
Etc.
GRAFOS
-
51
um par ordenado G = (V, E), com as seguintes propriedades:
O componente V um conjunto finito no-vazio. Seus elementos so
chamados de vrtices ou ns de G;
O componente E um conjunto finito de pares ordenados de V
vrtices. Seus elementos so chamados de arestas ou arcos de G.
G1=(V1E1)
Composto de 4 vrtices e 6 arestas:
V1 = {a, b, c, d}
E1 {(a,b), (a,c), (b,c), (c,a), (c,d), (d,d)}
GRAFO DIRECIONADO ou DGRAFO
-
52
Os ns esto conectados por arcos no-direcionados.
As duas extremidades da aresta so equivalentes, no existe origem
e destino.
G2=(V2E2)
Composto de 4 vrtices e 4 arestas:
V2 = {a, b, c, d}
E2 {(a,b), (a,c), (b,c), (c,d)}
GRAFO NO-DIRECIONADO
-
53
Possui informaes nas arestas ou nos ns do grafo.
Ex.: pode-se utilizar um grafo direcionado com rtulos nos
vrtices, para representar uma mquina de estado finito:
GRAFO ROTULADO
Cada vrtice corresponde a um estado da mquina;
Cada aresta corresponde a uma transio de estado possvel;
Pode-se rotular cada vrtice com o registro de alguma propriedade
do estado correspondente como o tempo de latncia do estado.
-
54
Ex.: Pode-se usar um grafo no-direcionado com arestas rotuladas
para representar informaes geogrficas:
Os vrtices representam locais geogrficos;
As arestas representam as rotas possveis entre as
localidades.
GRAFO ROTULADO
Pode-se usar um rtulo para cada aresta representando a distncia
entre os dois locais.
