PRG29003: Introdução a Listas

De MediaWiki do Campus São José
Revisão de 16h56min de 3 de março de 2020 por Msobral (discussão | contribs)
Ir para navegação Ir para pesquisar

[Próxima aula]



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. Pode-se fazer um paralelo com listas reais, que aparecem em diversas situações do dia-a-dia, como estas:


Prg29003-Playlist.jpg
Uma playlist		 Prg29003-Lista-tarefas.png
Uma lista de tarefas


Do ponto de vista computacional, podem-se citar estas aplicações de listas:

  • Armazenar um conjunto de dados cuja quantidade não pode ser conhecida de antemão. Exemplos são resultados de consultas a bancos de dados, listagens de arquivos de um diretório, resultados de separação de string em substrings.
  • Armazenar dados cuja ordem em memória é modificada frequentemente. Exemplos são listas de processos em execução mantidas por sistemas operacionais, listas de mensagens a serem transmitidas cuja ordem depende de suas prioridades, listas de tarefas a serem realizadas por um simulador, listas de reprodução em tocadores de músicas.

Praticamente todas as linguagens de programação usadas atualmente possuem sua própria implementação de lista. Seguem alguns exemplos:

A lista da STL

Do ponto de vista de uma estrutura de dados usada em programas, uma lista encadeada se aparenta com estes exemplos:

Prg2-2016-2-Lista1.jpg


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).


A STL apresenta uma lista cujas operações operações elementares definem como dados podem ser adicionados, obtidos e removidos, e também que informações sobre a lista podem ser obtidas. São elas:


Abaixo segue um exemplo de uso de algumas operações de uma lista: 

#include <cstdlib>
#include <list>
#include <iostream>
#include <string>

using namespace std;

void mostra_lista(list<string> & lista) {
    // itera a lista
    for (auto & dado: lista) {
      cout << dado << ",";
    }
    cout << endl;
}

int main(int argc, char** argv) {
    // cria uma lista de string
    list<string> nomes;
    
    // anexa três dados ao final da lista
    nomes.push_back("manuel");
    nomes.push_back("maria");
    nomes.push_back("bilica");
    
    // mostra comprimento e conteúdo da lista
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista(nomes);

    // insere dado no início da lista
    nomes.push_front("maneca");
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista2(nomes);

    // remove dado do início da lista
    nomes.pop_front();
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista(nomes);
    
    // ao final, lista é automaticamente destruída, e a memória utilizada
    // é liberada
    return 0;
}
}

Atividade

  1. Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas

Um resumo sobre a notação para complexidade de algoritmos

Prg2-Big-o-table.jpg Figura obtida deste artigo sobre estruturas de dados em Python

Operações quer percorrem a lista


A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

  • iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
  • procura: possibilita procurar dados dentro da lista

Iteração

Quando se necessitam acessar em sequência todos (ou uma boa parte) dos dados de uma lista, a melhor forma é por meio da operação de iteração. A lista é capaz de ser iterada por meio dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los: 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (! numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}


Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio: 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Procura por dados

Uma outra operações da lista útil e genérica diz respeito à busca de todos os dados que atendam algum critério de comparação, retornando uma outra lista com os dados encontrados.

A procura de um dado é uma operação que retorna todos os dados da lista de acordo com uma comparação de igualdade. Assim, os dados armazenados precisam ser comparáveis para que isso possa ser feito. Em outras palavras, o tipo de dados armazenado deve definir o operador de igualdade (==). Essa operação de procura está declarada assim na classe lista da prglib: 

  // 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 à própria lista "result" que foi passada como parâmetro.
  lista<T> & procuraMuitos(const T &algo, lista<T> & result) const;

Existem dois métodos para procura de dados na lista:

  • procura: procura a primeira ocorrência de um dado que seja igual a algo, retornando uma referência ao dado encontrado. Caso não o encontre, dispara uma exceção.
  • procuraMuitos: procura todos os dados que sejam iguais a algo, e os armazena na lista result. Caso nada encontre, não modifica a lista result e termina sem avisar qualquer erro.


