Separació dels elements menors i majors a un donat d'una llista doblement encadenada, circular i amb fantasma X79722


Statement
 

pdf   zip   tar

thehtml

Donada la classe Llista que permet guardar seqüències d’enters amb una llista doblement encadenada, circular i amb fantasma, cal implementar el mètode

void separa(Llista &l2, int x)

que a partir d’una llista l2 buida, separa els elements del paràmetre implícit quedant al paràmetre implícit els elements menors a x i a l2 els elements majors a x amb el mateix ordre.

Cal enviar a jutge.org només la implementació del mètode separa. Al principi del mètode implementat, dins d’un comentari, cal indicar el cost temporal amb el raonament corresponent, incloent l’equació de la recurrència si fos necessari. La classe Llista té la següent especificació:

#include <vector> #include <cstddef> using namespace std; typedef unsigned int nat; class Llista { // Llista doblement encadenada, circular i amb fantasma. private: struct node { int info; // Informació del node node *seg; // Punter al següent element node *ant; // Punter a l’anterior element }; node *_prim; // Punter a l’element fantasma nat _long; // Nombre d’elements public: Llista(); // Pre: True // Post: El p.i. és una llista buida. Llista(const vector<int> &v); // Pre: True // Post: El p.i. conté els elements de v amb el mateix ordre. ~Llista(); // Post: Destrueix els elements del p.i. nat longitud() const; // Pre: True // Post: Retorna el nombre d’elements del p.i. void mostra() const; // Pre: True // Post: Mostra el p.i. pel canal estàndard de sortida. void mostra_invertida() const; // Pre: True // Post: Mostra el p.i. en ordre invers pel canal estàndard de sortida. void separa(Llista &l2, int x); // Pre: l2 és buida // Post: S’han separat els elements del p.i., quedant al p.i. els elements // menors a x i a l2 els elements majors a x amb el mateix ordre. };



Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe Llista i un programa principal que processa línies d’enters amb els que crea llistes, llegeix un enter i desprès crida el mètode separa.

Entrada

L’entrada conté vàris parells de línies: La primera línia de cada parell conté una seqüència d’enters amb els elements que tindrà la llista i la segona línia conté un enter amb el valor x a usar per separar la llista.

Sortida

Per a cada parell de línies d’entrada, escriu dues línies amb el resultat desprès d’haver separat els elements menors a x i els majors a x: Per cada llista s’escriu el nombre d’elements de la llista seguit d’un espai, els elements de la llista entre claudàtors i separats per espais, i finalment aquests mateixos elements però amb ordre invers, també entre claudàtors i separats per espais.

Observació

Cal enviar la solució (el fitxer solution.cpp) comprimida en un fitxer .tar:

tar cvf solution.tar solution.cpp

Només cal enviar la implementació del mètode separa. Seguiu estrictament la definició de la classe de l’enunciat.

Al principi del mètode implementat, dins d’un comentari, cal indicar el cost temporal amb el raonament corresponent, incloent l’equació de la recurrència si fos necessari.

Public test cases

  • Input

    1

    Output

    0 [] []
0 [] []

  • Input

    5
6

    Output

    1 [5] [5]
0 [] []

  • Input

    5
4

    Output

    0 [] []
1 [5] [5]

  • Input

    5
5

    Output

    0 [] []
0 [] []

  • Input

    9 7
9

    Output

    1 [7] [7]
0 [] []

  • Input

    3 -6 8 0 4 -2 0
1

    Output

    4 [-6 0 -2 0] [0 -2 0 -6]
3 [3 8 4] [4 8 3]

  • Input

    3 -6 8 0 4 -2 0
0

    Output

    2 [-6 -2] [-2 -6]
3 [3 8 4] [4 8 3]
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make