Ejericios selectos para listas (C++).

Media aritmética (promedio).

Desviación estándar.

Regresión lineal.

Coeficiente de correlación.

1. Modifique el Ejemplo lista para que permita leer datos (int) desde la entrada estándar (teclado).
2. Considerando la definición de una lista enlazada, modifique el Ejemplo lista para que:
1. Incorpore un atributo privado numérico (n) que lleve el control del número de elementos insertados en la lista enlazada. Al respecto no olvide:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para el atributo n: obten_n( ) o si lo prefiere get_size( ).
2. Considere otras operaciones de inserción para la lista enlazada, como por ejemplo:
1. inserta_despues_de(e1, e2) inserta al elemento e1 después del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista enlazada), se deberá regresar false.
2. inserta_antes_de(e1, e2) inserta al elemento e1 antes del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista enlazada) se deberá regresar false.
3. inserta_ordenado(elemento) inserta al elemento en orden ascendente dentro de la lista enlazada.
3. De preferencia genere, como parte de su diseño, el diagrama de clases UML para la nueva definición de la lista enlazada. Puede apoyarse de los diagramas de clases presentados en el blog.
3. Modifique el Ejemplo lista para que almacene otro tipo de datos además de los de la clase string. Pruebe con al menos los siguientes:
1. int.
2. double.
3. persona y cientifico (del Ejemplo herencia).
   
4. En el blog (entrada Herencia vs. composición) se hace mención de los inconvenientes de la implementación de una pila por medio de la herencia de una lista enlazada. Compruebe con al menos un ejemplo, la posibilidad de realizar una operación no válida  para una pila. Puede basarse en el Ejemplo pila_herencia.
5. Con base en lo descrito en el blog (entrada Herencia vs. composición), realice la implementación de una cola de espera utilizando una lista enlazada. Para lo anterior, siga los enfoques de:
1. Herencia (apóyese del Ejemplo pila_herencia).
2. Composición (apóyese del Ejemplo pila_composición).
6. Respecto al ejercicio anterior, determine sus propias conclusiones respecto al mecanismo de herencia vs. composición para ambos tipos de implementación.
7. Modifique el Ejemplo pila_herencia y el Ejemplo pila_composición para asegurarse de que es posible almacenar otro tipo de datos. Pruebe con al menos los siguientes:
1. int.
2. double.
3. persona y cientifico (del Ejemplo herencia).
8. Con base en la descripción hecha en el blog (entrada Listas circulares) ¿Cuáles son las consideraciones necesarias para la implementación de una lista enlazada circular? ¿Cómo deben hacerse las inserciones? ¿Cómo deben hacerse las eliminaciones? ¿Cuáles serían las operaciones primitivas respecto de una lista simplemente enlazada? ¿Qué otras operaciones, además de las presentadas en el blog se podrían definir? En este sentido, implemente una lista enlazada circular y pruébela, ya que será necesaria para la solución del siguiente ejercicio.
9. Utilice la implementación de la lista enlazada circular del ejercicio anterior para resolver el problema de Josephus descrito en el blog (entrada Listas circulares). Para ello:
1. Considere que existen N soldados (se deberá solicitar y leer). Para cada uno de dichos soldados deberá solicitar su nombre, por lo que se recomienda que la lista enlazada circular almacene objetos de la clase String.
2. En cada iteración (determinación de la eliminación de un soldado), genere un número aleatorio n, donde 0 < n <= N.
3. De manera paralela al almacenamiento de los soldados en la lista enlazada circular, almacene el nombre de los soldados en un arreglo y genere otro número aleatorio m, de tal forma que m sea el índice correspondiente al arreglo de nombres de los soldados, y servirá para elegir al soldado inicial. Tome en cuenta que 0 <= m < N.
10. Con base en la descripción y la definición de una lista doblemente enlazada que se realizó en la entrada Listas doblemente enlazadas y considerando lo descrito en el diagrama de clases UML correspondiente, realice la implementación de una lista doblemente enlazada. Para ello, considere la siguiente descripción para los métodos a implementar:
1. inserta_al_inicio(elemento) agrega elemento al inicio de la lista doblemente enlazada.
2. inserta_al_final(elemento) agrega elemento al fin de la lista doblemente enlazada.
3. elimina_del_inicio( ) elimina un elemento del inicio de la lista doblemente enlazada.
4. elimina_del_final( ) elimina un elemento del fin de la lista doblemente enlazada.
5. esta_vacia( ) regresa verdadero o falso dependiendo de si la lista doblemente enlazada contiene o no elementos respectivamente.
6. imprime( ) imprime en la salida estándar (pantalla) los elementos de la lista doblemente enlazada.
7. get_size( ) regresa el número de elementos actualmente almacenados en la lista doblemente enlazada.
8. inserta_despues_de(e1, e2) inserta al elemento e1 después del elemento e2. Si e1 pudo ser insertado, se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista doblemente enlazada), se deberá regresar false.
9. inserta_antes_de(e1, e2) inserta al elemento e1 antes del elemento e2. Si e1 pudo ser insertado se debe regresar true para notificar éxito. En caso contrario (quizá el elemento e2 ni siquiera exista dentro de la lista doblemente enlazada) se deberá regresar false.
10. inserta_ordenado(elemento) inserta al elemento en orden ascendente dentro de la lista doblemente enlazada.
11. Con base en la implementación de la lista doblemente enlazada del ejercicio anterior ¿Qué cambios habría que realizar para la implementación de una lista doblemente enlazada circular?
12. Considere las fórmulas de media aritmética, desviación estándar, regresión lineal y coeficiente de correlación presentadas al inicio de la sección de ejercicios, donde n es el número de elementos en el conjunto de datos y x e y son elementos del conjunto de datos. Utilizando la implementación de la lista doblemente enlazada del Ejercicio 10, escriba un programa que realice el cálculo de cada una de las formulas mencionadas. Sugerencia: formule cada una de las expresiones como un método dentro de una clase que se llame Formulas.
13. Considere el Ejercicio 5 (Round robin) de la entrada Ejercicios selectos (colas) y la figura que aparece al final de la presente lista de ejercicios. Se tiene una lista enlazada (vertical) con tres nodos y en cada uno de ellos una referencia a una cola de espera representada en dicha figura por inicio. La figura muestra un estado determinado de tres colas de espera con números enteros que representan las cantidades a considerar (quantum). Utilizando cada una de las colas de espera referidas por la lista enlazada, implemente el algoritmo de Round robin por niveles tomando en consideración lo siguiente:
1. La atención de los elementos formados en la cola de espera consiste en restarle uno al quantum del nodo que se encuentra al inicio de la cola, y volverlo a formar al final de la misma para atender de manera análoga a los siguientes nodos. Tome en consideración que, una vez que el número llega a cero, el nodo correspondientes es eliminado.
2. La atención se realiza con base en la prioridad de los elementos de la cola de espera, la cual está representada por los números 1, 2 y 3 de la lista enlazada vertical, donde 3 y 1 son la prioridad más alta y más baja respectivamente. No es posible atender a los elementos formados en un cola de espera cuya prioridad sea menor siempre que existan elementos que necesitan ser atendidos en alguna cola de espera de prioridad mayor.
3. El proceso anteriormente descrito continúa hasta atender o despachar a todos los nodos formados en las tres colas de espera. Para lo anterior, considere:
1. Genere un número aleatorio entre 1 y 3, mismo que representará la prioridad para seleccionar la cola de espera correspondiente (Suponga que salió el 3).
2. Para cada cola de espera, genere un número aleatorio entre 10 y 50, el cual representará el número de nodos que contendrá la cola de espera en cuestión (Si el nuevo número aleatorio es 48 por ejemplo, se tendrán que generar 48 nodos que se formaran en la cola asociada al nivel 3).
3. Por cada nodo, genere nuevamente un número aleatorio entre 1 y 500, mismo que representará el quantum asignado a cada nodo.
4. No olvide construir también una clase de prueba para su implementación. La salida de su programa puede ser en la salida estándar o en un archivo de texto.
5. Quizá pueda resultar útil al lector revisar el siguiente Ejemplo de implementación de una lista de listas como apoyo para la generación de su propio diseño en la resolución de este interesante problema.
1. Como preámbulo al Ejemplo lista de listas, podría resultar útil al lector revisar antes el Ejemplo lista2 que es una versión alternativa del Ejemplo lista.
   

Representación de Round robin por niveles de prioridad.