O método procura pode ser testado com uma lista de inteiros. O programa de teste a seguir demonstra o uso de procura (obs: o programa depende da lista ter implementado o método escrevaSe): 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> l;

  l.anexa(5);
  l.anexa(1);
  l.anexa(5);
  l.anexa(5);
  l.anexa(1);
  l.anexa(8);
  l.anexa(2);

  // "procura" dispara uma exceção se não encontrar o dado, então 
  // deve-se capturar essa exceção para tratá-la.
  try {
    int res = l.procura(5);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 5 na lista" << endl;    
  }

  try {
    int res = l.procura(9);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 9 na lista" << endl;    
  }

  lista<int> lr;

  l.procuraMuitos(5, lr);
  cout << "Encontrou " << lr.comprimento() << " valores iguais a 5" << endl;
  lr.escrevaSe(cout, ",");
  cout << endl;
}

Comparação de igualdade

As operações de procura dependem da comparação de igualdade dos dados contidos numa lista. Isso significa que deve existir o operador == para o tipo desses dados. Esse operador existe na linguagem para tipos básicos, tais como int, float, char e outros. Mas o mesmo não vale para tipos de dados definidos pelo programador, ou mesmo classes. Nesse caso, o programador deve definir o operador == , pois somente ele sabe como valores desses tipos devem ser comparados. Observe-se também que a comparação dos dados não é um problema da lista, que apenas usa a comparação. Em suma, cada tipo e dados ou classe deve saber como comparar seus valores ou objetos.

A linguagem C++ possibilita definir como um determinado operador deve funcionar. Isso aplicado ao operador == resolve o problema da comparação de um tipo de dados definido pelo programador. A implementação de um operador pode ser feita de duas maneiras:

  1. Incluindo-o ao tipo struct ou à classe: 
    struct Registro {
  // atributos do tipo Registro

  bool operator==(const Registro & outro) const;
};
  2. Criando uma função: 
    // compara "este" com "outro"
bool operator==(const Registro & este, const Registro & outro) const {
  // implementação da comparação
}


Ambas as formas de implementar um operador são válidas e resolvem o problema. Uma observação diz respeito à implementação com uma função, a qual tem precedência sobre a implementação dentro da struct ou classe. Isso significa que mesmo que já exista o operador em questão definido dentro de uma struct ou classe, ele pode ser substituído por outra implementação desse operador em uma função. A isso se chama sobrecarga de operador.

Atividade

Faça estes exercícios que envolvem iteração e/ou procura por dados:

  1. Copiar uma lista usando iteração
  2. Filtra valores de uma lista
  3. Lista de contadores
  4. Palavras repetidas
  5. Contador de palavras

Operações que reorganizam a lista

Três operações disponíveis na lista reorganizam a ordem dados dados armazenados:

  • ordenamento: ordena os dados de forma eficiente
  • embaralhamento: mistura os dados aleatoriamente
  • inversão: inverte a ordem dos dados

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência (ele tem custo de tempo computacional O(n log n)), e isso é importante porque esse tipo de operação tem custo computacional considerável (pode ser proporcional ao quadrado da quantidade de dados se não for bem feito). O único requisito para ordenar uma lista é que os dados armazenados possuam uma relação de precedência. Em outras palavras, que possam ser comparados com operador < (menor que). O exemplo a seguir mostra o ordenamento de uma lista: 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

Como o método ordena depende da existência do operador < para o tipo dos dados armazenados, as mesmas considerações feitas quanto à operação de igualdade se aplicam aqui. A próxima subseção mostra um exemplo de ordenamento de uma lista que contém valores de um tipo definido pelo programador.

Ordenamento de uma lista com valores de um tipo definido pelo programador

Quando um programador define um novo tipo ou classe, seus operadores relacionais ainda não existem. Quer dizer, não se conseguem comparar valores desse novo tipo com operadores tais como <, >, <=, >= e ==, entre outros. O ordenamento da lista depende do operador <, portanto uma lista que contenha valores do novo tipo não pode ser ordenada a menos que esse operador seja declarado e implementado.

O exemplo a seguir mostra um programa que cria uma lista com valores de um novo tipo de dados, e a ordena.

Exemplo com o operador< como um método do novo tipo de dados 
// o novo tipo de dados: as coordenadas de um vetor bidimensional
struct Vetor {
  double x, y;

  Vetor(double X, double Y) {
    x = X;
    y = Y;
  }

  // calcula o módulo do vetor
  double modulo() const {
    return sqrt(x*x + y*y);
  }

  // operador < para Vetor: compara os módulos deste vetor com o outro vetor
  // retorna true se módulo deste vetor for menor que módulo de v2
  bool operador<(const Vetor & v2) {
    return modulo() < m2.modulo();
  }
};


int main() {
  lista<Vetor> lv;
  
  // acrescenta alguns vetores à lista
  lv.anexa(Vetor(2,2));
  lv.anexa(Vetor(1,3));
  lv.anexa(Vetor(3,2));
  lv.anexa(Vetor(0,5));
  lv.anexa(Vetor(3,3));

  // ordena a lista
  lv.ordena();

  // mostra os vetores ordenados
  lv.inicia();
  while (! lv.fim()) {
    Vetor & v = lv.proximo();

    cout << "x=" << v.x << ", " << y=" << v.y << endl;
  }
}
Exemplo com o operador< como uma função 
// o novo tipo de dados: as coordenadas de um vetor bidimensional
struct Vetor {
  double x, y;

  Vetor(double X, double Y) {
    x = X;
    y = Y;
  }

  // calcula o módulo do vetor
  double modulo() const {
    return sqrt(x*x + y*y);
  }
 
};

// operador < para Vetor: compara os módulos dos vetores v1 e v2
// retorna true se módulo do vetor v1 for menor que módulo de v2
bool operator<(const Vetor & v1, const Vetor & v2) {
    return v1.modulo() < v2.modulo();
}

int main() {
  lista<Vetor> lv;
  
  // acrescenta alguns vetores à lista
  lv.anexa(Vetor(2,2));
  lv.anexa(Vetor(1,3));
  lv.anexa(Vetor(3,2));
  lv.anexa(Vetor(0,5));
  lv.anexa(Vetor(3,3));

  // ordena a lista
  lv.ordena();

  // mostra os vetores ordenados
  lv.inicia();
  while (! lv.fim()) {
    Vetor & v = lv.proximo();

    cout << "x=" << v.x << ", " << y=" << v.y << endl;
  }
}
Outro exemplo visto em aula 
#include <iostream>
#include <string>
#include <prglib.h>
 
using namespace std;
using prglib::lista;

// Tipo Alguem: representa uma pessoa com seu nome e idade 
struct Alguem {
    string nome;
    int idade;
    
    Alguem() {
        idade = 0;        
    }
    
    Alguem(const string & umNome, int age) {
        nome = umNome;
        idade = age;
    }
    
    // sobrecarga do operador< para o tipo Alguem
    bool operator<(const Alguem & o) {
        if (idade == o.idade) {
            return nome < o.nome;
        }
        return idade < o.idade;
    }
    
};

// sobrecarga do operador << para stream de saída (ostream)
// com ele se consegue escrever na stream um valor do
// tipo Alguem

ostream & operator<<(ostream & out, const Alguem & x) {
    out << x.nome << ": " << x.idade;
    return out;
}

int main() {
  lista<Alguem> l;
  
  Alguem joao("Joao", 20);
  Alguem ninguem;
  
  Alguem x1("Amanda", 15);
  l.anexa(x1);
  
  Alguem x2("Gabriel", 19);
  l.anexa(x2);
  
  l.anexa(Alguem("Isadora", 18));
  l.anexa(Alguem("Gustavo", 18));
  
  // ordena a lista
  l.ordena();
 
  // isto só funciona porque agora existe o operador <<
  // que sabe apresentar o tipo Alguem
  l.escrevaSe(cout);
   
  cout << endl;
}

Embaralhamento

O embaralhamento envolve misturar eficientemente os dados da lista de forma aleatória. O algoritmo envolvido tem custo de tempo computacional O(n log n). Esse método está declarado assim na classe lista: 

  // embaralha os dados de uma lista
  void embaralha();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este: 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // embaralha a lista
  numeros.embaralha();

  numeros.escrevaSe(cout);

  cout << endl;
}

Inversão

A inversão da lista envolve inverter a ordem dos dados nela armazenados: o primeiro se torna o último, o segundo o penúltimo, e assim por diante. O algoritmo envolvido tem custo de tempo computacional O(n). Esse método está declarado assim na classe lista: 

  // inverte a ordem dos dados de uma lista
  void inverte();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este: 

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  // ... e agora a inverte, para obter um ordenamento decrescente
  numeros.inverte();

  numeros.escrevaSe(cout);

  cout << endl;
}

Atividade

Faça estes exercícios que envolvem ordenamento:

  1. Lista ordenada de números inteiros
  2. Ordenar linhas de um arquivo
  3. Ordenar linhas de um arquivo de acordo com comprimentos das linhas
