Suma d'una llista X33905

Preliminars

En aquest exercici extendrem la classe List suposant que el tipus T dels elements de la llista té definida la operació de suma +, és a dir, que dues variables de tipus T es poden sumar. Aquesta suma satisfarà la propietat d’associativitat usual ($x+(y+z)=(x+y)+z$), i tindrà element neutre (per exemple, $0$ és el neutre per a la suma d’enters, i l’string buit és el neutre per a la suma d’strings).

També suposem que una variable x de tipus T permet una assignació x = 0, de manera que, internament, a x se li assigna el neutre de la suma.

Testejarem l’exercici amb el tipus int i amb un tipus contenidor d’string que permetrà fer assignacions x = 0 (internament s’assignarà l’string buit). Fixeu-vos que en el cas d’strings la suma és de fet la concatenació d’strings, i que no és commutativa. Per exemple, "a"+"b" = "ab" $\neq$ "ba" = "b"+"a".

Exercici

Implementeu un nou mètode de la classe List que retorni la suma dels elements continguts a la llista des del principi fins al final. És a dir, si $[a_1,\ldots,a_n]$ és el contingut de la llista, el mètode ha de retornar $a_1+\cdots+a_n$.

D’entre els fitxers que s’adjunten en aquest exercici, trobareu list.old.hpp, a on hi ha una implementació de la classe genèrica List. En primer lloc, haureu de fer:

cp list.old.hpp list.hpp

A continuació, haureu de buscar dins list.hpp les següents línies:

// Pre:  Sigui [a1,...,an] el contingut actual de la llista.
// Post: Retorna a1+...+an.
// Descomenteu les següents dues linies i implementeu el mètode:
// T sum() {
// }

Descomenteu les dues linies que s’indiquen i implementeu el mètode. No toqueu la resta de la implementació de la classe, excepte si, per algun motiu, considereu que necessiteu afegir algun mètode auxiliar a la part privada.

Observació: Una implementació senzilla inicialitzant una variable de tipus T a $0$ (que es transformarà automàticament en el neutre de la suma) i recorrent i sumant-hi els elements de la llista hauria de ser suficient per a superar tots els jocs de proves.

D’entre els fitxers que s’adjunten a l’exercici també hi ha program.cpp (programa principal) i Makefile per a compilar. Per a pujar la vostra solució, heu de crear el fitxer solution.tar així:

tar cf solution.tar list.hpp

Entrada

L’entrada del programa té una primera línia amb o bé int o bé string, que indica el tipus T dels elements de la llista l amb la que treballarà el programa, que se suposa inicialment buida. Després, hi ha una seqüència d’instruccions del següent tipus que s’aniran aplicant sobre la llista i un iterador que se suposa situat inicialment al principi (i final) de la llista:

push_front x (x és de tipus T)
push_back x (x és de tipus T)
pop_front
pop_back
it = begin
it = end
it = erase it
it++
it--
++it
--it
*it = x (x és de tipus T)
insert it x (x és de tipus T)
cout << *it
cout << sum
cout << l

Se suposa que la seqüència d’entrada serà correcta, és a dir, que no es produeixen errors d’execució si s’apliquen correctament sobre una llista i un iterador amb les condicions abans esmentades.

El programa principal que us oferim ja s’encarrega de llegir aquestes entrades i fer les crides als corresponents mètodes de la classe list. Només cal que implementeu el mètode sum abans esmentat.

Sortida

Per a cada instrucció cout << *it s’escriurà el contingut apuntat per l’iterador. Per a cada instrucció cout << l s’escriurà el contingut de tota la llista. Per a cada instrucció cout << sum s’escriurà la suma de la llista. El programa que us oferim ja fa això. Només cal que implementeu el mètode sum abans esmentat.

Observació

Avaluació sobre 10 punts: (Afegiu comentaris si el vostre codi no és prou clar)

• Solució lenta: 6 punts.

• solució ràpida: 10 punts.

Entenem com a solució lenta una que és correcta i capaç de superar els jocs de proves públics. Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats.