Classe memoriaBST X68729

Això és el test de la classe memoriaBST, que correspon a la pràctica Simulació d’un SO. Aquesta classe implementa una memòria clàssica, és a dir, a un identificador de variable (del tipus string) li associa un valor (de tipus int). Cal que implementeu la classe memoriaBST amb un arbre de cerca (BST vol dir binary search tree). Per a fer-ho, possiblement caldrà que el valor que deseu a l’arbre sigui una tupla <string, int>, que haureu de definir (potser amb alguna operació associada) al fitxer .hpp.

Us passem el programa principal, que cridarà a una instància de la classe, i que cridarà els seus mètodes. Cal que:

1. Implementeu la funció

   void BST<T>::preOrdre(Item *node, vector<T>& R) const

   que es troba al final del fitxer BST.cpp.

   IMPORTANT!!: Malgrat el nom, aquest mètode ha d’implementar el recorregut en INORDRE, i no pas el recorregut en preordre.

2. Completeu l’especificació de la classe al fitxer memoriaBST.hpp.

3. Implementeu la classe memoriaBST al fitxer memoriaBST.cpp.

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, apart de les versions *.old dels altres fitxers que heu d’acabar d’implementar.

Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar memoriaBST.cpp memoriaBST.hpp BST.cpp

L’entrada és un nombre indeterminat de línies que poden ser:

• SET var val. Assigna el valor val a la variable var si no existeix a la memòria. Si la variable ja hi és, li assigna el valor val.

• GET variable. Cerca a la memòria el valor de la variable var.

• WRITE. Escriu tots els parells variable,valor que hi ha a la memòria, en ordre per nom de variable.