Listas Estáticas e suas Operações

Prévia do material em texto

Armazenagem de Dados
Listas Estática e Dinâmicas
 
Listas
● Estruturas de armazenagem de informações 
que utilizam uma estrutura formal para a 
manipulação dos dados
● As listas são divididas conforme a sua 
estrutura de manipulação:
– Listas Estáticas: possuem uma estrutura pré-
definida e com uma quantidade limitada de 
dados
– Listas Dinâmicas: possuem uma estrutura pré-
definida sem limitação de número de elementos
 
Listas Estáticas
● Estruturas de armazenagem com formato de 
manipulação de dados pré-definado e 
definição da quantidade máxima de 
elementos que poderão ser alocados nessa 
lista.
● As operações que abrangem as estruras de 
listas são:
– Inclusão (início, fim e qualquer posição)
– Exclusão (início, fim e qualquer posição)
– Pesquisa
 
Listas Estáticas - Estrutura
● Podemos criar estruturas de listas estáticas 
através da modelagem de seus dados em 
diversos formatos como:
– Registros
– Classes
– Banco de Dados
● Essa estrutura pode ser agrupada em:
– Fisicamente encadeada
– Lógicamente encadeada
 
Listas Estáticas - Inclusão
● A inclusão em listas estáticas fisicamente 
encadeada pode ser feita de 3 formas:
– Inclusão no início;
– Inclusão no fim e
– Inclusão em qualquer posição
● A forma mais simples de inclusão nessa 
estrutura de lista é a inclusão no fim.
 
Listas Estáticas - Inclusão
● Algoritmo inclusão no fim
subrotina inclui_fim
 inicio
 se(fim_lista == tam_lista)
 Escreva(“lista cheia”)
 senão inicio
 fim_lista = fim_lista+1
 lista[fim_lista] = elemento
 fim
 fim
 
Listas Estáticas – Inclusão no fim
fim_lista=2
0 421 3 5
A B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A B C D
 
Listas Estáticas - Inclusão
subrotina inclui_inicio
 inicio
 se(fim_lista == tam_lista)
 Escreva(“lista cheia”)
 senão inicio
 para(i=fim_lista; i>=0; i--)
 lista[i+1] = lista[i]
 lista[0] = elemento
 fim_lista = fim_lista+1
 fim
 fim
 
Listas Estáticas – Inclusão no fim
fim_lista=2
0 421 3 5
A B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A B C C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A B B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
A A B C
 
Listas Estáticas – Inclusão no fim
fim_lista=3
0 421 3 5
D A B C
 
Listas Estáticas - Inclusão
subrotina inclui_qq_posicao(pos:inteiro)
 inicio
 se(fim_lista == tam_lista)
 Escreva(“lista cheia”)
 senão inicio
 para(i=fim_lista; i>=pos; i--)
 lista[i+1] = lista[i]
 lista[pos] = elemento
 fim_lista = fim_lista+1
 fim
 fim
 
Listas Estáticas - Exclusão
subrotina exclui_inicio
 inicio
 se(fim_lista == -1)
 Escreva(“lista vazia”)
 senão inicio
 para(i=0; i<=fim_lista; i++)
 lista[i] = lista[i+1]
 fim_lista = fim_lista-1
 fim
 fim
 
Listas Estáticas – Exclusão início
fim_lista=3
0 421 3 5
A B C D
 
Listas Estáticas – Exclusão início
fim_lista=3
0 421 3 5
B B C D
 
Listas Estáticas – Exclusão início
fim_lista=3
0 421 3 5
B C C D
 
Listas Estáticas – Exclusão início
fim_lista=3
0 421 3 5
B C D D
 
Listas Estáticas – Exclusão início
fim_lista=2
0 421 3 5
B C D D
 
Listas Estáticas - Exclusão
subrotina exclui_fim
 inicio
 se(fim_lista == -1)
 Escreva(“lista vazia”)
 senão inicio
 fim_lista = fim_lista-1
 fim
 fim
 
Listas Estáticas – Exclusão no fim
fim_lista=3
0 421 3 5
A B C D
 
Listas Estáticas – Exclusão no fim
fim_lista=2
0 421 3 5
A B C D
 
Listas Estáticas - Exclusão
subrotina exclui_qq_pos(pos:inteiro)
 inicio
 se(fim_lista == -1)
 Escreva(“lista vazia”)
 senão inicio
 para(i=pos; i<=fim_lista; i++)
 lista[i] = lista[i+1]
 fim_lista = fim_lista-1
 fim
 fim
 
Listas Estáticas - Pesquisa
subrotina imprime
 inicio
 para(i=0; i<=fim_lista; i++)
 escreva(lista[i]);
 fim
 
Filas e Pilhas Estáticas Fisicamente 
Encadeadas
● São protocolos de manipulação de listas 
fisicamente encadeadas
● Essas regras servem para demonstrar o 
comportamento dessas estruturas
● Com isso temos as estruturas:
– Filas
– Pilhas
 
Fila Estática Fisicamente Encadeada
● A estrutura de fila segue o mesmo 
funcionamento das filas existentes no nosso 
cotidiano.
● O funcionamento é o mesmo: o elemento mais 
velho é o primeiro elemento que deve sair da 
fila e a inclusão de novos elementos devem 
ser feitas no final da fila.
● Sendo assim, a fila segue as seguintes regras:
– Inserção no fim
– Remoção no Início
 
Pilha Estática Fisicamente Encadeada
● A estrutura de pilha também obedece ao 
funcionamento das pilhas existentes no nosso 
cotidiano.
● O funcionamento é o mesmo: o elemento mais 
novo é o primeiro elemento que deve sair da 
pilha(fim da pilha) e a inclusão de novos 
elementos devem ser feitas no final da pilha 
também.
● Sendo assim, a fila segue as seguintes regras:
– Inserção no fim
– Remoção no fim
 
Listas Estáticas Logicamente 
Encadeadas
● Essas estruturas utilizam um marcador 
lógico que indica diretamente o próximo 
elemento da lista
● Esse marcador é que irá direcionar a ordem 
dos elementos dessa lista
 
Listas Estáticas Logicamente 
Encadeadas
● Exemplo de uma lista estática logicamente 
encadeada:
registro lele{
 texto elemento;
 int prox; };
lele lista[10];
int inicio=-1, fim=-1, tam=0;
 
Listas Est. Log. Enc. - Inclusão no Fim
● subrotina inserir_fim(texto tx, int pos)
 inicio
 se(tam == 10)
 Escreva(“lista cheia”)
 senão inicio
 se(fim= = -1)
 inicio = pos;
fim = pos;
lista[pos].elemento = tx;
lista[pos].prox = -1;
tam++;
senao
lista[pos].elemento = tx;
lista[pos].prox = -1;
lista[fim].prox = pos;
fim = pos;
tam++;
 
 
Listas Est. Log. Enc. - Inclusão em 
qualquer posição
● subrotina inserir_posicao(texto tx, int lugar, int novo)
 int tmp=-1, contador = 0;
 se(tam == 10)
 Escreva(“lista cheia”)
 senão inicio
 se(fim= = -1)
 inicio = novo;
fim = novo;
lista[novo].elemento = tx;
lista[novo].prox = -1;
tam++;
senao
enquanto (contador < lugar)
 tmp = lista[tmp].prox;
 contador ++;
lista[novo].elemento = tx;
lista[novo].prox = lista[tmp].prox;
lista[tmp].prox = novo;
tam++;
 
Listas Est. Log. Enc. - Inclusão no 
Início
● subrotina inserir_inicio(texto tx, int pos)
 inicio
 se(tam == 10)
 Escreva(“lista cheia”)
 senão inicio
 se(fim= = -1)
 inicio = pos;
fim = pos;
lista[pos].elemento = tx;
lista[pos].prox = -1;
tam++;
senao
lista[pos].elemento = tx;
lista[pos].prox = inicio;
inicio = pos;tam++;
 
 
Listas Est. Log. Enc. - Inclusão em 
qualquer posição
● subrotina inserir_qqposicao(texto tx, int lugar, int novo)
 int tmp=-1, contador = 0;
 se(tam == 10)
 Escreva(“lista cheia”)
 senão inicio
 se(fim= = -1)
 inicio = novo;
fim = novo;
lista[novo].elemento = tx;
lista[novo].prox = -1;
tam++;
senao
enquanto (contador < lugar)
 tmp = lista[tmp].prox;
 contador ++;
lista[novo].elemento = tx;
lista[novo].prox = lista[tmp].prox;
lista[tmp].prox = novo;
tam++;
 
Listas Est. Log. Enc. - Imprime todos 
elementos da lista
● subrotina imprimir()
 inicio
 se(tam == 10)
 Escreva(“lista cheia”)
 senão inicio
 se(fim= = -1)
 inicio = pos;
fim = pos;
lista[pos].elemento = tx;
lista[pos].prox = -1;
tam++;
senao
lista[pos].elemento = tx;
lista[pos].prox = inicio;
inicio = pos;
tam++;
 
 
Listas Est. Log. Enc. - Exclusão no 
Início
● subrotina exclusir_inicio()
 inicio
 se(tam == 0)
 Escreva(“lista vazia”)
 senão inicio
 inicio = lista[inicio].prox;
tam- -;
 
Listas Est. Log. Enc. - Exclusão no 
Fim
● subrotina excluir_fim()
int tmp = inicio; 
se(tam == 0)
 Escreva(“lista vazia”)
senão inicio
 enquanto(lista[tmp].prox != fim)
 tmp = lista[tmp].prox;
lista[tmp].prox = -1;
fim = tmp;
tam--;
 
 
Listas Est. Log. Enc. - Exclusão em 
qualquer posicao
● subrotina excluir_posicao(int pos)
int tmp = inicio; 
se(tam == 0)
 Escreva(“lista vazia”)
senão inicio
 enquanto(lista[tmp].prox != pos)
 tmp = lista[tmp].prox;
lista[tmp].prox = lista[pos].prox;
tam--;
 
 
Fila / Pilha Logicamente Encadeados
● Pilha
– Insere e remove no fim da lista logicamente encadeada
● Fila
– Insere no fim e remove no inicio da lista logicamente encadeada
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42