| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 |
- Assignment PA04: Sparse Array
- 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.
- In this question, you will implement a sparse array using a binary
- search tree and add two sparse array. Each tree node has two integers
- storing the index and the value. The binary search tree is built based
- on the indexes:
- -- If a node’s index is smaller than the parent’s index, this node is
- on the left side.
- -- If a node’s index is larger than the parent’s index, this node is
- on the right side.
- -- The indexes in the whole tree are distinct: no two nodes have the
- same index. It is possible to have two nodes of the same value (but
- different indexes).
- When merging two sparse array, array_1 and array_2:
- 1. The contents in array_1 and array_2 should not be changed. You
- should create a new array that stores the result of merging.
- 2. array_2 will be merged to array_1. This means you need to read
- nodes in array_2 and insert them into array_1.
- 3. You need to use post-order to traverse the array_2 tree.
- 4. Values of two nodes need to be added only when the indices are the
- same.
- 5. A node with value of 0 should be removed.
- 6. if array_2 have nodes with index different than any nodes in
- array_1, you should insert those nodes into array_1.
-
- Example:
- Consider the following indices and corresponding values:
- array_1:
- int indices_1 [ NUM_VALUES_1 ] = {1 , 2 , 3 , 7 , 8 , 9 };
- int values_1 [ NUM_VALUES_1 ] = {3 , 2 , -1 , -9 , -5 , 3 };
- array_2:
- int indices_2 [ NUM_VALUES_2 ] = {0 , 1 , 2 , 3 , 4 , 7 , 9};
- int values_2 [ NUM_VALUES_2 ] = {5 , -3 , -8 , 1 , 7 , 9 , 1};
- results:
- int indices_3 [ NUM_VALUES_3 ] = { 0 , 2 , 4 , 8 , 9 };
- int values_3 [ NUM_VALUES_3 ] = { 5 , -6 , 7 ,-5 , 4 };
- (elements whose values are zero are deleted)
- Another hint: You may need to write your own functions.
- About outputs:
- The output of pa04 only contains the final output, which means make test only works when all the function has been done.
- However, you can check your trees by "make testxx". (xx means some number, such as 01, 02) Array1 and Array2 will be printed out in "debug_files/", but this only works when you finished all functions except SparseArray_merge and SparseArray_copy.
|
