Examen de Metodologia de la Programació UAB 2018 · Segon Parcial Curs 2018-2019

Exercici 1 (2,5 punts). Operador d'assignació de la classe Vector

Considerem la classe Vector utilitzada per a la gestió d'un array dinàmic d'elements de tipus Punt. La declaració de la classe és la següent:

class Vector

{

public:

Vector(): m_array(nullptr), m_maxElements(0), m_nElements(0) {}

Vector(const Vector& v);

~Vector();

Vector& operator=(Vector& v);

bool insereix(const Punt& pt, int posicio);

bool elimina(int posicio);

int getNElements() const;

int getMaxElements() const;

Punt& operator[](int posicio);

private:

Punt* m_array;

int m_nElements;

int m_maxElements;

Punt m_valorDefecte;

};

Es demana redefinir el comportament de l'operador d'assignació quan s'executa una sentència del tipus v1 = v2, considerant les següents especificacions particulars:

L'operador ha de traspassar (moure) tots els elements de v2 cap a v1, buidant completament v2. En finalitzar l'operació, v2 ha de quedar en el mateix estat que tindria en ser inicialitzat pel constructor per defecte (sense memòria assignada i amb els comptadors a zero).

La capacitat màxima ( m_maxElements) de v1 ha de fixar-se exactament en el doble del nombre d'elements reals transferits des de v2 (tant si aquest valor és superior com inferior a la capacitat que tenia v2 prèviament). D'aquesta manera es permeten posteriors insercions o eliminacions sense necessitat d'un redimensionament immediat.

La resta del funcionament ha de seguir el patró estàndard d'un operador d'assignació: gestió correcta de l'autoassignació ( v1 = v1), alliberament de la memòria prèvia que contingui v1, gestió de vectors buits i retorn de la referència a l'objecte actual per permetre assignacions encadenades.

Vector& Vector::operator=(Vector& v)

Exercici 2 (2,5 punts). Mètode eliminaValor en llista doblement enllaçada

Es disposa d'una llista dinàmica doblement enllaçada en què cada node té enllaços cap a l'element següent i cap a l'anterior. Es faciliten les declaracions següents:

class LlistaDoble

{

private:

Node* m_primer;

Node* m_ultim;

};

class Node

{

public:

Node();

~Node();

Node(const int& valor): m_valor(valor), m_next(nullptr), m_prev(nullptr) {}

Node* getNext() const { return m_next; }

void setNext(Node* next) { m_next = next; }

Node* getPrev() const { return m_prev; }

void setPrev(Node* prev) { m_prev = prev; }

int getValor() const { return m_valor; }

void setValor(const int& valor) { m_valor = valor; }

private:

int m_valor;

Node* m_next;

Node* m_prev;

};

Implementeu el mètode de la classe LlistaDoble amb la capçalera:

bool eliminaValor(int valor);

Requeriments:

Ha d'eliminar totes les instàncies del valor indicat que estiguin presents a la llista.

Retornarà true si s'ha suprimit almenys un node, o false si el valor no s'ha trobat a la llista.

El mètode ha de contemplar tots els casos particulars: llista buida, eliminació del primer node, de l'últim node, d'un node intermedi o d'una llista amb un sol node.

Podeu utilitzar els mètodes públics de la classe Node, però no està permès cridar cap altre mètode de la classe LlistaDoble (com per exemple un mètode erase existent).

Exercici 3 (4 punts). Gestió de repositori de fitxers i desfer accions

Es vol dissenyar un sistema per controlar les versions dels fitxers d'un repositori o directori, oferint la possibilitat de desfer accions prèvies. Es compta amb la classe Fitxer:

class Fitxer

{

public:

Fitxer();

~Fitxer();

string getNom() const { return m_nom; }

string getData() const { return m_dataModificacio; }

FileContent getContingut() const { return m_contingut; }

void setNom(const string& nom) { m_nom = nom; }

void setData(const string& data) { m_data = data; }

void setContingut(const FileContent& contingut) { m_contingut = contingut; }

private:

string m_nom;

string m_dataModificacio;

FileContent m_contingut;

};

I la classe auxiliar Operacio que emmagatzema el tipus d'operació (0: afegir, 1: modificar, 2: eliminar) i l'estat anterior del fitxer:

class Operacio

{

public:

Operacio();

~Operacio();

int getTipus() const { return m_tipus; }

Fitxer getEstatAnterior() const { return m_estatAnterior; }

void setTipus(const int& tipus) { m_tipus = tipus; }

void setEstatAnterior(const Fitxer& estat) { m_estatAnterior = estat; }

private:

int m_tipus;

Fitxer m_estatAnterior;

};

a)

Definiu la part privada de la classe Repositori seleccionant els contenidors més adients de la biblioteca estàndard ( list, forward_list, stack, queue) tant per mantenir la col·lecció de fitxers (que s'ha de poder llistar ordenadament per nom) com per a la pila de desfer operacions.

b)

Implementeu els següents mètodes de Repositori (suposeu que eliminaFitxer i modificaFitxer ja estan implementats):

• afegeixFitxer: rep nom, data de creació i contingut; crea l'objecte Fitxer i l'insereix en la posició que li correspon per mantenir l'ordre alfabètic.

bool Repositori::afegeixFitxer(const string& nom, const string& data, const FileContent& contingut)

• fesOperacio: rep el tipus d'operació (0: afegir, 1: modificar, 2: eliminar), nom, data i contingut. Executa l'acció cridant el mètode corresponent i registra l'operació a l'històric guardant l'estat previ per permetre el desfer.

bool Repositori::fesOperacio(int tipus, const string& nom, const string& data, const FileContent& contingut)

• desfesOperacio: extreu l'última operació realitzada i la reverteix: si es va afegir, elimina el fitxer; si es va modificar, restaura l'estat previ; si es va eliminar, el torna a afegir.

bool Repositori::desfesOperacio()

Exercici 4 (1 punt). Complexitat algorísmica d'elimina i buidaVector

a.

A partir del codi següent del mètode elimina de la classe Vector, determineu-ne l'ordre de complexitat algorísmica en el cas pitjor i justifiqueu la resposta:

bool Vector::elimina(int posicio)

{

bool resultat = false;

if ((posicio >= 0) && (posicio < m_nElements))

{

resultat = true;

for (int i = posicio; i < (m_nElements - 1); i++)

m_array[i] = m_array[i + 1];

m_nElements--;

if (m_nElements < (m_maxElements / 4))

{

if ((m_maxElements / 2) > TAMANY_MINIM)

{

m_maxElements /= 2;

int* aux = new int[m_maxElements];

for (int i = 0; i < m_nElements; i++)

aux[i] = m_array[i];

delete[] m_array;

m_array = aux;

}

}

}

return resultat;

}

b.

Fent ús del mètode elimina, s'implementa el mètode buidaVector següent:

bool Vector::buidaVector()

{

for (int i = 0; i < m_nElements; i++)

elimina(0);

}

Quin és l'ordre de complexitat algorísmica d'aquest nou mètode? Justifiqueu detalladament la resposta.