Apostila Alg...ura de Dados - algoritmos e estrutura de dados - volume 3

Apostila Alg...ura de Dados - algoritmos e estrutura de dados - volume 3

(Parte 3 de 5)

► circular L

Perceba uma característica notável desse algoritmo: a união de duas listas é feita com um número constante de operações, ou seja, que independe do número de elementos representados. O algoritmo também funciona para o caso em que uma das listas ou ambas têm apenas um ou mesmo nenhum elemento.

Listas duplamente ligadas

Em uma lista duplamente ligada, cada célula tem dois ponteiros: prox, para o próximo elemento, e ant, para o anterior. Um exemplo, que também mostra como uma tal lista pode ser ilustrada:

Listas duplamente ligadas também podem ser circulares:

Algoritmos e Estrutura de Dados

Conhecer o elemento anterior de cada célula é uma facilidade muito útil. Por exemplo, a operação de remoção de uma célula em uma lista duplamente ligada é muito mais “limpa” do que a operação correspondente para os casos anteriores, pois a remoção pode ser feita conhecendo-se um ponteiro para a célula ao invés de um ponteiro para a célula anterior.

Por outro lado, toda operação com listas duplamente ligadas exige um cuidado adicional na administração dos ponteiros. O caso da inserção está ilustrado na figura a seguir. Note que tanto o ponteiro para a próxima célula quanto o ponteiro para a anterior devem ser atualizados na célula inserida.

Segue a inserção para uma lista duplamente ligada com cabeça (circular ou não):

algoritmo INSERE (L, M) prox[M]←prox[L] prox[L]←M ant[M]←L ant[prox[M]]←M

► Recebe uma lista duplamente ligada com ► cabeça L e uma célula M. Insere M no começo

Eis a operação de remoção, que, como observamos, pode ser feita a partir de um ponteiro para a célula a ser removida. Perceba que nenhum dado além desse ponteiro é necessário. Recorde também que a memória utilizada pela célula removida deve ser liberada após a operação.

algoritmo REMOVE (M) prox[ant[M]]←prox[M] ant[prox[M]]←ant[M]

► Remove uma célula M de uma lista duplamente ► ligada.

Algoritmos e Estrutura de Dados

Para ficar mais claro, que tal desenhar uma figura que ilustra essa operação?

Você Sabia?

Você já ouviu falar da linguagem Lisp (seu nome vem de LISt

Processing)? É uma das mais antigas linguagens de programação - foi concebida na década de 1950. Mas é bastante diferente das linguagens com que você talvez esteja acostumado, como a C. Tanto os dados quanto os programas em Lisp são baseados em listas, que podem ser compostas com outras listas para a formação de estruturas mais complexas.

A linguagem Lisp é importante em Inteligência Artificial. Se quiser aprender Lisp, talvez valha a pena conhecer o célebre editor de textos Emacs, onde essa linguagem funciona como uma extraordinária ferramenta de extensão.

Conheça Mais

Listas ligadas são um assunto muito fundamental em Computação e há uma vasta bibliografia que trata do assunto. Recomendamos em particular:

Wirth, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: Ed. Prentice Hall do Brasil, 2002.

Feofiloff, P. Algoritmos em linguagem C. Ed. Campus/Elsevier. 2008

Você também encontrará um vasto material na Internet a respeito.

É muito interessante que você compreenda como implementar e manipular listas em uma linguagem de programação. Estude em particular as linguagens C e Java. Duas referências básicas para essas linguagens são as seguintes:

Kernighan, B, Ritchie, D. C - A Linguagem de Programação Padrão ANSI. Ed. Campus/Elsevier. 1989

Algoritmos e Estrutura de Dados

Deitel, H. M., Deitel, P. J. Java: Como Programar. Ed. Prentice- Hall, 2005

Se você não conhece a linguagem Java, é uma excelente oportunidade para aprender. A implementação de classes para os diversos tipos de listas vai auxiliá-lo de quebra a entender programação orientada a objetos. Nos exercícios propostos a seguir, busque implementar suas soluções numa dessa linguagens.

Atividades e Orientações de Estudo

O exercício a seguir vai auxiliá-lo a ganhar experiência com a manipulação de listas ligadas. Você pode assumir que em todos os casos as listas em questão são com cabeça a menos que o contrário seja explicitamente dito. Você encontrará muitos outros exercícios nas referências bibliográficas.

Problema 1

Escreva um algoritmo que devolve o elemento mínimo de uma lista. Faça duas versões, uma para listas circulares que não têm cabeça, outra para listas que não são circulares. Qual a complexidade de seu algoritmo?

Problema 2

Escreva um algoritmo que devolve o último elemento de uma lista (o caso de uma lista duplamente ligada é muito elementar; considere que a lista não é duplamente ligada).

De forma mais geral, escreva um algoritmo que devolve o k-ésimo elemento de uma lista. Qual a complexidade do seu algoritmo?

Problema 3

Escreva um algoritmo que inverte uma lista ligada sem usar espaço auxiliar, ou seja, apenas alterando ponteiros. Repita o exercício para uma lista circular e uma lista duplamente ligada circular.

Problema 4 Escreva um algoritmo que devolve a soma de uma lista ligada de inteiros.

Algoritmos e Estrutura de Dados

Problema 5

Escreva um algoritmo que faz a união de duas listas ligadas não necessariamente circulares.

Problema 6 Escreva um algoritmo que busca um inteiro em uma lista em ordem crescente.

Problema 7 Escreva um algoritmo que ordena uma lista de inteiros.

Problema 8

Escreva um algoritmo que recebe uma lista ligada de inteiros em ordem crescente, um inteiro (ou um ponteiro para uma célula representando um inteiro), e insere esse inteiro mantendo a ordenação.

Problema 9

Escreva um algoritmo que recebe duas listas de inteiros ordenadas e constrói uma nova lista que representa a intercalação das duas sequências. Seu algoritmo não usa espaço auxiliar, mas faz isso alterando convenientemente os ponteiros das listas. Veja o módulo anterior para uma descrição da operação de intercalação.

Problema 10

Implemente as funções de inserção, remoção, busca e mínimo para um conjunto dinâmico de inteiros usando listas ligadas. Programe também uma interface simples que exibe o conteúdo do conjunto e apresenta ao usuário um menu para a escolha de uma operação. Decida a linguagem de programação com seu tutor.

Vamos Revisar?

Estudamos neste capítulo a estrutura de lista ligada, onde elementos de um conjunto dinâmico são representados na memória de um computador com o auxílio de ponteiros. Estudamos as operações de inserção, busca e remoção em listas, bem como suas complexidades. Também consideramos dois tipos bastante úteis de lista, as listas circulares e as listas duplamente ligadas.

Algoritmos e Estrutura de Dados Capítulo 2 – Pilhas

Vamos conversar sobre o assunto?

Se inserções e remoções podem ser realizadas em apenas uma extremidade de uma lista linear, temos uma pilha. O nome dessa estrutura de dados é uma analogia com pilhas de pratos ou livros, onde só podemos inserir ou retirar um novo item na extremidade superior. Também podemos dizer que uma pilha é um conjunto dinâmico onde só podemos remover o último elemento inserido.

Qual a utilidade dessa disciplina particular de inserções e remoções? Muitas. Encontramos frequentemente problemas em Computação que podem ser modelados em uma estrutura de pilha. Um exemplo importante é o gerenciamento de memória durante a execução de um programa. Quando uma função é chamada, o estado da memória (o conjunto das variáveis definidas pelo programa e o ponto de execução antes da chamada da função) devem ser armazenados, para que a execução retome esse mesmo estado após o término da execução da função. E o que acontece se várias funções são executadas, cada uma dentro de outra mais externa, como é o caso de funções recursivas? Esses estados de memória são empilhados e, posteriormente, desempilhados. Essa técnica é tão importante que certos processadores possuem registradores normalmente dedicados ao gerenciamento de uma estrutura de pilha.

