3 2 - Implementação de listas encadeadas simples

Prévia do material em texto

<p>Implementação de listas</p><p>encadeadas simples</p><p>Apresentação</p><p>A lista simplesmente encadeada é uma relação entre elementos, chamados nodos, interligados</p><p>entre si. Nela, cada elemento traz informações sobre o próximo item e o seu conteúdo, podendo</p><p>ser do tipo primitivo ou criado pelo usuário.</p><p>A partir daí, uma série de operações de manipulação de uma lista simplesmente encadeada permite</p><p>a manipulação de seus nodos durante sua execução.</p><p>O desenvolvimento dessas listas requer do programador conhecimento das bibliotecas, que irão</p><p>facilitar a construção do software. Todavia, as bibliotecas não disponibilizam todas as</p><p>funcionalidades necessárias para o desenvolvimento de uma aplicação. Portanto, compreender o</p><p>seu funcionamento interno é fundamental e permitirá desenvolver novas funcionalidades.</p><p>Nesta Unidade de Aprendizagem, você verá as listas encadeadas, saberá como analisar sua</p><p>estrutura e como desenvolvê-las, bem como sobre a sua implementação sem o uso de bibliotecas</p><p>específicas, com a ajuda de exemplos práticos e comentados.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Analisar a estrutura de listas em Python.•</p><p>Desenvolver listas encadeadas simples em Python.•</p><p>Resolver problemas que utilizem listas encadeadas simples.•</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Desafio</p><p>O desenvolvimento de lista simplesmente encadeada possibilita a inserção e a remoção de</p><p>elementos em quaisquer posições, bem como a não determinação de seu tamanho durante sua</p><p>declaração, possibilitando, assim, sua flexível extensão.</p><p>Suponha que você é desenvolvedor em uma empresa de transportes de produtos, responsável pela</p><p>área de despacho de mercadorias.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/b5456bc4-5cbd-40cb-80f8-42402825e194/9de3e15c-ac23-45a9-80d9-8eaf80e45e35.jpg</p><p>A partir do código iniciado, complete o método que informa o total de produtos que necessitam de</p><p>transporte refrigerado.</p><p>Infográfico</p><p>Os desenvolvedores, muitas vezes, não realizam o planejamento antes de iniciar o desenvolvimento</p><p>de uma aplicação ou nova funcionalidade, realizando as mudanças diretamente no código principal</p><p>sem levar em consideração os tipos de listas disponíveis.</p><p>Neste Infográfico, você compreenderá a principal diferença entre as listas encadeadas simples e as</p><p>duplas.</p><p>Laiane</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/e4a26954-1f56-4b4f-84c9-cf18fd05b8a5/01de1342-a955-4962-92e1-2f0747d3a9f1.jpg</p><p>Conteúdo do livro</p><p>O desenvolvimento de listas simplesmente encadeadas requer muita prática na realização de</p><p>exercícios sem o uso de bibliotecas, pois, antes de utilizá-las, é necessário compreender o seu</p><p>funcionamento.</p><p>No capítulo Implementação de listas encadeadas simples, da obra Estrutura de dados, você verá</p><p>as listas encadeadas, saberá como analisar sua estrutra e desenvolvê-las e entenderá como</p><p>funciona a implementação sem o uso de bibliotecas específicas, com a ajuda de exemplos práticos e</p><p>comentados.</p><p>Boa leitura.</p><p>Laiane</p><p>ESTRUTURA</p><p>DE DADOS</p><p>Lucas Plautz Prestes</p><p>Implementação de listas</p><p>encadeadas simples</p><p>Objetivos de aprendizagem</p><p>Ao final deste texto, você deve apresentar os seguintes aprendizados:</p><p>� Analisar a estrutura de listas em Python.</p><p>� Desenvolver listas encadeadas simples em Python.</p><p>� Resolver problemas que utilizem listas encadeadas simples.</p><p>Introdução</p><p>O estudo de listas encadeadas é o primeiro passo para a compreensão</p><p>do modo como manipulamos uma grande quantidade de dados em</p><p>programação. O desenvolvimento dessas listas pode ser realizado a partir</p><p>de bibliotecas disponíveis nas mais diferentes linguagens de programação.</p><p>As bibliotecas utilizadas em programação auxiliam no desenvolvi-</p><p>mento de listas simplesmente encadeadas e, apesar de serem práticas,</p><p>não disponibilizam todas as funcionalidades necessárias para o desen-</p><p>volvimento de uma aplicação; logo, é necessário que o programador</p><p>compreenda o que se encontra no interior dos métodos utilizados. Sendo</p><p>assim, durante os estudos, recomenda-se o desenvolvimento dos prin-</p><p>cipais métodos disponíveis nas bibliotecas utilizadas.</p><p>Neste capítulo, você vai estudar sobre as listas simplesmente enca-</p><p>deadas e o seu desenvolvimento e aplicação em linguagem Python.</p><p>1 Estrutura de listas em Python</p><p>Antes de iniciarmos o estudo e o desenvolvimento de listas em linguagem</p><p>Python, devemos remeter ao seu conceito primordial. A lista simplesmente</p><p>encadeada constitui uma relação entre elementos, nodos, interligados entre si,</p><p>em que cada elemento é composto de uma estrutura que contém um endereço</p><p>Laiane</p><p>para o próximo nodo e o seu respectivo conteúdo, podendo ser do tipo primitivo</p><p>ou criado pelo usuário (EDELWEISS; GALANTE, 2009).</p><p>Na Figura 1 é possível analisarmos a estrutura de uma lista simplesmente</p><p>encadeada, bem como do seu respectivo nodo.</p><p>Figura 1. Estrutura de uma lista encadeada simples.</p><p>Fonte: Edelweiss e Galante (2009, p. 89).</p><p>A linguagem Python contém funções, classes e métodos que irão nos</p><p>auxiliar no desenvolvimento de listas. As funções e os métodos utilizados são:</p><p>— Informa a quantidade de elementos enviados por parâ-</p><p>metro que existem na variável Lista.</p><p>Implementação de listas encadeadas simples2</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>— Realiza a limpeza de todos os nodos de uma lista. Essa limpeza</p><p>libera o espaço ocupado na memória do computador. Uma vez executada, os</p><p>dados não poderão ser recuperados.</p><p>— Adiciona a variável elemento ao final da lista.</p><p>3Implementação de listas encadeadas simples</p><p>Laiane</p><p>Laiane</p><p>— Adiciona o elemento em uma posição específica</p><p>de uma lista.</p><p>— Realiza a remoção da primeira ocorrência do elemento</p><p>em uma determinada lista.</p><p>Implementação de listas encadeadas simples4</p><p>Laiane</p><p>Laiane</p><p>— Retorna à posição da primeira ocorrência do elemento</p><p>em uma lista.</p><p>— Gera listas con-</p><p>tendo progressões aritméticas por intervalo informando, ou não, o respectivo</p><p>incremento entre os nodos.</p><p>5Implementação de listas encadeadas simples</p><p>Laiane</p><p>Laiane</p><p>O desenvolvedor deverá ter atenção nas chamadas de funções e conteúdo dos nodos</p><p>das listas quanto a letras maiúsculas e minúsculas, pois Python é case sensitive. Por</p><p>exemplo, a palavra Casa é diferente da palavra casa, pois a primeira palavra tem a</p><p>primeira letra em caixa-alta.</p><p>2 Desenvolvimento de listas encadeadas</p><p>simples</p><p>As operações de manipulação de uma lista simplesmente encadeada permitem</p><p>a manipulação de seus nodos durante a sua execução. Dessa forma, ao realizar-</p><p>mos o estudo dessas listas, recomenda-se a criação de algumas funções sem</p><p>o uso de bibliotecas específicas, assim, facilitará a sua correta compreensão</p><p>de forma a não depender de bibliotecas de terceiros ou até mesmo possibilitar</p><p>a criação de suas próprias bibliotecas.</p><p>Implementação de listas encadeadas simples6</p><p>Laiane</p><p>Laiane</p><p>As operações que devemos desenvolver, relacionadas às listas simplesmente</p><p>encadeadas, são:</p><p>1. Criar uma classe Nodo.</p><p>2. Criar uma classe Lista.</p><p>3. Criar uma função que verifica se a lista está vazia.</p><p>4. Criar uma função que informa o tamanho da lista</p><p>5. Criar uma função que adiciona um elemento no início da lista.</p><p>6. Criar uma função que adiciona um elemento no final da lista.</p><p>7. Criar uma função que adiciona um elemento em uma posição específica</p><p>da lista.</p><p>8. Criar uma função que remove um elemento em uma posição específica</p><p>da lista.</p><p>9. Criar uma função que remove o primeiro elemento da lista.</p><p>10. Criar uma função que remove o último elemento da lista.</p><p>11. Criar uma função que conta o número de ocorrências de um elemento</p><p>na lista.</p><p>Os exemplos com desenvolvimento em Python são dependentes. Logo, em todos os</p><p>exemplos, é necessário adicionar o código Python de exemplos anteriores de forma</p><p>retroativa para o seu correto funcionamento.</p><p>Os métodos</p><p>para a criação das classes nodo, lista encadeada, verificação</p><p>de lista vazia, adicionar e remover posição na lista são elementos básicos no</p><p>que se refere à implementação de listas encadeadas simples, nas quais você já</p><p>pode ter tido contato com eles anteriormente. No entanto, vamos retomá-los</p><p>aqui, pois são essenciais para o embasamento dos novos métodos que vamos</p><p>introduzir.</p><p>O desenvolvimento dos códigos a seguir foi adaptado a partir de exemplos</p><p>em Borges (2010) e Schildt (1996).</p><p>7Implementação de listas encadeadas simples</p><p>Laiane</p><p>Laiane</p><p>Criação de um Nodo</p><p>Criação da classe ListaEncadeada</p><p>Implementação de listas encadeadas simples8</p><p>Criação da função ListaVazia</p><p>Criação do método TamanhoLista</p><p>9Implementação de listas encadeadas simples</p><p>Criação da função Adiciona_Inicio</p><p>Implementação de listas encadeadas simples10</p><p>Criação da função Adiciona_Fim</p><p>11Implementação de listas encadeadas simples</p><p>Criação da função Adiciona_Pos</p><p>Implementação de listas encadeadas simples12</p><p>Criação da função Remove_Pos</p><p>13Implementação de listas encadeadas simples</p><p>Criação da função Remove_Inicio</p><p>Implementação de listas encadeadas simples14</p><p>Criação da função Remove_Fim</p><p>15Implementação de listas encadeadas simples</p><p>Criação da função Ocorrência</p><p>3 Problemas com o uso de listas encadeadas</p><p>simples</p><p>O desenvolvimento de listas encadeadas não se restringe exclusivamente aos</p><p>exemplos desenvolvidos neste capítulo, com o uso de classes primitivas, mas</p><p>com as aplicações que façam o uso de tipos de dados definidos pelo usuário.</p><p>Para isso, vamos desenvolver o algoritmo em linguagem de programação</p><p>Python, sem o uso de bibliotecas, referente a uma lista de funcionários em</p><p>Implementação de listas encadeadas simples16</p><p>Laiane</p><p>uma loja de departamentos. Essa lista deverá ser simplesmente encadeada,</p><p>com a criação dos seguintes métodos:</p><p>� criar as classes Lista, Nodo e Funcionario;</p><p>� informar o número de funcionários;</p><p>� adicionar um funcionário na lista;</p><p>� remover um funcionário da lista.</p><p>17Implementação de listas encadeadas simples</p><p>Laiane</p><p>Implementação de listas encadeadas simples18</p><p>19Implementação de listas encadeadas simples</p><p>Implementação de listas encadeadas simples20</p><p>BORGES, L. E. Python para desenvolvedores. 2. ed. Rio de Janeiro: Edição do Autor, 2010.</p><p>EDELWEISS, N.; GALANTE, R. Estruturas de dados. Porto Alegre: Bookman, 2009. (Livros</p><p>didáticos informática UFRGS, v. 18).</p><p>SCHILDT, H. C: completo e total. São Paulo: Makron Books, 1996.</p><p>21Implementação de listas encadeadas simples</p><p>Dica do professor</p><p>A compreenção de como implementar uma lista inicia-se a partir do entendimento das classes base</p><p>e os seus métodos.</p><p>Nesta Dica do Professor, você irá companhar o passo a passo para a criação de uma lista encadeada</p><p>simples e saberá como se organizam as classes e os métodos.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/6d87e196e74dc8b0103f020c7ba1ca5d</p><p>Exercícios</p><p>1) A análise de códigos é de suma importância para o desenvolvimento de um programador,</p><p>sendo uma das tarefas mais comuns no seu dia a dia, seja na compreensão do</p><p>desenvolvimento complementar, seja durante os seus estudos.</p><p>Realize a análise do código a seguir e assinale a alternativa que contém o seu objetivo:</p><p>def Metodo(self):</p><p>atual = self.inicio</p><p>self.inicio = atual.proximo</p><p>A) Realizar a inclusão de um novo nodo.</p><p>B) Realizar a exclusão do último nodo.</p><p>C) Realizar a exclusão do primeiro nodo.</p><p>D) Realizar a impressão do primeiro nodo.</p><p>E) Realizar a limpeza da lista.</p><p>As operações de manipulação de uma lista simplesmente encadeada permitem a</p><p>manipulação de seus nodos durante sua execução.</p><p>Analise o código a seguir e informe qual o seu objetivo:</p><p>def Metodo(self):</p><p>atual = self.inicio</p><p>if self.inicio == None:</p><p>print("none")</p><p>else:</p><p>while atual != None:</p><p>print(atual)</p><p>2)</p><p>Laiane</p><p>Laiane</p><p>Método que realiza a remoção do primeiro elemento:def Remove_Inicio(self):#Realiza a atribuição do início da lista para um o nodo atual.atual = self.inicio#Atualiza o primeiro elemento da lista para o elemento posterior ao primeiro nodo, excluindo o nodo inicial.self.inicio = atual.proximo</p><p>Laiane</p><p>#Realiza a impressão de todos os elementos de uma lista def Impressão(self):#Ponteiro atual recebe o início da lista:atual = self.inicio#verifica se a lista encontra-se vazia e informa o usuário if self.inicio == None:print("none")#Caso a lista tenha conteúdo, percorre toda a lista e imprime em cada interação o seu respectivo conteúdo. else:while atual != None:print(atual)atual = atual.proximo</p><p>atual = atual.proximo</p><p>A) Realizar a inclusão de um elemento.</p><p>B) Realizar a exclusão do último elemento.</p><p>C) Realizar a impressão de uma lista.</p><p>D) Realizar a exclusão de uma lista.</p><p>E) Realizar a contagem de seus nodos.</p><p>3) O desenvolvimento de listas encadeadas pode ser realizado de diversas formas, com ou sem</p><p>o uso de bibliotecas.</p><p>O método da biblioteca de listas chamado append(Elemento) realiza qual função no código?</p><p>A) Adiciona um elemento no início da lista.</p><p>B) Adiciona um elemento ao final da lista.</p><p>C) Remove o primeiro elemento.</p><p>D) Remove o último elemento.</p><p>E) Realiza a contagem do número de ocorrências de determinado elemento.</p><p>4) As bibliotecas utilizadas em programação auxiliam no desenvolvimento de listas</p><p>simplesmente encadeadas.</p><p>O método da biblioteca de listas chamado index(Elemento) realiza qual função no código?</p><p>A) Informa o número de ocorrências de um elemento na lista.</p><p>B) Informa se há o elemento na lista.</p><p>C) Imprime determinado elemento.</p><p>D) Retorna à posição da primeira ocorrência do elemento na lista.</p><p>E) Retorna à última posição da ocorrência do elemento na lista.</p><p>5)</p><p>Laiane</p><p>Laiane</p><p>#Código em Python:       # Lista de letras       letras= ['A', 'H', 'T']       # Metodo que adiciona a letra D no final da lista       animais.append('D')       # imprime a nova lista       print('Atualização da lista: ', letras)#Saída do programa            # Atualização da lista:  ['A', 'H', 'T','D']</p><p>Laiane</p><p>Laiane</p><p>Laiane</p><p>#Código em Python:       # Lista de letras       letras = ['A', 'G', 'P','G']       # imprime a  lista       print(letras)       # Retorna e imprime a posição da primeira ocorrência do elemento Gprint(letras.index('G'))#Saída do programa # ['A', 'G', 'P','G']            #1</p><p>Os métodos para a criação das classes nodo, lista encadeada, verificação de lista vazia,</p><p>adicionar e remover posição na lista são elementos básicos no que se refere à</p><p>implementação de listas encadeadas simples.</p><p>Analise o código a seguir e informe qual o seu objetivo:</p><p>def Metodo(Lista):</p><p>if Lista.inicio == None :</p><p>return True</p><p>else:</p><p>return False</p><p>A) Verificar se existe uma lista.</p><p>B) Verificar se a lista está cheia.</p><p>C) Verificar se a lista está vazia.</p><p>D) Verificar qual é o nodo de início da lista.</p><p>E) Realizar a contagem de quantos elementos tem na lista.</p><p>Laiane</p><p>#Método que verifica se a lista está Vazia, Caso positivo Retorna True caso contrário False.def ListaVazia(Lista):# Verifica se o ponteiro para o início da lista está vazio, se positivo retorna True, logo lista vazia.if Lista.inicio == None :return  True#Caso o item anterior seja falso, retorna Falso, logo lista contém itens na lista.    else:return False</p><p>Laiane</p><p>Na prática</p><p>O desenvolvimento de listas encadeadas deve ser realizado com planejamento adequado a partir de</p><p>um problema proposto.</p><p>Antes de implementar o código, é recomendado realizar o teste do algoritmo em ambiente</p><p>controlado para garantir o seu funcionamento na posterior integração.</p><p>Acompanhe, em Na Prática, o desenvolvimento do teste de um algoritmo para solucionar</p><p>problemas com as bagagens em aeroportos.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/e2a55693-452b-49e4-b246-58922421bda5/72a34370-48d5-4024-a8d7-b8001dedd6ca.jpg</p><p>Saiba +</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>O uso da computação desplugada em um contexto de</p><p>gamificação para o ensino de estrutura de dados</p><p>Neste link, você acessa um artigo que relata a experiência do ensino de estrutura de dados em um</p><p>ambiente gamificado.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Como trabalhar com listas em Python</p><p>Neste link, você acessa um conteúdo relacionado a listas em linguagem Python com exemplos</p><p>práticos.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>ODIN - Ambiente Web de apoio ao ensino de estruturas de</p><p>dados lista encadeada</p><p>Neste link, você acompanha um artigo que demostra o funcionamento do software ODIN, aplicado</p><p>no ensino de estrutura de dados de forma visual e simplificada.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.seer.ufrgs.br/renote/article/view/89272</p><p>https://www.devmedia.com.br/como-trabalhar-com-listas-em-python/37460</p><p>http://periodicos.unesc.net/sulcomp/article/view/800/752</p><p>Compilador On-line Python</p><p>Neste link, você acessa um compilador on-line da linguagem Python sem a necessidade de</p><p>instalação de programas de terceiros.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.programiz.com/python-programming/online-compiler/</p>