Implementação de ForwardList em C++: Concatenação, Remoção e Clonagem

list Implementar FowardList Funções Adicionais Parte 2 Motivação Listas Simplesmente Encadeadas Muitos problemas em computação necessitam que os dados sejam previamente organizados em estruturas de dados que forneçam acesso rápido aos dados juntamente com operações que realizem transformações eficientes nesses dados Muitos algoritmos requerem que os dados estejam previamente armazenados em listas lineares Listas Sequenciais são relativamente fáceis de implementar mas possuem limitações dado que o array usado como base para construir a lista possui um tamanho préfixado Neste sentido Listas simplesmente encadeadas são melhores pois gerenciam melhor o espaço de memória utilizado Neste exercício você deve completar a implementação de uma lista simplesmente encadeada A classe usada para implementar a lista encadeada chamase ForwardList e você deve implementar as seguintes operações Arquivo FowardListh Concatena a lista atual com a lista lst A lista lst eh modificada apos essa operacao Por exemplo seja l1 1 2 3 4 e l2 7 9 8 Após fazer l1concatl2 você deve obter l1 1 2 3 4 7 9 8 e l2 Restrição está proibido usar funções auxiliares para resolver esta questão inclusive qualquer dos operadores sobrecarregados void concatForwardList lst Remove da lista todas as ocorrencias do Item x Se a lista estiver vazia esta funcao nao faz nada Restricao Esta funcao deve ter complexidade On no pior caso Restrição está proibido usar funções auxiliares nesta questão inclusive qualquer dos operadores sobrecarregados void removeconst Item x Devolve um ponteiro para uma copia desta lista Veja que uma copia nao eh a mesma lista ela contem uma copia dos dados Esta funcao deve ter complexidade On no pior caso Restrição está proibido usar funções auxiliares nesta questão inclusive qualquer dos operadores sobrecarregados ForwardList clone Copia os elementos do vector vec para o final da lista Esta funcao deve ter complexidade On no pior caso Restrição está proibido usar funções auxiliares nesta questão inclusive qualquer dos operadores sobrecarregados void appendVectorconst vectorItem vec Troca o conteudo dessa lista pelo conteudo de lst Os tamanhos das listas podem diferir Apos a chamada para esta funcao os elementos nesta lista sao aqueles que estavam em lst antes da chamada e os elementos de lst sao aqueles que estavam nesta lista void swapForwardList lst Determina se a lista lst passada por parametro eh igual a lista em questao Duas listas sao iguais se elas tem o mesmo tamanho e o valor do kesimo elemento da primeira lista eh igual ao kesimo valor da segunda lista Restrição está proibido usar funções auxiliares nesta questão inclusive qualquer dos operadores sobrecarregados bool equalsconst ForwardList lst const Inverte a ordem dos nós o primeiro node passa a ser o último o segundo passa a ser o penultimo etc Restricao Essa operacao faz isso sem criar novos nodes apenas altera os ponteiros Voce pode criar ponteiros auxiliares um número constante deles mas nao pode alocar novos nós Repetindo está proibido chamar o operador new nesta questão Restrição Também não é permitido usar funções auxiliares nesta questão void reverse retorna o elemento na posicao index Se index 0 ou index msize então lance uma excecao stdrangeerror com a mensagem de erro index out of range Caso contrario retorne o elemento Sera preciso incluir o cabecalho stdexcept para a excecao ser reconhecida Item getint index const Item getint index const Exemplo de Entrada create create show append 1 7 2 2 2 5 2 2 2 show append 1 3 4 4 4 show append 0 8 3 3 3 3 3 3 3 3 show exit Exemplo de Saída create create show lista 0 lista 1 append 1 7 2 2 2 5 2 2 2 show lista 0 lista 1 7 2 2 2 5 2 2 2 append 1 3 4 4 4 show lista 0 lista 1 7 2 2 2 5 2 2 2 3 4 4 4 append 0 8 3 3 3 3 3 3 3 3 show lista 0 8 3 3 3 3 3 3 3 3 lista 1 7 2 2 2 5 2 2 2 3 4 4 4 exit Observação 1 As funções possuem restrições que devem ser obedecidas Se as restrições não forem satisfeitas haverá redução da nota Observação 2 O arquivo maincpp já foi codificado e foi incluído nesta atividade Resta implementar apenas as funçõesmembros da classe listadas acima O programa principal maincpp lê comandos passados como entrada e manipula uma ou mais listas Os comandos aceitos pelo menu principal estão listados abaixo Comando Significado exit sair do programa create cria uma nova lista vazia createWith k cria uma nova lista com os mesmos elementos da lista k já existente show mostra todas as listas na tela get i k imprime o valor do elemento na posição i da lista k clone k cria uma cópia da lista k e a guarda no vetor de listas do programa removeAll x k remove todos os valores x da lista k equals p q retorna true se e somente se as listas p e q forem iguais reverse k Inverte os elementos da lista k append k a1 a2 a3 an adiciona os inteiros a1 a2 an no final da lista k ARQUIVOS EM ANEXO PARA ESTA SEGUNDA PARTE concat k p concatena a lista p ao final da lista k swap l1 l2 troca os conteúdos das duas listas l1 e l2 list Implementar FowardList Funções Adicionais Parte 1 Motivação Listas Simplesmente Encadeadas Muitos problemas em computação necessitam que os dados sejam previamente organizados em estruturas de dados que forneçam acesso rápido aos dados juntamente com operações que realizem transformações eficientes nesses dados Muitos algoritmos requerem que os dados estejam previamente armazenados em listas lineares Listas Sequenciais são relativamente fáceis de implementar mas possuem limitações dado que o array usado como base para construir a lista possui um tamanho préfixado Neste sentido Listas simplesmente encadeadas são melhores pois gerenciam melhor o espaço de memória utilizado Neste exercício você deve completar a implementação de uma lista simplesmente encadeada A classe usada para implementar a lista encadeada chamase ForwardList e você deve implementar as seguintes operações Arquivo FowardListh retorna uma referencia para o primeiro elemento na lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados Item front const Item front const insere um elemento no inicio da lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados void pushfrontconst Item val deleta o primeiro elemento da lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados void popfront retorna uma referencia para o ultimo elemento na lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados Item back const Item back const insere um elemento no final da lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados void pushbackconst Item val deleta o ultimo elemento da lista Restricao estar proibido usar funções auxiliares nesta questao inclusive qualquer dos operadores sobrecarregados void popback Exemplo de Entrada create show pushback 1 0 pushback 2 0 pushback 3 0 show exit Exemplo de Saída create show lista 0 pushback 1 0 pushback 2 0 pushback 3 0 show lista 0 1 2 3 exit Observação 1 As funções possuem restrições que devem ser obedecidas Se as restrições não forem satisfeitas haverá redução da nota Observação 2 O arquivo maincpp já foi codificado e foi incluído nesta atividade Resta implementar apenas as funçõesmembros da classe listadas acima O programa principal maincpp lê comandos passados como entrada e manipula uma ou mais listas Os comandos aceitos pelo menu principal estão listados abaixo Comando Significado exit sair do programa ARQUIVOS EM ANEXO create cria uma nova lista vazia createWith k cria uma nova lista com os mesmos elementos da lista k já existente show mostra todas as listas na tela pushback x k insere x no final da lista k pushfront x k insere x no início da lista k popback k remove o último elemento da lista popfront k remove o primeiro elemento da lista front retorna o valor do primeiro elemento da lista back retorna o valor do último elemento da lista