Prévia do material em texto
Listas Sequenciais Apresentação As listas sequenciais são estruturas que servem para armazenar elementos de maneira relacionada e lógica, ficando dispostos um depois do outro — por isso, o nome sequencial dado a ela. Na literatura, encontramos as listas sequenciais referenciadas, também, por listas lineares, listas estáticas lineares ou listas estáticas sequenciais. A sua aplicação é mais adequada para casos em que o conjunto de dados é pequeno e bem definido e quando é possível fazer a operação de inserção e remoção de elemento no final da lista. Nesta Unidade de Aprendizagem, você vai estudar o funcionamento de uma lista, de suas funções e seus procedimentos, tais como a inserção, a remoção, a atualização e a consulta de um elemento, assim como aplicar as listas sequenciais. Bons estudos. Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados: Identificar o funcionamento de uma lista (inserção, remoção, atualização e consulta em qualquer ponto da lista). • Reconhecer como funcionam funções e procedimentos de uma lista (inserção, remoção, atualização e consulta). • Aplicar o uso de listas.• Desafio As listas sequenciais são utilizadas, preferencialmente, quando é necessário manipular listas pequenas, quando se pode limitar o seu tamanho e quando a inserção e a remoção de um elemento puderem ser realizadas por meio da utilização da última posição. Nesse sentido, aplicações que manipulem listas, como a escalação de um time de futebol, os alunos de uma determinada disciplina, os funcionários de um setor, entre tantas outras que se encaixem nesses critérios, consistem em boas aplicações para listas sequenciais. Agora, você precisa elaborar um programa que preencha uma lista com as 3 notas de um aluno, previamente informadas pelo seu professor, e calcule a média dessas notas, a ser inserida ao final da lista. - As notas devem ser as seguintes: 7.50, 8.30 e 10.00, portanto a média das notas deverá ser 8.60. - Ao final, apresente a lista com as notas inseridas e a média calculada. - Depois disso, o professor deseja alterar a nota 2 para 8.50, o que vai fazer com que a média das notas fique em 8.67. - Apresente, novamente, a lista com as novas notas e a média recalculada. Infográfico Uma lista sequencial serve para armazenar elementos de maneira relacionada e lógica, em que eles ficam dispostos um depois do outro. Esse tipo de lista também é conhecido por lista estática linear ou lista estática sequencial. Neste Infográfico, você verá algumas operações que podem ser executadas com filas sequenciais. Conteúdo do livro As listas sequenciais são estruturas que servem para armazenar elementos de maneira relacionada e lógica, ficando dispostos um depois do outro — por isso, o nome sequencial dado a ela. Na literatura, encontramos as listas sequenciais referenciadas, também, por listas lineares, listas estáticas lineares ou listas estáticas sequenciais. A sua aplicação é mais adequada para casos em que o conjunto de dados é pequeno e bem definido e quando é possível fazer a operação de inserção e remoção de elemento no final da lista, pois uma desvantagem para a utilização de uma lista sequencial acontece quando a inserção ou a remoção de um elemento gera o deslocamento de todos os elementos da lista, a fim de ajustá-la para que nenhum elemento fique nulo. Em contrapartida, com uma lista sequencial, há a possibilidade de acesso direto a qualquer elemento, por meio de um índice. No capítulo Listas sequenciais, do livro Estrutura de dados, você vai estudar o funcionamento de uma lista, de suas funções e seus procedimentos, tais como a inserção, a remoção, a atualização e a consulta de um elemento, assim como aplicar as listas sequenciais. ESTRUTURA DE DADOS Jeanine Barreto Listas sequenciais Objetivos de aprendizagem Ao final da leitura deste capítulo, você deverá apresentar os seguintes aprendizados: Identificar o funcionamento de uma lista (inserção, remoção, atuali- zação e consulta em qualquer ponto da lista). Reconhecer como funcionam as funções e os procedimentos de uma lista (inserção, remoção, atualização e consulta). Aplicar o uso de listas. Introdução As listas sequenciais são estruturas que servem para armazenar elementos de maneira relacionada e lógica, ficando estes dispostos um depois do outro, por isso o nome sequencial dado a ela. Na literatura, encontramos as listas sequenciais referenciadas também por listas lineares, listas estáticas lineares ou listas estáticas sequenciais. A sua aplicação é mais adequada para os casos em que o conjunto de dados é pequeno e bem definido e para quando for possível fazer as operações de inserção e remoção de elemento no final da lista. Neste capítulo, você vai estudar o funcionamento de uma lista, reco- nhecer como funcionam as funções e os procedimentos de uma lista, tais como a inserção, a remoção, a atualização e a consulta de um elemento, e também como aplicar as listas sequenciais. O funcionamento de uma lista (inserção, remoção, atualização e consulta em qualquer ponto da lista) Uma lista sequencial é um tipo de estrutura que serve para fazer o armazena- mento de elementos de uma forma relacionada e lógica, de maneira que estes estejam dispostos um depois do outro. Por conta disso, uma lista sequencial ou linear pode ser chamada também de lista estática linear ou lista estática sequencial (LAUREANO, 2008). Quando se trabalha com uma estrutura do tipo lista, é possível saber o seguinte sobre ela: qual é o seu primeiro elemento; que elemento vem depois de um determinado elemento; qual é o seu último elemento; quantos elementos existem na lista toda; como se faz para inserir um elemento na lista; como se faz para remover um elemento da lista. Uma lista estática sequencial é mais adequada para os casos em que o con- junto de elementos é pequeno, quando existe um tamanho bem definido para a quantidade de elementos da lista, e para quando se deseja fazer a inserção ou a remoção de elementos no final da lista. A utilização de uma lista estática sequencial traz como vantagens básicas: a possibilidade de acesso direto, por meio de índices, a qualquer um dos elementos da lista; um tempo de demora uniforme para efetivar o acesso a qualquer um dos elementos, pois isso vai depender apenas do índice. Em contrapartida, a utilização desse tipo de lista também traz algumas desvantagens: movimentação, em alguns casos, de toda a lista para que um elemento seja inserido ou removido; o tamanho máximo deve ser predefinido e não poderá ser redefinido em tempo de execução da aplicação. De acordo com os tipos de operações que são permitidas, e que podem ser realizadas, as listas sequenciais podem ser classificadas em filas, pilhas e deques (LORENZI; MATTOS; CARVALHO, 2007). Uma fila é uma lista sequencial, em que o primeiro elemento a entrar também é o primeiro elemento a sair. Essa característica, a principal da fila, é conhecida pela expressão em inglês FIFO ( first in first out). Em uma fila, os elementos são inseridos pela parte de trás e são removidos pela parte da frente. Listas sequenciais2 É possível fazer a abstração de uma fila imaginando pessoas em uma fila de banco, ou uma fila de formigas trabalhando e descarregando alimento, sendo assim, fica claro que a remoção de um elemento é pela frente e a inserção é feita pela parte de trás (Figura 1). Figura 1. Exemplo de fila. Fonte: Nemeroff (2017). Uma pilha é uma lista sequencial, sendo que o primeiro elemento a entrar será o último elemento a sair. Essa característica é conhecida também pela expressão em inglês LIFO (last in first out). A pilha só tem uma entrada, que é o topo, e é a partir dele que os elementos entram e saem da estrutura (Figura 2). Para fazer a abstração de uma pilha, imagine uma pilha de pratos, ou uma pilha de livros, ou ainda uma pilha de cartas de baralho. Fazer a inserção e a remoçãode um elemento pelo topo é uma atividade bem mais prática nessas pilhas. 3Listas sequenciais Figura 2. Exemplos de pilhas. Fonte: Victoria Shapiro/Shutterstock.com, Galyna Motizova/Shutterstock.com. Um deque é uma lista sequencial na qual os elementos podem sair ou entrar pela parte da frente ou de trás. Por isso, essa estrutura é conhecida como deque (do inglês double ended queue). O deque pode ser definido como uma generalização da estrutura fila. A lista sequencial deve conter elementos de um mesmo tipo de dados, os quais estão dispostos em sequência lógica e também em sequência física. A sua implementação é feita em forma de vetor, que pode estar ordenado ou não e ter elementos repetidos ou não. A alocação da memória é estática e a forma de armazenamento na memória é sequencial, ou seja, os elementos são armazenados em endereços de memória vizinhos. Dentro de uma lista sequencial, os elementos ficam dispostos de forma consecutiva, sendo que nenhum deles pode ser nulo. Nesse sentido, quando um novo elemento é inserido, ou quando um dos elementos existentes é remo- vido da lista, isso causa um deslocamento dos demais itens, a fim de torná-la organizada novamente, caso ela seja uma lista ordenada. Algumas das operações que podem ser executadas com listas sequenciais são: Criação da lista: a sua criação acontece quando se declara o vetor que vai conter os seus elementos. Inicialização da lista: envolve a preparação da lista para que sejam inseridos os elementos. Inicialmente, a lista possui 0 elementos. Inserção de elemento: se a lista estiver desordenada, consiste em in- serir um elemento na primeira posição disponível do vetor e ajustar a quantidade de elementos caso a lista esteja cheia. Listas sequenciais4 Percorrer a lista: envolve mostrar os valores de todos os elementos da lista em qualquer direção. Pesquisar na lista: consiste na busca sequencial, de elemento por ele- mento, de um valor ao longo da lista. Consiste em procurar um valor dentro da lista. Remoção de elemento: envolve o ajustamento da organização dos ele- mentos da lista e também da quantidade. É importante lembrar que um elemento só pode ser removido da lista se ela não estiver vazia e se ele for encontrado. Concatenação de listas: é a união de duas listas em uma lista única. Partição de listas: consiste em repartir uma lista em duas ou mais listas. Como funcionam as funções e os procedimentos de uma lista (inserção, remoção, atualização e consulta) A criação de uma lista sequencial acontece quando é declarado o vetor que vai conter os elementos da lista (Figura 3). Figura 3. Criação de uma lista sequencial. 0 int n 1 2 3 4 Na Figura 3, o vetor da lista foi declarado com 5 elementos e a variável n será responsável por armazenar a quantidade de elementos da lista em tempo de execução. A inicialização de uma lista consiste em prepará-la para que sejam inseri- dos elementos. Nesse momento, a variável n vai conter 0, que é a quantidade inicial de elementos da lista. É importante observar que, quando uma lista 5Listas sequenciais é sequencial, a variável n poderá ser entendida também como a variável que guarda a posição em que um elemento novo deverá ser inserido (Figura 4) (DEITEL; DEITEL, 2011). Figura 4. Inicialização de uma lista sequencial. 0 int = 5 1 2 3 4 a b c d e Na Figura 4, é possível observar que, caso um elemento contendo a letra f precise ser inserido na lista, ele será colocado na posição 5, que também corresponde à quantidade de elementos da lista. A inserção de uma lista sequencial levará em conta que ela pode ou não estar ordenada, e pode ou não conter elementos repetidos. Nesse sentido, um elemento novo será inserido na posição equivalente ao valor da variável n e deverá ser feito um ajuste na quantidade de dados da lista, desde que ela já não esteja cheia. Para que um elemento novo seja inserido na lista, é preciso conhecer o vetor que a representa, o valor que precisa ser inserido, a quantidade atual de elementos da lista e qual o tamanho máximo da lista (Figura 5). Figura 5. Inserção de elemento em uma lista sequencial. 0 1 2 3 4 a Listas sequenciais6 A função de inserção será semelhante ao português estruturado: Na função main, o usuário deverá informar um valor, o qual será arma- zenado na variável valor, e será feita uma chamada para a função inserir, passando os quatro parâmetros necessários. A consulta em uma lista sequencial é uma operação que faz uma busca sequencial, elemento por elemento, a fim de encontrar um determinado valor, retornando à posição em que ele foi encontrado. Para que essa operação fun- cione, é necessário conhecer o vetor da lista, o valor que deve ser procurado e a quantidade atual de elementos da lista. A função de consulta deve ser semelhante a esta: Na função main, o usuário deverá informar um valor para ser consultado na lista, o qual será armazenado na variável valor, e será feita uma chamada para a função consultar, passando os três parâmetros necessários. A remoção de um determinado elemento de uma lista sequencial, que pode ou não estar ordenada, é uma operação que envolve o ajustamento do vetor e da sua quantidade, lembrando que a remoção só poderá ser feita se a lista não estiver vazia e se o elemento for encontrado (DEITEL; DEITEL, 2011). Para implementar essa função, é preciso conhecer o vetor da lista, o valor a ser removido da lista e a quantidade de elementos existentes na lista. 7Listas sequenciais A função de remoção deve ser semelhante a esta: Na função main, o usuário deverá informar um valor a ser removido e será feita a chamada da função remover, passando os três parâmetros necessários. A atualização de um elemento da lista envolve uma operação semelhante à consulta, pois é necessário varrer a lista para encontrar o elemento a ser alterado. Para que essa operação funcione, é necessário conhecer o vetor da lista, o valor que deve ser procurado, o novo valor do elemento e a quantidade de elementos atual da lista. A função de atualização deve ser semelhante a esta: Na função main, o usuário deverá informar um valor para ser consultado na lista e também um valor novo para esse elemento. Deverá ser feita uma chamada para a função atualizar, passando os quatro parâmetros necessários. O uso de listas As listas sequenciais são utilizadas, preferencialmente, quando é necessário manipular listas pequenas, quando se pode limitar o seu tamanho e quando a inserção e a remoção de um elemento puderem ser realizadas utilizando a última posição. Listas sequenciais8 Nesse sentido, aplicações que manipulem listas, como a escalação de um time de futebol, os alunos de uma determinada disciplina, os funcionários de um setor, entre tantas outras que se encaixem nesses critérios, consistem em boas aplicações para listas sequenciais. As listas são muito utilizadas em sistemas computacionais, pois diversas atividades do mundo real podem ser abstraídas e representadas por elas. Entre as utilizações possíveis para as listas, estão os itens de uma lista de compras, a relação de candidatos aprovados no vestibular de determinada faculdade, a listagem de funcionários de um setor, a relação de jogadores escalados para um time, a relação de nomes de uma lista telefônica, entre outras. Para fazer a inserção de um elemento em uma lista, pode-se utilizar um código em linguagem C: 9Listas sequenciais Entre as linhas 10 e 16 do código acima, foi transcrito, para a linguagem de programação C, o português estruturado apresentado anteriormente. É feito um teste se a tentativa de inserção está ocorrendo em uma posição acima do tamanho da lista e, se não estiver, insere-se o valor na posição liberada da lista, que no caso é a 0, pois o elemento é o primeiro a ser inserido. A função main solicita a digitação de um caractere pelo usuário, faz a cha- mada para a função de inserção e depois apresenta os elementos da lista na tela. A tela deexecução do código acima deve ser semelhante à apresentada na Figura 6. Figura 6. Função de inserção de elemento em lista. Se a intenção for elaborar uma função para fazer a consulta de um valor na lista, o código do programa deverá se parecer com o seguinte: Listas sequenciais10 Nas linhas 10 a 18 do código anterior, utiliza-se um laço for para verificar, elemento a elemento, se o seu valor coincide com o valor informado pelo usu- ário para servir de critério para a busca. Caso o valor seja igual ao que consta naquela posição da lista, será exibida uma mensagem na tela com a posição em que o valor foi encontrado. Caso contrário, será exibida uma mensagem informando que o valor não consta na lista. A função main solicita a digitação de um caractere pelo usuário, para que ele seja procurado na lista, faz a chamada para a função de consulta e depois apresenta os elementos da lista na tela. A tela de execução do código acima deve ser semelhante à apresentada na Figura 7. 11Listas sequenciais Figura 7. Função de consulta de elemento em lista. Para excluir um elemento da lista, deve-se utilizar um código de programa semelhante ao apresentado a seguir: Listas sequenciais12 Nas linhas 10 a 21 do código acima, utiliza-se um laço for para verificar, elemento a elemento, se o seu valor coincide com o valor informado pelo usuário para servir de critério na busca e na remoção. Caso o valor seja igual ao que consta naquela posição da lista, todos os elementos da lista serão deslocados, a fim de deixar livre o último elemento, e o tamanho da lista é atualizado. Caso contrário, será exibida uma mensagem informando que o valor não consta na lista. A função main solicita a digitação de um caractere pelo usuário para que ele seja removido da lista, faz a chamada para a função de remoção e depois apresenta os elementos da lista na tela (Figura 8). Figura 8. Função de remoção de elemento em lista. Por fim, para fazer a atualização de um elemento da lista, o código deverá se assemelhar ao seguinte: 13Listas sequenciais Nas linhas 10 a 20 do código anterior, utiliza-se um laço for para verificar, elemento a elemento, se o seu valor coincide com o valor informado pelo usuário para servir de critério para a atualização. Caso o valor seja igual ao que consta naquela posição da lista, o valor do elemento será alterado para o novo valor, o qual foi informado pelo usuário. Caso contrário, será exibida uma mensagem informando que o valor não consta na lista. Listas sequenciais14 A função main solicita a digitação de dois caracteres pelo usuário, sendo que o primeiro será encontrado na lista e o segundo será o novo valor daquele elemento, faz a chamada para a função de atualização e depois apresenta os elementos da lista na tela (Figura 9). Figura 9. Função de atualização de elemento em lista. DEITEL, P.; DEITEL, H. C: como programar. 6. ed. São Paulo: Pearson Education, 2011. 818 p. LAUREANO, M. Estrutura de dados com algoritmos e C. São Paulo: Brasport, 2008. 182 p. LORENZI, F.; MATTOS, P.; CARVALHO, T. Estruturas de dados. São Paulo: Cengage Le- arning, 2007. 200 p. NEMEROFF, N. 32ee0c45cd10702651560f31136dcdec.jpg. 12 mar. 2017. Altura: 601 pixels. Largura: 650 pixels. 51 KB. Formato JPEG. Pngtree. Disponível em: . Acesso em: 2 abr. 2018. 15Listas sequenciais Encerra aqui o trecho do livro disponibilizado para esta Unidade de Aprendizagem. Na Biblioteca Virtual da Instituição, você encontra a obra na íntegra. Conteúdo: Dica do professor Uma lista sequencial é um tipo de estrutura que serve para fazer o armazenamento de elementos de uma forma relacionada e lógica, de maneira que estejam dispostos um depois do outro. Por conta disso, uma lista sequencial ou linear pode ser chamada, também, de lista estática linear ou lista estática sequencial. Veja mais sobre o assunto na Dica do Professor, a seguir. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/e146457407530fd06df69067bcf4e6e4 Exercícios 1) Assinale a alternativa que contém os casos em que o uso de uma lista sequencial é mais adequado: A) Listas de tamanho pequeno, com tamanho bem definido e quando os elementos puderem, de preferência, ser inseridos e removidos do fim da lista. B) Listas de tamanho grande, com tamanho variável e quando os elementos puderem, de preferência, ser inseridos e removidos do início da lista C) Listas de tamanho definido em tempo de execução e quando os elementos puderem, obrigatoriamente, ser inseridos e removidos do início da lista D) Listas de tamanho grande, com tamanho variando em tempo de execução e quando os elementos não tiverem que ser inseridos ou removidos, pois a lista deve ser estática. E) Listas de tamanho grande e fixo, onde os elementos devam ser inseridos e removidos do início da lista, obrigatoriamente. 2) Qual pode ser a desvantagem da utilização de uma lista sequencial? A) Não é possível inserir nem remover elementos, pois a lista é estática. B) O vetor da lista deve ser sempre ordenado em ordem crescente. C) Ter de movimentar todos os elementos da lista, em alguns casos, quando um elemento é inserido ou removido. D) A lista sequencial só pode ser utilizada para listas grandes, com números gigantescos de elementos. E) O tamanho máximo da lista nunca poderá ser definido previamente. 3) Quais são os tipos de listas sequenciais? A) Vetores, matrizes e estruturas. B) Pilhas, sequências e vetores. Uma lista estática sequencial é mais adequada para casos em que o conjunto de elementos seja pequeno, que exista um tamanho bem definido para a quantidade de elementos da lista, e para quando se deseja fazer a inserção ou a remoção de elementos no final da lista. A utilização de listas sequenciais traz algumas desvantagens como: movimentação, em alguns casos, de toda a lista para que um elemento seja inserido ou removido; e o tamanho máximo, que deve ser predefinido, e não poderá ser redefinido em tempo de execução da aplicação. C) Filas, matrizes e vetores. D) Árvores, vetores e deques. E) Filas, pilhas e deques. 4) Os elementos de uma lista sequencial devem: A) ter tipos de dados diferentes,e ficar dispostos em forma de matriz bidimensional. B) ser do mesmo tipo de dados, estar dispostos em forma de vetor, ordenado ou não, e em forma sequencial e consecutiva. C) ter tipos de dados iguais e ficar dispostos em forma de vetor, com um elemento nulo após cada elemento que contenha um dado válido. D) ser de tipos de dados diferentes, dispostos de maneira consecutiva e ordenada de forma decrescente. E) ser de tipos de dados iguais, dispostos em forma de vetor ordenado em ordem crescente de valor. 5) Quando um elemento é removido de uma lista sequencial, o que acontece com ela? A) Ela deve ser ordenada novamente em ordem crescente. B) O elemento é excluído, e a posição em que ele estava fica vazia. C) A lista deve ser ordenada novamente em ordem decrescente. D) Para não ficar com uma posição vazia, no lugar do elemento removido, é colocada a informação de quantos elementos a lista contém no momento. E) Todos os elementos que estão depois do elemento que foi excluído são deslocados uma posição para a esquerda, a fim de preencher o espaço vazio deixado pelo elemento removido. Fila: o primeiro elemento a entrar é o primeiro elemento a sair (FIFO); pilha: o primeiro elemento a entrar é o último elemento a sair (LIFO); deque: os elementos podem entrar ou sair pela parte da frente ou de trás (DEQUE). Os elementos de uma lista sequencial devem ser do mesmo tipo de dados e estar dispostos em sequência lógica e física, em forma de vetor, o qual pode ou não estar ordenado. O elemento a ser removido é encontrado na lista, excluído, e todos os elementos posteriores a ele são deslocados uma posição para a esquerda, a fimde preencher o elemento que ficou vazio. Depois disso, o índice que contém o tamanho máximo da lista é ajustado. Na prática As listas são muito utilizadas em sistemas computacionais, pois diversas atividades do mundo real podem ser abstraídas e representadas por elas. Entre as utilizações possíveis para as listas, estão os itens de uma lista de compras, a relação de candidatos aprovados no vestibular de determinada faculdade, a listagem de funcionários de um setor, a relação de jogadores escalados para um time, a relação de nomes de uma lista telefônica, entre outras. Veja, a seguir, uma situação prática de Como funcionam funções e procedimentos de uma lista. Clique no botão abaixo para ver o código desta situação prática: Veja o código https://statics-marketplace.plataforma.grupoa.education/sagah/6729cf5c-f696-4bdd-aa8d-f0b98a46e8ec/9b1390d3-c7eb-4854-aa5b-0902610ee611.docx Saiba + Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor: Listas: funcionamento de pilha e fila Assista ao vídeo a seguir para saber mais sobre pilhas e filas. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. Aula 04 - Listas Parte 2 - Lista estática sequencial Assista ao vídeo a seguir para saber mais sobre listas sequenciais em C. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. Aula 05 - Listas Parte 3 - Implementando lista estática Assista ao vídeo a seguir para se aprofundar no conteúdo de listas sequenciais. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. https://www.youtube.com/embed/aiBp8RmmPiw https://www.youtube.com/embed/rxVrRdF0MTE https://www.youtube.com/embed/UCDCEjRDYrE