Mudanças entre as edições de "PRG29003: Introdução a Listas"
(Criou página com ' * [https://video.search.yahoo.com/video/play;_ylt=A0LEV7lAXs1XG2sA1rwPxQt.;_ylu=X3oDMTBsa3ZzMnBvBHNlYwNzYwRjb2xvA2JmMQR2dGlkAw--?p=linked+list+video+khan+academy&tnr=21&vid=a261...') |
|||
Linha 1: | Linha 1: | ||
− | |||
* [https://video.search.yahoo.com/video/play;_ylt=A0LEV7lAXs1XG2sA1rwPxQt.;_ylu=X3oDMTBsa3ZzMnBvBHNlYwNzYwRjb2xvA2JmMQR2dGlkAw--?p=linked+list+video+khan+academy&tnr=21&vid=a261fe6fc79a3f7e4fd85faea0b52f1c&l=574&turl=http%3A%2F%2Fts2.mm.bing.net%2Fth%3Fid%3DOVP.Vb3ec24372ca57a7f1037e17de2583d2b%26pid%3D15.1&sigi=12b13n06v&rurl=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DJu5q1hhFCso&sigr=11bh4tdn6&tt=b&tit=Linked+Lists%3A+Introduction&sigt=10qig1lga&back=https%3A%2F%2Fsearch.yahoo.com%2Fyhs%2Fsearch%3Fp%3Dlinked%2Blist%2Bvideo%2Bkhan%2Bacademy%26type%3D__alt__ddc_linuxmint_com%26hspart%3Dddc%26hsimp%3Dyhs-linuxmint%26fr%3Dyhs-ddc-linuxmint%26ei%3DUTF-8&sigb=14vc076df&hspart=ddc&hsimp=yhs-linuxmint Um video introdutório da Khan Academy] | * [https://video.search.yahoo.com/video/play;_ylt=A0LEV7lAXs1XG2sA1rwPxQt.;_ylu=X3oDMTBsa3ZzMnBvBHNlYwNzYwRjb2xvA2JmMQR2dGlkAw--?p=linked+list+video+khan+academy&tnr=21&vid=a261fe6fc79a3f7e4fd85faea0b52f1c&l=574&turl=http%3A%2F%2Fts2.mm.bing.net%2Fth%3Fid%3DOVP.Vb3ec24372ca57a7f1037e17de2583d2b%26pid%3D15.1&sigi=12b13n06v&rurl=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DJu5q1hhFCso&sigr=11bh4tdn6&tt=b&tit=Linked+Lists%3A+Introduction&sigt=10qig1lga&back=https%3A%2F%2Fsearch.yahoo.com%2Fyhs%2Fsearch%3Fp%3Dlinked%2Blist%2Bvideo%2Bkhan%2Bacademy%26type%3D__alt__ddc_linuxmint_com%26hspart%3Dddc%26hsimp%3Dyhs-linuxmint%26fr%3Dyhs-ddc-linuxmint%26ei%3DUTF-8&sigb=14vc076df&hspart=ddc&hsimp=yhs-linuxmint Um video introdutório da Khan Academy] | ||
− | Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. | + | Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Qualquer dado em uma lista pode ser acessado, independente de sua posição, assim como pode ser adicionados ou removidos de uma posição qualquer. Além disso, a ordem dos dados em uma lista pode ser modificada de diferentes maneiras (ordenamento, embaralhamento, inversão, ...). Tudo isso graças à forma com que uma lista encadeia os dados, em que cada dado armazenado possui referências tanto a seu sucessor quanto seu antecessor. A figura abaixo ilustra uma lista encadeada: |
[[imagem:prg2-2016-2-Lista1.jpg]] | [[imagem:prg2-2016-2-Lista1.jpg]] | ||
Linha 9: | Linha 8: | ||
Uma lista possui algumas características: | Uma lista possui algumas características: | ||
− | * Os | + | * Os dados são armazenados dinamicamente, por isso a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz). |
− | * A lista não precisa ocupar uma área de memória contígua: como | + | * A lista não precisa ocupar uma área de memória contígua: como dados são armazenados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos dados em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz). |
− | * Não é possível indexar os | + | * Não é possível indexar os dados, por isso para acessar um dado deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada sucessor ou antecessor até chegar àquele procurado. |
− | * Para adicionar um | + | * Para adicionar um dado, basta modificar a referência ao sucessor do dado que deve antecedê-lo na lista. Assim, não é necessário ''"empurrar"'' os dados seguintes para frente (como seria o caso de um vetor). |
− | * Para remover um | + | * Para remover um dado é a mesma coisa: basta modificar a referência de seu antecessor. Assim, não é necessário ''"deslocar pra trás"'' os dados seguintes (como seria o caso de um vetor). |
Linha 29: | Linha 28: | ||
{{collapse top | A lista encadeada da biblioteca Prglib}} | {{collapse top | A lista encadeada da biblioteca Prglib}} | ||
<syntaxhighlight lang=c> | <syntaxhighlight lang=c> | ||
− | + | #ifndef LISTA_H | |
− | + | #define LISTA_H | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | #ifndef | ||
− | #define | ||
#include <cstddef> | #include <cstddef> | ||
Linha 45: | Linha 37: | ||
#include <algorithm> | #include <algorithm> | ||
#include <random> | #include <random> | ||
− | |||
using std::shared_ptr; | using std::shared_ptr; | ||
Linha 97: | Linha 88: | ||
// Procura todos os dados equivalentes a "algo", e os | // Procura todos os dados equivalentes a "algo", e os | ||
// anexa a "lista". Retorna uma referência a "lista". | // anexa a "lista". Retorna uma referência a "lista". | ||
− | |||
lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; | lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; | ||
Linha 143: | Linha 133: | ||
<syntaxhighlight lang=c> | <syntaxhighlight lang=c> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
#include <cstdlib> | #include <cstdlib> | ||
#include <prglib.h> | #include <prglib.h> |
Edição das 19h31min de 12 de março de 2018
Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Qualquer dado em uma lista pode ser acessado, independente de sua posição, assim como pode ser adicionados ou removidos de uma posição qualquer. Além disso, a ordem dos dados em uma lista pode ser modificada de diferentes maneiras (ordenamento, embaralhamento, inversão, ...). Tudo isso graças à forma com que uma lista encadeia os dados, em que cada dado armazenado possui referências tanto a seu sucessor quanto seu antecessor. A figura abaixo ilustra uma lista encadeada:
Uma lista possui algumas características:
- Os dados são armazenados dinamicamente, por isso a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
- A lista não precisa ocupar uma área de memória contígua: como dados são armazenados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos dados em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
- Não é possível indexar os dados, por isso para acessar um dado deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada sucessor ou antecessor até chegar àquele procurado.
- Para adicionar um dado, basta modificar a referência ao sucessor do dado que deve antecedê-lo na lista. Assim, não é necessário "empurrar" os dados seguintes para frente (como seria o caso de um vetor).
- Para remover um dado é a mesma coisa: basta modificar a referência de seu antecessor. Assim, não é necessário "deslocar pra trás" os dados seguintes (como seria o caso de um vetor).
As operações elementares de uma lista definem como dados podem ser adicionados, obtidos e removidos da lista, e também que informações sobre a lista podem ser obtidas. São elas:
- anexa: adiciona um dado ao final da lista
- insere: adiciona um dado em uma determinada posição da lista
- remove: remove um dado de uma determinada posição da lista
- obtem: obtém um dado de uma determinada posição da lista
- comprimento: obtém o comprimento da lista
- esvazia: esvazia a lista (remove todos os dados)
A biblioteca Prglib possui uma lista,cuja declaração é apresentada a seguir:
A lista encadeada da biblioteca Prglib |
---|
#ifndef LISTA_H
#define LISTA_H
#include <cstddef>
#include <ostream>
#include <string>
#include <list>
#include <algorithm>
#include <random>
using std::shared_ptr;
namespace prglib {
template <typename T> class lista {
public:
//construtor: não precisa de parâmetros para criar uma nova lista
lista();
// construtor de cópia
lista(const lista &outra);
// destrutor
virtual ~lista();
// insere "algo" no inicio da lista
void insere(const T & algo);
// adiciona "algo" no final da lista
void anexa(const T & algo);
// insere "algo" em uma posição específica da lista
void insere(const T & algo, int posicao);
void insereOrdenado(const T & algo);
// remove o dado que está na "posicao" na lista, e retorna
// uma cópia desse dado
virtual T remove(int posicao);
// remove todos os dados que forem equivalentes a "algo"
void retira(const T & algo);
// estas duas operações são idênticas: retorna
// uma referência ao dado que está na "posicao" na lista
T& obtem(int posicao) const;
T& operator[](int pos) const;
// atribuição: torna esta lista idêntica à outra lista
virtual lista& operator=(const lista<T> & outra);
// compara duas listas: são iguais se tiverem mesmo comprimento
// E todos os dados armazenados forem iguais e na mesma ordem
bool operator==(const lista<T> & outra) const;
// Retorna uma referência a um dado que seja equivalente a "algo"
T& procura(const T &algo) const;
// Procura todos os dados equivalentes a "algo", e os
// anexa a "lista". Retorna uma referência a "lista".
lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const;
// retorna a quantidade de dados armazenados na lista
int comprimento() const;
// retorna true se lista estiver vazia
bool vazia() const;
// Esvazia a lista
void esvazia();
// apresenta o conteúdo da lista no stream "out"
void escrevaSe(std::ostream & out) const;
void escrevaSe(std::ostream & out, const std::string & delim) const;
// ordena a lista
void ordena();
// iteração do início pro fim
void inicia();
T & proximo();
bool fim() const;
// ... e do fim pro início
void iniciaPeloFim();
T & anterior();
bool inicio() const;
// inverte a ordem nos nodos na lista
void inverte();
// embaralha os dados de uma lista
void embaralha();
// obtém uma sublista
lista<T> * sublista(unsigned int pos1, unsigned int pos2) const;
lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const;
};
|
Abaixo segue um exemplo de uso de algumas operações de uma lista:
#include <cstdlib>
#include <prglib.h>
#include <iostream>
#include <string>
using namespace std;
using prglib::lista;
int main(int argc, char** argv) {
// cria uma lista de string
lista<string> nomes;
// anexa três dados ao final da lista
nomes.anexa("manuel");
nomes.anexa("maria");
nomes.anexa("bilica");
// mostra comprimento e conteúdo da lista
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// insere dado no início da lista
nomes.insere("maneca");
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// insere dado na posição 2 da lista
nomes.insere("joaquim", 2);
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// remove dado do início da lista
nomes.remove(0);
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// remove dado da posição 2 da lista
nomes.remove(2);
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// esvazia a lista
nomes.esvazia();
cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
nomes.escrevaSe(cout, ",");
cout << endl;
// ao final, lista é automaticamente destruída, e a memória utilizada
// é liberada
return 0;
}
Atividade
- Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas