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:

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&amp😉;  

/*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&amp😉 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

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;
}

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!