Tarea #4 [solución]

Lista-Vectorizada inteligente

      Lo usual es implementar una lista usando un puntero a los nodos enlazados en memoria dinámica. Muchos alumnos de computación han implementado esa lista, pero es difícil encontrar una lista que pueda cambiar su representación interna de acuerdo a su uso. Su trabajo consiste en producir una lista que comience almacenando sus valores en un vector de dimensión 64, pero que luego pueda cambiar de manera que almacene sus valores en nodos enlazados.

      Si lo desea, escriba su implementación completa, aunque lo más recomendable es que reutilice alguna de las implementaciones ya disponibles. En el Rep de la clase incluya varios atributos que le permitan convertir la lista vectorial en enlazada cuando la operación de inserción ya ha gastado el máximo de copias de valores en el vector (suponga que ese máximo no es superior a 5 veces la dimensión del vector interno de la lista). Recuerde que si agrega valores al final de la lista, en muchos casos la inserción se puede hacer rápidamente porque no hay que copiar ningún valor, mientras que una inserción al principio del vector obliga a copiar todos los valores almacenados.

      Implemente las siguientes operaciones de la lista: push_back(), pop_back(), push_front(), pop_front(), insert(). Como insert() usa un iterador, implemente también la clase iterador con todas sus operaciones. Recuerde que siempre debe incluir ejemplos de uso BUnit.h en la documentación Doxygen de todas las clases.

Consulta:

Profesor: no entiendo cuándo es que la lista vectorial se debe transformar en lista enlazada. Para mi lo que tiene sentido es que la lista vectorial se convierta en enlazada cuando en el vector no le quepan más valores (que en este caso serían 64). La lista enlazada se usaría solo si hay que almacenar más de 64 valores.

Respuesta:

Hay 2 razones por las que hay que desechar el vector para utilizar la lista. La primera ocurre cuando la cantidad de operaciones de copia es tan grande que sobrepasa el límite, que es (64 x 5). La otra razón por la que habría que desechar el vector es porque la lista tiene que almacenar más de 64 valores. En el Rep de la clase es necesario mantener contadores que indican cuántos elementos tiene la lista y también cuántas operaciones de copia se han realizado.

1. Si la lista inteligente está almacenando sus valores en el vector, agregar un valor al final de la lista sólo requiere 1 copia.
2. Si la lista inteligente está almacenando sus valores en el vector, agregar un valor al principio de la lista requiere un montón de copias, pues hay que mover hacia la derecha todos los valores que ya estaban en el vector. En este caso, la cantidad de copias será n==size().

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2010
Derechos de autor reservados © 2010