Inversió dels elements d'una llista doblement encadenada usant memòria dinàmica X15018


Statement
 

pdf   zip   tar

html

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

void inverteix(); /* Pre: cert */ /* Post: S'ha invertit l'ordre dels elements del p.i. El punt d'interes apunta al mateix element. Exemple: [4 5 2 1] => [1 2 5 4] */

que inverteix l’ordre dels elements del paràmetre implícit. El punt d’interès apunta al mateix element que abans.

Els nodes de la classe Llista estan doblement encadenats amb punters al següent (seg) i a l’anterior (ant). Una llista té quatre atributs: la longitud i tres punters a nodes, un pel primer element (primer_node), un per l’últim (ultim_node) i un altre per l’element actual (act), on tenim situat el punt d’interès de la llista.

Entrada

Com a entrada hi haurà una llista amb punt d’interès: el nombre de vegades que cal avançar el punt d’interès respecte el primer element, el nombre d’enters de la llista i els enters que la formen.

Per llegir les llistes, s’ha utilitzat l’operador >> que es troba definit a la classe Llista.

Sortida

Com a sortida es mostrarà la llista original. A continuació es mostrarà la llista desprès d’haver-la invertit una vegada i desprès d’haver-la invertit 1000 vegades (en cada cas es mostraran tots els elements de la llista recorrent-la del primer a l’últim i recorrent-la de l’últim al primer).

Per escriure les llistes, s’ha utilitzat l’operador << que es troba definit a la classe Llista.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar llista_inverteix.cpp

Observeu que per compilar us donem el Makefile, la classe Llista amb tots els seus mètodes implementats excepte inverteix i el programa principal program.cpp.

Public test cases

  • Input

    1 4
4 5 2 1

    Output

    [4,(5),2,1]>

[1,2,(5),4]>
[4,(5),2,1]<

[4,(5),2,1]>
[1,2,(5),4]<

  • Input

    3 3
7 2 3

    Output

    [7,2,3]>

[3,2,7]>
[7,2,3]<

[7,2,3]>
[3,2,7]<

  • Input

    0 1
8

    Output

    [(8)]>

[(8)]>
[(8)]<

[(8)]>
[(8)]<
    • Information
    Author
    Neus Català - Jordi Esteve
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make