Como vemos, o conceito de pilha é bastante natural. Vamos neste capítulo aprender como implementar pilhas em vetores e em listas ligadas, e adquirir alguma experiência com essa estrutura através de algumas aplicações.

Bom estudo!

1. Definição de pilha

A estrutura de dados pilha é semelhante a uma pilha de pratos ou livros. Você não ousará retirar ou enfiar livros no meio de uma pilha, a menos que queira correr o risco de um desastre. Há um único local seguro para fazer isso: o topo da pilha.

Algoritmos e Estrutura de Dados

Em Computação, não empilhamos livros ou pratos, mas sim dados. Essa é da definição de pilha: uma lista linear (de inteiros, por exemplo) onde inserções e remoções só podem ser realizadas em uma extremidade. Dando nomes aos bois, essa extremidade é chamada topo, e uma pilha P suporta duas operações básicas:

• EMPILHA (P, x): insere o elemento x na pilha, ou seja, após o topo (o novo topo é a posição do elemento inserido);

• DESEMPILHA (P): retira o elemento no topo da pilha (o novo topo é o elemento anterior ao retirado).

Perceba que em uma pilha o último elemento a entrar, aquele que está na estrutura há menos tempo, é o primeiro a sair. Há uma sigla em inglês popular para descrever esse comportamento: dizemos que pilhas são estruturas LIFO, de last-in, first-out.

É claro que a operação desempilha só faz sentido se a pilha não estiver vazia. O empilhamento a princípio sempre é possível, mas em certas implementações um limite para o tamanho da pilha é imposto. É o caso de implementação com vetores, que estudaremos na próxima seção.

Atenção

Na literatura em inglês, pilha é “stack”, empilha é “push” e desempilha é “pop”.

Algoritmos e Estrutura de Dados

2. Implementando uma pilha em um vetor

Podemos representar uma pilha de no máximo N elementos em um vetor P de tamanho N. A cada instante, os elementos são armazenados da posição 1 até uma posição t, o topo da pilha. A pilha está vazia se t = 0 e cheia se t = N. Eis um vetor que representa uma pilha de 5 elementos, e para o qual N = 7:

Algumas operações nessa pilha: • EMPILHA (P, 73)

• EMPILHA (P, 52) • EMPILHA (P, 38)

O que acontece se um novo empilhamento é realizado na última pilha do exemplo acima? Ocorre um transbordamento (em inglês, overflow). Essa situação é anormal, e em um programa correto não

Algoritmos e Estrutura de Dados deveria ocorrer nunca. Também é anormal tentar desempilhar de uma pilha vazia (situação em inglês conhecida como underflow).

É preciso ficar claro que, mesmo que em um vetor temos acesso automático a qualquer posição, não faz sentido espiar os elementos de uma pilha abaixo do topo. De fato, só vamos usar uma pilha em aplicações onde o único elemento relevante é aquele que está no topo – senão, usamos outra estrutura.

Vamos concluir essa seção com código em Portucal para as operações empilha e desempilha de uma pilha de inteiros. Também importa termos funções para testar se uma pilha está cheia, vazia e obter o elemento no topo de uma pilha. Cada uma dessas operações é executada em complexidade constante.

Para simplificar, vamos admitir que uma pilha é um registro que engloba o vetor, o topo da pilha, e o número máximo de elementos; também vamos usar a mesma letra para denotar um ponteiro para esse registro e o vetor que armazena a pilha. Assim, para acessar a posição do topo e o tamanho de uma pilha P, escrevemos topo[P], N[P] e para acessar o elemento no topo escrevemos P[topo[P]]

Fica claro aqui, mais uma vez, a utilidade do uso de registros (ou estruturas, ou classes – depende da linguagem) que encapsulam as propriedades relevantes de uma pilha em uma unidade lógica. De fato, quando desejamos passar uma pilha para uma função, basta passar um ponteiro para esse registro ao invés de três argumentos (um para o vetor, outro para o topo e um terceiro para o número máximo de elementos). Muito mais simples, claro e seguro.

