Afegir indexació T97061

Donada la classe Llista que ja coneixem, volem afegir a les nostres llistes la possibilitat d’accedir als elements i de canviar els seus valors mitjançant un índex numèric entre claudàtors (igual que podem fer amb les llistes de Python).

Hem fet una subclasse de Llista, anomenada Llista_Extesa, on sobreescrivim els mètodes heretats d’object que ens permeten fer això. Aquests mètodes tenen com a capçalera def __getitem__(self,index) i def __setitem__(self,index,valor) (vegeu el fitxer code.py). Amb aquests mètodes sobreescrits, si lst és instància de Llista_Extesa i index és un enter positiu on 0 $\leq$ index < lst.mida(), podrem demanar l’element a la posició corresponent amb lst[index] o canviar el valor emmagatzemat a aquesta posició amb lst[index] = valor.

Un cop fet això, podem interactuar amb les instàncies de Llista_Extesa fent, per exemple:

>>> from code import *
>>> 
>>> lst = Llista_Extesa().inserir("un").inserir("dos").inserir("tres").inserir("quatre")
>>> print(lst)
un -- dos -- tres -- quatre
>>> 
>>> lst[2]
'tres'
>>> lst[0]
'un'
>>> 
>>> lst[2] = 3
>>> print(lst)
un -- dos -- 3 -- quatre
>>> 
>>> lst[0] = 1
>>> print(lst)
1 -- dos -- 3 -- quatre
>>> 

Entrada

L’entrada al programa serà una col·lecció d’elements, que formen la llista. Pot no haver cap element (llista buida).

Vegeu els exemples del joc de proves públic.

Sortida

La sortida, tal com veieu a code.py, és una línia amb els elements de la llista separats per un guionet entre espais, i en la línia següent els elements de la llista en ordre invertit, també separats per un guionet entre espais.

Aquestes escriptures de la llista i de la llista invertida han estat generades fent servir la indexació afegida en l’exercici (un cop més, vegeu el programa principal de code.py).

Si la llista d’entrada és buida, cal escriure llista buida

Vegeu els exemples del joc de proves públic.

Observacions

Heu de baixar-vos el fitxer code.py (icona de la serp). Aquest fitxer és un programa amb tot el que cal per executar els jocs de prova públics. Només falta, clar, el codi dels mètodes que us demanem a l’enunciat. Aquest fitxer l’heu de completar amb el codi que falta, i això, tot, és el que heu d’enviar al Jutge com a solució.

Dins el fitxer code.py teniu la classe Llista, que hem treballat a l’assignatura, i la subclasse Llista_Extesa amb les capçaleres dels mètodes demanats per aquest enunciat. No caldrà que la vostra solució faci cap import ni res. Tot el codi que us cal el teniu dins de code.py.

Atenció: El cos dels mètodes demanats no pot fer servir CAP mètode de la classe Llista (tret de mida, que es fa servir a l’assert, i només aquí). Heu de fer el que cal manipulant la implementació interna amb les instàncies de _Node que conté la llista.

Atenció: L’eficiència en l’accés i manipulació dels elements de les instàncies de Llista_Extesa fent servir claudàtors NO ha de ser la mateixa que l’eficiència de les operacions equivalents en llistes de Python. L’accés i manipulació dels elements de les llistes de Python fent servir claudàtors té cost $\Theta(1)$. No serà aquest el cas dels mètodes demanats en aquest exercici.

L’eficiència i la qualitat de la solució es tindran en compte a la correcció manual.