A vector is a one-dimensional array of elements. The natural C++ implementation of a vector is as a one-dimensional array. However, in many applications, the elements of a vector have mostly zero values. Such a vector is said to be sparse. It is inefficient to use a one-dimensional array to store a sparse vector. It is also inefficient to add elements whose values are zero in forming sums of sparse vectors. Consequently, we should choose a different representation.
One possibility is to represent the elements of a sparse vector as a linked list of nodes, each of which contains an integer index, a numerical value, and a pointer to the next node. Generally, the entries of the list will correspond to the non-zero elements of the vector in order, with each entry containing the index and value for that entry. (This restriction may be violated if a zero value is explicitly assigned to an element).
Your goal is to write a program to add pairs of sparse vectors, creating new sparse vectors. The results of addition should not include any elements whose values are zero. You should then print the resulting vectors with elements in ascending order of index (from smallest index to largest).
The input will be several pairs of sparse vectors, with each vector on a separate line. Each sparse vector will consist of a number of index-value pairs, where the first number in each pair is an integer representing the index (location), and the second number is a floating-point number representing the actual value. You may assume all index locations are non-negative. Elements will be entered in ascending order of index. The list of vectors is terminated by a line containing only -1.
The output will be sparse vectors representing the sum of each pair of input vectors, each on a separate line. Vector elements should appear as pairs of indices and values, separated by a comma and a blank and enclosed in square braces. Vectors should appear as lists of elements separated by commas. The vector elements must be printed in ascending order of index. Vectors with no elements should appear as the string "empty vector".
Input:
3 1.0 2500 6.3 5000 10.0 60000 5.7 1 7.5 3 5.7 2500 -6.3 10 0.0 15000 6.7 100 -1.0 100 1.0 -1
Output:
[1, 7.5], [3, 6.7], [5000, 10], [60000, 5.7] [15000, 6.7] empty vector
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |