UBA - CienciaS http://ubacs.com.ar/ubacs/ |
|
TP Labo Algoritmos 2 http://ubacs.com.ar/ubacs/viewtopic.php?f=189&t=1002 |
Página 1 de 1 |
Autor: | Pape [ 26 Abr 2009, 19:41 ] |
Asunto: | TP Labo Algoritmos 2 |
Bueno,el tp consistía en armar una lista doblemente enlazada....en c++. Ya que el tp está corregido ya para todos los que cursamos algo2, me pareció un buen aporte postear la resolucion,tanto el .h como el .cpp (que incluye tests,lo cual esta bueno para ver tmb) para la gente de algo1 o q siga computacion y quiera ver q onda lo q se va a ver mas adelante, y aparte porq hace mil años q no posteo nada....bueno ahi va: |
Autor: | Pape [ 26 Abr 2009, 19:45 ] |
Asunto: | Re: TP Labo Algoritmos 2 |
Este sería el lista.h donde van todas las implementaciones de las funciones q se mencionan arriba(al ser templates, las implementaciones se colocan en el .h tmb) Nota: conviene hacer copy paste de las cosas para verlos en algún editor de texto copado,para ver con colorcitos y d mas las cosas....sino pueden verlo de aca pero va a ser mas bondi....(recomiendo algun editor de linux,el code blocks o el notepad++ para windows) #ifndef __LISTA_H__ #define __LISTA_H__ #include <iostream> #include <cassert> using namespace std; template<class T> //se puede asumir que el tipo T tiene constructor por copia class Lista { public: /*constructor por defecto, con la lista vacia*/ Lista(); /*constructor por copia, una vez copiada, ambas listas deben ser *independientes, es decir, cuando se borre una no debe morir la otra*/ Lista(const Lista&); /*Constructor que genera una lista con n copias del elemento e*/ Lista(int n, const T& e); /*Destructor. Liberar toda la memoria!*/ ~Lista(); /*Dice cuantos elementos tiene la lista*/ int tamanio() const; /*Dice si la lista es vacia. Cuidado! Esta funcion debe ser mas *eficiente que tamanio*/ bool esVacia() const; /*Devuelve el elemento de mas a la izquierda de la lista*/ const T& izquierda() const; /*Devuelve el elemento de mas a la derecha de la lista*/ const T& derecha() const; /*Inserta el elemento a la izquierda de la lista*/ void insertarALaIzquierda(const T& e); /*Inserta el elemento a la derecha de la lista*/ void insertarALaDerecha(const T& e); /*Elimina el elemento de mas a la izquierda de la lista*/ void eliminarDesdeLaIzquierda(); /*Elimina el elemento de mas a la derecha de la lista*/ void eliminarDesdeLaDerecha(); /*Muestra la lista en formato [e1,e2,...,en] por el stream que recibe *como parametro. La lista vacia se muestra como [] y una lista *con un solo elemento e como [e]*/ void mostrarLista(ostream&) const; /*Elimina el iesimo elemento de la lista, numerando entre 0 y *tamanio()-1. El elemento 0 es de la punta izquierda.*/ void eliminarIesimo(int i); private: //defino una clase Nodo con 4 punteros: primero,ultimo,anterior y siguiente //punteroNodo es un typedef de Nodo* para que se entienda mejor //el constructor de nodo toma solo el valor constante T para construirlo,los valores de los punteros son asignados //para cada función en particular. Ademas debe tener un tamaño(tam) y un valor (val) class Nodo { public: Nodo(const T & e); T val; Nodo* ant; Nodo* sig; }; typedef Nodo *punteroNodo; int tam; punteroNodo primero; punteroNodo ultimo; /*Completar con su implementacion*/ }; /*constructor por defecto, con la lista vacia, para ello se le asigna Null al ultimo y primero y el tamaño es 0*/ template <class T> Lista<T>::Lista() : tam(0), primero(NULL), ultimo(NULL) {} /*constructor por copia, al ppio la crea como vacía(como antes) y le voy insertando a la derecha desde el primero al último de la lista de parámetro "otra" para que respete el orden (insertar a la derecha se encarga de que se respeten los punteros)*/ template <class T> Lista<T>::Lista(const Lista& otra) : tam(0), primero(NULL), ultimo(NULL) { for(punteroNodo iterador = otra.primero;iterador != NULL;iterador = iterador->sig) insertarALaDerecha(iterador->val); } //un simple for que inserta el elemento "e" tantas veces como lo indique "n" template <class T> Lista<T>::Lista(int n, const T& e) : tam(0),primero(NULL),ultimo(NULL) { for(int i=0;i<n;i++) insertarALaDerecha(e); } //el destructor...elimina desde la Izq(en este caso) mientras la lista sea no-vacia template <class T> Lista<T>::~Lista<T>() { while (!esVacia()) eliminarDesdeLaIzquierda(); } //simplemente devuelve el valor de "tam" que contiene el tamaño template <class T> int Lista<T>::tamanio() const { return tam; } //checkea si el tamaño actual es 0 template <class T> bool Lista<T>::esVacia() const { return tam == 0; } //devuelve el valor del puntero "primero" template <class T> const T& Lista<T>::izquierda() const { assert(!esVacia()); return primero->val; } //devuelve el valor del puntero "ultimo" template <class T> const T& Lista<T>::derecha() const { assert(!esVacia()); return ultimo->val; } //inserta a la Izq el elemento "e" que es const template <class T> void Lista<T>::insertarALaIzquierda(const T& e) { //primero creamos un nuevo puntero-nodo que apunte al Nodo que contiene a "e" llamado "nuevo" punteroNodo nuevo = new Nodo(e); //si la lista es vacía,el unico elemento será "e" asique en particular va a ser el ultimo y el primero if (esVacia()) primero = ultimo = nuevo; //los punteros anterior y el siguiente de primero y ultimo = NULL (ver el constructor de Nodo abajo de todo) else //si no es el unico elemento de la lista { //el anterior de mi primero viejo es el nuevo primero->ant = nuevo; //el siguiente del nuevo nodo,es el primero viejo nuevo->sig = primero; //mi nuevo primero es el nuevo primero = nuevo; } //incremento el tamaño porque agregué un elemento a mi lista tam++; } //similar a insertarALaIzquierda template <class T> void Lista<T>::insertarALaDerecha(const T& e) { punteroNodo nuevo = new Nodo(e); if (esVacia()) primero = ultimo = nuevo; else { ultimo->sig = nuevo; nuevo->ant = ultimo; ultimo = nuevo; } tam++; } template <class T> void Lista<T>::eliminarDesdeLaIzquierda() { //me aseguro que no se llame a esta funcion si la lista es vacía assert(!esVacia()); //setteo un puntero-nodo al primero(ya qe voy a borrar de la Izq) punteroNodo aBorrar = primero; //si justo tenia un solo elemento if (primero == ultimo) //hago que ultimo apunte a NULL ultimo = NULL; else //hago que el puntero ant del segundo apunte a NULL primero->sig->ant = NULL; //mi nuevo primero es el valor a donde apuntaba el primero viejo de la lista(esto cubre los 2 casos) primero = primero->sig; //borro mi puntero creado al ppio delete aBorrar; //reduzco el tamaño en 1,porq borré un elemento de la lista tam--; } //similar a eliminarDesdeLaIzq template <class T> void Lista<T>::eliminarDesdeLaDerecha() { assert(!esVacia()); punteroNodo aBorrar = ultimo; if (primero == ultimo) primero = NULL; else ultimo->ant->sig = NULL; ultimo = ultimo->ant; delete aBorrar; tam--; } //muestr la lista template <class T> void Lista<T>::mostrarLista(ostream& salida) const { //comienzo mi lista escupiendo un "[" salida << "["; for(punteroNodo iterador = primero; iterador != NULL; iterador = iterador->sig) { //si no es el primero,escupe una ",",si es el primero no hace nada y sigue con la sig instrucción if (iterador != primero) salida << ","; //luego escupe el valor del iterador salida << iterador->val; } //al salir del for,escupe "[" para cerrar la primer llave salida << "]"; } //eliina el elemento en la posición i-ésima template <class T> void Lista<T>::eliminarIesimo(int pos) { punteroNodo iterador = primero; for(int i=0;i<pos;i++) { //me aseguro q donde me voy a parar para borrar es una posicion de la lista "válida" assert(iterador != NULL); //me paro en los dif valores hasta que llegue al i-ésimo iterador = iterador->sig; } //me aseguro nuevamente que mi iterador sea "válido" en la lista,porq hice un último "sig" sin checkear assert(iterador != NULL); //si era una lista de un solo elemento,y pasó los asserts,entonces la unica alternativa es eliminar ese elemento,para eso //setteo a primero y ultimo apuntando a NULL if (primero == ultimo) primero = ultimo = NULL; else { //si no era el primero(teniendo mas de un elemento) if (iterador->ant != NULL) //el puntero "sig" del elemento anterior a mi iterador apunta ahora a el elemento posterior al iterador iterador->ant->sig = iterador->sig; else //si era el primero, mi nuevo primero es el siguiente de mi primero viejo(es decir el 2do) primero = iterador->sig; //si no es el ultimo if (iterador->sig != NULL) //el puntero ant del elemento siguiente al iterador apunta a donde apuntaba el ant del iterador iterador->sig->ant = iterador->ant; else //si es el ultimo, mi nuevo ultimo es el ant de mi ultimo viejo ultimo = iterador->ant; } //elimino el puntero delete iterador; //reduzco el tamaño en 1 tam--; } //Acá queda claro que al crear un nuevo nodo se setea val=e, ant y sig apuntan a NULL template <class T> Lista<T>::Nodo::Nodo(const T & e) : val(e),ant(NULL),sig(NULL) {} template<class T> ostream& operator<<(ostream& out, const Lista<T>& l) { l.mostrarLista(out); return out; } #endif |
Autor: | Pape [ 26 Abr 2009, 19:46 ] |
Asunto: | Re: TP Labo Algoritmos 2 |
Este es el .cpp #include "lista.h" #include <iostream> #include <sstream> #include <string> #include <cassert> #include <cstdlib> using namespace std; template<class T> void asegurar(const Lista<T>& l, string s) { ostringstream out; l.mostrarLista(out); string t = out.str(); if (s != t) { cerr << s << " != " << t << endl; assert(false); } } template<class T> void asegurar(const Lista<T>& l, const Lista<T>& lp) { ostringstream out; lp.mostrarLista(out); asegurar(l, out.str()); } void randList(Lista<int>& l, int n) { while(!l.esVacia()) { l.eliminarDesdeLaDerecha(); } while(n--) { l.insertarALaDerecha(rand()%1000); } } #define RUNTEST(t) { cerr << "Corriendo test " << #t << endl; t (); cerr << "Terminado test " << #t << endl; } void testVacia() { Lista<int> l; Lista< Lista<int> > ll; Lista<int> lc(l); assert(l.esVacia()); assert(ll.esVacia()); assert(lc.esVacia()); asegurar(l, "[]"); asegurar(ll, "[]"); asegurar(lc, "[]"); } void testCopia() { Lista<int> l; randList(l, 10); Lista< Lista<int> > ll; ll.insertarALaIzquierda(l); l.eliminarDesdeLaDerecha(); ll.insertarALaIzquierda(l); l.eliminarDesdeLaIzquierda(); ll.insertarALaDerecha(l); Lista<int> lc(l); Lista< Lista<int> > llc(ll); asegurar(lc, l); asegurar(llc, ll); } void testIns() { Lista<int> l; l.insertarALaDerecha(4); asegurar(l, "[4]"); l.insertarALaDerecha(5); asegurar(l, "[4,5]"); l.insertarALaIzquierda(3); asegurar(l, "[3,4,5]"); l.insertarALaIzquierda(2); asegurar(l, "[2,3,4,5]"); l.insertarALaDerecha(6); asegurar(l, "[2,3,4,5,6]"); l.insertarALaIzquierda(1); asegurar(l, "[1,2,3,4,5,6]"); Lista< Lista<int> > ll; ll.insertarALaDerecha(l); l.insertarALaDerecha(7); ll.insertarALaIzquierda(l); l.eliminarDesdeLaIzquierda(); ll.insertarALaDerecha(l); ll.insertarALaIzquierda(l); asegurar(ll, "[[2,3,4,5,6,7],[1,2,3,4,5,6,7],[1,2,3,4,5,6],[2,3,4,5,6,7]]"); } void testTamanio() { Lista<int> l; assert(l.tamanio() == 0); l.insertarALaDerecha(1); assert(l.tamanio() == 1); randList(l, 50); assert(l.tamanio() == 50); l.eliminarDesdeLaIzquierda(); for(int n=49;n>=0;--n) { assert(l.tamanio() == n); if (n > 0) { l.eliminarDesdeLaDerecha(); } else { assert(l.esVacia()); } } } void testIzqDerElim() { Lista<int> l(1, -15); int iz = -15, de = -15; int ci = 0, cd = 0; assert(l.izquierda() == iz); assert(l.derecha() == de); for(int i=0;i<50;++i) { bool id = rand()%2 == 0; int e = rand()%1000; if (id) { l.insertarALaIzquierda(e); iz = e; ++ci; } else { l.insertarALaDerecha(e); de = e; ++cd; } assert(l.izquierda() == iz); assert(l.derecha() == de); } while(ci + cd > 0) { if (ci > cd) { --ci; l.eliminarDesdeLaIzquierda(); } else { --cd; l.eliminarDesdeLaDerecha(); } } asegurar(l, "[-15]"); assert(l.izquierda() == -15); assert(l.derecha() == -15); } void testElimI() { Lista<int> l; randList(l, 50); for(int tam=l.tamanio();tam>0;tam=l.tamanio()) { l.eliminarIesimo(rand()%tam); assert(l.tamanio() == tam-1); } for(int i=1;i<=10;++i) { l.insertarALaDerecha(i); } asegurar(l, "[1,2,3,4,5,6,7,8,9,10]"); l.eliminarIesimo(5); asegurar(l, "[1,2,3,4,5,7,8,9,10]"); l.eliminarIesimo(0); asegurar(l, "[2,3,4,5,7,8,9,10]"); l.eliminarIesimo(7); asegurar(l, "[2,3,4,5,7,8,9]"); l.eliminarIesimo(2); asegurar(l, "[2,3,5,7,8,9]"); l.eliminarIesimo(2); asegurar(l, "[2,3,7,8,9]"); l.eliminarIesimo(3); asegurar(l, "[2,3,7,9]"); l.eliminarIesimo(2); asegurar(l, "[2,3,9]"); } void testGrupoTP() { Lista<int> l; l.insertarALaIzquierda(20); asegurar(l, "[20]"); l.eliminarDesdeLaDerecha(); asegurar(l, "[]"); l.insertarALaDerecha(7); asegurar(l, "[7]"); l.insertarALaIzquierda(12); asegurar(l, "[12,7]"); l.insertarALaDerecha(8); asegurar(l, "[12,7,8]"); l.eliminarDesdeLaDerecha(); asegurar(l, "[12,7]"); l.insertarALaIzquierda(9); asegurar(l, "[9,12,7]"); l.insertarALaDerecha(6); asegurar(l, "[9,12,7,6]"); l.eliminarIesimo(2); asegurar(l, "[9,12,6]"); l.eliminarIesimo(0); asegurar(l, "[12,6]"); cout << " la lista es: [12,6] (si esta bien hecha).... " << l << endl; Lista<int> h(4,5); cout<< "la lista [5,5,5,5] es : " << h << endl; } int main() { RUNTEST(testVacia); RUNTEST(testCopia); RUNTEST(testIns); RUNTEST(testTamanio); RUNTEST(testIzqDerElim); RUNTEST(testElimI); RUNTEST(testGrupoTP); return 0; } |
Autor: | FJL [ 21 May 2010, 14:32 ] |
Asunto: | Re: TP Labo Algoritmos 2 |
Hey, te dejo los míos, creo que lo que pedían en el TP de este cuatrimestre es parecido, o incluso idéntico. lista.h: http://pastebin.com/bsX2BQQe test.cpp: http://pastebin.com/p7XWF2k5 Si (dentro de varios meses) no andan los links de pastebin, avísenme y los subo. Prefiero pastearlos ahí porque hay coloreo de sintaxis y se lee fácil el código Saludos! |
Página 1 de 1 | Todos los horarios son UTC - 3 horas |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |