Estrutura de dados II

Prévia do material em texto

Estrutura de Dados 
Listas Lineares
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms Amilton Souza Martha
Revisão Textual:
Profa. Esp.Vera Lídia de Sá Cicarone
5
• Introdução
• Pilhas
• Controle de Chamadas e Retornos de Rotinas
 
 Atenção Atenção
Para um bom aproveitamento do curso, leia o material teórico atentamente antes de realizar as 
atividades. É importante também respeitar os prazos estabelecidos no cronograma.
 · Nesta unidade, vamos trabalhar com estruturas de dados 
lineares e implementá-las utilizando alocação dinâmica 
encadeada baseada em listas ligadas.
 · Os programas já estão prontos no material, mas é muito 
importante que o aluno escreva os códigos e faça vários 
testes. Não basta apenas entender os códigos; mas é preciso 
saber utilizá-los.
Listas Lineares
• Avaliação de Expressões
• Filas
6
Unidade: Listas Lineares
Contextualização
Muitos problemas computacionais possuem soluções algorítmicas semelhantes. Por exemplo, 
um spool de impressão, atendimentos de um caixa de banco ou a lista de e-mails pendentes em 
uma caixa de saída são problemas em que a ordem de entrada dos elementos é a mesma ordem 
de saída, ou seja, uma aplicação típica de FILA.
Assim também abrir menus e submenus, criar uma pilha de produtos em um supermercado 
ou simular uma torre de Hanói são algoritmos em que a ordem de entrada é o contrário da 
ordem de saída, ou seja, aplicação típica de PILHA.
Portanto, faz-se necessário entender como essas estruturas funcionam, como usar a 
implementação dos algoritmos para servir como ferramenta na hora em que um problema 
exigir uma solução semelhante.
Não só entender a parte teórica, mas também saber implementar, utilizando um Tipo Abstrato 
de Dados, em uma linguagem POO, como Java, e um tipo de alocação de memória estudado 
é fundamental para poder usar o conteúdo aprendido.
7
Introdução
Uma lista linear é um tipo abstrato de dado (TAD) que representa uma coleção L:[a1,a2,...,an], 
n>=0 cuja propriedade estrutural baseia-se apenas na posição relativa dos elementos, que são 
dispostos linearmente. Se n=0, dizemos que a lista L é vazia; caso contrário, são válidas as 
seguintes propriedades:
 » a1 é o primeiro elemento da lista L;
 » an é o último elemento da lista L;
 » ak, 1<k<n, é precedido pelo elemento ak-1 e seguido por ak+1 na lista L.
Ou seja, a característica fundamental de uma lista linear é o sentido de ordem unidimensional 
dos elementos que a compõem; uma ordem que nos permite dizer com precisão onde a coleção 
inicia e onde termina, sem possibilidade de dúvida. Temos alguns casos especiais de Listas 
Lineares que são frequentemente utilizadas na modelagem de problemas a serem resolvidos 
computacionalmente. Elas são: Pilhas, Filas e Listas Ordenadas.
Para podermos implementar as listas lineares, devemos avaliar como armazenaremos os 
elementos da lista na memória do computador. A alocação de memória, do ponto de vista do 
programador, pode ser classificada em duas categorias. A primeira refere-se à quantidade de 
memória usada para armazenar os dados na estrutura; nesse caso a alocação pode ser Estática 
ou Dinâmica. A segunda refere-se à forma como os elementos estão alocados em relação ao 
seu sucessor; aqui, a alocação pode ser Sequencial ou Encadeada.
Dizemos que a alocação é estática quando, durante toda a execução, a quantidade de 
memória utilizada pelo programa não varia, ou seja, a área de memória alocada já foi prevista no 
código do programa. Por outro lado, se o programa for capaz de criar novas variáveis enquanto 
executa, isto é, se áreas de memória que não foram declaradas no programa passarem a existir 
durante a sua execução, então, dizemos que a alocação é dinâmica. 
Uma vantagem da alocação estática é que a maioria das linguagens de programação possui 
esse recurso embutido na criação de arrays. Veja, a seguir, como criar um vetor de inteiros com 
tamanho fixo de 50 posições em Java:
• int[] x = new int[50];
Note que o vetor vai ocupar 50 posições de memória, mesmo que não seja preenchido totalmente, 
o que é uma desvantagem da alocação estática, pois podemos ter superdimensionamento ou 
subdimensionamento da estrutura. Já, na alocação dinâmica, podemos solicitar mais memória 
à medida que ela for necessária durante a execução do programa ou devolvê-la quando não for 
mais necessária, porém requer implementação.
A alocação sequencial consiste em dispor os elementos de uma lista em células de memória 
consecutivas, uma após a outra. Assim, se um elemento está na posição de memória “&” e 
cada elemento possui o mesmo tipo e ocupa “k” bytes, o elemento posterior da lista estará na 
posição (&+k) e o anterior em (&-k). Essa é uma grande vantagem da alocação sequencial, 
pois, dado o endereço inicial & e o índice i de um elemento qualquer da lista, podemos acessá-
lo imediatamente, com um simples cálculo. O ponto fraco deste tipo de alocação aparece 
8
Unidade: Listas Lineares
quando precisamos inserir ou excluir elementos no meio de uma lista, o que torna o processo 
mais complicado, pois devemos mover os elementos de modo a abrir um espaço para inserção 
ou ocupar um espaço de um elemento excluído. Na Figura 1, podemos ver um exemplo de 
alocação sequencial. Note que os elementos estão fisicamente na sequência.
Figura 1 – Alocação Sequencial de Memória
 Porém, na alocação encadeada, os elementos não precisam, necessariamente, ocupar 
posições consecutivas de memória, ou seja, podem ocupar quaisquer células. Contudo, para 
conseguir manter uma ordem, cada elemento da lista carrega consigo a posição de memória 
do próximo elemento da lista. A grande vantagem na alocação encadeada é a facilidade 
de inserção e remoção de elementos, pois não precisamos movimentar os dados, somente 
precisamos atualizar o campo de ligação do elemento antecessor àquele que será inserido ou 
removido. A desvantagem surge quando desejamos acessar uma posição específica da lista, já 
que conhecemos inicialmente somente o endereço do primeiro elemento e precisamos varrer a 
lista até encontrar o elemento desejado. É claro que, para listas muito extensas, esta operação 
pode ser bastante desvantajosa em relação ao tempo. 
Veja, na Figura 2, que cada elemento aponta para o próximo elemento, compondo uma lista 
encadeada ou, também chamada, lista ligada.
Figura 2 – Alocação Encadeada de Memória
 Em teoria, podemos combinar os 2 tipos de locação de memória tendo as seguintes combinações:
 » Alocação Estática Sequencial
 » Alocação Estática Encadeada
 » Alocação Dinâmica Sequencial
 » Alocação Dinâmica Encadeada
Porém, na prática, a alocação Estática Sequencial é muito utilizada, baseando-se em Tipos 
Estruturados como vetores, já que são pré-alocados e disponíveis na maioria das linguagens. A 
alocação Estática Encadeada é inviável, já que tem a desvantagem do desperdício de memória 
e tempo de busca. A alocação Dinâmica Sequencial não é possível, já que devemos solicitar 
memória dinamicamente e não garantimos a sequência de memória disponível, e a alocação 
Dinâmica Encadeada é o melhor modelo para implementação.
9
Pilhas
 A Pilha é um tipo especial de lista linear em que todas as inserções e remoções são feitas em 
uma mesma extremidade denominada topo. Então, temos acesso somente ao topo da pilha, ou 
seja, quando queremos inserir um elemento na pilha, colocamos no topo e, se quisermos excluir 
um elemento da pilha, só podemos excluir aquele que está no topo.
Esses tipos de listas em que a inserção e remoção são feitas por uma única extremidade são 
conhecidas como listas LIFO (Last-In/First-Out) - último elemento que entra é o primeiro que sai.
Uma Pilha possui três operações básicas:
 » TOP: acessa o elemento posicionado no topo da pilha e retorna;
 » PUSH: insere um novo elemento no topo da pilha;
 » POP: remove um elemento do topo da pilha e retorna;