A partir daqui, habitue-se a pensar em termos de registros, estruturas ou classes para implementação de estruturas de dados.

Enfatizamos que o topo será a única posição acessada na pilha (como acabamos de comentar, não se deve bisbilhotar o interior de uma pilha).

Não vamos incluir nesse código um tratamento explícito para a ocorrência de overflow. O caso de underflow na operação de desempilhamento pode ser detectado a partir do retorno da função.

Lembrete

Em programação orientada a objetos (o paradigma adotado na linguagem Java, entre outras) as operações descritas a seguir seriam normalmente codificadas na própria classe pilha, e não em funções avulsas

Algoritmos e Estrutura de Dados

Em uma implementação robusta para aplicações práticas, essas situações de exceção, se detectadas, devem resultar em um código de erro ou disparar um tratamento adequado.

algoritmo VAZIA (P) se topo [P] = 0 então devolva V senão devolva F

► Testa se uma pilha está vazia algoritmo CHEIA (P) se topo [P] = N[P] então devolva V senão devolva F

► Testa se uma pilha está cheia algoritmo EMPILHA (P, x) se NÃO VAZIA (P) então topo[P] ←topo[P] + 1 P[topo[P]]←x

►Empilha um inteiro x em uma pilha P algoritmo DESEMPILHA (P) se NÃO VAZIA (P) então x ←P [topo[P]] topo[P] ←topo[P] - 1 devolva P[topo[P]] devolva nil

► Desempilha o elemento no topo de uma pilha P

Um comentário sobre a função DESEMPILHA. Note que não é necessário “apagar” o elemento desempilhado do vetor. De fato, o que está acima do topo não tem relevância para a pilha, e assim, basta

Algoritmos e Estrutura de Dados diminuir o topo de uma unidade. Também atente para o fato de que a função DESEMPILHA devolve o elemento no topo da pilha, e caso a pilha esteja vazia, retorna um valor que permite identificar o erro (nil, que é diferente de todo inteiro). O mesmo ocorre na função a seguir:

algoritmo TOPO (P) se NÃO VAZIA (P) então devolva P[topo[P]] devolva nil

Nos exercícios propostos deste capítulo, queremos convidá-lo a implementar essas funções em uma linguagem de programação.

3. Implementando uma pilha em uma lista ligada

Também podemos implementar uma pilha em uma lista ligada com cabeça, não necessariamente circular nem duplamente ligada. O topo da pilha é o primeiro elemento da lista após a cabeça. A pilha é acessada a partir de um ponteiro para a cabeça.

Vejamos um exemplo. A figura abaixo apresenta uma pilha, P, e o empilhamento de uma célula. Antes do empilhamento o topo contém o número 5.

A vantagem da representação com uma lista é a inexistência de um limite superior para o tamanho da pilha (exceto evidentemente o tamanho da memória), graças à alocação dinâmica de espaço. Em particular, a função CHEIA descrita na seção anterior não faz sentido aqui. Quando a pilha está vazia? Quando o ponteiro da cabeça vale nil.

Algoritmos e Estrutura de Dados

Segue a descrição das operações fundamentais de uma pilha implementada como uma lista. Todas têm complexidade constante.

algoritmo VAZIA (P) se prox[P] = nil então devolva V senão devolva F

► Testa se uma pilha está vazia algoritmo EMPILHA (P, M) prox [M] ←prox [P] prox [P] ← M algoritmo DESEMPILHA (P) se NÃO VAZIA (P) então

M ←prox [P] prox [P] ←prox[M] devolva M devolva nil

► Desempilha o elemento no topo de uma pilha P algoritmo TOPO (P) se NÃO VAZIA (P) então devolva info[prox[P]] devolva nil

►Devolve o elemento no topo de uma pilha P

Aprenda Praticando

Vamos estudar uma aplicação da estrutura de pilha, desenvolvendo uma calculadora para expressões aritméticas em notação posfixa.

(Parte 3 de 5)

Comentários