ece264/solutions/ECE264Solutions/PA07

Assignment PA07: Linked list with Sparse Array

Given below is the general information regarding Sparse Arrays:

"Consider a data structure called a sparse array: most elements of a
sparse array are 0. This means that most elements do not need to be
stored in the array. Only the elements whose values are non-zero are
stored. In a C program, a normal array of size N occupies a contiguous
piece of memory allocated for indexes from 0 to N − 1. It would be
inefficient to store a sparse array in a normal C array because most
space is wasted. Instead, you can use a data structure that stores
only non-zero elements."

Credits given to Yuhao Chen for this general information


/**
* ASSIGNMENT DETAILS
*/

YOU ARE EXPECTED TO MAKE YOUR OWN MAKEFILE

For this programming assignment, you will be given two sparse arrays as input.
You are tasked to build a linked list for these two arrays, and then merge them together.
Each linked list node holds two integers: the "index", and the "value".

The linked list nodes should be sorted by their "index"; however, when you read them off
disk they are unsorted. The nodes are sorted by their "index", not their value.
THIS IS IMPORTANT. Furthermore, the "index" should be unique in each list. If two nodes
have the same "index", then you should combine them into one node by summing their "value"s
together. A sparse array should NOT have any index that is negative.
(There is an example following.) Finally, no node can have "value" zero. If
you sum together two nodes and the resulting "value" is zero, then that node should be
removed from the sparse array.

An EXAMPLE will illustrate the concepts on what you are asked to do in this assignment.
You will be given two inputs in the form of a pointer.
each input would contain an array of index and value.

The following example will have this format: (index, value)

Array 1:
(3, 8) (2, -5) (0, 5)

Array 2:
(3, 2) (1, 2) (2, 5)

Then after reading these 2 arrays, you would have to sort them in an ASCENDING
order, with their index as the "key".

Array 1:
(0, 5) (2, -5) (3, 8)

Array 2:
(1, 2) (2,5) (3, 2)

After sorting them, you should make a copy of Array 1.
The reason for this is so that when you merge the two arrays, you will still hold an
original copy of Array 1.

Array 1:
(0, 5) (2, -5) (3, 8)

Array 2:
(1, 2) (2,5) (3, 2)

Copy of Array 1:
(0, 5) (2, -5) (3, 8)

Now the final step is to merge the Array 2 with the Copy of Array 1.
your final spare array should a linked list as follows:
__________ __________ __________
/ \ / \ / \
|index = 0| ==\ |index = 1| ==\|index = 3| ==\ NULL
|value = 5| ==/ |value = 2| ==/|value = 10| ==/
\__________/ \__________/ \__________/

Notice that the nodes appear in increasing order by "index". Also, the two "index=3" inputs
have been merged. The two "index=2" inputs were discarded because their "value" summed to zero.

When you insert a new (index, value) pair into the spare-array, you must always preserve
these two properites.

(1) The list is always sorted ascending on "index"
(2) No element has "value" zero. If an insert/merge results in a "value" of zero,
then the node is omitted or removed.

When completing this assignment, the last function that you should attempt is "List_merge".
In this function, you merge two spare-arrays. The output spare-array must obey the two
properties above.

EXAMPLE:
Consider the following scenario:

link1:

(1, 3) ==> (2, 2) ==> (3, -1) ==> (7, -9) ==> (8, -5) ==> (9, 3) ==> NULL

link2:

(0, 5) ==> (1, -3) ==> (2, -8) ==> (3, 1) ==> (4, 7) ==> (7, 9) ==> (9, 1) ==> NULL

results of List_merge(link1, link2):

(0, 5) ==> (2, -6) ==> (4, 7) ==> (8, -5) ==> (9, 4) ==> NULL

Note the result is sorted.

HINT:
It is recommended that you write your own functions.

NOTES:
The input will be in the following format (example taken from input0_A):

3 --> The length of the array for both the index and value
1 ----\
2 ----= These 3 numbers corresponds to the index. They are not necessarily in this ascending order.
3 ----/
1 ----\
1 ----= These 3 numbers corresponds to the value in each respective index.
1 ----/

This means for this array, it will produce the following (index, value) list:

(1, 1) (2, 1) (3, 1).

Another example is shown below to help better illustrate this process.

Say in your input file you're given the following:

4
6
2
7
2
9
3
1
2

Again, the first number corresponds to the length of the array for both index and values. This means

4 --> The length

The indexes are:
6
2
7
2

The values are:
9
3
1
2

Now at index 6, the value corresponding this index is 9. For index 2, the value corresponding
this index is 3, and so on. So for this input, the (index, value) list should yield:

(6, 9) (2, 3) (7, 1) (2, 2)


/**
*WHAT TO SUBMIT
**/

You should only submit answer07.c.

You are not expected to submit your git log or anything else.