EJERCICIO 22Vectores DispersosArchivos(VectoresDispersos.cpp, vectoresDispersos.in, vectoresDispersos.out)
Escribir un programa para realizar operaciones con vectores dispersos. Un vector disperso es aquel cuyo numero de elementos es grande, sin embargo muchos de esos elementos son cero. La representacion se ha de hacer mediante una lista doblemente enlazada.
cada nodo de la lista ha de tener un elemento del vector distinto de cero junto al indice del elemento. El programa debe permitir las siguiente operaciones:
- Dado un vector disperso, representarlo en una lista doble
[li]Dados dos vectores mediante sendas listas L1, L2, obtener el vector suma L1+L2. Podra haber nuevas posiciones que sean cero que se deben guardar en el vector resultante.
Formato de entrada:La entrada consiste en varios casos de prueba cada caso comienza con una linea que contiene un unico caracter con el simbolo '+' que indica la operacion de suma seguido de dos lineas, cada linea contiene un primer numero n (n es un entero entre 1 y 1000) que indica el numero de elementos distintos de cero en el vector disperso seguido de n elementos del vector, cada elemento del vector esta representado por una cadena de la forma X:Y donde X representa el indice del vector (X es un numero entre 1 y 100.000.000) y Y es el valor de ese elemento (Y es un numero en punto flotante cualquiera diferente de cero de doble precision).
Un caracter '#' indica el fin de la entrada.
Formato de salida:La salida consta de el vector resultante de la suma de los vectores expresando cada elemento en la forma X:Y explicado en la entrada
Observacion: La entrada viene ordenada por el indice de los elementos, esta entrada por ejemplo no seria valida:
2 40:1 30:3
Entrada de ejemplo:+
2 30:1 40:3
3 10:2.3 20:3.4 40:2.3
+
4 100:-5.0245 3000:421.015 500000:452 1000000:8
2 500001:452 1000000:-8
+
2 1000:-4 3000:4
2 1000:4 3000:-4
+
5 1:1 10:2 100:3 1000:4 10000:5
5 10:-1 100:-2 1000:-3 10000:-4 100000:2
+
3 1:1 3:3 5:5
3 2:2 4:4 6:6
+
4 1:1 3:3 5:5 7:7
3 2:2 4:4 6:6
+
3 1:1 3:3 5:5
4 2:2 4:4 6:6 7:7
+
1 20000:1
1 20000:1
#
Ejemplo de Salida:4 10:2.3 20:3.4 30:1 40:5.3
4 100:-5.0245 3000:421.015 500000:452 500001:452
0
6 1:1 10:1 100:1 1000:1 10000:1 100000:2
6 1:1 2:2 3:3 4:4 5:5 6:6
7 1:1 2:2 3:3 4:4 5:5 6:6 7:7
7 1:1 2:2 3:3 4:4 5:5 6:6 7:7
1 20000:2
Consejos- Utilizar estructuras de datos
[li]Aprovechar el hecho de que la entrada viene ordenada por el indice de los elementos
[li]Trabajar modularmente (usar Funciones!)
Algunas Funciones utlies- int atoi(const char *)
[li]double atof(const char *)
Espero lo disfruten B)
Saludos...
Anselmo