Estruturas de Dados - Lista, Pilha e Fila (Guilherme)

Prévia do material em texto

Estruturas de Dados
Lista, Pilha & Fila
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/33
Estruturas de Dados Lineares
Lista
- Conjunto ordenado de EDs onde inclusa˜o, exclusa˜o ou consulta dos
elementos da lista podem acontecer de forma aleato´ria
- Aberta - o u´ltimo no´ aponta para nada
- Fechada - o u´ltimo no´ aponta para o primeiro
- Simplesmente Encadeada
- Refereˆncia para a pro´xima ED
- Duplamente Encadeada
- Refereˆncia para a pro´xima ED
- Refereˆncia para a ED anterior
- Vantagem: tamanho varia´vel
- Desvantagem: acesso sequencial
gnramos (CIC/UnB) 116319 - Estruturas de Dados 2/33
Estruturas de Dados Lineares
Lista
Exemplos:
Aberta Fechada
Simples lista telefoˆnica escalonamento Round-Robin
Dupla histo´rico do navegador cantos de um pol´ıgono
gnramos (CIC/UnB) 116319 - Estruturas de Dados 3/33
Estruturas de Dados Lineares
Lista
Tipo abstrato → definido pelas operac¸o˜es.
- criar uma lista vazia
- inserir um item novo (em qualquer posic¸a˜o)
- remover um item
- localizar um item
- copiar a lista
- combinar duas ou mais listas
- dividir uma lista em duas ou mais listas
- etc.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 4/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Lista
typedef struct slist t {
slist node t ∗ first ;
// int num elementos; /∗ contador de elementos ∗/
} slist t ;
Criar novo elemento
slist node t ∗ slist new node (data t data, slist node t ∗next){
slist node t ∗node = ( slist node t ∗) malloc(sizeof( slist node t )) ;
if (node) {
node−>data = data;
node−>next = next;
}
return node;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 5/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Criar nova lista
slist t ∗ slist new (data t ∗data){
slist t ∗ lista = ( slist t ∗)malloc(sizeof( slist t )) ;
if ( lista )
lista −>first = (data ? slist new node(∗data, NULL) : NULL);
return lista ;
}
Obter o u´ltimo elemento
slist node t ∗ slist last ( slist t ∗ lista ) {
slist node t ∗ last = lista−>first;
while ( last && last−>next) last = last−>next;
return last ;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 6/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Inserc¸a˜o
void slist insert ( slist t ∗ lista , data t data, int posicao) {
slist node t ∗aux = lista−>first;
if (!aux || posicao == 0) { // primeiro da lista
lista −>first = slist new node(data, aux);
} else { // posicao arbitraria
int i = 1;
while ( i < posicao && aux−>next) {
aux = aux−>next;
++i;
}
aux−>next = slist new node(data, aux−>next);
}
}
caso especial
gnramos (CIC/UnB) 116319 - Estruturas de Dados 7/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Remoc¸a˜o
slist node t ∗ slist remove ( slist t ∗ lista , int posicao) {
slist node t ∗aux = lista−>first;
if (posicao == 0) { // primeiro da lista
lista −>first = aux−>next;
return aux;
} else { // posicao arbitraria
int i = 1;
while ( i < posicao && aux−>next) {
aux = aux−>next;
++i;
}
if ( i > posicao) return NULL;
slist node t ∗aux2 = aux−>next;
aux−>next = (aux2 ? aux2−>next : NULL);
return aux2;
}
}
caso especial
gnramos (CIC/UnB) 116319 - Estruturas de Dados 8/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Limpar lista
void slist empty ( slist t ∗ lista ) {
slist node t ∗aux;
while ( lista −>first)
aux = slist remove( lista , 0);
free(aux);
}
Pesquisa
slist node t ∗ slist find ( slist t ∗ lista , data t data) {
slist node t ∗aux = lista−>first;
while (aux && !data compare(data, aux−>data))
aux = aux−>next;
return aux;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 9/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Copiar lista
slist t ∗ slist copy ( slist t ∗ lista ) {
slist t ∗copy = slist new(NULL);
slist node t ∗aux = lista−>first;
while (aux) {
slist insert (copy, aux−>item, INT MAX);
aux = aux−>next;
}
return copy;
}
Eficiente?
gnramos (CIC/UnB) 116319 - Estruturas de Dados 10/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Combinar listas
void slist append ( slist t ∗ list1 , slist t ∗ list2 ) {
slist node t ∗ last = slist last ( list1 ) ;
if (! last )
list1 −>first = list2−>first;
else
last−>next = list2−>first;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 11/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
Aplicac¸a˜o: Soma de inteiros (super) longos
O hardware da maioria dos computadores so´ permite inteiros de um
tamanho ma´ximo espec´ıfico. Como representar inteiros positivos de
tamanhos arbitrariamente grandes?
Usando uma lista para armazenar pedac¸os valor: cada no´ armazena
alguns d´ıgitos do nu´mero. Por exemplo, o nu´mero 1234 5678 9012 3456,
seria armazenado como:
3456 9012 5678 1234
gnramos (CIC/UnB) 116319 - Estruturas de Dados 12/33
Estruturas de Dados Lineares
Lista Aberta Simplesmente Encadeada
E como escrever uma func¸a˜o que retorne a soma de dois nu´meros inteiros
deste tipo?
3456 9012 5678 1234
9999 0044 7998 1030
3455 9057 3676 2265
gnramos (CIC/UnB) 116319 - Estruturas de Dados 13/33
Estruturas de Dados Lineares
Lista Aberta Duplamente Encadeada
Elemento da lista
typedef struct dlist data t {
data t item;
struct dlist data t ∗next, ∗previous ;
} dlist data t ;
Novo elemento
dlist data t ∗dlist new item (data t item, dlist data t ∗next, dlist data t
∗previous) {
dlist data t ∗data = ( dlist data t ∗) malloc(sizeof( dlist data t )) ;
if ( dlist item ) {
dlist item −>item = item;
dlist item −>next = next;
dlist item −>previous = previous;
}
return data;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 14/33
Estruturas de Dados Lineares
Lista Aberta Duplamente Encadeada
Inserc¸a˜o
void dlist insert ( dlist t ∗ lista , data t item, int posicao) {
dlist data t ∗ item before = lista−>first;
if (! item before || posicao == 0) { // primeiro da lista
lista −>first = dlist new item(item, lista−>first, NULL);
if ( item before ) item before−>previous = lista−>first;
} else { // posicao arbitraria
int i = 1;
while ( i < posicao && item before−>next) {
item before = item before−>next;
++i;
}
dlist data t ∗ item after = item before−>next;
item before−>next = dlist new item(item, item after, item before ) ;
if ( item after ) item after−>previous = item before−>next;
}
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 15/33
Estruturas de Dados Lineares
Lista Aberta Duplamente Encadeada
Remoc¸a˜o
dlist data t ∗dlist remove ( dlist t ∗ lista , int posicao) {
dlist data t ∗aux = lista−>first;
if (posicao == 0) { // primeiro da lista
lista −>first = aux−>next;
if ( lista −>first) lista −>first−>previous = NULL;
return aux;
} else { // posicao arbitraria
int i = 1;
while ( i < posicao && aux−>next) {
aux = aux−>next; ++i;
}
dlist data t ∗aux2 = aux−>next;
aux−>next = aux2−>next;
if (aux2−>next) aux2−>next−>previous = aux;
return aux2;
}
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 16/33
Estruturas de Dados Lineares
Pilha
- Lista LIFO (Last In, First Out)
- Os elementos sa˜o colocados na pilha e retirados (ou processados)
em ordem inversa a de chegada
- Inserc¸a˜o apenas no topo da pilha
- Remoc¸a˜o apenas do topo da pilha
gnramos (CIC/UnB) 116319 - Estruturas de Dados 17/33
Estruturas de Dados Lineares
Pilha
Operac¸o˜es poss´ıveis:
- limpar a pilha
- verificar se a pilha esta´ vazia
- colocar elemento no topo da pilha
- retirar o elemento no topo da pilha
- etc.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 18/33
Estruturas de Dados Lineares
Pilha
Criar elementostack node t ∗stack new node(data t item, stack node t ∗next){
stack node t ∗stack item = (stack node t ∗) malloc(sizeof(stack node t));
if (stack item) {
stack item−>item = item;
stack item−>next = next;
}
return stack item ;
}
Criar pilha
stack t ∗stack new(data t ∗item) {
stack t ∗pilha = (stack t ∗)malloc(sizeof(stack t)) ;
if (item) push(pilha , ∗item);
else pilha−>first = NULL;
return pilha ;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 19/33
Estruturas de Dados Lineares
Pilha
Inserir
void push(stack t ∗pilha , data t item) {
pilha−>first = stack new node(item, pilha−>first);
}
Remover
stack node t ∗pop(stack t ∗pilha) {
stack node t ∗aux = pilha−>first;
pilha−>first = aux−>next;
return aux;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 20/33
Estruturas de Dados Lineares
Pilha
Esvaziar pilha
void stack empty(stack t ∗pilha ) {
while ( pilha−>first)
free(pop(pilha)) ;
pilha−>first = NULL;
}
Verificar se esta´ vazia
int stack is empty (stack t ∗pilha ) {
return ( pilha−>first == NULL);
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 21/33
Estruturas de Dados Lineares
Pilha
E´ ideal para processamento de estruturas aninhadas de profundidade
imprevis´ıvel.
Uma pilha conte´m uma sequeˆncia de obrigac¸o˜es adiadas. A ordem de
remoc¸a˜o garante que as estruturas mais internas sera˜o processadas antes
das mais externas.
- Quando e´ necessa´rio caminhar em um conjunto de dados e guardar
uma lista de coisas a fazer posteriormente.
- O controle de sequeˆncias de chamadas de subprogramas.
- A sintaxe de expresso˜es aritme´ticas.
As pilhas ocorrem em estruturas de natureza recursiva (como a´rvores) e
sa˜o utilizadas para implementar a recursividade.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 22/33
Estruturas de Dados Lineares
Pilha - Aplicac¸a˜o
Controle de delimitadores em uma equac¸a˜o (rastrear o escopo).
{(A+ B) ∗ C + (D + E )/[F + G ] + H}/I
1 se um inicializador de escopo for encontrado, ele e´ empilhado
2 se um finalizador de descopo for encontrado, a pilha e´ verificada
- se estiver vazia → equac¸a˜o incorreta
- se na˜o, desempilhar e comparar ao finalizador
Ao final, a pilha deve estar vazia.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 23/33
Estruturas de Dados Lineares
Pilha
Aplicac¸o˜es de Pilhas: recursividade
- a soluc¸a˜o de um problema depende da soluc¸a˜o de instaˆncias menores
do mesmo problema
- um programa de computador finito para processar algo
potencialmente infinito
Fatorial iterativo
int factorial ( int n) {
int fact = 1;
while(n > 1) {
fact ∗= n;
n −= 1;
}
return fact ;
}
Fatorial recursivo
int factorial ( int n) {
if (n<=1)
return 1;
else
return n∗ factorial (n−1);
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 24/33
Estruturas de Dados Lineares
Pilha
Quanto e´ 4! ?
factorial(4) → 4*factorial(3)
factorial(3) → 3*factorial(2)
factorial(2) → 2*factorial(1)
factorial(1) → 1 1
2*1 = 2
3*2 = 6
4*6 = 24
gnramos (CIC/UnB) 116319 - Estruturas de Dados 25/33
Estruturas de Dados Lineares
Fila
Em certas aplicac¸o˜es, tornam-se u´teis estruturas de dados constitu´ıdas
por conjuntos de elementos organizados, na˜o pelos valores dos dados,
mas em func¸a˜o de uma determinado crite´rio que regulamenta a entrada e
a sa´ıda dos dados na estrutura.
- atendimento ao cliente
- processamento de tarefa
- etc.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 26/33
Estruturas de Dados Lineares
Fila
- Lista FIFO (First In, First Out)
- Os elementos sa˜o colocados na fila e retirados (ou processados) por
ordem de chegada
- Inserc¸a˜o apenas no final da fila
- Remoc¸a˜o apenas do in´ıcio da fila
gnramos (CIC/UnB) 116319 - Estruturas de Dados 27/33
Estruturas de Dados Lineares
Fila
Uma fila permite va´rias operac¸o˜es
- criar uma fila vazia
- inserir um item novo (ao final)
- remover um item (do in´ıcio)
- esvaziar a fila
- etc.
gnramos (CIC/UnB) 116319 - Estruturas de Dados 28/33
Estruturas de Dados Lineares
Fila
Elemento de fila
typedef struct queue item t {
item t item;
struct queue item t ∗next;
} queue item t;
Fila
typedef struct queue t {
queue item t ∗ first , ∗ last ;
/∗ int num items; ∗/
} queue t;
gnramos (CIC/UnB) 116319 - Estruturas de Dados 29/33
Estruturas de Dados Lineares
Fila
Criar fila
queue t ∗queue new(item t ∗item) {
queue t ∗fila = (queue t ∗)malloc(sizeof(queue t));
if ( fila ) {
if (item) enqueue( fila , ∗item);
else ( fila −>first = fila−>last = NULL);
}
return fila ;
}
Esvaziar fila
void queue empty(queue t ∗fila) {
while ( fila −>first)
free(dequeue( fila )) ;
fila −>last = NULL;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 30/33
Estruturas de Dados Lineares
Fila
Inserir
void enqueue(queue t ∗fila , item t item) {
if (! fila −>last) { // fila vazia
fila −>first = queue new item(item, NULL);
fila −>last = fila−>first;
} else { // ao final
fila −>last−>next = queue new item(item, NULL);
fila −>last = fila−>last−>next;
}
}
Remover
queue item t ∗dequeue(queue t ∗fila) {
queue item t ∗aux = fila−>first;
fila −>first = aux−>next;
return aux;
}
gnramos (CIC/UnB) 116319 - Estruturas de Dados 31/33
Estruturas de Dados Lineares
Fila Aplicac¸o˜es
As filas sa˜o utilizadas quando desejamos processar itens de acordo com a
ordem de chegada (o primeiro a chegar sera´ o primeiro a ser processado.
Sistemas operacionais, por exemplo, usam filas para regular a ordem em
que as tarefas devem receber processamento e recursos devem ser
alocados a processos.
- fila de prioridade (inserc¸a˜o ordenada)
gnramos (CIC/UnB) 116319 - Estruturas de Dados 32/33
Estruturas de Dados Lineares
Exerc´ıcios
- Soma de inteiros (super) longos (ex5)
- Controle de delimitadores em uma equac¸a˜o (ex6)
- Implementac¸a˜o de uma fila de prioridade descendente (ex7)
- Manipulac¸a˜o de uma sequeˆncia de caracteres (ex8)
gnramos (CIC/UnB) 116319 - Estruturas de Dados 33/33
	Estruturas de Dados Lineares
	Lista