Veja na Tabela 1, a seguir, um exemplo de manipulação de Pilhas
Tabela 1 – Exemplo de Manipulação de Pilha
--------P:[ ] Inicialmente a Pilha está Vazia.
push(a) P:[a] Insere o elemento a na Pilha P.
push(b) P:[a, b] Insere o elemento b na Pilha P. Note que, agora, o topo é b.
push(c) P:[a, b, c] Insere o elemento c na Pilha P. Agora o topo contém c.
pop() P:[a,b] Remove o elemento do topo e retorna o conteúdo. No caso c.
push(d) P:[a, b, d] Insere o elemento d no topo..
top() P:[a, b, d] Não altera a Pilha, apenas retorna o valor do topo da Pilha (d).
push(top()) P:[a, b, d, d] Insere no topo mais uma cópia do topo.
push(pop()) P:[a, b, d, d] Insere no topo o que foi excluído do topo (fica do mesmo jeito).
Para a implementação de uma Pilha, podemos escolher dois modelos de alocação de 
memória: a Estática-Sequencial ou a Dinâmica-Encadeada.
Vamos começar mostrando uma implementação mais simples com alocação Estática-
Sequencial usando a linguagem Java, porém o conceito pode ser utilizado em qualquer outra 
linguagem de programação.
10
Unidade: Listas Lineares
Figura 3 – Trecho de uma Pilha Estática Sequencial
 Na Figura 3, podemos ver um trecho de implementação de uma Pilha Estática Sequencial. 
Podemos notar que os elementos da pilha serão armazenados em um vetor de Objects com 
tamanho fixo de 30 posições. 
Um problema encontrado nas Pilhas Estáticas é a limitação da inserção de elementos na Pilha, 
pois ela estava limitada pelo tamanho do vetor declarado. A Pilha dinâmica faz uma requisição à 
heap (área de memória disponível no sistema) toda vez que um novo elemento precisa ser inserido 
na Pilha assim como desaloca a memória usada por um elemento que foi excluído dela. Com isso, 
usamos somente a quantidade de memória exata de que o programa necessita. 
Portanto, vamos implementar apenas uma Pilha Dinâmica Encadeada e, para isso, vamos 
imaginar que cada elemento da Pilha será um nó, em que teremos acesso somente ao topo 
(estrutura LIFO). Cada elemento deverá conter o endereço do próximo elemento da Pilha. 
Chamamos de Lista Simplesmente Encadeada, pois o elemento só conhece o endereço do 
seu próximo e não do seu anterior. Se fosse necessário armazenar também o endereço do nó 
anterior, teríamos uma Lista Duplamente Encadeada.
Veja, na Figura 4, a seguir, a implementação de um tipo abstrato para o nó de uma lista 
simplesmente encadeada, que servirá para nossa Pilha Dinâmica. Veja que, além do dado que 
será armazenado, temos um campo para guardar a referência do próximo nó (prox).
Figura 4 – Nó de uma Lista Simplesmente Encadeada
 Como, em uma Pilha, só manipulamos uma das extremidades denominada topo, precisamos 
ter a referência somente de um nó. Veja, a seguir, na Figura 5, a implementação de uma Pilha 
Dinâmica Encadeada.
11
 Figura 5 – Pilha Dinâmica Encadeada
 
 
Aplicação de Pilhas
Qualquer aplicação em que a ordem de entrada dos elementos é contrária à ordem de saída 
é uma candidata ao uso de Pilhas para implementação de seus elementos. Vamos ver, agora, 
alguns exemplos de uso de pilhas na computação.
12
Unidade: Listas Lineares
Controle de Chamadas e Retornos de Rotinas
Tanto na programação estruturada como na orientada a objetos, as funções ou métodos 
são técnicas bastante utilizadas para o reaproveitamento de algoritmos implementados. Essas 
funções são sub-rotinas ou subprogramas dentro de seu programa principal.
Para formar os programas, as rotinas são conectadas entre si através de um mecanismo 
de chamada e retornos, e as pilhas desempenham um papel fundamental no seu controle. 
Considere uma linguagem hipotética com as seguintes instruções: 
 » print - imprime mensagem no vídeo 
 » call - chama a sub-rotina 
 » return - retorna à sub-rotina que chamou 
Veja o programa a seguir dividido em 3 sub-rotinas (rotina A, rotina B e rotina C). A execução 
começa pela rotina A e o controle é passado às sub-rotinas e retornado de onde parou na rotina 
que chamou até encerrar na última linha da rotina A. 
Rotina A Rotina B Rotina C
1 - Print “Um” 5 - Call C 8 - Print “Dois
2 - Call B 6 - Print “Três” 9 - Return
3 - Call C 7 - Return
4 - Return
Cada vez que chamamos uma sub-rotina, o sistema operacional precisa guardar o endereço 
de retorno, continuando de onde parou quando o controle foi transferido. Nesse caso, os 
endereços de retorno são empilhados. Veja a pilha de controle na Tabela 2 a seguir:
Tabela 2 – Controle de Chamadas usando Pilhas
Instrução Pilha de Controle
-------- P:[ ]
1 - print “Um” P:[ 0 ]
2 - call B P:[ 0, 3 ]
5 - call C P:[ 0, 3, 6 ]
8 - print “Dois” P:[ 0, 3, 6 ]
9 – return P:[ 0, 3 ]
6 - print “Três” P:[ 0, 3 ]
13
7 – return P:[ 0 ]
3 - call C P:[ 0, 4 ]
8 - print “Dois” P:[ 0, 4 ]
9 – return P:[ 0 ]
4 – return P:[ ]
Podemos notar, na Tabela 2, que a pilha começa com 0, que simboliza o programa sendo 
executado na memória. A cada chamada de sub-rotina (comando call), o próximo endereço é 
armazenado na pilha para que seja executado quando a sub-rotina for encerrada (comando 
return). Ao final do processo, a pilha de controle deverá estar vazia, simbolizando que o programa 
encerrou com sucesso.
Caso haja uma falha na execução do programa no meio do caminho, a pilha de memória 
não é esvaziada normalmente, ocorrendo erros como “Este programa executou uma operação 
ilegal e será finalizado ...”. E, nesse caso, o sistema operacional vai esvaziar a pilha de controle.
Avaliação de Expressões
Estamos tão acostumados a digitar expressões e receber resultados que raramente paramos 
para pensar sobre o que deve acontecer dentro do computador a partir do momento em que 
fornecemos uma expressão até o momento em que recebemos a resposta. 
As operações são efetuadas de acordo com a ordem determinada pelas regras usuais 
da matemática (prioridades), ou seja, em primeiro lugar as multiplicações e divisões e, 
posteriormente, as somas e subtrações, sendo que os parênteses podem alterar a ordem de 
prioridade entre as operações.
Existem duas dificuldades ao avaliar uma expressão:
1 - A existência de prioridades diferentes para os operadores, que não nos permite efetuá-los 
na ordem em que encontramos na expressão;
2 - A existência de parênteses, que alteram a prioridade das operações.
Felizmente, um lógico polonês chamado Jan Lukasiewicz conseguiu criar uma representação 
para expressões em que não existem prioridades e nem a necessidade do uso dos parênteses.
Habitualmente, nós usamos a representação na qual o operador fica no meio dos operandos, 
mas existem outras possibilidades.
 » Infixa: operador aparece entre os operandos ( A + B )
 » Pré-Fixa: operador aparece antes dos operandos ( +AB )
14
Unidade: Listas Lineares
 » Pós-Fixa: operador aparece após os operandos ( AB + )
A forma pré-fixa é chamada Notação Polonesa e a pós-fixa, Notação Polonesa Reversa 
(NPR). A Notação Polonesa Reversa tem se mostrado mais eficiente no uso para a avaliação de 
expressões e estudaremos mais profundamente esse caso. 
A vantagem do uso dessa notação é que, como o operador aparece imediatamente após os 
operandos que deve operar, a ordem em que aparecem é a ordem em que deve ser efetuada a 
operação, sendo desnecessário o uso de parênteses ou regras de prioridade. Veja, na Tabela 3, 
alguns exemplos de conversão da notação infixa para notação polonesa reversa.
 
Tabela 3 – Exemplos de Conversão para NPR
Notação Infixa NPR
A + B * C A B C * +
A * ( B + C ) A B C + *
( A + B ) / ( C - D ) A B + C D - /
( A + B ) / ( C - D ) * E A B + C D - / E *
Para converter uma expressão infixa para NPR, usamos o algoritmo abaixo:
1. Parentetizar completamente a expressão (definir a ordem de avaliação).
2. Varrer a expressão da esquerda para a direita e, para cada símbolo:
3. Se for parêntese de abertura, ignorar;
4. Se for operando, copiar direto para a saída;
5. Se for operador, empilhá-lo;
6. Se for parêntese de fechamento, copiar para a saída o último operador empilhado. 
Para exemplificar a aplicação do algoritmo, veja, na Tabela 4, a seguir, como usamos uma 
pilha para converter a expressão A + B * C - D em NPR.Note que o primeiro passo do 
algoritmo é parentetizar a expressão, ou seja, colocar parênteses para definir as prioridades. 
Portanto a expressão a ser analisada a partir do passo 2 é ( ( A + ( B * C ) ) - D ) 
 
Tabela 4 – Aplicação do Algoritmo para conversão em NPR
Simbolo Pilha Saída
( P: [ ]
( P: [ ]
A P: [ ] A
+ P: [ + ] A
( P: [ + ] A
15
B P: [ + ] A B
* P: [ +, * ] A B
C P: [ +, * ] A B C
) P: [ + ] A B C *
) P: [ ] A B C * +
- P: [ - ] A B C * +
D P: [ - ] A B C * + D
) P: [ ] A B C * + D -
O problema do algoritmo apresentado é que precisamos parentetizar a expressão antes 
de colocar no programa, porém, na prática, o usuário não utiliza dessa forma a expressão. A 
prioridade deve ser dada pelo usuário, para que o programa saiba por onde começar. Para 
resolver esse problema, usaremos uma função chamada “prio”, que dá a prioridade dos 
operadores da expressão. A função é apresentada na Figura 6 a seguir: 
Figura 6 – Função prio para definir prioridades das operações
 
Portanto, o novo algoritmo pode ser descrito nos seguintes passos: 
1. Inicie com uma pilha vazia.
2. Realize uma varredura na expressão infixa, copiando todos os identificadores encontrados 
diretamente para a saída.
a. Ao encontrar um operador:
I. enquanto a pilha não estiver vazia e houver, no seu topo, um operador com prioridade 
maior ou igual ao encontrado, desempilhe o operador e coloque-o na saída.
II. empilhe o operador encontrado.
b. Ao encontrar um parêntese de abertura, empilhe-o.
c. Ao encontrar um parêntese de fechamento, remova um símbolo da pilha e copie-o na saída 
até que seja desempilhado o parêntese de abertura correspondente.
3. Ao final da varredura, esvazie a pilha e copie para a saída os símbolos removidos.
16
Unidade: Listas Lineares
Percorrendo qualquer expressão em notação polonesa reversa, da esquerda para a direita, 
ao encontrarmos um operador, sabemos que deve operar os dois últimos valores pelos quais 
passamos. Percebemos, novamente, a ideia de que “os últimos serão os primeiros processados” 
e, novamente, a aplicação de pilhas.
Vejamos um exemplo na expressão em NPR:
  AB+CD-/E*
Vamos atribuir valores numéricos às variáveis da expressão a ser avaliada:
  A= 7; B= 3; C= 6; D= 4; E= 9.
Agora, seguiremos o algoritmo a seguir:
1. Iniciamos com uma pilha vazia.
2. Varremos a expressão da esquerda para a direita e para cada elemento encontrado:
3. Se for operando, empilhar;
4. Se for operador, desempilhar os dois últimos valores, efetuar a operação com eles e empilhar de 
volta o resultado obtido.
No final do processo, o resultado da avaliação estará no topo da pilha. Veja a 
aplicação do Algoritmo na Tabela 5 a seguir:
Tabela 5 – Aplicação do Algoritmo para Avaliar a Expressão
Elemento Ação Pilha
A Empilha valor de A P:[7]
B Empilha valor de B P:[7,3]
+
Desempilha um y=3
Desempilha outro x=7
Empilha resposta x+y=10
P:[10]
C Empilha valor de C P:[10,6]
D Empilha valor de D P:[10,6,4]
-
Desempilha um y=4
Desempilha outro x=6
Empilha resposta x-y=2
P:[10,2]
/
Desempilha um y=2
Desempilha outro x=10
Empilha resposta x/y=5
P:[5]
E Empilha valor de E P:[5,9]
*
Desempilha um y=9
Desempilha outro x=5
Empilha resposta x*y=45
P:[45]
17
Uma alternativa para dar valores aos operandos é criar um vetor de 26 posições (máximo de 
letras que pode ser utilizado) e, para cada letra encontrada na expressão, perguntar o seu valor.
Filas
Uma fila é um tipo especial de lista linear em que as inserções são realizadas num extremo 
enquanto as remoções são feitas no outro. O extremo em que os elementos são inseridos é 
denominado final da fila e aquele em que são removidos é denominado começo da fila. 
A ordem de saída dos elementos corresponde diretamente à ordem de entrada dos mesmos 
na fila, de modo que os primeiros elementos que entram serão os primeiros a sair, caracterizando 
uma estrutura FIFO (First-In/First-Out). 
A palavra queue, da língua inglesa, significa fila. As duas operações básicas que 
uma fila suporta são:
 » enqueue: insere um elemento no final da fila.
 » dequeue: remove um elemento do começo da fila.
Veja, na Tabela 6, a seguir, um exemplo de manipulação de Filas, sendo F uma fila.
Tabela 6 – Manipulação de Filas
Operação Estudo da Fila
-------------- F:[ ]
F.enqueue(a) F:[ a ]
F.enqueue(b) F:[ a, b ]
F.enqueue(c) F:[ a, b, c ]
F.enqueue(d) F:[ a, b, c, d ]
F.dequeue() F:[ b, c, d ]
F.enqueue(F.dequeue()) F:[ c, d, b ]
F.enqueue(e) F:[ c, d, b, e ]
F.enqueue(F.dequeue()) F:[ d, b, e, c ]
18
Unidade: Listas Lineares
Assim como nas pilhas a manipulação é feita apenas nas extremidades da estrutura, não 
havendo inserção e remoção no meio dela, podemos implementar as filas de maneira estática-
sequencial ou dinâmica-encadeada.
Ao tentarmos implementar uma Fila Estática Sequencial, deparamos com dois problemas:
  as inserções são feitas sempre no fim da fila e as remoções no começo. Como é inviável 
o deslocamento de todos os elementos para a esquerda na remoção, existirão espaços em 
branco no início da fila que não podem ser reaproveitados, pois a inserção é sempre à direita;
  quando inserimos elementos até ela ficar cheia (fim=MAX), temos que não há mais 
possibilidades de inserção. Porém, mesmo que removamos todos os elementos, ainda 
assim ela vai achar que está cheia por não ter possibilidade de inserção e vazia por não 
ter mais elementos. 
Para resolver o primeiro problema, podemos criar uma Fila Circular, em que, após o último 
elemento voltar para a primeira posição e se estiver disponível para inserção, podemos colocar 
mais elementos.
O segundo problema, para descobrir se a Fila está cheia ou vazia, basta criar um contador de 
elementos e, se estiver zerado, é porque a fila está vazia e, se estiver com MAX, ela está cheia.
Sendo assim, a melhor solução também é implementar apenas com alocação Dinâmica-
Encadeada. Para criarmos uma Fila Dinâmica, ainda vamos usar a notação na qual cada 
elemento da Fila será um nó contendo um dado e o endereço do próximo nó da Fila através de 
Listas Simplesmente Encadeadas. Porém, a Fila, por ser uma estrutura FIFO, deve manipular as 
duas extremidades (começo e final), pois as inserções são feitas no final da Fila e as remoções 
no começo. Além disso, usaremos um contador para armazenar a quantidade de elementos que 
a Fila possui. 
Veja, na Figura 7, a seguir, a implementação de uma Fila Dinâmica Encadeada usando a 
mesma classe Node que foi utilizada na nossa Pilha Dinâmica.
19
Figura 7 – Fila Dinâmica Encadeada
 
Aplicação de Filas
Apesar da simplicidade do conceito de Filas, ele tem se mostrado essencial para o 
desenvolvimento de muitas aplicações, sobretudo quando se trata de simular, no computador, 
situações reais, nas quais algum tipo de atendimento é modelado.
Em resumo, qualquer aplicação em que a ordem de entrada é a mesma ordem de saída dos 
elementos a mesma é candidata .
20
Unidade: Listas Lineares
Uma interessante aplicação de Fila em computação gráfica são os algoritmos para colorir 
regiões de desenhos, representados sob a forma de matrizes de pontos. Uma região de um 
desenho é um conjunto de pontos conectados entre si e que têm a mesma cor. Dizemos que dois 
pontos Pi e Pj estão conectados entre si se, e somente se, pudermos partir de Pi, incrementar (ou 
decrementar) sua abscissa (ou ordenada e não ambas) e chegar ao ponto Pj. 
Para colorir uma região R, podemos utilizar o seguinte algoritmo básico:
1. Obter um ponto inicial P0 de cor C0, seguramente pertencente à região R;
2. Obter uma nova cor C1 para a região R;
3. Colocar P0 numa Fila V, inicialmente vazia;
4. Enquanto a Fila V não esvaziar:
5. remover um ponto da fila V;
6. inserir em V todos os pontos conectados a P, cuja cor seja C0;
7. alterar a cor de P para C1.
Para poder simular o efeito, vamos representar uma imagem qualquer através de uma 
matriz, em que cada elemento da matriz representa um ponto do desenho(pixel) e cada pixel 
é discriminado pelascoordenadas da sua posição na matriz, conforme podemos ver na Figura 
8. Cada elemento da matriz armazena um valor correspondente à cor do ponto representado 
(0=branco, 1=cinza, 2=preto...)
Figura 8 – Representação de uma imagem através de uma matriz 
 
Na Figura 9, você pode conferir a implementação do Algoritmo para colorir regiões gráficas 
utilizando Filas.
21
Figura 9 – Programa para colorir regiões gráficas
 
22
Unidade: Listas Lineares
Material Complementar
1) Simuladores:
• http://www.cafw.ufsm.br/~bruno/disciplinas/estrutura_dados/applets/stack.html
• http://www.cafw.ufsm.br/~bruno/disciplinas/estrutura_dados/applets/queue.html
2) YouTube
• http://www.youtube.com/watch?v=z0WseEPdzd0
3) Wikipedia:
• http://pt.wikipedia.org/wiki/Estrutura_de_dados
PREISS, B. R. Estruturas de Dados e Algoritmos: Padroes de Projetos Orientados a 
Objetivos Com. Rio de Janeiro:Campus, 2001.
WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: Ltc-Livros Tecnicos e 
Cientificos, 1999.
MORAES, C. R. Estruturas de Dados e Algoritmos: Uma Abordagem Didatica. Sao Paulo: 
Berkeley, 2001.
FORBELLONE, A. L. V.; EBERSPACHER, H. F. Logica de Programacao: A Construcao de 
Algoritmos e Estrutura de Dados. 3. ed. Sao Paulo: Makron Books do Brasil, 2005.
VELOSO, P.; FURTADO, A.; SANTOS, C. S. Estruturas de Dados. 26. ed. Rio de Janeiro: 
Campus, 2003.
TENENBAUM, A. M.; LANGSAM, Y. Estruturas de Dados Usando C. Sao Paulo: Makron 
Books do Brasil, 2005.
DROZDEK, A. Estrutura de Dados e Algoritmos em C++. São Paulo: Pioneira Thomson 
Learning, 2005.
ASCENCIO, Ana F.G., Estruturas de Dados: algoritmos, análise da complexidade e 
implementações em Java e C/C++ São Paulo: Pearson Prendice Hall, 2010
DEITEL, Harvey M., Java Como Programar, 8.a edição, São Paulo: Pearson Prentice Hall, 2010
23
Referências
ASCENCIO, Ana F.G. Aplicações das Estruturas de Dados em Delphi. São Paulo: Pearson 
Prendice Hall, 2005.
GOODRICH, M. T.; TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 2. ed. 
Porto Alegre: Bookman, 2002.
LAFORE, R. Estruturas de Dados & Algoritmos em Java. Rio de Janeiro: Ciência 
Moderna, 2004.
PEREIRA, S. L. Estruturas de Dados Fundamentais: Conceitos e Aplicações. 9. ed. São 
Paulo: Erica, 2001.
WEISS, M. A. Data Structures And Algorithm Analysis In Java. 2. ed. Massachusetts: 
Addison-Wesley, 2007.
24
Unidade: Listas Lineares
Anotações
www.cruzeirodosulvirtual.com.br
Campus Liberdade
Rua Galvão Bueno, 868
CEP 01506-000
São Paulo SP Brasil 
Tel: (55 11) 3385-3000
www.cruzeirodosulvirtual.com.br
Rua Galvão Bueno, 868
Tel: (55 11) 3385-3000