Uma solução para o exercício 3 
#include <fstream>
#include <iostream>
#include <prglib.h>
using prglib::lista;

using namespace std;

// Este novo tipo de dados foi criado para possibilitar comparar
// strings pelos seus comprimentos.
// Note que o tipo Linha apenas encapsula uma string (campo string s),
// e define o operador <

struct Linha {
   // a string encapsulada
   string s;

   Linha() {}
   Linha(const string & algo) {
     s = algo;
   }    
};

// o operador < compara as strings s1 e s2 (s1 < s2)
// a comparação é feita pelos comprimentos das strings encapsuladas
bool operator<(const Linha & s1, const Linha & s2) {
  return s1.s.size() < s2.s.size();
}

int main(int argc, char * argv[]) {
    // implemente aqui seu programa
    ifstream arq(argv[1]);

    // Cria uma lista de Linha, para ser possível ordenar pelo comprimento de string
    lista<Linha> l;

    string x;
    
    // para cada linha lida e guardada na variável "x"
    while (getline(arq, x)) l.anexa(x);

    // ordena a lista: a comparação entre os valores armazenados será feita usando o 
    // operador < do tipo Linha
    l.ordena();
    
    // Usa iteração para apresentar o conteúdo da lista na tela
    l.inicia();
    while (! l.fim()) {
        Linha & linha = l.proximo();
        
        cout << linha.s << endl;
    }

    return 0;
}
Outra solução para o exercício 3 ... ver o uso da operação escrevaSe da lista (depende do operador << para o tipo Linha) 
#include <fstream>
#include <iostream>
#include <prglib.h>
using prglib::lista;

using namespace std;

// Este novo tipo de dados foi criado para possibilitar comparar
// strings pelos seus comprimentos.
// Note que o tipo Linha apenas encapsula uma string (campo string s),
// e define o operador <

struct Linha {
   // a string encapsulada
   string s;

   Linha() {}
   Linha(const string & algo) {
     s = algo;
   }    
};

// o operador < compara as strings s1 e s2 (s1 < s2)
// a comparação é feita pelos comprimentos das strings encapsuladas
bool operator<(const Linha & s1, const Linha & s2) {
  return s1.s.size() < s2.s.size();
}

// define como funciona o operador << (escrita formatada) para o tipo Linha
ostream& operator<<(ostream & out, const Linha & linha) {
  out << linha.s;
  return out;
}

int main(int argc, char * argv[]) {
    // implemente aqui seu programa
    ifstream arq(argv[1]);

    // Cria uma lista de Linha, para ser possível ordenar pelo comprimento de string
    lista<Linha> l;

    string x;
    
    // para cada linha lida e guardada na variável "x"
    while (getline(arq, x)) l.anexa(x);

    // ordena a lista: a comparação entre os valores armazenados será feita usando o 
    // operador < do tipo Linha
    l.ordena();
    
    l.escrevaSe(cout);
    cout << endl;

    return 0;
}


Curiosidade: contando quantas vezes cada valor existe em uma lista

No projeto 2, o requisito "listar os atores que mais atuaram, por ordem decrescente de atuações em filmes" poderia ser resolvido de mais de uma maneira. Uma abordagem é criar uma lista contendo todos os nomes de atores que atuaram nos filmes, de forma que, se um ator trabalhou em três filmes, seu nome apareceria três vezes nessa lista. Basicamente isso implica listar os atores de cada filme, e acrescentá-los a essa nova lista. Ao final, bastaria contar quantas vezes cada ator aparece na lista.

Ao menos dois algoritmos podem ser pensados para esse problema:

  1. Para cada ator da lista, usar a operação procuraMuitos da lista para contar quantas vezes seu nome aparece. O comprimento da lista resultante dessa procura é a quantidade de vezes em que seu nome aparece. Há que cuidar para realizar essa procura somente para a primeira vez em que cada ator é avaliado.
  2. Ordenar a lista de atores, e então iterá-la. Os nomes de atores ficarão contíguos, o que facilita contá-los. Se o próximo ator da iteração for diferente do anterior, então registra-se a contagem do ator anterior e reinicia-se o contador.


Qual dos dois algoritmos é melhor, do ponto de vista de custo computacional (tempo para concluirem) ? O gráfico abaixo responde essa questão !

PRG2-Conta repetidos.png
Custo computacional dos algoritmos para ocntar valores repetidos em uma lista, para listas de números inteiros

Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=PRG29003:_Introdução_a_Listas&oldid=165595”